← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 5443

社交图对称化决定相似关系

理解等级:中级

书中谱聚类采用非负对称相似图,需要先把关注、转发等有向互动按规则转为无向边。对称化会丢失部分方向信息,规则决定“关系紧密”的含义。该前提属于这里使用的标准对称谱方法,不能推广为所有谱分析都无法处理有向图;聚类输出也不直接等于现实社群真值。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 机器学习:分布式算法 · 查看原书依据

      图16-9展示了使用谱聚类解决微博环境下社交圈挖掘问题的流程示意图。首先我们获得用户之间的互动数据,由于谱聚类只能处理无向图,而用户之间的互动数据是有向的,所以首先根据一定规则将有向图转换为无向图,之后就形成了所有用户的无向相似性图。根据谱聚类算法要求,将这个相似性图对应的对称矩阵转换为拉普拉斯矩阵,然后对这个矩阵求其前k 个最小特征值及其对应的特征向量,求解得到前k 个特征值及其对应特征向量s 1 ,s 2 ,…sk 组成矩阵S [n ][k ](n 为用户编号,k 为低维特征编号),这样就将一个原本是n ×n 的矩阵转换为小得多的n ×k 矩阵,对矩阵S 按行进行K-means聚类,每一行对应相似图中的一个用户节点,其最终聚类结果就是谱聚类最终的输出结果。这样即可将社交关系密切的用户群体挖掘出来。

    参考来源

    - 位置:《大数据日知录:架构与算法》第16章《机器学习:分布式算法》,原文段落130,OEBPS/text00021.html。 - 结论依据:原书给出的机制、公式或算法与其适用范围;实验百分比和2014年系统状态不当作当前普遍保证。 - 原始内容:图16-9展示了使用谱聚类解决微博环境下社交圈挖掘问题的流程示意图。首先我们获得用户之间的互动数据,由于谱聚类只能处理无向图,而用户之间的互动数据是有向的,所以首先根据一定规则将有向图转换为无向图,之后就形成了所有用户的无向相似性图。根据谱聚类算法要求,将这个相似性图对应的对称矩阵转换为拉普拉斯矩阵,然后对这个矩阵求其前k 个最小特征值及其对应的特征向量,求解得到前k 个特征值及其对应特征向量s 1 ,s 2 ,…sk 组成矩阵S [n ][k ](n 为用户编号,k 为低维特征编号),这样就将一个原本是n ×n 的矩阵转换为小得多的n ×k 矩阵,对矩阵S 按行进行K-means聚类,每一行对应相似图中的一个用户节点,其最终聚类结果就是谱聚类最终的输出结果。这样即可将社交关系密切的用户群体挖掘出来。