# Probability density in kNN algorithm

I have been reading an implementation of the KNN algorithm to determine what is the probability that the price of an item A with certain attributes is between X and Y dollars.

In order to find such a distribution, we use a training set which contains some attributes (age, ranking, etc) and a price. We take those attributes (that is, everything except the price) and compute a distance (good old euclidean metric) between each item in our training set and the item A we are interested in. We use this set of distances as input for a gaussian distribution to get a weight for each element (in such a way that elements which are nearer of item A are considered more important than items far away).

Finally, we calculate the probability in the following way:

$P(X \leq \text{Price} \leq Y) = \displaystyle \frac{\sum \text{weights of items with price between X and Y}}{\sum \text{all weights}}$

where $\sum$ is performed for the nearest k items to item A.

Hopefully, that makes sense.

Question: We are using price as a variable in the probability function but we use weights to calculate such a probability. Why?

-
Might go better in stats.stackexchange.com? – highBandWidth Aug 19 '11 at 2:41

Some preliminaries: First, I wouldn't say that the algorithm "determines what is the probability that the price of an item A with certain attributes is between X and Y dollars." That sounds (to me) as if there's some objective probability and the algorithm allows you to determine it. Rather, the algorithm is one possible way to rationally assign a probability distribution to the price. As far as there is some overarching model in which it makes sense to talk about objective probabilities for prices, the algorithm doesn't calculate but estimates those probabilities. (At least I'd be quite surprised if there were a model of economics that leads to exactly this distribution.)

Second, I don't see the reason for the "but" in the question. It would indeed be strange if you weren't also using the price to assign/estimate a probability (which the "but" seems to be implying), but you are. So what you're effectively saying is that you're expecting nothing other than the price to be used in assigning a probability to the price. But we use information about related events to assign probabilities all the time -- if you want to predict today's weather, you're going to use information about yesterday's weather; to assign a probability distribution to the height of a randomly chosen person, you're going to use information about the heights of other people you've measured, and so on. It's only in very simple symmetric situations like symmetric dice that we can assign probabilities without any "external" information at all.

What you're doing in this case is to assume that the price for an item is likely to be near the price of similar items, and the weights are just a means of making the distribution come out that way. If an item is very close in your Euclidean similarity metric, it gets a high weight, and that increases the probability assigned to price ranges near that item's price.

-
Thanks for your answer. As for your first paragraph, absolutely. Obviously, this is a very simple example just for illustrative purposes. Regarding your second paragraph, my question is focused to know why is it valid to estimate this probability using gaussian-distributed weights which depend on a distance. Of course, this distance must depend on price (because its attributes depend on price), but such a relation can be very complicated, so the suggestion that this calculation can be regarded as an estimated probability probably is relying in some additional assumptions. – Robert Smith Aug 19 '11 at 17:18