用于意外检测的几种图划分算法

在安保畛域，“图剖析”宽泛运行在账户买卖意外、不共事情关联等各种场景下。与其余机器学习算法类比拟，其特有的好处在于剖析方法合乎人的思想方式，剖析环节能直观地可视化。

举例来说，下图是把瀚思某客户企业中几类安保事情 ： 登陆、经常使用USB盘、检测到病毒、机器IP、 用户经常使用机器 - 综合到一同做关联剖析。

图中“边”代表出现过事情;点(机器、用户、IP、病毒、USB盘五类之一)的大小代表事情多少。一张图上咱们可以极速定位迸发次数最多的病毒、哪些用户违规经常使用同台机器、哪些机器经常使用过同一个USB盘。

下图是另一类例子，瀚思帮银行客户做的买卖意外剖析：点大小与出度成正比，色彩随着入度大小按蓝色⇒白色⇒白色方向变动。用金融术语来说：出渡过大的叫火山，入渡过大的叫黑洞。这类状况往往和坑骗洗钱关系。

但是，图一旦变大，剖析环节会变慢，须要剖析的边数量，即使最坏不会到全连通有向图中等于节点数N的N*(N-1)/2，也往往远大于N。而且可视化由于屏幕大小和易读性的限度，不宜再把不可胜数个节点和对应的边放到一张图上。

这种状况下，咱们驳回分而治之战略：应用实践阅历中图的社区性特色，把图宰割成若干个强联通的区域， 对每一个区域做剖析和可视化。

好的图划分算法在实践运行中要额外有三个特色：

1、高速度，***能并行化或许能用GPU减速。

2、能处置小环球网络特色(也就是节点度数呈肥尾散布)。

3、对参数不敏感。

很多算法无法满足2和3，教科书中算法大多是把图均分，而且假定知道图要分为多少类。

依据前文所述，瀚思应用“图计算”在实践运行中，协助客户处置了有关意外行为检测的上班。而本文将重点针对三类运行宽泛、效率较高并可以运行于意外检测的图划分算法启动详述。

谱划分

谱划分算法：它是最早用于处置图划分的一类算法，其思想起源于谱图划分通常。 矩阵的谱就是它的特色值和特色向量。 求图划分准绳的***解是一个NP难疑问。一个很好的求解方法是思考疑问的延续松弛方式，将原疑问转换成求解Laplacian 矩阵的谱合成， 因此将这类方法统称为谱划分。

假定将每个数据样本看作图中的顶点V，依据样本间的相似度将 顶点间的边 E 赋权重值，便可获取一个基于相似度的无向加权图 G=(V,E). 相似矩阵通罕用W 或 A 示意，有时也称为亲和矩阵(Affinity Matrix)， 往往是经过计算高斯核获取。

将相似度矩阵的每行元素相加，即获取对应点的度，以一切度值为对角元素导致的对角矩阵称为度矩阵，通常记为 D。定义好相似矩阵W及度矩阵D，便可得如下的Laplacian 矩阵：

依据不同的准绳函数及谱映射方法，谱划分算法开展了很多不同的详细成功方法，但都可以演绎为上方的三个关键步骤：

关于给定的图G=(V,E)，计算图的 Laplacian 矩阵L;

对L矩阵启动特色值合成，取其前 k 个特色值对应的特色向量，构建特色向量矩阵Q;

应用K-means算法或其余经典聚类算法对矩阵Q启动划分，每一行代表一个样本点, 即原图的顶点所属的类别.

上述步骤只是谱划分的一个框架，在详细成功中，还存在着不同的划分准绳，经常出现的有 Minimum Cut，Ratio Cut，NormalizedCut等。

谱划分算法，首先经过引入 Laplacian 矩阵，运用 Laplacian Eigenmap 启动降维，再对这些低维数据应用聚类算法启动划分，使得运算量大大较少.下图是用谱划分算法成功的成果图：

但谱划分算法也有一些无余之处：

1)构建特色向量矩阵Q无疑是该算法中最耗期间的， 在高维状况下, 不说求解特色向量就是求解特色值都十分艰巨;

2)须要借助先验常识定义递归中断条件，即不具有智能识别图类别总数的才干;

3)事实环球中的复杂网络图往往蕴含多个类，而递归的二分战略不能保障获取的划分是***的划分。

多层划分算法

第二类图划分算法，称为*多层划分(Multilevel Partitioning，1995，Karypis)*。

以高效及运算期间快著称，比谱划分算法快10%-50%， 计算千万数级的图，期间基本是以秒计算。其关键成功步骤通常分为图的 粗化阶段(Coarseningphase), 初始划分阶段(Initial partitioning phase)和细化阶段 (Uncoarsening phase)三个阶段。

简言之，如下图所示，该算法就是将原始图经粗化阶段一层一层紧缩变“小”，获取顶点数目足够小的图，再将这个数目足够小的图经过初始划分阶段和细化阶段一层一层恢复变“大”，直到恢复成原始图，成功划分。

粗化阶段关键是为了缩小原始图的复杂性，构建图的多级档次. 它对原始图的点和边启动紧缩兼并， 结构了一个档次化的较小的图序列,最终将原始图紧缩成一个顶点数目足够小的图。 这种紧缩的思想(详见下图)可以方式化地定义为婚配 (Matching)，图的婚配是指边的汇合，其中恣意两条边都没有公共顶点。 在一个图的一切婚配中，所含婚配边数最多的婚配，称为这个图的***婚配.

在整个粗化阶段，原始图的一切点以及权重都会累计，最终反响在最小规模图。将最小规模图启动便捷的划分，称为初始划分阶段，该阶段由于结点数目较少，运算十分快，基本不耗时。也不是多层算法的中心部分，其算法与接上去的细化阶段算法咨询比拟相似，这里不再赘述.

细化阶段，也可称为图的恢复提升阶段，该阶段依照粗化档次一层一层将图恢复成原始图，并在恢复环节中应用某些精细的算法逐层提升，直到获取对原始图的划分.

这其中的经常出现的划分算法有谱二分法算法有Spectral Bisection(SB)，Graph Growing Algorithm(GGP),Greedy Refinement(GR)， Kernighan-Lin Refinement(KLR)等，其中比拟驰名的是Kernighan-Lin划分算法。

*Kernighan-Lin划分算法*，简称KL算法，由Kernighan和Lin在1970年提出，是一个部分搜查提升算法,提升的指标函数是衔接不同类的边权之和最小。

举个便捷的例子，如下图，紫色的点属于一类，彩色的点属于一类，KL算法是成功将下图(a)转换成下图(b)的环节。

如何成功将紫色类别中的点和彩色类别中的点启动替换，则是经过计算不同类别损失权重的差值来判别的，即替换前的内外权重差(如下图(a)的数字所示)减去替换后的内外权重的值。当且仅当该值为正启动替换，否则拒绝替换。 重复以上步骤，直至该值为负。

KL算法，较易了解，但获取的解往往是部分***。下图，是应用多层划分算法启动图划分的例子：

多层划分算法***的局限在于它***的局限性在于须要先验常识来发生一个较好的初始类。

***谈谈，Markov Cluster Algorithm(2000, Stijn van Dongen), 简称MCL算法，是一种极速可裁减的无监视图形聚类算法，有时也可以用于图的划分，其思想十分便捷，关键是基于 随机游走(Random walk) 和马尔科夫链 (Markov chain)。先便捷说一下这两个概念.

随机游走说的是，假设咱们从图中的某一个点开局“瞎转”，那么很或许就会在某一个子图外面转悠，而不是在子图间来回游荡. 而随机游走的计算是经过Markov链来成功的. Markov链指的是一个随机序列，该序列满足“无后效性”，即 未来的形态只依赖形态，而与过去的形态有关。

MCL算法的关键思想就是：”随机遨游者到达浓密的类后，不会随便的分开该类”. 前者是随机游走的环节，后者依据是 Markov链的“无后效性”。MCL算法中随机遨游的环节，其实是一个不时修正转移概率矩阵的环节，该环节 重复口头裁减(Expansion)和收缩(Inflation)两个操作。

裁减就是前面提到的马尔科夫链的转移矩阵的极限散布， 这个步骤不时地对转移概率矩阵启动自乘直到它不再扭转为止。目的是衔接图的不同区域。收缩是对每一个元素启动幂操作，再将每一列归一化，目的是为了强街坊的衔接更强，弱街坊的衔接更弱，也就是让转移矩阵中概率大的概率更大，而小的更小。这两个操作重复口头不时到概率转移矩阵收敛为止，获取最终的矩阵，依据最终的矩阵便可得结果。

MCL算法对无权图及有权图均试用，划分的子图个数无需事前设定，这是该算法的 ***好处; 划分的子图是非平均的，试用于长尾散布的数据。 下图就是应用 MCL启动图划分的结果：

但是MCL算法对图的直径较大的状况不实用. (直径是指两个点之间的距离***值，距离是两个点之间的一切路的长度的最小值)