一种基于自适应相似矩阵的谱聚类算法(2)
【作者】网站采编
【关键词】
【摘要】2 基于测地距离和密度的自适应谱聚类算法 2.1 测地距离 在构建相似度测度时,距离函数占着至关重要的地位,没有任何一种距离测度适合所有的数据集。
2 基于测地距离和密度的自适应谱聚类算法
2.1 测地距离
在构建相似度测度时,距离函数占着至关重要的地位,没有任何一种距离测度适合所有的数据集。传统的欧式距离做测度度量时,只是单纯的计算连接两点的直线段的长度,如图2 a),如若这两点间存在障碍物或者说存在另一个结构中的样本,此时的欧式距离是没有实际意义的,这就是欧氏距离的局限性,图2 b)是要得到的真实距离效果。越来越多的文献都在做距离测度方法的改进,文献[11]提出用有效距离函数代替传统的地理距离函数,刻画了目标样本和其他所有数据样本之间的距离信息,具有全局特性。文献[12]提出一种基于电阻距离的中文文本谱聚类算法,把文本表示成二分图形式,使用电阻值表示两点间的相似度值,电阻值随着节点间路径减小而减小,从而计算出任意节点间的有效电阻距离更具有实际意义。
图2 欧氏距离和真实距离的对比图Fig.2 Comparison of Euclidean distance and real distance
测地距离是数学形态学中的一个重要概念,最早是TENENBAUM等[13]在研究非线性降维时提出的,能很好地表示流形结构上样本之间的真实距离。如图3中的点A,B,C位于同一流形结构上,dAB,dAC,dBC分别表示点A和点B,点A和点C,点B和点C之间的欧式距离,gAC,gBC分别表示点A和点C,点B和点C之间的测地距离,假设点A和点B之间存在障碍物不能直接计算欧式距离,在同一结构中,从点A到达点B的路径有很多条,最短的一条测地弧的长度称为点A和点B间的测地距离。由图3可以看出,当A,C两点非常近时,取gAC≈dAC,即认为A,C两点间的测地距离近似等于其欧氏距离。而当A,B两点之间相距较远时,则取两点间的测地距离等于其近邻点间的测地距离累加和,即gAB=gAC+gCB≈dAC+dCB,从而得到待聚类数据集中每对数据点之间的实际最短距离。
图3 测地距离示例Fig.3 Sample geodesic distance
测地距离具体算法如下。
1)输入数据集X=[x1,x2,…,xi,…,xn],根据欧式距离计算点xi的k个近邻。
2)初始化测地距离:
dG(xi,xj)=
其中d(xi,xj)表示的是点xi和点xj之间的欧氏距离。
3)计算任意两点间最短路径:
For m=1:n
dG(xi,xj)= min{dG(xi,xj),
dG(xi,xm)+dG(xm,xj)}
End
2.2 密度
仅用距离来描述数据之间的相似性远远不够,特别是对密度分布不均的数据集,好的相似性度量不仅不依赖于尺度参数σ,而且能够根据每个点所处邻域的稠密程度得到正确的聚类结果。JARVIS等[14]曾提出一种基于共享近邻相似度测量方法的聚类,本研究借鉴其中的共享近邻的定义来表征两点间的局部密度,进而影响两点间的相似度。共享近邻的定义如下。
定义1 数据集X={x1,x2,…,xn}中任意两点xi和xj的共享近邻定义为
其中n(xi)表示离点xi距离最近的前p个点,n(xj)表示离点xj距离最近的前p个点。一般地,参数p=20,本研究取数据集中样本点数的5%。
2.3 所提算法
谱聚类算法是依托谱图划分理论发展起来的,能在任意形状的样本空间上得到全局最优解。其主要核心是对特征向量的聚类,而特征向量是由样本数据的相似矩阵特征分解得到的,构建一个性能优越的相似矩阵至关重要。本研究构建了一种自适应的相似矩阵,首先选用测地距离函数表征数据间的距离度量,相距较近的两点间的距离近似于欧式度量,相距较远的两点间的距离则是通过最近邻点间的欧式度量叠加得到的,这样得到的距离度量克服了欧式距离的局限性,实际意义较明显。然后根据每个点所处邻域的稠密程度,用两点间的共享近邻数表征其密度,进而得到待聚类数据点的基于测地距离和共享近邻数的相似度,构建对应的相似矩阵,对其特征分解后得到的特征向量进行聚类。算法流程如下。
输入:待聚类数据集X={x1,x2,…,xn},聚类个数k,共享近邻数p;
1)根据2.1节计算数据集X={x1,x2,…,xn}中数据点之间的测地距离dG(xi,xj);
2)根据定义1计算任意两点xi和xj的前p个共同近邻数SNN(xi,xj);
3)计算基于测地距离和共享近邻的数据点之间的相似度,构造相应的相似矩阵W=[wij]n×n,其中:
式中σi和σj分别表示点xi和xj到各自第l个近邻的欧式距离,参见文献[15],建议l=7。
文章来源:《应用数学和力学》 网址: http://www.yysxhlx.cn/qikandaodu/2021/0311/385.html