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.