谱聚类算法的算法的新进展

发布网友发布时间：2022-05-03 10:03

共1个回答

热心网友时间：2023-10-20 12:17

Zha和Dhillon等人研究了基于二分图G=<X, Y, W>上的谱聚类，发现最小化目标函数可以等同于与二分图相关联的边权重矩阵的奇异值分解。
Meila和Shi将相似性解释为Markov链中的随机游动，分析了这种随机游动的概率转移矩阵P=DW的特征向量(W为相似度矩阵)，并且利用随机游动对Ncut进行了概率的解释，提出了基于随机游动的新的算法。同时，在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类方法，在图像分割中取得了很不错的效果。
Cu等人分析了核k-means的方法，发现最小化核k-means的目标函数等同于一个由数据向量组成的Gram矩阵的迹最大化问题。同时，迹最大化问题的松散解可以通过Gram矩阵的部分特征分解获得，首次用谱松散的方法获得核k-means的目标函数的全局最优解。Dhillon[29]在此基础上，又研究了加权核k-means的目标函数，将其与Ncut目标函数建立联系，提出了一个可以单调递减Ncut值的新颖的加权核k-means算法。
Ncut是一个很好的聚类目标函数。它的求解是一个NP难问题。传统的方法是宽松的谱松散方法。Xing与Jordan[分析了对Ncut的半正定规划(SDP)模型。根据该模型，对Ncut提出了一个比谱松散更紧的下限。同时指出了Ncut本身不能得到最优的聚类，但它可以通过不同的松散方法获得合理的聚类。
谱聚类方法不仅用于无监督学习中，也用于有约束的半监督学习中。Kamvar等人将PageRank[32]的随机游动模型运用到相似度矩阵中，根据已知样本的类别修正相似度矩阵。然后根据谱聚类算法获得聚类结果。Bach与Jordan则是根据一个基于已知划分与Ncut谱松散结果的误差，提出了新的目标函数，通过最小化新的目标函数推出新的谱聚类算法。
王玲，薄列峰，焦李成认为在聚类搜索过程中充分利用先验信息会显著提高聚类算法的性能，并分析了在聚类过程中仅利用成对*信息存在的不足，提出利用数据集本身固有空间一致性先验信息的具体方法。在经典的谱聚类算法中同时引入两类先验信息的基础上提出一种密度敏感的半监督谱聚类算法，两类先验信息在指导聚类搜索的过程中能够起到相辅相成的作用，使得算法相对于仅利用成对*信息的聚类算法在聚类性能上有了显著的提高。
王娜，李霞提出了一种基于监督信息特性的主动学习策略，找出同一类中距离相对较远的数据对象对和不同类中距离相对较近的数据对象对组成监督信息并将其引入谱聚类算法，构建新颖的主动半监督谱聚类算法，结果优于采用随机选取监督信息的谱聚类性能。

热心网友时间：2023-10-20 12:17