Helpful Information
 
 
Category: Software Design
weighting algorithm

I'm not sure if I can explain myself well enough to get my problem across, but here goes:

I have three numbers. Any numbers, but let's say 10, 15 and 25. I want to pick a new number that is somewhere between the lowest and the highest (in this case, 10 and 25).

I want these numbers (10, 15 and 25) to have weights that influence the new number that I pick.

For example, if 15 was weighted the highest, followed by 10 and then by 25, the new number would be nearer 10 or 15 than 25.

I don't just want to average the numbers.

Can anyone explain to me how to accomplish this? If I haven't made any sense, I can try to explain myself better.

would it work to weight by multiplication?

weight1=10 // 10%
weight2=50 // 50%
weight3=40 // 40%

weightAvg=(number1*weight1+number2*weight2+number3*weight3)/(3*100)

(i am no mathematic genius, so this might be totally wrong...)

Mr. Hirsch-

Thanks for your input. I've already played with an idea like that, but it did not work the way that I wanted it to.

I will keep trying, though.

It sounds like a case for vector math. I picture it as if each of the existing numbers is exerting a certain amount of "pull" on the new number to be materialized. Is this the case? Can you iterate through a few examples of what you are talking about? I'm not quite sure I get it.

A. Who or what is choosing the "heaviness" of the weighting? For example, you say that in the set 10, 15, and 25, you would want 15 weighted the highest. Does this mean 15 is assigned a "1" ranking, and 10 has a "2" rank, while 15 is ranked 3rd. Do you mean that in a set of N numbers there are exactly N possible rankings to the weight, evenly distributed, or is there a possible scale to each weighting, such as 15 having a weighting of %80, 10 having a weighting of 15%, and 25 getting the final 5% left over.

Basically, I'm asking whether the weightings are really rankings.

B. Is this intended to be an iterative process, where each new number adds to the set of existing numbers, redistributing the rankings, and then waiting for the next new number? If so, who or what chooses the weighting/ranking of each new number coming in?

C. And is there any randomness desired to how closely the new number tracks to these weightings?

D. Am I asking too many questions? ;)

This is probably way above my head, but I'm going to give it a try. I'm assuming you can assign weights(not rankings) to each number, but it wouldn't really matter.
Let's say the number 10 has weight 10, number 15 weight 4 and 20 weight 2. Now you'd have to start multiplying them all and then taking the average:
10*10+15*4+20*2=200
200/16 = 12.5
What you basically want now are random numbers of which the average is not 15(which would be normal between 10 and 20), but random numbers with an average of 12.5.
I'm not really sure how to do this, but I guess someone can work this out.

rycamor uses the word 'pull factor' which is the best way to describe this idea, but a few notes are required to explain it:

1) Your wieghting/ranking values are arbitary.

2) Only you know the criteria for assigning weighting values, so only you can write an algoithm to manage this part of the process. Again, it could be random and arbitary.

3) From what I understand in your original question, the difficult part is finding the new number, which is 'pulled towards' those values with a big weighting MORE than it is 'pulled towards those with a small weighting.

4) try this: all your values have weightings - whatever these weightings are - it doesn't matter - sum them (to get W) and divide by 100 to get a %age for each one,

so: pull factor of value = value's weight/(total weight)/100,

or more succinctly, f=w/(W/100)

Now with these pull factors calculated, you want to place a new value into the set, it's position determined by the pull factors of the existing values:

- Pick a point along x (I'm picturing this on an axis, where x represents the value and y represents the weight).

- Place the new value here to start with.

- Multiply it's 'distance from each value' by 'the value 's pull factor'

- Sum all these products in the +ve and -ve directions (bit like solving turning moments)

- Iteratively relocate the new value along x (probably recursively selecting midpoint of most recent test and starting point in the direction of the remaining pull.

- This processs continues until the system reaches equilibrium, ie. total pull on new value (in +ve and -ve directions) =0

Note, I am working with an x-axis, representing the values. You should to, but make it start with your lowest value and end with your highest.


That should be a start
Christo

first, thank you all very much.

Pull factor is the best way I can think of to describe what I want to do.

I'm trying to figure out how to explain my idea...

Here's an attempt:

'A' is an object that is positioned at 0,0 on a grid, a graph, a plane, a screen, whatever. It has a heading of 90 degrees, so it is travelling straight up the Y-axis.

'B' and 'C' are other objects of the same type, positioned elsewhere on the same plane. B has a heading of 123 degrees and A has a heading of 65 degrees.

A: 90 degrees
B: 123 degrees
C: 65 degrees

When A wants to pick a new heading, I want it to be based on the heading of B and C, but I don't want it to be just an average of their headings. If B is closer to A than C is, I want B's heading to have more influence, or 'pull'.

So, proximity is what is determining the weights.

I have been trying to learn enough about vectors to do this with vectors, but so far I haven't gotten anywhere at all.

I hope maybe this will clear up my intentions a little bit... I appreciate any help that you can give me.

Let's see if we can break down your problem into smaller ones:

1. What is the relative 'degree of closeness' that B and C have with A?

2. What is the difference in headings of B and C, expressed mathematically?

3. How does that relative degree of closeness pull the new heading of A OFF from the mean between the headings of B and C?

So, if B is 20 units away from A, and is facing at 45 degrees, while C is 10 units away, facing at 105 degrees, then we first establish the 'degree of closeness' (I picture it better this way, than to say relative distance).

1. Add both distances, and you get 30 units. Now calculate the percentage of that whole that is owned by B and C. B has 33.333% while C has 66.666% (to whatever level of floating point precision you want).

2. Get the differance between the headings: 105 - 45 = 60 degrees. If both pulls were even, the new heading would be halfway between, or 75%. This is the mean heading.

3. Now apply the "pull" to 75%. If each object was equidistant from A, then the pull would be 50/50, so the new heading would be 75%. As either object approaches zero distance to A, it's pull approaches 100%, so the new heading would be 45% or 105%. Since C has 66.666% of the pull, then that new heading is 66,666% of the difference from 45% to 105% (C has 2/3 of the pull), and thus is 85%. For the sake of pushing the example, let's not choose such an easy numerical value. Say C had 71% of the pull, and B had 29%. So the new heading is 71% of the difference between the two, or 45 + (60 * .71) = 42.6 degrees added to 45: the new heading is 86.6 degrees.

(This is starting to look to me like you are creating a bezier node/curve editing tool or somesuch.)

So, if this is what you are looking for, then your homework is to reduce this to a nice tight mathematical expression.

Others: please poke any and all holes in my logic.

I think you have worked everything out pretty much how I would, however, when adding 45 to 42.6, I think the answer tends to be 87.6 not 86.6. On a side note though, is this limited to just 3 objects? or are we going to have the scenario of say 5 objects, with different weightings, and headings, and we then have to work out the collective weightings for each side of the reference object?

when adding 45 to 42.6, I think the answer tends to be 87.6 not 86.6

Details... details.... <hand-wave />

Yes, obviously, the problem gets more complex as you add more points, but the basic idea is still the same.

I would like to suggest a different approach.

I think we should look at this as if it where a geometric
problem.

Suppose you had a container which was really small at the top and and large at the bottem

| |
/ \
/ \
/ \
---------

Suppose you choose a random number between the minimum volume
and the maximum volume and then filled your container to that
level

If you measured the height from the bottem of the container to
to the point you filled it too you would have then have a
number weighted by the shape of the container.

So I think you should right your solution like this

Step 1.
-Find the Total area of the shape that created by your
numbers and their weights

Step 2.
-Pick a random number between 0 and the total area.

Step 3.
-Using the random area value. Figure out how far you have
filled your container.

Of course the fun part is finding the area. If your lucky your pull can be expressed by a equation that you can use calculus against.

Here is a quick perl script to show what I mean using a really simple case.

----
#!/bin/perl
# value 1= 0 & pull=0
# value 2= 10 & pull=10
$x_1=0;
$y_1=0;
$x_2=10;
$y_2=10;

#$k is the slope
$k= ($y_1-$y_2)/($x_1-$x_2);
#area should be obvious
$area= abs(($y_1-$y_2)*($x_1-$x_2)*.5);

#fill and array with 0s
for ($i=0;$i<$x_2;$i++) {
$arry[$i]=0;
}

#$area = .5 * x^2 * k
#$x=sqrt( 2 * area / k)

for ($i=0;$i<100000;$i++) {
# create a random number between 0 and $area
$rand=rand($area);
# use our solved formula to translate figure out what our
# weighted x should be
$x= int sqrt ($rand * 2 / $k);
$arry[$x]++;
}

for ($i=$x_1;$i<$x_2;$i++) {
print "i=$i,".$arry[$i]."\n";
}
----

sorry for the delay... I've been sort of busy lately.

rycamor, I think that I like your way of doing this, but I am not sure that I understand it very well. Can you run through it once more?

How about with these points? (I have just pulled these out of the air, so I'm not sure how messy this will be)


Point A: Reference point
Point B: 10px away, 30° heading
Point C: 18px away, 78° heading
Point D: 24px away, 150° heading


Here's what I come up with, using your way:



Total distance, of all the points: 53px
==========================
B: 18.9% of total (0.1887)
C: 34% of total (0.3396)
D: 45.3% of total (0.4528)


Mean heading: 86°

But now I'm lost... I don't know how to apply your step 3 to this situation (with more than 2 competing points). And, the way I'm going to use this, I don't know how many points there will be competing.

...need to think about this a little more, because I think I might see a hole in my logic.

As either object approaches zero distance to A, it's pull approaches 100%
This part of my above thesis might not hold true. What is this meant to be a model of? Relative gravitational pull for objects in motion? Does reference point A in any way influence the other points?

I need a little more description.

once again, I'm sorry for the long time between my responses.

rycamor: I am trying to implement some very, very simple flocking behavior. The weighting is based on each boid's distance from the current boid, so that the closer they are, the greater their weight should be.

I finally started to understand vectors, and some of the simple math involved (like just addition, subtraction, and multiplication).

The vectors that I have created are all unit vectors. In testing, weighting the vectors by simply scaling them worked well...

Now, my problem is figuring out some sort of equation that will give me good weights based on the distances. My first thought was to do it like you had suggested, rycamor, and have the weights be based on percentages of the total distance owned by the other boids.

I just did that this morning, and I quickly realized that this equation made the boids that are farthest away the heaviest-weighted, which is backwards.

As I was writing this, the idea came to me that I just needed to use 1 minus the percentage to find the right weights...

If anyone has any ideas about this, I'm all ears.

And thank you all for your help.


-Will

An obvios approach woulld be to weigh with inverse distance
w = 1/(distance(myobject, otherobject)
this gives an enormous influence for ther nearest partner
You can ammeliorate this a bit by two variations

a: add a positive constant to the distance
w = 1/(const + distance)
this moves the hyperbola to the left on the x axis, so the infinite value at 0 distance is replaced by a sharp peak

b: take a powerfunction of the distance
w = 1/(ocnst+distance)^power
if power>1 this gives a smooth bell shaped curve (it flatens at the center)

It certainly seems that WoR is right about this. Now we know exactly what the problem is, we can give more constructive suggestions.

So far, all the solutions have assumed linear interpolation between the known values, but gaussian weighting certainly seems to be a more natural way of doing it. Working out what variance the gaussians should have is a well-understood problem which occurs, inter-alia, in statistical learning.

Basically, the larger the variance you choose, the smoother the flocking behaviour will be - giving you a smoothness parameter to the final interpolated flow field.

last night I started trying to find some information about Gaussian weighting, but I could not find an explanation or an equation simple enough for me to understand.

The simplest equation I found looked like so:


G(x) = A * exp(-1 * sqr(x) / (2*sqr(sigma));

where A is a constant and sigma is the 'spread' or 'standard deviation'.

I don't know what the 'spread' or 'standard deviation' is, or how to calculate it.

Can anyone explain to me how to implement Gaussian weighting in my situation?

I have an unknown number of objects that are less than 50 pixels away from a given object. I want them to be weighted more the closer they are to the given object.

(and, the 50 pixels is not necessarily 50, but whatever it is, I know it. It is not random.)

2.10. Generating Biased Random Numbers
Problem
You want to pick a random value where the probabilities of the values are not equal (the distribution is not even). You might be trying to randomly select a banner to display on a web page, given a set of relative weights saying how often each banner is to be displayed. Alternatively, you might want to simulate behavior according to a normal distribution (the bell curve).

Solution
If you want a random value distributed according to a specific function - e.g., the Gaussian (Normal) distribution - consult a statistics textbook to find the appropriate function or algorithm. This subroutine generates random numbers that are normally distributed, with a standard deviation of 1 and a mean of 0.

sub gaussian_rand {
my ($u1, $u2); # uniformly distributed random numbers
my $w; # variance, then a weight
my ($g1, $g2); # gaussian-distributed numbers

do {
$u1 = 2 * rand() - 1;
$u2 = 2 * rand() - 1;
$w = $u1*$u1 + $u2*$u2;
} while ( $w >= 1 );

$w = sqrt( (-2 * log($w)) / $w );
$g2 = $u1 * $w;
$g1 = $u2 * $w;
# return both if wanted, else just one
return wantarray ? ($g1, $g2) : $g1;
}
If you have a list of weights and values you want to randomly pick from, follow this two-step process: First, turn the weights into a probability distribution with weight_to_dist below, and then use the distribution to randomly pick a value with weighted_rand:

# weight_to_dist: takes a hash mapping key to weight and returns
# a hash mapping key to probability
sub weight_to_dist {
my %weights = @_;
my %dist = ();
my $total = 0;
my ($key, $weight);
local $_;

foreach (values %weights) {
$total += $_;
}

while ( ($key, $weight) = each %weights ) {
$dist{$key} = $weight/$total;
}

return %dist;
}

# weighted_rand: takes a hash mapping key to probability, and
# returns the corresponding element
sub weighted_rand {
my %dist = @_;
my ($key, $weight);

while (1) { # to avoid floating point inaccuracies
my $rand = rand;
while ( ($key, $weight) = each %dist ) {
return $key if ($rand -= $weight) < 0;
}
}
}
Discussion
The gaussian_rand function implements the polar Box Muller method for turning two independent uniformly distributed random numbers between 0 and 1 (such as rand returns) into two numbers with a mean of 0 and a standard deviation of 1 (i.e., a Gaussian distribution). To generate numbers with a different mean and standard deviation, multiply the output of gaussian_rand by the new standard deviation, and then add the new mean:

# gaussian_rand as above
$mean = 25;
$sdev = 2;
$salary = gaussian_rand() * $sdev + $mean;
printf("You have been hired at \$%.2f\n", $salary);
The weighted_rand function picks a random number between 0 and 1. It then uses the probabilities generated by weight_to_dist to see which element the random number corresponds to. Because of the vagaries of floating-point representation, the accumulated errors of representation might mean we don't find an element to return. This is why we wrap the code in a while to pick a new random number and try again.

In addition, the CPAN module Math::Random has functions to return random numbers from a variety of distributions.

Heh, this is like a year old thread.

This problem is simillar to the gravitational pull of objects on another object (Google: Newton's law of gravitation). If it is flocking objects, you have must have a 2d velocity, so changing to an acceleration shold not be that tough. Further, assuming all objects are points and a mass of 1, then change in acceleration is simply proportional to 1/(r*r) where r is distance between two points.

The real proportion is G which wont really work when your distance unit is pixels instead of meters, so you would have to fiddle with it until you get a pulling effect that looks right.

So every time step, you would move all objects that don't respond to pulling, then for the remaining objects, apply all the changes in accelleration from every other obejct.

I answered here to a wrong question. I couldn't find a way to delete my posting.. Please ignore.

Anyway, my answer was to the above mentioned discrete distribution case when there is no need to find a new kind of element but randomly choose one from the existing elements with their weights having an effect.

My answer is a memory consuming one while the above mentioned is time consuming:


sub generate {
my @hit;
my $element;
my $weight;

while ( ($element, $weight) = each %hash )
{
push @hit, $element while ($weight--);
}

return $hit[int rand @hit];
}

The idea is to create a temporary array with multiple equivalent elements for each kind of element based on its weight and then randomly pick one element from the resulting array. This way the weights affect the probability of choosing a certain kind of element.

This approach is imho better than the one proposed above since the order in which the elements are in the hash does not effect the probability of choosing certain kind of element.










privacy (GDPR)