大家好，又见面了，我是你们的朋友全栈君。

http://blog.csdn.net/pipisorry/article/details/49052255

海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之社交网络之社区检测：高级技巧-线性代数方法

{这篇博客的内容：使用linear algebra的概念来解释如何 break graphs optimally (i.e., break the fewest edges) into disjoint “communities.”}

Note: 高级方法不需要用户指定社区个数，算法自动学习出来，有点类似聚类检测。

聚类检测

Networks & Communities

图中有三个clusters，并且有些clusters还可以继续划分成小clusters(hierarchical structure)。

图聚类的目的和应用

Goal : Find densely linked clusters.
示例：下面的邻接矩阵中的点表示用户查询一个词，广告投放者是否投放广告。从中检测微市场。

应用一

Note: 这些advertiser和query的坐标都是经过某种排序才可以发现这些特定的clusters。

应用二：社交网络中发现社交圈/社区find social communities, or call them social circles
皮皮blog

 

 

聚类检测方法1：图聚类划分conductance score

{怎么聚类，首先要定义什么是好的聚类。需要说明的是，下面这个划分准则并不是最好的，这个划分准则对应的算法是N-P难的问题}

划分任务好坏的直觉

首先给定一个图G，要对其进行划分

图切割和cut score

将cluster质量表示成一个cut函数，cut就是边的一点节点在聚类中，另一个不在。

这样我们的目标是找到一个相当容易被切割的nodes集合，但是这样会出现总是找到uninteresting degenerate solutions(无趣的退化解)。

根本原因是没有考虑内部nodes的连接。

图划分准则：传导conductance score

所以这里就加入一个分母，使划分尽量均匀。

Φ(A)公式解读：

1 分子其实就是cut(A)，对应external cluster connections。

2 分母则是集合A的容量volume，是至少有一条边在A中的边的权重和，也就是A中节点度的和（实际上是看成了有向边来计算的）。取min是因为if I have set a to be very big, then the volume of A can kind of overpower the whole thing.所以假定A的大小小于整个图的一半。

3 pi(A)计算的值越小，那么找到的cluster越好。

优点：某种程度上生成的pieces clusters在大小上是可比的。

但是。。。，怎么查找要cut的边呢？这是一个NP难问题，所以就有了谱图划分。

皮皮blog

 

 

聚类检测方法2：谱图划分spectral graph partitioning

{通常的算法里面，“谱”主要指 Laplacian matrix 的应用，具体物理意义应该是反映了图中各种节点之间的某种内在的连接信息。

lz: 矩阵理论中，“谱”是矩阵A所以特征值λ的集合。}

图的最优划分是一个NP难问题，需要寻找另一种解决思路——谱图划分。

谱图理论

Note: n就是networks中的nodes数目。可知yi是节点i所有邻居的权重和。

谱图理论Spectral graph theory

谱图划分示例

lz觉得这主要是说明d是邻接矩阵的谱吧。

示例一：d-regular graph

证明一个全1向量是矩阵A的特征向量（假定G中所有点都有相同的度d），这样就得到一个特征对。

示例二：Graph on 2 components

d-regular graph不是连通的情况， 2-regular graph。证明图不连通（或者勉强连接）时，特征值为d对应多个不同的特征向量。

直觉上，图G勉强连接和图分离的特征向量不会改变太多，基本一样。if our graph is disconnected, we already know what the eigenvectors will be.If the graph will be barely connected,the eigenvectors, we hope,won’t change too much.

图的拉普拉斯矩阵的表示

邻接矩阵Adjacency Matrix A的定义

1. 实对称矩阵A的不同特征值所对应的特征向量是正交的。[矩阵论、组合数学基础] 向量正交就是任意两个向量点积为0。

2. 矩阵A所有元素相加和为图中所有边数*2。

度矩阵Degree Matrix D的定义

图的拉普拉斯矩阵Laplacian Matrix L的定义和性质

 

 

拉普拉斯矩阵 的性质

  

 
，

[图的拉普拉斯矩阵(Graph Laplacians)]

 

使用拉普拉斯矩阵进行图的划分

{通过拉普拉斯矩阵的特征值和特征向量寻找能将图划分成两个的最优划分：这里要解决的是怎样将图的划分问题转化为下面定义的λ2的最小化问题。

注意这里的x是点的标志labeling(是一个称作Fiedler vector的向量)，也就是拉普拉斯矩阵L的次小特征值对应的特征向量。这个次小特征值和特征向量有下面讲到的神奇性质。}

L矩阵的次小特征值second smallest eigenvalue

注意，对拉普拉斯矩阵进行特征分解就可以得到其特征值和对应的特征向量。

Note:

1. 等式推导中第3个等号的解释：因为D是一个对角矩阵故第一项是对角元素相关的式子。而第二项实际是xTAx，所有xixj的二次项的和，即是所有可能边xixj的和的两倍，其实也就是矩阵A所有元素之和。

2. 等式推导中第4个等号解释：所有点的出度和等于所有边对应的点数和的和，也就是有多少个出度xi^2就会加和多少次，等价于所有条边(i, j)对应的两个点xi^2+xj^2的和的和。for every node we have to take its squared value entry,and then sum it up together D times.What this basically means is that we can take the squared value, and sum it up once for every edge.

3 右边最小值为什么是L的次小特征值？一个直觉的解释是，L的性质中知道，L的最小特征值为0，而其它特征值都>0。λx’x = x’Mx可知λ是M的特征值，要取最小又不为0只能是次小特征值了。

次小特征值对应的特征向量x的性质

构造次小特征值表达式

拉普拉斯矩阵次小特征值在图上的性质。

如果我们对每个节点设置一个标志labeling，使这些标志和为0，并且这些标志的平方和为1。这样λ2的最小化就变成了有边节点标志的差的平方和（分子）的最小化问题了。

Note: 分母的值为1。

分子最小化时，就是说有边连接的两个节点就放在0的同一侧（同时为正或者同时为负，否则λ不可能最小），即让通过原点0的边尽可能少，同时让同一侧的边尽可能多。其目的就是将两个clusters的划分转化为求次小特征值及其对应的特征向量问题。

可知，图最优划分时（式右），刚好节点的聚类取值是拉普拉斯矩阵M的次小特征值λ2对应的特征向量x。

回到寻找最优划分问题

Fieldler’1973

首先如果我们只是将每个节点赋予标志+1或者-1，通过最小化f(y)，并不能解决问题。

瑞利定理Rayleigh Theorem

这里对节点标志重新赋值成实数值，并使其节点和为0，平方和为1，minf(y)也就成了上面提到的次小特征值了。

故f(y)的最小值对应于找到一个Fiedler vector向量（就是拉普拉斯矩阵L的次小特征值λ2对应的特征向量）对节点的标志进行赋值，就能通过最小化∑(yi – yj)^2来得到f(y)的最小值。这样Fiedler vector（拉普拉斯矩阵L的次小特征值lambda2对应的特征向量）也就告诉我们哪些点被放到同一个cluster中，哪些放到另一个cluster中。

谱聚类算法Spectral Clustering三大步骤

第一步：通过图G计算矩阵A,D， D – A => L.

第二步：求次小特征值lambda2和其对应的特征向量x，然后根据x对所有节点赋标志值（x的第i个value对应第i个node,value>0属于类0，>=0属于类1。如下图示例）。In particular, we are interested in the second smallest eigenvalue lambda 2 and the corresponding eigenvector x.

第三步：最后通过x得到一个划分（如通过0进行划分），得到的分类也就是clusters。once we have the vector x,all we have to do is to do the grouping where we basically look at the components of x.And determine which nodes belong to the set A, and which nodes belong to the set B.这里的cluster A B也就是划分后0的左右侧节点集合。

谱划分算法步骤示例

Note: 这里对lambda排序时，特征向量也跟着排序了，但是每个节点对应的特征向量中的值是没有改变的，也不用排序。

 

谱划分示例

求解2个clusters问题图解：拉普拉斯矩阵L的次小特征值λ2对应的特征向量x2。

求解4个clusters问题图解：拉普拉斯矩阵L的次小特征值λ2对应的特征向量x2。

下面x1是拉普拉斯矩阵L的最小特征值λ1对应的特征向量（可以看到都是相等的，根本无法区分），x3拉普拉斯矩阵L的第三小特征值λ3对应的特征向量

k路谱聚类(将图G划分为k个clusters)

第二种方法就是将计算拉普拉斯矩阵L的2～k+1小的特征值和其对应的特征向量，并通过这多个特征向量将图中每个节点reduce到一个坐标向量中（而不是一个点），之后再通过k-means等聚类算法对这些reduced后的节点进行聚类，就得到k个类了。

[谱聚类(spectral clustering)]

[谱聚类算法(Spectral Clustering)]

[从拉普拉斯矩阵说到谱聚类 ]

[A Tutorial on Spectral Clustering：http://engr.case.edu/ray_soumya/mlrg/Luxburg07_tutorial_spectral_clustering.pdf]

皮皮blog

 

 

聚类检测方法3：Trawling

{这种方法可以检测多种类型非常不同的clusters}

Trawling

Note: 这种想法来源于hubs and authorities。红点是hubs，蓝点是authorities。提前说明一下，这里的红点其实就是图G中所有的节点，蓝点是节点指向的其它节点且这些节点是一种频繁项集。

我们的目标就是要找到这种dense 2-layer graph，其代表的含义就是同类的人讨论同样的话题。

更形式化要解决问题的定义

完全二分图：左图每个点都有边指向右图所有点。

目标改为枚举所有完全二分子图。每个不同的完全二分子图应该也说要找的不同的clusters吧？

 

频繁项集和二分图

{解决上面的枚举所有完全二分子图问题}

频繁项集挖掘描述

[Agrawal-Srikant ‘99]

[海量数据挖掘MMDS week2: Association Rules关联规则与频繁项集挖掘]

频繁项集和二分图之间的联系

[Kumar et al. ‘99]

红点就是图G中所有的节点，蓝点是节点指向的其它节点且这些节点的出现是一种频繁项集。

1）将图G中每个点看成是一个basket，它指向的节点就是basket中的items，然后设置最小支持度和项集大小。

2）如果发现了一个频繁项集就意味着：

3）这也就代表我们发现了一个完全二分子图

算法示例

这里找到的两个完全二子分图就是我们找到的两个clusters？

皮皮blog

 

 

Reviews复习

通过谱图划分算法计算得到

拉普拉斯矩阵L =
[[ 2. -1. -1.  0.  0.  0.]
 [-1.  3.  0. -1.  0. -1.]
 [-1.  0.  2. -1.  0.  0.]
 [ 0. -1. -1.  3. -1.  0.]
 [ 0.  0.  0. -1.  2. -1.]
 [ 0. -1.  0.  0. -1.  2.]]
次小特征值对应特征向量

x2 = [-0.5 -0.  -0.5  0.   0.5  0.5]

划分

[2 4 5 6]
[1 2 3 4]

可知，点2，4都是ties，由随机概率可能是两个clusters中的任意一个。但是56或者13只能是同一clusters中。

Code:

 

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
__title__ = '谱图划分'
__author__ = '皮'
__mtime__ = '10/16/2015-016'
__email__ = 'pipisorry@126.com'

"""
import math
import numpy as np
from scipy import linalg
import matplotlib.pyplot as plt
from Utility.Contant import eps
from Utility.PrintOptions import printoptions

G = {'V': [0, 1, 2, 3, 4, 5], 'E': [(0, 1), (0, 2), (1, 3), (2, 3), (1, 5), (3, 4), (4, 5)]}


# G = {'V': [0, 1, 2, 3, 4, 5], 'E': [(0, 1), (0, 2), (0, 4), (2, 3), (1, 2), (3, 4), (3, 5), (4, 5)]}


def BuildLaplacian(G):
    '''
    通过图G构造拉普拉斯矩阵L
    '''
    V = G['V']
    E = G['E']
    A = np.zeros([len(V), len(V)])
    for s_nodeid, e_nodeid in E:
        A[s_nodeid, e_nodeid] = A[e_nodeid, s_nodeid] = 1
    D = np.diag(np.sum(A, 1))
    L = D - A
    return L


def EigenCalculate(L):
    '''
    拉普拉斯矩阵L的特征值和特征向量计算
    '''
    eigen_value, eigen_vec = linalg.eig(L)  # eigen_vec的列i对应于第i个特征值
    eigen_vec = eigen_vec.T  # 转换为eigen_vec的行i对应于第i个特征值

    sort_index = np.argsort(eigen_value)
    return eigen_value[sort_index], eigen_vec[sort_index]


def PlotEigenvalue(Y, spliting_point=0, vertice_strat_index=1):
    '''
    绘制特征向量的值分布
    '''
    x_min, x_max = vertice_strat_index, len(Y) + vertice_strat_index - 1
    y_min, y_max = min(Y), max(Y)
    margin = [1, 0.1]
    X = range(vertice_strat_index, len(Y) + vertice_strat_index)
    plt.plot(X, Y, 'r-o', label='')
    plt.axhline(spliting_point)

    # 设置图形展示效果
    def setAx(x_min, x_max, y_min, y_max, margin):
        plt.xlim(x_min - margin[0], x_max + margin[0])
        plt.ylim(y_min - margin[1], y_max + margin[1])
        plt.xlabel('Rank in x2')
        plt.ylabel('Values of x2')
        plt.legend(loc='lower right')
        plt.title('Components of x2')

    setAx(x_min, x_max, y_min, y_max, margin)

    plt.show(block=True)


if __name__ == '__main__':
    V = np.array(G['V']) + 1
    L = BuildLaplacian(G)
    print('L = \n%s' % L)
    eigen_value, eigen_vec = EigenCalculate(L)

    x2 = eigen_vec[1]
    with printoptions(precision=1, suppress=True):
        print('x2 = %s' % x2)
    print(V[(x2 + eps) >= np.mean(x2)])
    print(V[(x2 - eps) <= np.mean(x2)])
    PlotEigenvalue(x2)

from:http://blog.csdn.net/pipisorry/article/details/49052255

ref:社区发现算法FastUnfolding的GraphX实现