jaHoltz
commented
11 years ago Up and pushed is an implementation of agglomerative hierarchical clustering (in AnalysisFunctions.cc) named agglo_clust. My implementation takes a set of trees and returns a vector of treesets.
The process is fairly simple, it stores all of the trees in a map as individual clusters, and then copies all of the indexes to a set remaining, currently it then computes the distance using the distance function I wrote for silhouette (may eventually either take in a distance method or a distance matrix if that's preferable).
Then using a stack of pairs representing cluster keys from the map and the distance of that cluster to it's parent in the stack it computes clusters to be merged. The stack is initialized to some element from remaining, and then a function is run to find the closest neighbor. The closest neighbor is a pair who's second value is its distance from the top item in the stack. If that distance is less than the distance between the top cluster and its parent, we simply add the neighbor we found to the stack (removing it from remaining), and repeat. If the neighbor is less similar to the top cluster than the parent, we put the neighbor back in remaining and merge the top cluster and it's parent (they are as similar as it is possible to be).
After merging the two clusters in the cluster map the distance matrix is then recomputed with the new cluster in mind, and the process is repeated. This ends when the number of clusters in the map is equal to the number of desired clusters (currently set to 4). The map is then moved to the return vector, because the cluster ids are kind of arbitrary for later use.
I've tested this with a small number of cases to see how it works, and it appears to function. It forms clusters, although whether it does this as fast/efficiently as possible I'm not sure.
magikker
marclsmith
What: This would be a new function or set of functions which would take a set of trees (all trees?) and divide them into groups based on some measure.
Title: cluster (could use a better name?)
Input/Output: It would take a set of trees. And return clusters of trees. Some clustering measure would require other inputs, such as a the number of clusters, or a similarity measure.
Implementation:
There are tons of ways to approach clustering. Some require you to know how many clusters you want, others "discover" clusters as they go. I might start exploring ideas in the "Hierarchical clustering" class of algorithms as it doesn't require you to know how many clusters you're looking for.
You'll need similarity/distance measures between trees, but also ones for groups of trees. You'll also need to implement measure to evaluate cluster quality.
Possible Variations: Endless.
Agglomerative Hierarchical clustering Divisive Hierarchical clustering K-means Distribution-based clustering ....