prism

Prism: an unsupervised clustering and nearest neighbor search algorithm

Clustering places similar vectors into the same cluster. Nearest neighbor search finds similar vectors to a search query vector. Prism does both of these things using artificial neural networks and decision trees The gradient descent learning algorithm is used to find an artificial neural network autoencoder. The autoencoder is trained to maximize the variance of the output of the middle layer for the given training data. The top half of the autoencoder is removed and a decision is learned using variance reduction. The learned decision is used to split the training data into two sets, and the algorithm is recursively applied to create a binary tree.

Results

The below results are from applying the algorithm to the iris data set. The label entropy is computed for the learned clusters. The entropy is normalized between 0 and 1. Lower entropy is better. The best entropy of kmeans is 0.153569, and the best entropy of the prism algorithm is 0.086526. Prism performs ~1.8 times better than kmeans on the iris data set.

Results for kmeans with different distance metrics

Results for run of algorithm with seed of 1

Averaged results for 16 runs of algorithm with different seeds