|
I'm sure there's a relatively-straightforward way to do this, but my research so far has been a bit overwhelming... Heavy statistics and calculus have never been one of my strengths...
Basically, I need to calculate a best-fit curve on a scatter graph... Points are not evenly spaced on either axis, and there's no cost function to work with (These are derivations of stock/bond price histories)... Just raw (X,Y) values.
I've been trying to work out an algorithm that'll start with a second-degree polynomial function, iterate through and minimize the difference, and then jump to third-degree if it's not within tolerance (And so on, up to a maximum degree). Juggling the data around is something I can do blindfolded, but there's one thing I can't figure out...
Given the polynomial coefficients ((a,b,c,d) -> y = a + bx + cx^2 + dx^3) and a function to determine the total difference across the curve (Or the total square difference, or whatever's needed), how do I adjust the coefficients for the next pass? I mean, how do I choose new values?
I was originally going to try to fix the highest-degree coefficient first, then drill down to the zeroth-degree one (I have a root-solving algorithm that I use for yield calculations - Was going to adapt that), but then I looked at it again with the proper amount of caffeine, and realized that solving one coefficient at a time wasn't going to work 
SOLVED: See my reply below... Linear/Polynomial Regression
|
|
|
|
|
Not sure if this will help but, have you tried a spline interpolation algorithm?
|
|
|
|
|
Kind of the opposite of where I'm going here... The goal isn't to pass through every point, but to give more of a trend-line.
Generally going to be working with a few hundred data points, but only looking for maybe a second or third-degree function in most cases.
<small><i>Proud to have finally moved to the A-Ark. <a href="http://en.wikipedia.org/wiki/Places_in_The_Hitchhiker%27s_Guide_to_the_Galaxy#Golgafrincham">Which one are you in?</a></i><br>Author of the <a href="http://www.serpentooth.com">Guardians Saga</a> (Sci-Fi/Fantasy novels)</br></small>
|
|
|
|
|
Ok, now I understand it better. Then maybe bezier curves would be a better choice.
|
|
|
|
|
Hi Ian,
I don't think there are any closed formula's for what you are trying. What I would recommend is this, inspired by Newton-Raphson:
1. have some values a1,b1,c1,d1 and the corresponding value of your error function e1.
2. slightly change a1 (say by 1%) and recalculate e; find the "a-sensitivity" as (change in e)/(change in a)
3. same for b1, then c1, then d1
4. now choose new values a2,b2,c2,d2 based on the four sensitivities, maybe like so: a2=a1+coef*e/"a-sensitivity" where maybe coef is one.
then iterate until convergence is reached (i.e. sufficiently accurate); warning: this might diverge right away, if so try smaller values of coef (you could halve it in each consecutive try).
FWIW: with more-or-less random data, you'll never find a good fit with a single polynomial. What one normally does is a local approximation, which applies in a small region only. That is similar to a font being drawn as a sequence of Bezier curves; it pays of to have several simple Bezier curves, rather than trying to have a single very complex one (which in general will not be good enough).
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Hmm, didn't think of the sensitivity thing... Giving that a shot now.
FWIW: with more-or-less random data, you'll never find a good fit with a single polynomial. What one normally does is a local approximation, which applies in a small region only. That is similar to a font being drawn as a sequence of Bezier curves; it pays of to have several simple Bezier curves, rather than trying to have a single very complex one (which in general will not be good enough).
It's not actually random data... It's graphing related values, so it should roughly cluster around y=x unless there's another factor (Which is what I'm trying to illustrate).
Proud to have finally moved to the A-Ark. Which one are you in?
Author of the Guardians Saga (Sci-Fi/Fantasy novels)
|
|
|
|
|
If you suspect some periodicity, I'd suggest you first subtract x, so according to what you said the average becomes zero, and the first-order approximation would be the x-axis itself. Then consider a Fourier analysis.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Not a cyclic function, really... Bond valuations are a bit odd, so hard to explain... But dropping it to the X-axis does kinda help the initial approximation.
Still needs a lot more work (Got it to approximate the first degree, and working on expanding from there), but the sensitivity thing is working like a charm. Thanks
<small><i>Proud to have finally moved to the A-Ark. <a href="http://en.wikipedia.org/wiki/Places_in_The_Hitchhiker%27s_Guide_to_the_Galaxy#Golgafrincham">Which one are you in?</a></i><br>Author of the <a href="http://www.serpentooth.com">Guardians Saga</a> (Sci-Fi/Fantasy novels)</br></small>
|
|
|
|
|
you're welcome.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Assuming that standard numerical methods such as simplex aren't going to work here, and given that you do alreaduy have a fitness function available and a few coefficients to tweak, I'm wondering if perhaps a genetic algorithm or something like simulated annealing would work here?
|
|
|
|
|
Thanks for the input, guys... Got me thinking along the right lines, and that got me to the right google search...
I was searching for things like "curve fitting" and "best fit algorithm"... Turned out the 'proper' term was "Linear Regression"... And that got me here:
An Algorithm for Weighted Linear Regression[^]
Figures, the solution would be right here on CP
|
|
|
|
|
I'm surprised with all those answers, no one gave you the right approach: Polynomial Regression: http://en.wikipedia.org/wiki/Polynomial_regression[^]
It will give you a best-fit quadratic or cubic equation (or even higher orders if you want). The Wikipedia link defines it, but the explanation there isn't very intuitive. The basic idea is you get an equation for the error terms, take the derivative, and set it to zero. Solving that gives you the equation with the minimum error.
|
|
|
|
|
Well, to be fair, the answers got me thinking along the right lines, and led me to the right terms, which brought me right back one of Walt's articles on CP... See my above post
Marked the original as solved
|
|
|
|
|
But if your data set naturally has a curve, a linear model will be inaccurate.
|
|
|
|
|
Well it's multiple linear regression... It lets me specify the degree.
Using Walt's library, it's looking perfect... Using third-degree (x^3, so a possible S-shape in the curve), and releasing the update next week.
|
|
|
|
|
Hello,
I have an image and I mush find the shortest ways to connects points, and walls must be bypassed.
http://imageshack.us/photo/my-images/863/exampley.png
Can you recommend algorithm(s), that will help to make this program?
|
|
|
|
|
I suggest you start here[^].
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Look up the maze routing algorithm - it may work for what you're trying to do. Here is an applet[^] that shows you the basic steps of the search (the forward "wave" and the backtracking).
|
|
|
|
|
This is the code of Ackermann Algorithm.
Private Function T(ByVal m As Double, ByVal n As Double) As Double
Dim s1 As New Stack
Dim s2 As New Stack
s1.Clear()
s2.Clear()
If m = 0 Then
GoTo point
Else
Back: While n<>0
s1.Push(m – 1)
n = n - 1
End While
m = m - 1
n = 1
GoTo Point
point: Select Case (m)
Case 0
If s1.Count = 0 Then
Return n + 1
Else
s2.Push(n + 1)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 1
If s1.Count = 0 Then
Return n + 2
Else
s2.Push(n + 2)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 2
If s1.Count = 0 Then
Return (2 * n) + 3
Else
s2.Push((2 * n) + 3)
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case 3
If s1.Count = 0 Then
Return 5 + (8 * ((2 ^ n) – 1))
Else
s2.Push(5 + (8 * ((2 ^ n) – 1)))
m = s1.Pop
n = s2.Pop
GoTo Point
End If
Case Else
GoTo Back
End Select
End If
End Function
|
|
|
|
|
Thanks for Sharing. Now where do we use it? 
♫ 99 little bugs in the code,
99 bugs in the code
We fix a bug, compile it again
101 little bugs in the code ♫
|
|
|
|
|
this is not something I'm going to read as the code is not formatted. What happened to indentation?
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Is this a question? If so it is missing something. If it is supposed to be a Tip or Trick then please format it correctly, add some commentary about what it is and how it could be used, and post it in the proper place - you've been a member of CodeProject long enough to know where that is.
The best things in life are not things.
|
|
|
|
|
Hi, I am coding an algorithm that searches for a box on the screen. So far I got the snake to find the food which works great except that for example. If the snake is moving right it will sometimes move left and move ontop of it's self. I've spent awhile trying to figure it out on my own with no success. I think it has to do with the two blocks of if statements but I'm not sure. Maybe they need to be combined somehow? This is the last thing I need to figure out and my program is finished. Thanks in advance.
I tried.
if(direction_comp!=1){direction_comp=-1;} else {direction_comp=2;}
direction_comp of 1 = left;
direction_comp of -1 = right;
direction_comp of 2 = up;
direction_comp of -2 = down;
void comp_direction()
{
if(tick_comp==0 && avoiding==false)
{
if(segments_comp[head_comp]->panel->Left <= Food->Left)
{
if(segments_comp[head_comp]->panel->Top >= Food->Top){direction_comp =2;}
else{direction_comp=-1;}
}
else if(segments_comp[head_comp]->panel->Left >= Food->Left)
{
if(segments_comp[head_comp]->panel->Top >= Food->Top){direction_comp =2;}
else{direction_comp=1;}
}
if(segments_comp[head_comp]->panel->Top <= Food->Top)
{
if(segments_comp[head_comp]->panel->Left <= Food->Left){direction_comp =-1;}
else{direction_comp=-2;}
}
else if(segments_comp[head_comp]->panel->Top >= Food->Top)
{
if(segments_comp[head_comp]->panel->Left >= Food->Left){direction_comp =1;}
else{direction_comp=2;}
}
}
}
|
|
|
|
|
First off, there appears to be some redundant checks in the "else if" lines. Unless I'm missing something, the "if" portion of the "else if" will always be true since the "else" implies the converse of the "<=" operator from the original "if" block.
Now this won't effect the outcome of the snippet you posted but removing it and formatting it with some slightly different indentation and a few constant symbols might be easier to read in order to understand your implementation. If one took the liberty to do this, without impacting the logic, it might look like this...
const int LEFT = 1;
const int RIGHT = -1;
const int UP = 2;
const int DOWN = -2;
void comp_direction()
{
if (tick_comp == 0 && avoiding == false) {
if (segments_comp[head_comp]->panel->Left <= Food->Left) {
if (segments_comp[head_comp]->panel->Top >= Food->Top) {
direction_comp = UP;
} else {
direction_comp = RIGHT;
}
} else {
if (segments_comp[head_comp]->panel->Top >= Food->Top) {
direction_comp = UP;
} else {
direction_comp = LEFT;
}
}
if (segments_comp[head_comp]->panel->Top <= Food->Top) {
if (segments_comp[head_comp]->panel->Left <= Food->Left) {
direction_comp = RIGHT;
} else {
direction_comp = DOWN;
}
} else {
if (segments_comp[head_comp]->panel->Left >= Food->Left) {
direction_comp = LEFT;
} else {
direction_comp = UP;
}
}
}
}
You did not really provide much detail about your algorithm so I'm afraid I can't help much but I must ask, did you intend for the code to keep overwriting "direction_comp" even if it had been assigned earlier in the method?
|
|
|
|
|
No I didn't intend for the code to overwrite "direction_comp". That's the part I need help with. What the code does is make a snake home in on a food box. It works but sometimes the snake moves backwards on it's self. I think I know how to code that part but it won't work cuzz "direction_comp" keeps getting overwritten from the previous if block.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
