Detecting misclassified data points using distance matrix I have a data set of around 65,000 items from a public database that have each been assigned to one of around 1,800 classes, but unfortunately I am aware that quite a few are misclassified. My goals are the following:


*

*I am trying to end up with classes such that for each point, the largest distance to another point in the class is less than the smallest distance to any other point not in the class.

*For now I am only dropping data points instead of reassigning to another pre-existing class. I would like to minimize the number of dropped data points while still achieving goal #1.

*Some classes may be split into smaller ones if necessary.


Some issues I am encountering are that:


*

*The classes vary significantly in size, both in terms of the number of points they contain (anywhere from 2 to 5000+) and the average distance from each point to another.

*Comparison between intra-class and inter-class distances for a data point is difficult, outliers in the same class make otherwise well-classified data points seem comparatively too close to other classes.

*Data points do not lie in a vector space, so determining the "center" of a class is difficult. The most I can do is select a representative member of the data set.

*Some classes are much to large and and contain other classes "within" them. These are the ones I am trying to break up.

*I am not entirely sure about how to interpret my distance metric, which is the Jaccard distance and ranges from 0-1. I am worried this penalizes large distances less than it should when taking the average of a set of distances or dividing one by another. I wonder if using some transformation of this distance may be more appropriate but I'm not sure which one to use.


What I have tried so far:


*

*First pass cleaning things up by calculating the mean intra-class distance for each data point and dropping those for which this value is X standard deviations above the class' mean. I think this is a good idea.

*Splitting up large classes that are enveloping other smaller ones. I've been doing this using UPGMA clustering on the large class and smaller ones nearby, then picking subtrees containing mostly members of the larger class that are reasonably separated from the smaller classes and each other.

*Also tried dividing up large classes using k-medoids, but did not have much success. I think this is because this algorithm assumes cluster size is relatively uniform, which is not true in my data set.

*Additional pruning by looking at Silhouette values.


Sadly although the above steps look like they are making improvements, I still have a very large number of violations of goal #1, and simply going through and removing all data points for which those violations occur removes most of my data set. At this point I feel like I am sort of running out of ideas and am looking for pointers on what to try next. I believe my goals should be achievable because I was able to accomplish them using a significantly smaller version of this data set with manual removal.
 A: You seem to be using unsupervised algorithms like classical clustering and silhouette scores.
You did not mention learning algorithms.  They are the best tool for automatic and highly accurate classification.  You would need to know the correct class of a lot of the examples to use supervised learning, however. I cannot tell from your description.
The problem of one-class-contains-another is a different problem that would need to be fixed in advance before using supervised learning.
1800 classes is a lot of classes. I've never heard of that large of a class-space before.
If a human can do something, that's a good indication that a supervised learning algorithm can do the same thing. You said "unfortunately I am aware that quite a few are misclassified" which makes me optimistic that supervised learning would work here.
Take a class on supervised learning at a MOOC, because that's the fastest way to learn about learning algorithms and get started today.  I suggest to start, the Statistical Learning course by Hastie and Tibshirani at lagunita.stanford.edu website.  If you like math a lot, Andrew Ng has an equally excellent course Machine Learning at coursera web site.
A: Rather than clustering, relate your method to nearest neighbor classification.


*

*Optimize the classificator parameters (neighborhood size, decision.function), then reclassify data.

*Minimize classification errors. Check for points which are not correctly classified. Then check which points can be relabeled to reduce the classsification error.

*Don't do anything. Your data does not need to be perfect (usually) - just make sure to not overfit. overfitting is worse if you have errors in your labels.
