Experiments: Ground truth comparison with K-means

For this experiment, we try to discover how well NPclassify does at classification by comparing it with K-means. In this case, K-means is allowed to know a priori how many classes are in the input data set while NPclassify is not. Thus, K-means is given an initial advantage for this experiment. What we are interested in finding out is how good either method is at forming classes compared to the other. An input feature can either be erroneously classified as belonging to the wrong group or simply left out of the correct group. This sort of trend can be seen if classes are accidentally split or merged by the classification scheme (figure 1). Additionally, you might even have noise features that should not be classified in any class at all.

Figure 1: Given a set of input classes two kind of classification mistakes can be made. Either a single class can be split into several other classes or one or more classes can be accidentally merged into a single class. Additionally, you can have combinations of splits and merges.

For our experiment we create 40 images of 2d points with ground truth classes in them. Each class was created by hand since this allows one to create natural class shapes, but avoid the bias of creating test sets using a standard function. Thus, if we create a data set using a Gaussian function, we should expect that a Gaussian classification scheme will perform superior.  While such a method  may be greeted  with skepticism, it should be noted that the data sets were created prior to testing. However, since we can see that in figure 2 K-means does a reasonable job, as does NPclassify, most likely the input data set is reasonable. As figure 2 shows, as well as figure 5, without noise, NPclassify works as well at classification as K-means. This is a very nice result because it shows that without prior knowledge of how many classes one has and their general distribution, you can still classify features well in polynomial time using NPclassify.

Figure 2: Here NPclassify is compared with K-means with no noise points. In this case, K means knows a priori the number of classes in each set while NPclassify does not, nor does NPclassify know their distribution. The ground truth shows what are the actual classes. The color of a point gives what class it belongs in. The classes each algorithm finds can be seen with the eigen-matrix crosses superimposed. These show where each algorithm thinks the class is and what distribution it thinks the class has. In the first example on the first row, four classes are placed very close. NP classify accidentally merges the red and orange class into a single class, but finds the white and yellow class correctly. K-means splits the orange class and merges the yellow and red classes. As can be seen, while NPclassify does not know how many classes it must find, its performance is similar to K-means. 

In addition to a no noise condition, we created a noise condition in which noise was added semi-randomly by hand prior to testing. The noise images are the same as the no noise images except that noise has been added as points that do not belong to any class. From the results (figures 3,4 and 5), it can be seen that NPclassify performs significantly better than K-means. In general, NPclassify does a fairly decent job at ignoring noise. Most likely this is due to the fact that noise points have a link to non-noise points that has a significant length. As such, they tend to be pruned by the NPclassify graph cutting scheme.

Figure 3: Here NPclassify is compared with K-means where noise points have been added. Again, NPclassify does not know a priori how many classes it must find. As can be seen in the first example, NPclassify finds the red, white and orange class, but misses the yellow class. K-means finds all four classes, but has a very high error for where it thinks the classes are. Thus, an additional advantage is seen with NPclassify. It not only does not need to know how many classes it must find, but it is not as sensitive to noise like K-means.

Figure 4: Back to back, it can be seen that NPclassify has two advantages. The first as stated is that it does not need to know either the distribution of points or the number of classes in order to classify. Additionally, NPclassify is more robust to noise.

Figure 5: Error from classification with NPclassify and K-means is shown here with error bars. Interclass error is where a point is classified in another class in which it does not belong. Intraclass error is where a point is not classified in a class it belongs. Thus, interclass error is where points are split between classes while intraclass error is where points are merged into classes they do not belong. For the no-noise condition, NPclassify performs slightly better, but not at a statistically significant level. However, when noise is introduced, NPclassify performs statistically significantly better. Again, it performs better, even though it does not know the distribution or number of classes a priori.

In conclusion, figure 5 shows that NPclassify works as well as K-means for the no noise condition, even with K-means having the advantage of prior knowledge of the number of classes. However, NPclassify performs even better than K-means under noise. As such NPclassify can classify features better than K-means, but with less prior knowledge about what is being classified.

<<<BACK