全连接相似度图中任意两个数据点都互相连接，因此这里不再绘制结果如图 1 所示:2.0-■ ■«« ■« •• • * V4 4* 4 • •* •• •• • ■ ■* •• ■ • •• •«>*■* « * ii* *« * «4 « *•# * «• • ■ ♦■1.5 55 Z C.5 7 5 75sepal JengUiil.cml3 日.53J1JZ.3C-2.&-2.0-b) £ 邻近图， £ =0.3(a)数据点分布(c) k邻近图，k=5(d)互k邻近图，k=5图 1 相似度图由图1(b)可知，£邻近图在数据分布密度不同时会出现有些数据点无法连接的问题由 图1(c)可知k邻近图很好地解决了£邻近图存在的问题，且可以连接不同密度的数据点 由图1 (d)可知互k邻近图介于£邻近图和k邻近图之间，且倾向于连接相同密度部分，而 不连接不同密度部分将相似度图对应的权重矩阵进行可视化，结果如图 2 所示a) £ 邻近图， £ =0.3b) k 邻近图， k=5(c)互k邻近图，k=5 (d)全连接图 2 邻接权重矩阵由图 2 可知全连接相似度图的邻接权重矩阵最为稠密，互 k 邻近图的邻接权重矩阵最稀疏，且所有相似度图对应的邻接权重矩阵均为对称阵。
3.相似度图划分目标函数和拉普拉斯矩阵3.1 相似度图划分的目标函数寻找能完成聚类的相似度图划分，可以采用代价函数的思想，即不同划分需要付出不同 的代价，当将距离较近的、看似为同一个类的两个点切分为不同类时，需要付出较大代价； 将距离较远的两个点切分到不同子图时，需要付出较小代价，这样聚类问题就转化为寻找一 个划分使得代价函数最小的优化问题令化为第k个子图所包含的数据点集合，A为第k个子图的补图，即A nA =0, k k k kA A -V，从而有k k3-1)V = A A A1 2 m设完成聚类需要 m 次划分，则代价函数可以表示为3-2)Cut(V) = Cut(A ,A，…，A )1 2 m因为对于Ak，有V = A A，所以k k k3-3)Cut(V)仝 Cut(A , A )kkk=1即式（32 ）中的多聚类问题可以分解为如式（33 ）所示的多次二聚类问题在相似度图中’连接两个数据点的边权值越大表示两点越近’因此Ak和Ak的划分代价可用连接两个子图所有边的权值之和表示，即Cut (V) = £ Cut (A , A )= 工 wk k 2 _ jx gA , x gAi k j k34 )k=1式（34）中左乘1/2是因为存在w二w ,即相同边的权重被相加了两次。
从而得到了分类 ij优化目标函数，即最小分割目标函数min Cut(V )= min1££ w2 - jxigAk,xjgAk353.2 拉普拉斯矩阵的引入[1]在二聚类问题中，如果使用一个布尔值f来标识数据点x所属类别，则有 ix g Ai _kx g Aik36则对于任意两个数据点有f - fij-1g A orkx,xi j -- _x g A , x g Ai _k j kx g A , x g Ai k j kx ,x g Ai j k37这样可以把式（35 ）展开为min Cut (V)=min 2xi GAk，xj GAk£ w = min-ij1 工(f -f }2 ij i ji=1 j=138 )根据图论中度的定义，可以得到对于相似度图中的任意数据点x ,度d为与它相连的 ii所有边的权重之和，即d = £ wi ijj=1则对于整个数据集，可以得到一个n x n的度矩阵D，即310 )d它是一个对角阵，第i行对应第i个数据点的度d ,ij如果把式（38 ）中的W.C - 展j开可以得到—为另 W (f - f )=—为区(w f 2 - 2 f f W + W f 2 )ij i j 2 ij ij=— i=— j=—2 i=1i j ij ij311 )因为 w = wij ji所以W f 2 = )ij j i1 1 i 2 2 in ni=1 j=1 i=1丄(w 2 +・・・ + W f 2 )312 )1i 1 2 i 2 ni ni=1=f 2 d + f 2 d +・・・ + f 2 d11 2 2 n nii i=12ffwi j ij i=1 j=1则根据矩阵二次型的原理可将式（311 ）化简为2 ij i j i ii=— j =— i=—313 )= f TDf - f TWf=f TLf式（313）中f = [/—，f，・・・，f 1称为指示向量，它指定了每个数据点所属的类别。
这样 1 2 n就得到了如下形式的拉普拉斯矩阵314 )即未正则拉普拉斯矩阵，由于D和W都是对称阵，所以拉普拉斯矩阵也是个对称阵这样分类优化目标函数可以等价为min Cut(V )=min f TLf315 )现在将上述原理拓展得到多聚类问题中，设总共有 m 个分类，则表示每个数据点所属 类别的布尔值为1 x e Ai k (i = 1,2,・・・，n; k = 1,2,・・・，m)0 x电Aik则指示向量为h =B，h ,h ]T如果是理想分类，即每个数据点以概率1属于某k 1k 2 k nkhik3-16)个类，而不会同时属于多个类，则指示向量是相互正交的将 m 个指示向量按列组合在起，就得到了指示矩阵H，由指示向量正交可以得出HTH =n这样多聚类优化目标函数为min Cut(A , A ，.・.，A ) = min HtLH1 2 m3-17)4.分类优化目标函数求解4.1 分类优化目标函数改进由最小分割目标函数可知其倾向于将所连边最少且边权值较低的孤立点分割出来，如图3 所示，因此需要加入其它限制以改进目标函数分割效果图 3 最小分割局限性改进最小分割目标函数的基本思想是将代价函数除以子图的规模，从而消除子图规模对代价函数的影响。
子图的规模有以下两种度量方法：1)子图的势，即子图包含的数据点数量2)子图的体积vol(A )=工 d okix. gAzik由此得到了两种改进方法，即：Ratio-Cut和N-Cut，定义如下:k=1鬥 V* Cut (A , A ) k k .vol(A )k=1 kmin RatioCut(A , A，…，A )= min V Cut(行，A/41 )1 2 k .■‘min Ncut(A , A，…，A )= min1 2 k4.2 Ratio-Cut 目标函数求解4.2.1 基于二聚类问题推导求解方法同样从二聚类问题出发，推导 RatioCut 目标函数的求解方法设i42 )代入 f TLf 得2fTLf = 1 工Vw.. (f - f )1+ 一212wijVx eA , x eA ij2AIA丿=Cut (A, A)辺+門llA IAI=Cut (A, A)=|V>Cut (A, A)—IAI+1 Al+I Al+1A-1 + M IA丿=VpRatioCut (A, A)V |是数据集中数据点的个数，是个常数，因此另外，指示向量 f 还存在以下性质：⑴fTf ="f =工胃+Y罟=显i=1 x eA x eA |i i= |V| = n2)ii=1 x eAijA = 0，即fT・1二0, 1表示元素均为 1 的列向量。
式（44 ）是离散函数，无法求导，因此直接求解很困难如果令 f 可取任意实数，则 i可得到一个连续函数优化问题，即min f T LffT4 = 0 (。