美文网首页机器学习
13 聚类算法 - 谱聚类

13 聚类算法 - 谱聚类

作者: 白尔摩斯 | 来源:发表于2018-12-10 22:57 被阅读121次

    11 聚类算法 - 密度聚类 - DBSCAN、MDCA
    12 聚类算法 - 代码案例五 - 密度聚类(DBSCAN)算法案例

    十、谱聚类概述

    谱聚类是基于谱图理论基础上的一种聚类方法,与传统的聚类方法相比:具有在任意形状的样本空间上聚类并且收敛于全局最优解的优点

    通过对样本数据的拉普拉斯矩阵特征向量进行聚类,从而达到对样本数据进行聚类的目的;其本质是将聚类问题转换为图的最优划分问题,是一种点对聚类算法。

    谱聚类算法将数据集中的每个对象看做图的顶点V,将顶点间的相似度量化为相应顶点连接边E的权值w,这样就构成了一个基于相似度的无向加权图G(V,E),于是聚类问题就转换为图的划分问题。基于图的最优划分规则就是子图内的相似度最大,子图间的相似度最小

    谱聚类的构建过程主要包含以下几个步骤:
    1、构建表示对象相似度的矩阵W。
    2、构建度矩阵D(对角矩阵);
    3、构建拉普拉斯矩阵L。
    4、计算矩阵L的前k个特征值的特征向量(k个列向量);
    5、将k个列向量组成矩阵U。
    6、对矩阵U中的n行数据利用K-means或其它经典聚类算法进行聚类得出最终结果。


    拉普拉斯矩阵变形

    1、拉普拉斯矩阵

    2、对称拉普拉斯矩阵

    3、随机游走拉普拉斯矩阵


    谱聚类应用场景及面临的问题

    应用场景:

    图形聚类、计算机视觉、非凸球形数据聚类等。

    面临的问题:
    1、相似度矩阵的构建问题:业界一般使用高斯相似函数或者k近邻来作为相似度量,一般建议 使用k近邻的方式来计算相似度权值。
    2、聚类数目的给定。
    3、如何选择特征向量。
    4、如何提高谱聚类的执行效率。


    根据经验来说,谱聚类的分类效果还是比较好的,但前提还是得调参调得好。
    记住真言:无论模型有多好,只要参数调得不给力,神仙也救不了你。

    谱聚类推导 一 谱聚类推导 二 谱聚类推导 三 谱聚类推导 四

    看个例子:
    14 聚类算法 - 代码案例六- 谱聚类(SC)算法案例

    相关文章

      网友评论

        本文标题:13 聚类算法 - 谱聚类

        本文链接:https://www.haomeiwen.com/subject/mwjjhqtx.html