k-NN object

[Karl MacMillan]

I have posted an implementation of the k-NN algorithm as a pd object to my
website:

mambo.peabody.jhu.edu/~karlmac/download/pd/knn.tar.gz

There is a help patch and a readme, but they are probably not that much
help.  Feel free to ask me questions.  The general idea is that objects
can be classified by their feature vector (just a pd list of floating
point numbers - the numbers can refer to anything i.e. size, shape,
spectral features, etc.).  You train the classifier by inputting known
feature vectors.  After the training is complete you can input an unknown
feature vector which will be assigned the same classification as the
majority of the k (k is a small number like 3 or 5) closest feature
vectors in the database (nearest neighbors).  The classification is pretty
quick as the entire database is in ram and is usually pretty small (a few
hundred to a few thousand).

This implementation also has the ability to weight features - that is give
more importance to a certain feature.  This is done with a vector the same
size as the feature vector with weights between 0 and 1.  The default is
to treat all of the features equally.  I have some code that will
determine the optimum weights for a database using a genetic algorithm - I
will release this after I clean it up a bit.

Here at Peabody we have used a k-NN classifier to successfully recognize
sheet music (http://mambo.peabody.jhu.edu/omr) and timbre (I will post
papers about this soon).  At this point I should give credit to Dr. Ichiro
Fujinaga who has done most of this research - I am his graduate student
and helped with the implementation and some of the research, but he is the
one that deserves most of the credit.

One problem with the current implementation is the the length of the
feature vectors and the maximum number of classes is fixed at compile
time.  If this is really a problem for anyone let me know.

Karl

_____________________________________________________
| Karl W. MacMillan                                 |
| Computer Music Department                         |
| Peabody Institute of the Johns Hopkins University |
| karlmac at peabody.jhu.edu                           |
| www.peabody.jhu.edu/~karlmac                      |
-----------------------------------------------------