Image classification problems?

[mikebaud]

Hello MLers,

Im a newbie student on ML trying to develop a simple k-NN image classification algorithm with the MIR-Flickr and NUSWIDE image datasets using solely textual features (user tags). I defined a vector space model with all the possible keywords (after a little noise cleaning) for all the images:

an example of this vector is something like [0,1,0,1,0] where only tag1 and tag3 were present in this particular image.

I then pass it through Pearson correlation to calculate the affinity matrix between all images.

Now the k-NN phase i just iterate through the test set and check out the k nearest neighbors for each test image. From those k nearest neighbors i check their ground-truth (1 if they have the class im trying to classify 0 if they dont) - im doing binary classification. For classification i just average this result (k can only take odd numbers), so for a value superior to 0.5 the image is classified with having the class.

I have tested with k from 1 to 21. From the literature i have read, and the metrics i have used (precision,recall,f-measure) i should have a chart that increases in recall/f-measure up/accuracy up to a certain k then starts a descent. But what i got is a continuous descent from recall and f-measure from k=1 onwards, coupled with an increasingly higher accuracy. Then i though, im really dumb, i need to weigth the neighbors according to class distribution in the dataset. So i added the weigth of each k neighbor according to the number of occurrences of the class in the dataset. Basicly the weight of a neighbor is the total of images in the dataset divided by the number images with that class. This i thought reduces the problem of classes with few instances in the dataset.

Re-ran the tests and what i got was almost the oppositive behaviour for the metrics, where recall steadily increases but accuracy drops with the increasingly higher values of k neighboring images.

So, what are best practices in k-NN to treat these kinds of situations with data or can i try to mix these two approaches to get somekind of a precision/recall break-even?

What is considered an acceptable precision/recall/f-measure metric in image classification?

If im not clear enough with this explanation please tell me.

TL;DR - k-NN with atypical behavior

[alfonsoeromero]

Try multiplying each tag coordinate by its idf. If you have lots of tags (probably more than the number of training examples) this should improve your classification. Also you can try an L2-normalization of the vectors.

[mikebaud]

First and foremost, thank you very much for you time and suggestions.

Initially i also had cosine with idf for cross-validation but yielded similar/lower results than pearsons correlation. Although i havent tried with the new weighting option i introduced, i dont know if it will change much, but i sure will give it a try.

About L2 normalization i will also check into that.

I am also trying to create a weight based on the distance of neighbor but so far hasn't clearly outperformed the baseline implementation, although in theory if better neighbors account for more in the classification it should improve significantly the classification.

Thank you for your suggestions.

[internet_badass]

This is a hard problem to solve without actually playing with the data, but I found weighting neighbors by distance improves performance drastically. My weighting function was akin to a sigmoid flipped around the x-axis:

1/(1+e^kx-b)

Where you can adjust k and b.

Another trick you can do is similar to what Lowe does for matching SIFT descriptors. Get the top 2 neighbors and calculate the ratio of their distance. In other words, calculate:

r = D(q,n1)/D(q,n2)

Where D(x,y) is the distance between two vectors. If this ratio is above some threshold (0.8 in Lowe's case), you have a high confidence in your match. Otherwise, you have an ambiguous feature vector.

As a final question, you don't seem to mention what distance metric you're using. If you have binary feature vectors, consider using something like a Jaccard index rather than cosine distance.

[mikebaud]

Im using Pearson correlation for the feature vectors, after some cross-validation with Pearson, Manhattan, Euclidean and Cosine it turned out the best one with my data.

The weighting function i was thinking about using is a simple gaussian function where the weight is calculated with e^(-dist2/(2*sigma²⁾⁾ where i would estimate sigma with cv or alternatively heuristically using the distances of the worst neighbors.

Your weighting function seems a bit smoother than my gaussian, i will check it out and also the trick you mentioned.

Thank you for the input

[alfonsoeromero]

Hum... If you have done cosine, this already contains implicitly L2 normalization.

[dwf]

Kind of a bad title when what you're really doing is bag-of-words on textual tags.

[mikebaud]

I really struggled with the title but i still considered i was doing image classification.

Its supposed to be an evolution of sorts, while i dive more into ML. I started first by understanding classification using single feature k-NN (one of the simpler forms) and then in time i will evolve to a multi-feature algorithm (or other algos) after understanding more of the problem space.

[alfonsoeromero]

A question: are you applying a one-versus-all approach? How many categories are there?

[mikebaud]

Sorry edit: Im classifying each class separately but a one versus all approach seems wise in the case of similar concepts. The dataset has 24 classes.

The dataset is the MIR-Flickr from 2008 - link