The Tor Browser: comparison toolkit/components/places/ClusterLib.js

comparison: toolkit/components/places/ClusterLib.js

toolkit/components/places/ClusterLib.js

branch: TOR_BUG_3246
changeset 7: 129ffea94266

equal deleted inserted replaced

--1:000000000000
+:c10e5ee33c58
+/* This Source Code Form is subject to the terms of the Mozilla Public
+* License, v. 2.0. If a copy of the MPL was not distributed with this
+* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+/**
+* Class that can run the hierarchical clustering algorithm with the given
+* parameters.
+*
+* @param distance
+*        Function that should return the distance between two items.
+*        Defaults to clusterlib.euclidean_distance.
+* @param merge
+*        Function that should take in two items and return a merged one.
+*        Defaults to clusterlib.average_linkage.
+* @param threshold
+*        The maximum distance between two items for which their clusters
+*        can be merged.
+*/
+function HierarchicalClustering(distance, merge, threshold) {
+this.distance = distance || clusterlib.euclidean_distance;
+this.merge = merge || clusterlib.average_linkage;
+this.threshold = threshold == undefined ? Infinity : threshold;
+}
+HierarchicalClustering.prototype = {
+/**
+* Run the hierarchical clustering algorithm on the given items to produce
+* a final set of clusters.  Uses the parameters set in the constructor.
+*
+* @param items
+*        An array of "things" to cluster - this is the domain-specific
+*        collection you're trying to cluster (colors, points, etc.)
+* @param snapshotGap
+*        How many iterations of the clustering algorithm to wait between
+*        calling the snapshotCallback
+* @param snapshotCallback
+*        If provided, will be called as clusters are merged to let you view
+*        the progress of the algorithm.  Passed the current array of
+*        clusters, cached distances, and cached closest clusters.
+*
+* @return An array of merged clusters.  The represented item can be
+*         found in the "item" property of the cluster.
+*/
+cluster: function HC_cluster(items, snapshotGap, snapshotCallback) {
+// array of all remaining clusters
+let clusters = [];
+// 2D matrix of distances between each pair of clusters, indexed by key
+let distances = [];
+// closest cluster key for each cluster, indexed by key
+let neighbors = [];
+// an array of all clusters, but indexed by key
+let clustersByKey = [];
+// set up clusters from the initial items array
+for (let index = 0; index < items.length; index++) {
+let cluster = {
+// the item this cluster represents
+item: items[index],
+// a unique key for this cluster, stays constant unless merged itself
+key: index,
+// index of cluster in clusters array, can change during any merge
+index: index,
+// how many clusters have been merged into this one
+size: 1
+};
+clusters[index] = cluster;
+clustersByKey[index] = cluster;
+distances[index] = [];
+neighbors[index] = 0;
+}
+// initialize distance matrix and cached neighbors
+for (let i = 0; i < clusters.length; i++) {
+for (let j = 0; j <= i; j++) {
+var dist = (i == j) ? Infinity :
+this.distance(clusters[i].item, clusters[j].item);
+distances[i][j] = dist;
+distances[j][i] = dist;
+if (dist < distances[i][neighbors[i]]) {
+neighbors[i] = j;
+}
+}
+}
+// merge the next two closest clusters until none of them are close enough
+let next = null, i = 0;
+for (; next = this.closestClusters(clusters, distances, neighbors); i++) {
+if (snapshotCallback && (i % snapshotGap) == 0) {
+snapshotCallback(clusters);
+}
+this.mergeClusters(clusters, distances, neighbors, clustersByKey,
+clustersByKey[next[0]], clustersByKey[next[1]]);
+}
+return clusters;
+},
+/**
+* Once we decide to merge two clusters in the cluster method, actually
+* merge them.  Alters the given state of the algorithm.
+*
+* @param clusters
+*        The array of all remaining clusters
+* @param distances
+*        Cached distances between pairs of clusters
+* @param neighbors
+*        Cached closest clusters
+* @param clustersByKey
+*        Array of all clusters, indexed by key
+* @param cluster1
+*        First cluster to merge
+* @param cluster2
+*        Second cluster to merge
+*/
+mergeClusters: function HC_mergeClus(clusters, distances, neighbors,
+clustersByKey, cluster1, cluster2) {
+let merged = { item: this.merge(cluster1.item, cluster2.item),
+left: cluster1,
+right: cluster2,
+key: cluster1.key,
+size: cluster1.size + cluster2.size };
+clusters[cluster1.index] = merged;
+clusters.splice(cluster2.index, 1);
+clustersByKey[cluster1.key] = merged;
+// update distances with new merged cluster
+for (let i = 0; i < clusters.length; i++) {
+var ci = clusters[i];
+var dist;
+if (cluster1.key == ci.key) {
+dist = Infinity;
+} else if (this.merge == clusterlib.single_linkage) {
+dist = distances[cluster1.key][ci.key];
+if (distances[cluster1.key][ci.key] >
+distances[cluster2.key][ci.key]) {
+dist = distances[cluster2.key][ci.key];
+}
+} else if (this.merge == clusterlib.complete_linkage) {
+dist = distances[cluster1.key][ci.key];
+if (distances[cluster1.key][ci.key] <
+distances[cluster2.key][ci.key]) {
+dist = distances[cluster2.key][ci.key];
+}
+} else if (this.merge == clusterlib.average_linkage) {
+dist = (distances[cluster1.key][ci.key] * cluster1.size
++ distances[cluster2.key][ci.key] * cluster2.size)
+/ (cluster1.size + cluster2.size);
+} else {
+dist = this.distance(ci.item, cluster1.item);
+}
+distances[cluster1.key][ci.key] = distances[ci.key][cluster1.key]
+= dist;
+}
+// update cached neighbors
+for (let i = 0; i < clusters.length; i++) {
+var key1 = clusters[i].key;
+if (neighbors[key1] == cluster1.key ||
+neighbors[key1] == cluster2.key) {
+let minKey = key1;
+for (let j = 0; j < clusters.length; j++) {
+var key2 = clusters[j].key;
+if (distances[key1][key2] < distances[key1][minKey]) {
+minKey = key2;
+}
+}
+neighbors[key1] = minKey;
+}
+clusters[i].index = i;
+}
+},
+/**
+* Given the current state of the algorithm, return the keys of the two
+* clusters that are closest to each other so we know which ones to merge
+* next.
+*
+* @param clusters
+*        The array of all remaining clusters
+* @param distances
+*        Cached distances between pairs of clusters
+* @param neighbors
+*        Cached closest clusters
+*
+* @return An array of two keys of clusters to merge, or null if there are
+*         no more clusters close enough to merge
+*/
+closestClusters: function HC_closestClus(clusters, distances, neighbors) {
+let minKey = 0, minDist = Infinity;
+for (let i = 0; i < clusters.length; i++) {
+var key = clusters[i].key;
+if (distances[key][neighbors[key]] < minDist) {
+minKey = key;
+minDist = distances[key][neighbors[key]];
+}
+}
+if (minDist < this.threshold) {
+return [minKey, neighbors[minKey]];
+}
+return null;
+}
+};
+let clusterlib = {
+hcluster: function hcluster(items, distance, merge, threshold, snapshotGap,
+snapshotCallback) {
+return (new HierarchicalClustering(distance, merge, threshold))
+.cluster(items, snapshotGap, snapshotCallback);
+},
+single_linkage: function single_linkage(cluster1, cluster2) {
+return cluster1;
+},
+complete_linkage: function complete_linkage(cluster1, cluster2) {
+return cluster1;
+},
+average_linkage: function average_linkage(cluster1, cluster2) {
+return cluster1;
+},
+euclidean_distance: function euclidean_distance(v1, v2) {
+let total = 0;
+for (let i = 0; i < v1.length; i++) {
+total += Math.pow(v2[i] - v1[i], 2);
+}
+return Math.sqrt(total);
+},
+manhattan_distance: function manhattan_distance(v1, v2) {
+let total = 0;
+for (let i = 0; i < v1.length; i++) {
+total += Math.abs(v2[i] - v1[i]);
+}
+return total;
+},
+max_distance: function max_distance(v1, v2) {
+let max = 0;
+for (let i = 0; i < v1.length; i++) {
+max = Math.max(max, Math.abs(v2[i] - v1[i]));
+}
+return max;
+}
+};