code spectral clusteraalbertini nbsp 2

1、code spectral clusteraalbertini nbsp 2code spectral cluster 2010年07月22日1 根据数据构造一个graph, graph的每个节点对应一个数据点， 边的权重表示数据之间的相似度， 0表示完全不相似（通常为减少计算量， 将相似度低于阀值r的都记为0）。 graph用邻接矩阵的形式表示出来， 记为W. 2 把W的每一列元素加起来得到N个数，把他们放在对角上形成一个N * N矩阵， 记为D， D的其他元素都是0。 并令 L = D - W 3 求出L的前k个特征值及其对应的特征列向量 4 将这k个特征列向量排列在一起组成一个N * k的矩阵， 将每一行看做是一个k维空间中的向量， 然后对这N个k维向量进行聚类。 聚类的结果就是最终graph中的点的类别。 cut(A, B) = sigma(i in A, j in B) wij RatioCut(A, B) = cut(A, B)/|A| + cut(A, B)/|B| NCut(A, B) = cut(A, B)/vol(A) + cut(A,B)/vol(B), NCut

2、 是normalized cut, vol(A)表示A中的边之和 两者都可以算作 A 的大小的一种度量，通过在分母上放置这样的项，就可以有效地防止孤立点的情况出现，达到相对平均一些的分割。 public class SpectralClusterer /* * The points of the dataset */ protected DoubleMatrix2D v; /* * The class number of each point in the dataset */ protected int cluster; /* * The number of different clusters found */ protected int numOfClusters = 0; /* * The alpha star parameter value */ protected double alpha_star = 0.5; /* * The distance cut factor */ protected double r = -1; /* * The sigma scaling f

3、actor */ protected double sigma = 1.0; /* * The using sparse matrix flag */ protected boolean useSparseMatrix = false; /计算x, y之间的欧式距离 protected static double distnorm2(DoubleMatrix1D x, DoubleMatrix1D y) DoubleMatrix1D z = x.copy(); z.assign(y, Functions.minus); return z.zDotProduct(z); /合并两个无交集的点集合。 点用整数表示 protected static int merge(int a, int b) int v = new inta.length + b.length; System.arraycopy(a, 0, v, 0, a.length); System.arraycopy(b, 0, v, a.length, b.length); return v; /note, asso 与 cut

4、 正好相对 /a,b表示两个点集，W是点的相似度矩阵； asso返回Cut(a, b). /Computes the association degree between two partitions of a graph protected static double asso(DoubleMatrix2D W, int a, int b) return W.viewSelection(a, b).zSum(); /同上， 返回NCut(a, b) protected static double Nasso(DoubleMatrix2D W, int a, int b) int v = merge(a, b); return Nasso(W, a, b, v); /相对于指定subgraph v的NCut(a, b) .? protected static double Nasso(DoubleMatrix2D W, int a, int b, int v) return asso(W, a, a) / asso(W, a, v) + asso(W, b, b) / asso(W,

5、b, v); /Returns the normalized dissimilarity degree (or cut) between two partitions protected static double Ncut(DoubleMatrix2D W, int a, int b) return 2 - Nasso(W, a, b); /Returns the normalized dissimilarity degree (or cut) between two partitions protected static double Ncut(DoubleMatrix2D W, int a, int b, int v) return 2 - Nasso(W, a, b, v); /计算 W的bestCut （最小）； 得到两个partition, 分别表示两个点集(cluster) protected static int bestCut(DoubleMatrix2D W) int n = W.columns(); / Builds the diagonal matrices D

6、 and D(-1/2) (represented as their diagonals) DoubleMatrix1D d = DoubleFactory1D.dense.make(n); DoubleMatrix1D d_minus_1_2 = DoubleFactory1D.dense.make(n); for(int i = 0; i n; i+) double d_i = W.viewRow(i).zSum(); d.set(i, d_i); /d就是步骤2中的D，w中各列加起来形成的对角矩阵 d_minus_1_2.set(i, 1 / Math.sqrt(d_i);/d_minus_1_2 是什么？ DoubleMatrix2D D = DoubleFactory2D.sparse.diagonal(d);/这里的D是什么 DoubleMatrix2D X = D.copy(); / X = D(-1/2) * (D - W) * D(-1/2), X就是步骤2中的L。？ X.assign(W, Functions.minus); for(int i = 0; i n;

7、i+) for(int j = 0; j n; j+) X.set(i, j, X.get(i, j) * d_minus_1_2.get(i) * d_minus_1_2.get(j); / Computes the eigenvalues and the eigenvectors of X /计算特征值与特征向量 EigenvalueDecomposition e = new EigenvalueDecomposition(X); DoubleMatrix1D lambda = e.getRealEigenvalues(); / Selects the eigenvector z_2 associated with the second smallest eigenvalue / Creates a map that contains the pairs /得到第2小的特征值 AbstractIntDoubleMap map = new OpenIntDoubleHashMap(n); for(int i = 0; i n; i+) map.put(i, Math.abs(lamb

8、da.get(i); IntArrayList list = new IntArrayList(); / Sorts the map on the value map.keysSortedByValue(list); / Gets the index of the second smallest element int i_2 = list.get(1); / y_2 = D(-1/2) * z_2 DoubleMatrix1D y_2 = e.getV().viewColumn(i_2).copy(); y_2.assign(d_minus_1_2, Functions.mult); / Creates a map that contains the pairs map.clear(); for(int i = 0; i n; i+) map.put(i, y_2.get(i); / Sorts the map on the value map.keysSortedByValue(list); / Search the element in the map previuosly or

9、dered that minimizes the cut / of the partition double best_cut = Double.POSITIVE_INFINITY; int partition = new int2; / The array v contains all the elements of the graph ordered by their / projection on vector y_2 int v = list.elements(); / For each admissible splitting point i for(int i = 1; i n; i+) / The array a contains all the elements that have a projection on vector / y_2 less or equal to the one of i-th element / The array b contains the remaining elements int a = new inti; int b = new intn - i; System.arraycopy(v, 0, a, 0, i); System.arraycopy(v, i, b, 0, n - i); double cut = Ncut(W, a, b, v); if(cut best_cut) best_cut = cut; partition0 = a; partition1 = b; return partition; /* * Splits recursively the points of the

《code spectral clusteraalbertini nbsp 2》由会员小**分享，可在线阅读，更多相关《code spectral clusteraalbertini nbsp 2》请在金锄头文库上搜索。