精华内容
下载资源
问答
  • 提出了一种基于层次聚类(HCCG)的复杂网络粗粒度方法。 通过使用层次聚类方法对网络节点进行分组,然后更新聚类之间边缘的权重以提取粗粒度网络。 在几个典型的复杂网络上进行的大量仿真实验表明,HCCG方法可以...
  • 复杂网络中基于层次聚类的粗粒度方法
  • 基于层次聚类复杂网络社区检测方法
  • 传统层次聚类算法在复杂网络社区挖掘过程中,需要计算所有顶点对之间的相似度。针对这一缺点,在详述了常见相似度计算方法和顶点重要性度量方法的基础上,将ego角色的探测过程引入层次聚类算法,而后只计算其他顶点...
  • 一种基于层次聚类复杂网络社区划分算法,朱帅兵,殷传涛,随着互联网的发展和普及,人们对复杂网络的研究越来越多。复杂网络中存在社区结构,而找出社区结构有助于挖掘复杂网络中一些有用
  • 复杂网络聚类算法总结

    千次阅读 2019-03-15 18:18:50
    20世纪60年代,两位匈牙利数学家Erdos和Renyi建立了随机图理论,被公认为是在数学上开创了复杂网络理论的系统性研究。之后的40年里,人们一直讲随机图理论作为复杂网络研究的基本理论。然而,绝大多数的实际网络并...

     

    网络,数学上称为图,最早研究始于1736年欧拉的哥尼斯堡七桥问题,但是之后关于图的研究发展缓慢,直到1936年,才有了第一本关于图论研究的著作。20世纪60年代,两位匈牙利数学家Erdos和Renyi建立了随机图理论,被公认为是在数学上开创了复杂网络理论的系统性研究。之后的40年里,人们一直讲随机图理论作为复杂网络研究的基本理论。然而,绝大多数的实际网络并不是完全随机的。1998年,Watts及其导师Strogatz在Nature上的文章《Collective Dynamics of Small-world Networks》揭示了复杂网络的小世界性质。随后,1999年,Barabasi及其博士生Albert在Science上的文章《Emergence of Scaling in Random Networks》又揭示了复杂网络的无标度性质(度分布为幂律分布),从此开启了复杂网络研究的新纪元。
            随着研究的深入,越来越多关于复杂网络的性质被发掘出来,其中很重要的一项研究是2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological networks》,指出复杂网络中普遍存在着聚类特性,每一个类称之为一个社团(community),并提出了一个发现这些社团的算法。从此,热门对复杂网络中的社团发现问题进行了大量研究,产生了大量的算法,本文试图简单整理一下复杂网络中聚类算法,希望对希望快速了解这一部分的人有所帮助。本文中所谓的社团跟通常我们将的聚类算法中类(cluster)的概念是一致的。

    0. 预备知识

            为了本文的完整性,我们首先给出一些基本概念。
            一个图通常表示为G=(V,E),其中V表示点集合,E表示边集合,通常我们用n表示图的节点数,m表示边数。一个图中,与一个点的相关联的边的数量称为该点的度。对于一个图,图中所有点的度的和恰好等于边数的两倍。图通常用邻接矩阵A表示,邻接矩阵的(i,j)位置元素是1表示点i到点j右边,0表示无边。
            本文中我们会用到随机图的概念,所谓随机图,就是指一个图中任何两个点之间连边的概率相等。首先确定n个点,然后以固定概率p去给图中的一对顶点连边,就形成了一个随机图。在研究中,随机图通常用来作为一个null model来与实际网络进行比较,从而得出一些性质结论。
            研究社团的划分,一个需要解决的问题是,如何来衡量一个社团的划分的好坏?一个比较简单直观的原则是使得社区内部的边尽可能地多,社区之间的边间可能地少。另外一个稍微复杂点但是更为常用的度量是Newman等人提出的模块度(modularity)的概念,基本的想法是这样的:我们假设在随机图中是不存在这种社团结构的,将实际网络跟其相应的随机网络进行比较,如果一个网络跟随机网络之间的差异越大,表示社团结构越明显。这样,我们对划分后的每一个子网络计算一个“密度”,然后计算该子网络随机情况下的“密度”,这两个“密度”存在一个差值,表示了该子网络偏离随机情况的一种程度,并且这个值越大表示这个子网络相对随机网络越稠密。一个网络中包含的所有子网络的这个差值加到一起的和就是这个复杂网络的模块度,数学公式表示如下:
            1
    其中Aij表示图的邻接矩阵,ki 表示点i 的度,m是图的边数,ki*kj/2m表示点 i 和点 j之间边的期望。进一步将模块度可以化为等式右边的形式,nc是社团的总个数,lc是社团c内的边数,dc是社团内的点的度数之和 (note: 社团内的每一个点可能跟本社团内部的点有边,也可能有跟其他社团点连边,故通常 dc> lc)

    有了这些知识,我们来看一下复杂网络社团划分的各种算法吧。

    1. 图的剖分

            把一个网络划分成多个社团就是把一个图剖分成多个图,图的剖分问题是图论中一个比较难的问题,也是研究比较多的问题,理论上是NP-hard的。因此,人们通常研究比较简单的情况:图的二剖分,即把一个图分成两个(一般要求大小相等)的图,比较有名的算法是Kernighan-Lin 算法和谱平分法。

    1.1 Kernighan-Lin 算法[1]

    思想:不断交换两个子图中的点,使得两个子图之间的边尽可能地少
    定义增益函数: Q=两个社团内的边数-社团之间的边数
    算法步骤:
    Step1 随机划分为已知大小的两个社团
    Step2 从两个社团各取一个点,尝试交换并计算ΔQ = Q交换后-Q交换前,选择使ΔQ最大的一对节点对交换
    Step3 规定每个节点只能交换一次,对剩余节点重复step2, 直到 ΔQ <0,或者某个子图的所有节点都被交换了一次为止。
    Step4 允许每个节点的第二次交换,开始新一轮迭代,直到没有节点对可以交换

    1.2 谱平分法

            所谓“谱”,就是矩阵的特征值;所谓“平分”,就是将一个图分成大小相等的两个子图。谱平分法就是利用图的拉普拉斯矩阵的第二小特征向量来进行聚类的一种方法。 这里暂且先放一下,下面介绍完谱算法之后再回头具体介绍谱平分法。

    1.3 总结

            图的剖分常常需要制定子图的个数(否则,整体作为一个),甚至每个子图的大小(否则,常常会将一个点分为一个子图)。但是如果已知一个图就是两个社团组成,谱评分法往往可以得到很好的效果。

    2. 凝聚法

            这是一大类算法,总体思想是寻找社团“最中心”的边,不断地把最相似的两个点聚到一起,从点聚到小社团,再聚成大社团。根据定义两个点的相似性的不同,产生了很多不同的算法。有的算法并不直接计算相似性,而是看两个点合并到一起后模块度的变化情况,根据变化的大小来选择需要合并的两个点。比较有代表性的算法是Newman在2004年的一个算法[2]

    2.1 Newman算法

    思想:不断地选择是模块度增长最大的两个社团进行合并
    算法步骤:
    Step1. 每个点当作一个社团
    Step2. 计算两个社团合并后模块度的变化(增长) ΔQ,选取使得ΔQ最大的两个社团进行合并 
    Step3. 重复step2直到最后合并为一个社团

    2.2 Newman算法的优化

    Newman算法复杂性是O((m+n)n),Clause,Newman和Moore利用最大堆将该算法复杂度降低为O(n(logn)^2)[3]
    对于该算法, 人们想出了很多改进措施,例如以下两个策略: 
    1. multistep贪婪算法:每次迭代合并多个社团
    2. 归一化ΔQ,消除社团大小的影响

    2.3 总结

            凝聚法优点是简单,限制少,不需要预先指定社团个数,可以发现社团的层次关系。缺点是缺乏全局目标函数; 两个点一旦合并,就永远在一个社团中了,无法撤消;另外,这种算法往往对单个的点比较敏感

    3. 分裂法

            分裂法的基本思想是找出最有可能位于社团之间的边,把这些边去掉,就自然产生了不同的社团。代表性的算法是Girvan 和Newman在2002年的一个算法 [4].

    3.1 GN 算法[4]

    首先给出介数(etweenness)的定义,一个边的介数(edge betweenness)是指通过该边的最短路的条数。
    直观上,社团之间的边有较高的betweenness,而社团内部的边betweenness相对较小,这样,通过逐个去掉这些高betweenness的边,社团结构就会逐步显现出来。
    算法步骤:
    Step1. 计算每条边的介数 (O(nm) with BFS)
    Step2. 去掉具有最高介数的边
    Step3. 如果满足了社团划分的要求, stop; 否则, 转step1.

    利用各种其他度量(如边聚类系数等)来代替边介数,该算法也产生了各种各样的变种。

    3.2 其他分裂方法

            分裂法还有很多,如MST,JP算法等等,在此就不一一描述了。

    3.3 总结

            凝聚法跟分裂法是对应的,一个自下而上,一个自上而下,一个不断把点连在一起,一个不断去边把点分开。分裂法的优缺点跟凝聚法类似。

    4. 谱算法

            首先给出一个概念——图的Laplacian 矩阵(L-矩阵)。设A为图的邻接矩阵; D为一个对角阵(对角元素为点 i 的度),则图的Laplacian矩阵L=D-A。关于L-矩阵,有很多性质,如:(1) 矩阵的每一行的元素之和为0 ,由此可以知道该矩阵至少一个0特征值,并且0特征值对应的特征向量为全1向量(1,1,...,1)。(2)0 特征向量的个数与连通分支的个数相同;如果一个图是连通的,那么其Laplacian矩阵只有一个0特征值,其余特征值都是正的。(3)不同特征值的特征向量正交的。
    所谓谱,就是指矩阵的特征值。谱算法就是利用邻接矩阵或者拉普拉斯矩阵的特征向量,将点投影到一个新的空间,在新的空间用传统的聚类方法(如k-means)来聚类。

    谱算法的一般步骤是:
    Step1. 计算相似矩阵(如邻接矩阵A)的前 s 个特征向量 
    Step2. 令 U 是一个 n× s 矩阵,每一列是一个特征向量 
    Step3. U 的第 i 行作为点 i 的坐标,用层次聚类法或者k-means等得到最终的社团
    需要说明一点是: 如果是计算邻接矩阵的特征值,一般取最大的s个特征值;如果是计算Laplacian矩阵的特征值,则是计算最小的(除0外)s个特征值。

            前面我们提到过谱平分法,就是利用Laplacian矩阵倒数第二个小的特征值对应的特征向量(称为Fiedler 向量)来聚类的。因为需要把一个图平分成两个子图,因此就把Fiedler向量中正的分量对应的点分成一类,负的分量对应的点分成另一类。

            谱算法的计算瓶颈是计算矩阵的特征值,因为少数的几个特征向量就可以得到很好的聚类,所以只需要计算最大的几个特征值既可以,可以考虑用Lanczos method。

    5. 矩阵分解

            谱算法的实质是矩阵分解,其他的矩阵分解方法还有SVD 和 NMF 等,矩阵分解的整体思想就是把点从一个空间映射到另一个空间,在新的空间利用传统的聚类方法来聚类。

    6. 标签传播算法

            标签传播(Label propagation)算法是由Zhu X J于2002年提出[5],它是一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。2007年,Raghavan U N等最早提出将LPA最早应用于社区发现,该算法被简称为RAK算法[6]

    思想: 每个节点赋予一个标签标志着其所在社区,每次迭代,每个节点标签根据其大多数邻近节点的标签而修改,收敛后具有相同标签的节点属于同一个社区。
    算法步骤:
    Step1 给每一个节点随机生成一个标签
    Step2 随机生成一个所有节点的顺序,按照该顺序将每一个节点的标签修改为其大多数邻居节点的标签。
    Step3 重复step2,直到每个节点的标签都不再变化,具有相同标签的节点组成了一个社区。

    7. 随机游走

    随机游走: 从一个顶点向下一个顶点移动时,以相等的概率来选择当前顶点的一个邻居作为下一个顶点。
    基本思想: 社团时相对比较稠密的子图,因此在图中进行随机游走时很容易“陷入”一个社团中。

    随机游走的过程构成了一个Markov链。图中每一个顶点对应一种状态;不同状态之间的转移概率为 2
    t 步随机游走从 i 到 j 的概率是 Pij 的t次幂

    下面我们介绍一个代表性的随机游走算法,叫做Walktrap 算法[7]

    Walktrap 算法

    定义如下距离:
    顶点 i 和 j 的距离:3
    社团C到点j的距离:4
    社团C1到C2的距离: 5

    算法步骤:
    Step1 每一个点当做一个社区,计算相邻的点(社团)之间的距离
    Step2 选取使得下式最小的两个社团C1和C2 合并为一个社团,
    6
    重复这一步骤直到所有点合并为一个社团。

    标签传播算法尽管速度快,但是效果并不太理想。

    8. Louvain (BGLL) 算法

            Louvain (BGLL) 算法[8]是一个基于模块度最优化的启发式算法,算法两层迭代,外层的迭代是自下而上的凝聚法,内层的迭代是凝聚法加上交换策略,避免了单纯凝聚方法的一个很大的缺点(两个节点一旦合并,就没法再分开)。

    算法步骤:
    Step1 每一个点初始时被看作一个社团, 按一定次序依次遍历每一个顶点. 对每一个顶点i ,考虑将 i 移至其邻居顶点 j 的社团中模块度的变化ΔQ 。如果 ΔQ>0,将 顶点i 移至使得ΔQ变化最大的顶点的社团中; 否则,顶点 i 保持不动。重复这个过程,直到任何顶点的移动都不能使模块度增大。
    Step2 将step1得到的每一个社团看作一个新的顶点,开始新的一轮迭代,直到模块度不再变化。

    该算法简单、直观,容易实现;速度快,并且效果也很好。综合效率和效果两方面考虑,该算法应该是目前最好的方法之一。

    9.Canopy算法 + K-Means

    9.1 Canopy算法

    思想:选择计算代价较低的方法计算相似性,将相似的对象放在一个子集中,这个子集被叫做Canopy,不同Canopy之间可以是重叠的
    算法步骤:
    Step1 设点集为 S,预设两个距离阈值 T1和 T2(T1>T2);
    Step2 从S中任选一个点P,用低成本方法快速计算点P与所有Canopy之间的距离,将点P加入到距离在T1以内的Canopy中;如果不存在这样的Canopy,则把点P作为一个新的Canopy的中心,并与点P距离在 T2 以内的点去掉;
    Step3 重复step2, 直到 S 为空为止。

    该算法精度低,但是速度快,常常作为“粗”聚类,得到一个k值,再用k-means进一步聚类,不属于同一Canopy 的对象之间不进行相似性计算。

    9.2 K-Means

    K-Means大家都比较熟悉,基本思想是首先找各个社团的“中心点”, 然后就近分配每个顶点
    算法步骤:选取k个点作为 k个社团的初始中心点
    Step1. 把每个点分配到最近的中心点所在的社团;
    Step2. 重新计算中心点,如果中心点不变, stop; 否则, 转 step1.
    K-Means算法计算量相对比较大,效果往往还不错,但是使用前要考虑一点:通过各个分量求平均得到的中心点是否有意义, 也就是说在你的问题中欧式距离是否有意义。

    10. 基于密度的快速聚类

    今年science上有一篇关于聚类的文章[9],提出一种快速的聚类方法,基本思想是: 找出每个类的中心点,将剩余的点按一定策略分配到每个类中。思想很简单,但是文中找每个类中心点的做法还是很有新意的。
    算法步骤
    Step1 对每一个点i,计算两个量:点i的密度 7 和点 i 到比其密度更高的其他所有点的最小距离 8
    Step2 选取10 都较大的点作为每一社团的中心点(背后的思想是:类的中心应该密度比较大,不同类的中心相互之间应该离的比较远)
    Step3 对于剩余的非中心点,分配给离它最近且密度比它高的邻点所坐在的社团

    参考文献

    [1].Kernighan & Lin ,An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49: 291–307,1970.
    [2] Newman. Fast Algorithm for Detecting Community Structure in Networks. Phy.Rev.E, 2004.
    [3] Clauset et al. Finding community structure in very large networks, Phy.Rev.E, 2004.
    [4] Girvan& Newman,Community structure in social and biological networks, PNAS, 2002
    [5] Zhu et al . Learning From Labeled and Unlabeled Data With Label Propagation, Technical Report, CMU-CALD-02-107,2002
    [6] Raghavan et al. Near linear time algorithm to detect community structures in large-scale networks, Phy.Rev.E., 2007.
    [7] P. Pons et al. Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications,2006.
    [8] Vincent D. Blondel et al, Fast Unfolding of Communities in Large Networks, Phy.Rev.E, 2008
    [9] Rodriguez & Laio, Clustering by fast search and find of density peaks. Science.2014

    展开全文
  • 目前挖掘网络展现出的广泛、潜在的应用价值等问题,整引起国内外学术界的高度重视
  • 介绍了因分析对象的不同而产生的四类社区发现方法:矩阵谱分析方法、层次聚类方法、基于边图思想的方法和基于极大团思想的方法。对其中性能最优的层次聚类方法进行了详细的综述, 并对其典型算法进行了分析比较。...
  • 针对传统Mashup服务推荐算法在关键字聚合搜索和网络构建等方式中计算复杂度过高的问题,提出一种基于语义标签的植入引导式层次聚类Mashup服务推荐算法。首先,为提高聚类算法的收敛精度,提高算法运行效率来满足大型...
  • 层次聚类算法 算法Take a look at the image below. It’s a collection of bugs and creepy-crawlies of different shapes and sizes. Take a moment to categorize them by similarity into a number of groups. ...

    层次聚类算法 算法

    Take a look at the image below. It’s a collection of bugs and creepy-crawlies of different shapes and sizes. Take a moment to categorize them by similarity into a number of groups.

    看看下面的图片。 它是各种形状和大小的错误和令人毛骨悚然的爬行动物的集合。 花一点时间按照相似性将它们分为多个组。

    This isn’t a trick question. Start with grouping the spiders together.

    这不是一个技巧性的问题。 首先将蜘蛛分组在一起。

    Done? While there’s not necessarily a “correct” answer here, it’s most likely you split the bugs into four clusters. The spiders in one cluster, the pair of snails in another, the butterflies and moth into one, and the trio of wasps and bees into one more.

    做完了吗 虽然这里一定不是一个“正确”的答案,这是最有可能拆分的错误分为四个集群 。 蜘蛛在一个簇中,成对的蜗牛在另一个簇中,蝴蝶和飞蛾成一团,WaSP和蜜蜂三人成群。

    That wasn’t too bad, was it? You could probably do the same with twice as many bugs, right? If you had a bit of time to spare — or a passion for entomology — you could probably even do the same with a hundred bugs.

    还不错吧? 您可能会用两倍多的错误来做同样的事情,对不对? 如果您有空余时间-或对昆虫学充满热情-您甚至可以用一百个bug来做同样的事情。

    For a machine though, grouping ten objects into however many meaningful clusters is no small task, thanks to a mind-bending branch of maths called combinatorics, which tells us that are 115,975 different possible ways you could have grouped those ten insects together.

    但是对于一台机器来说,将十个对象分组到许多有意义的簇中并不是一件容易的事,这要归功于一个名为combinatorics的弯弯曲曲的数学分支,该分支告诉我们,有115,975种不同的可能方式可以将这十个昆虫分组在一起。

    Had there been twenty bugs, there would have been over fifty trillion possible ways of clustering them.

    如果有二十个错误,那么将有超过五十万亿种可能的方法将它们聚类。

    With a hundred bugs — there’d be many times more solutions than there are particles in the known universe.

    有一百个错误-解决方案的数量比已知宇宙中存在的粒子多很多倍。

    How many times more? By my calculation, approximately five hundred million billion billion times more. In fact, there are more than four million billion googol solutions (what’s a googol?).

    还有多少倍? 根据我的计算,大约是五千亿亿倍 。 实际上,有超过四十亿个googol解决方案( 什么是googol? )。

    For just a hundred objects.

    仅用于一百个对象。

    Almost all of those solutions would be meaningless — yet from that unimaginable number of possible choices, you pretty quickly found one of the very few that clustered the bugs in a useful way.

    几乎所有这些解决方案都是毫无意义的-但是,从众多难以想象的可能选择中,您很快就找到了以有用的方式对错误进行聚类的少数几个。

    Us humans take it for granted how good we are categorizing and making sense of large volumes of data pretty quickly. Whether it’s a paragraph of text, or images on a screen, or a sequence of objects — humans are generally fairly efficient at making sense of whatever data the world throws at us.

    我们人类理所当然地认为我们在分类和快速理解大量数据方面有多出色。 无论是一段文字,还是屏幕上的图像,还是一系列对象,人类通常都能有效地理解世界向我们提供的任何数据。

    Given that a key aspect of developing A.I. and machine learning is getting machines to quickly make sense of large sets of input data, what shortcuts are there available?

    鉴于开发AI和机器学习的关键方面是使机器快速理解大量输入数据,有哪些捷径可用?

    Here, you can read about three clustering algorithms that machines can use to quickly make sense of large datasets. This is by no means an exhaustive list — there are other algorithms out there — but they represent a good place to start!

    在这里,您可以了解机器可以用来快速理解大型数据集的三种聚类算法。 这绝不是一个详尽的清单-那里还有其他算法-但这是一个不错的起点!

    You’ll find for each a quick summary of when you might use them, a brief overview of how they work, and a more detailed, step-by-step worked example. I believe it helps to understand an algorithm by actually carrying out yourself.

    您将找到每种使用时间的快速摘要,它们如何工作的简要概述以及更详细的分步工作示例。 我相信通过实际执行自己的算法有助于理解算法。

    If you’re really keen, you’ll find the best way to do this is with pen and paper. Go ahead — nobody will judge!

    如果您真的很热衷 ,您会发现使用笔和纸是实现此目的的最佳方法。 继续-没有人会判断!

    K均值聚类 (K-means clustering)

    在...时使用 (Use when...)

    …you have an idea of how many groups you’re expecting to find a priori.

    …您对希望找到先验的小组有一个想法。

    这个怎么运作 (How it works)

    The algorithm randomly assigns each observation into one of k categories, then calculates the mean of each category. Next, it reassigns each observation to the category with the closest mean before recalculating the means. This step repeats over and over until no more reassignments are necessary.

    该算法将每个观察随机分配到k个类别之一,然后计算每个类别的平均值 。 接下来,它将在重新计算均值之前将每个观察值分配给具有最均值的类别。 重复这一步骤,直到不再需要重新分配为止。

    工作实例 (Worked Example)

    Take a group of 12 football (or ‘soccer’) players who have each scored a certain number of goals this season (say in the range 3–30). Let’s divide them into separate clusters — say three.

    以一组12名足球(或“足球”)球员为例,他们每个赛季都进球数(例如3-30)。 让我们将它们分为单独的集群-说三个。

    Step 1 requires us to randomly split the players into three groups and calculate the means of each.

    步骤1要求我们将参与者随机分为三组,并计算每组的均值。

    Group 1
      Player A (5 goals),
      Player B (20 goals),
      Player C (11 goals)
    Group Mean = (5 + 20 + 11) / 3 = 12 goals
    
    Group 2
      Player D (5 goals),
      Player E (3 goals),
      Player F (19 goals)
    Group Mean = 9 goals
    
    Group 3
      Player G (30 goals),
      Player H (3 goals),
      Player I (15 goals)
    Group Mean = 16 goals

    Step 2: For each player, reassign them to the group with the closest mean. E.g., Player A (5 goals) is assigned to Group 2 (mean = 9). Then recalculate the group means.

    步骤2:对于每位玩家,将他们重新分配给具有最接近均值的组。 例如,玩家A(5个进球)被分配给第2组(平均值= 9)。 然后重新计算组均值。

    Group 1 (Old Mean = 12 goals)
      Player C (11 goals)
    New Mean = 11 goals
    
    Group 2 (Old Mean = 9 goals)
      Player A (5 goals),
      Player D (5 goals),
      Player E (3 goals),
      Player H (3 goals)
    New Mean = 4 goals
    
    Group 3 (Old Mean = 16 goals)
      Player G (30 goals),
      Player I (15 goals),
      Player B (20 goals),
      Player F (19 goals)
    New Mean = 21 goals

    Repeat Step 2 over and over until the group means no longer change. For this somewhat contrived example, this happens on the next iteration. Stop! You have now formed three clusters from the dataset!

    一遍又一遍地重复步骤2,直到组的含义不再改变为止。 对于这个有些人为的例子,这发生在下一次迭代中。 停止! 现在,您已经从数据集中形成了三个聚类!

    Group 1 (Old Mean = 11 goals)
      Player C (11 goals),
      Player I (15 goals)
    Final Mean = 13 goals
    
    Group 2 (Old Mean = 4 goals)
      Player A (5 goals),
      Player D (5 goals),
      Player E (3 goals),
      Player H (3 goals)
    Final Mean = 4 goals
    
    Group 3 (Old Mean = 21 goals)
      Player G (30 goals),
      Player B (20 goals),
      Player F (19 goals)
    Final Mean = 23 goals

    With this example, the clusters could correspond to the players’ positions on the field — such as defenders, midfielders and attackers.

    在这个例子中,集群可以对应于球员在场上的位置,例如防守者,中场球员和进攻者。

    K-means works here because we could have reasonably expected the data to fall naturally into these three categories.

    K均值之所以在这里起作用,是因为我们可以合理地预期数据自然会落入这三类。

    In this way, given data on a range of performance statistics, a machine could do a reasonable job of estimating the positions of players from any team sport — useful for sports analytics, and indeed any other purpose where classification of a dataset into predefined groups can provide relevant insights.

    这样,给定一系列性能统计数据,一台机器就可以合理地估算出任何团队运动项目中球员的位置,这对运动分析非常有用,并且在将数据集分类为预定义组的其他任何目的上都非常有用提供相关见解。

    更细的细节 (Finer details)

    There are several variations on the algorithm described here. The initial method of ‘seeding’ the clusters can be done in one of several ways.

    这里描述的算法有几种变体。 可以通过以下几种方式之一来完成“播种”群集的初始方法。

    Here, we randomly assigned every player into a group, then calculated the group means. This causes the initial group means to tend towards being similar to one another, which ensures greater repeatability.

    在这里,我们将每个玩家随机分配到一个组中,然后计算组均值。 这导致初始组手段趋于彼此相似,从而确保了更大的可重复性。

    An alternative is to seed the clusters with just one player each, then start assigning players to the nearest cluster. The returned clusters are more sensitive to the initial seeding step, reducing repeatability in highly variable datasets.

    另一种选择是给每个只有一个玩家的集群播种,然后开始将玩家分配到最近的集群。 返回的簇对初始播种步骤更加敏感,从而降低了高度可变的数据集中的可重复性。

    However, this approach may reduce the number of iterations required to complete the algorithm, as the groups will take less time to diverge.

    但是,这种方法可能会减少完成算法所需的迭代次数,因为组将花费更少的时间进行分离。

    An obvious limitation to K-means clustering is that you have to provide a priori assumptions about how many clusters you’re expecting to find.

    K均值聚类的一个明显限制是,您必须提供关于要找到多少个聚类的先验假设。

    There are methods to assess the fit of a particular set of clusters. For example, the Within-Cluster Sum-of-Squares is a measure of the variance within each cluster.

    有一些方法可以评估特定集群集的拟合度。 例如,集群内平方和是每个集群内方差的度量。

    The ‘better’ the clusters, the lower the overall WCSS.

    群集越“好”,则总体WCSS越低。

    层次聚类 (Hierarchical clustering)

    在...时使用 (Use when...)

    …you wish to uncover the underlying relationships between your observations.

    …您希望揭示观察结果之间的潜在关系。

    这个怎么运作 (How it works)

    A distance matrix is computed, where the value of cell (i, j) is a distance metric between observations i and j.

    计算距离矩阵,其中像元( i,j)的值是观测值ij之间的距离度量。

    Then, pair the closest two observations and calculate their average. Form a new distance matrix, merging the paired observations into a single object.

    然后,将最接近的两个观测值配对并计算它们的平均值。 形成一个新的距离矩阵,将成对的观测值合并为一个对象。

    From this distance matrix, pair up the closest two observations and calculate their average. Repeat until all observations are grouped together.

    从这个距离矩阵中,配对最接近的两个观测值并计算它们的平均值。 重复直到将所有观察结果分组在一起。

    工作的例子 (Worked example)

    Here’s a super-simplified dataset about a selection of whale and dolphin species. As a trained biologist, I can assure you we normally use much more detailed datasets for things like reconstructing phylogeny.

    这是有关鲸和海豚物种选择的超级简化数据集。 作为一名训练有素的生物学家,我可以向您保证,我们通常使用更详细的数据集来重建系统发育

    For now though, we’ll just look at the typical body lengths for these six species. We’ll be using just two repeated steps.

    现在,我们只看这六个物种的典型体长。 我们将仅使用两个重复步骤。

    Species          Initials  Length(m)
    Bottlenose Dolphin     BD        3.0
    Risso's Dolphin        RD        3.6
    Pilot Whale            PW        6.5
    Killer Whale           KW        7.5
    Humpback Whale         HW       15.0
    Fin Whale              FW       20.0

    Step 1: compute a distance matrix between each species. Here, we’ll use the Euclidean distance — how far apart are the data points?

    步骤1:计算每个物种之间的距离矩阵。 在这里,我们将使用欧几里得距离 -数据点相距多远?

    Read this exactly as you would a distance chart in a road atlas. The difference in length between any pair of species can be looked up by reading the value at the intersection of the relevant row and column.

    就像在道路地图集上绘制距离图一样,仔细阅读本章。 可以通过读取相关行和列相交处的值来查找任意一对物种之间的长度差异。

    BD   RD   PW   KW   HW
    RD  0.6                    
    PW  3.5  2.9               
    KW  4.5  3.9  1.0          
    HW 12.0 11.4  8.5  7.5     
    FW 17.0 16.4 13.5 12.5  5.0

    Step 2: Pair up the two closest species. Here, this will be the Bottlenose & Risso’s Dolphins, with an average length of 3.3m.

    步骤2:配对两个最接近的物种。 在这里,这将是宽吻海豚和海豚的海豚,平均长度为3.3m。

    Repeat Step 1 by recalculating the distance matrix, but this time merge the Bottlenose & Risso’s Dolphins into a single object with length 3.3m.

    通过重新计算距离矩阵来重复步骤1,但是这次将宽吻瓶和里索的海豚合并为一个长度为3.3m的单个对象。

    [BD, RD]   PW   KW   HW
    PW       3.2               
    KW       4.2   1.0          
    HW      11.7   8.5  7.5     
    FW      16.7  13.5 12.5  5.0

    Next, repeat Step 2 with this new distance matrix. Here, the smallest distance is between the Pilot & Killer Whales, so we pair them up and take their average — which gives us 7.0m.

    接下来 ,使用这个新的距离矩阵重复步骤2。 在这里,飞行员与虎鲸之间的距离最小,因此我们将它们配对并取它们的平均值,即为7.0m。

    Then, we repeat Step 1 — recalculate the distance matrix, but now we’ve merged the Pilot & Killer Whales into a single object of length 7.0m.

    然后 ,我们重复步骤1-重新计算距离矩阵,但是现在我们将“飞行员与杀人鲸”合并为一个长度为7.0m的对象。

    [BD, RD] [PW, KW]   HW
     [PW, KW]      3.7              
     HW           11.7      8.0     
     FW           16.7     13.0   5.0

    Next, repeat Step 2 with this distance matrix. The smallest distance (3.7m) is between the two merged objects — so now merge them into an even bigger object, and take the average (which is 5.2m).

    接下来 ,使用此距离矩阵重复步骤2。 最小的距离(3.7m)在两个合并的对象之间-现在将它们合并成更大的对象,并取平均值(即5.2m)。

    Then, repeat Step 1 and compute a new distance matrix, having merged the Bottlenose & Risso’s Dolphins with the Pilot & Killer Whales.

    然后 ,重复步骤1并计算新的距离矩阵,将宽吻鼻和里索的海豚与飞行员和虎鲸合并。

    [[BD, RD] , [PW, KW]]    HW
    HW                   9.8    
    FW                  14.8   5.0

    Next, repeat Step 2. The smallest distance (5.0m) is between the Humpback & Fin Whales, so merge them into a single object, and take the average (17.5m).

    接下来 ,重复步骤2。座头鲸和鳍鲸之间的最小距离(5.0m),因此将它们合并为一个对象,并取其平均值(17.5m)。

    Then, it’s back to Step 1 — compute the distance matrix, having merged the Humpback & Fin Whales.

    然后 ,返回到步骤1-合并了座头鲸和鳍鲸,计算距离矩阵。

    [[BD, RD] , [PW, KW]]
    [HW, FW]                  12.3

    Finally, repeat Step 2 — there is only one distance (12.3m) in this matrix, so pair everything into one big object. Now you can stop! Look at the final merged object:

    最后,重复步骤2-这个矩阵只有一个距离(12.3m),因此将所有东西配对成一个大物体。 现在您可以停止! 查看最终的合并对象:

    [[[BD, RD],[PW, KW]],[HW, FW]]

    It has a nested structure (think JSON), which allows it to be drawn up as a tree-like graph, or 'dendrogram'.

    它具有嵌套结构(例如JSON ),可以将其绘制为树状图或“树状图”。

    It reads in much the same way a family tree might. The nearer two observations are on the tree, the more similar or closely-related they are taken to be.

    它的读取方式与家谱的读取方式几乎相同。 树上的两个观测值越接近,它们被认为越相似或紧密相关。

    The structure of the dendrogram gives insight into how the dataset is structured.

    树状图的结构使您可以深入了解数据集的结构。

    In this example, there are two main branches, with Humpback Whale and Fin Whale on one side, and the Bottlenose Dolphin/Risso’s Dolphin and Pilot Whale/Killer Whale on the other.

    在此示例中,有两个主要分支,一侧是座头鲸和鳍鲸,另一侧是宽吻海豚/里索的海豚和领航鲸/杀人鲸。

    In evolutionary biology, much larger datasets with many more specimens and measurements are used in this way to infer taxonomic relationships between them.

    在进化生物学中,以这种方式使用具有更多标本和测量值的更大的数据集来推断它们之间的分类学关系。

    Outside of biology, hierarchical clustering has applications in data mining and machine learning contexts.

    在生物学之外,层次聚类在数据挖掘和机器学习环境中具有应用。

    The cool thing is that this approach requires no assumptions about the number of clusters you’re looking for.

    有趣的是,这种方法无需假设您要寻找的群集数量。

    You can split the returned dendrogram into clusters by “cutting” the tree at a given height. This height can be chosen in a number of ways, depending on the resolution at which you wish to cluster the data.

    您可以通过以指定高度“切割”树来将返回的树状图拆分为簇。 可以通过多种方式选择此高度,具体取决于您希望对数据进行聚类的分辨率。

    For instance, looking at the dendrogram above, if we draw a horizontal line at height = 10, we’d intersect the two main branches, splitting the dendrogram into two sub-graphs. If we cut at height = 2, we’d be splitting the dendrogram into three clusters.

    例如,查看上面的树状图,如果我们在height = 10处绘制一条水平线,我们将与两个主要分支相交,将树状图分为两个子图。 如果我们在高度= 2处进行切割,我们会将树状图分成三个簇。

    更细的细节 (Finer details)

    There are essentially three aspects in which hierarchical clustering algorithms can vary to the one given here.

    从本质上讲,层次聚类算法可以在三个方面与此处给出的算法有所不同。

    Most fundamental is the approach — here, we have used an agglomerative process, whereby we start with individual data points and iteratively cluster them together until we’re left with one large cluster.

    最基本的方法是这种方法-在这里,我们使用了一个凝聚过程,即从单个数据点开始,然后将它们迭代地聚类在一起,直到剩下一个大的聚类。

    An alternative (but more computationally intensive) approach is to start with one giant cluster, and then proceed to divide the data into smaller and smaller clusters until you’re left with isolated data points.

    另一种替代方法(但计算量更大)是从一个巨型群集开始,然后将数据分成越来越小的群集,直到剩下孤立的数据点为止。

    There are also a range of methods that can be used to calculate the distance matrices. For many purposes, the Euclidean distance (think Pythagoras’ Theorem) will suffice, but there are alternatives that may be more applicable in some circumstances.

    还有多种方法可用于计算距离矩阵。 对于许多目的,欧几里德距离(认为毕达哥拉斯定理)就足够了,但是有些替代方法可能在某些情况下更适用。

    Finally, the linkage criterion can also vary. Clusters are linked according to how close they are to one another, but the way in which we define ‘close’ is flexible.

    最后, 链接标准也可以变化。 群集根据彼此之间的接近程度进行链接,但是我们定义“关闭”的方式很灵活。

    In the example above, we measured the distances between the means (or ‘centroids’) of each group and paired up the nearest groups. However, you may want to use a different definition.

    在上面的示例中,我们测量了每个组的均值(或“质心”)之间的距离,并将最接近的组配对。 但是,您可能要使用其他定义。

    For example, each cluster is made up of several discrete points. You could define the distance between two clusters to be the minimum (or maximum) distance between any of their points — as illustrated in the figure below.

    例如,每个群集由几个离散点组成。 您可以将两个聚类之间的距离定义为它们的任意点之间的最小(或最大)距离,如下图所示。

    There are still other ways of defining the linkage criterion, which may be suitable in different contexts.

    还有其他定义链接标准的方式,可能适用于不同的上下文。

    图社区检测 (Graph Community Detection)

    使用时 (Use when)

    …you have data that can be represented as a network, or ‘graph’.

    …您拥有可以表示为网络或“图形”的数据。

    这个怎么运作 (How it works)

    A graph community is very generally defined as a subset of vertices which are more connected to each other than with the rest of the network.

    通常将图社区定义为顶点的子集,这些顶点彼此之间的联系比与网络其余部分的联系更多。

    Various algorithms exist to identify communities, based upon more specific definitions. Algorithms include, but are not limited to: Edge Betweenness, Modularity-Maximsation, Walktrap, Clique Percolation, Leading Eigenvector…

    基于更具体的定义,存在各种算法来标识社区。 算法包括但不限于:边缘中间性,模块化最大化,Walktrap,集团渗透,前导特征向量…

    工作的例子 (Worked example)

    Graph theory, or the mathematical study of networks, is a fascinating branch of mathematics that lets us model complex systems as an abstract collection of ‘dots’ (or vertices) connected by ‘lines’ (or edges).

    图论或网络的数学研究是数学的一个引人入胜的分支,它使我们可以将复杂的系统建模为由“线”(或 )连接的“点”(或顶点 )的抽象集合。

    Perhaps the most intuitive case-studies are social networks.

    也许最直观的案例研究是社交网络。

    Here, the vertices represent people, and edges connect vertices who are friends/followers. However, any system can be modelled as a network if you can justify a method to meaningfully connect different components.

    在这里,顶点代表人,边连接作为朋友/跟随者的顶点。 但是,如果可以证明一种方法有意义地连接不同的组件,则可以将任何系统建模为网络。

    Among the more innovative applications of graph theory to clustering include feature extraction from image data, and analysing gene regulatory networks.

    图论在聚类中的更多创新应用包括从图像数据中提取特征以及分析基因调控网络。

    As an entry-level example, take a look at this quickly put-together graph. It shows the eight websites I most recently visited, linked according to whether their respective Wikipedia articles link out to one another.

    作为入门级示例,请看一下此快速汇总的图表。 它显示了我最近访问的八个网站,这些网站根据各自的Wikipedia文章是否相互链接而链接在一起。

    You could assemble this data manually, but for larger-scale projects, it’s much quicker to write a Python script to do the same. Here’s one I wrote earlier.

    您可以手动组装此数据,但是对于大型项目,编写Python脚本来完成此操作要快得多。 这是我之前写的

    The vertices are colored according to their community membership, and sized according to their centrality. See how Google and Twitter are the most central?

    顶点根据其社区成员资格进行着色,并根据其中心性进行大小调整。 看看Google和Twitter是最核心的吗?

    Also, the clusters make pretty good sense in the real-world (always an important performance indicator).

    此外,集群在现实世界中非常有意义(始终是重要的性能指标)。

    The yellow vertices are generally reference/look-up sites; the blue vertices are all used for online publishing (of articles, tweets, or code); and the red vertices include YouTube, which was of course founded by former PayPal employees. Not bad deductions for a machine.

    黄色顶点通常是参考/查找站点; 蓝色顶点全部用于在线发布(文章,推文或代码的发布); 红色顶点包括YouTube,它当然是由前PayPal员工创立的。 对机器的扣减还不错。

    Aside from being a useful way to visualize large systems, the real power of networks comes from their mathematical analysis. Let’s start by translating our nice picture of the network into a more mathematical format. Below is the adjacency matrix of the network.

    除了是可视化大型系统的有用方法之外,网络的真正功能还在于它们的数学分析。 让我们首先将网络的漂亮图片转换成更数学的格式。 下面是网络的邻接矩阵

    GH Gl  M  P  Q  T  W  Y
    GitHub    0  1  0  0  0  1  0  0  
    Google    1  0  1  1  1  1  1  1
    Medium    0  1  0  0  0  1  0  0
    PayPal    0  1  0  0  0  1  0  1
    Quora     0  1  0  0  0  1  1  0
    Twitter   1  1  1  1  1  0  0  1
    Wikipedia 0  1  0  0  1  0  0  0
    YouTube   0  1  0  1  0  1  0  0

    The value at the intersection of each row and column records whether there is an edge between that pair of vertices.

    每行和列的交点处的值记录该对顶点之间是否存在边。

    For instance, there is an edge between Medium and Twitter (surprise, surprise!), so the value where their rows/columns intersect is 1. Similarly, there is no edge between Medium and PayPal, so the intersection of their rows/columns returns 0.

    例如,Medium和Twitter之间有一条边(惊讶,令人惊讶!),因此它们的行/列相交的值是1。类似地,Medium和PayPal之间没有边,因此它们的行/列的交点返回0。

    Encoded within the adjacency matrix are all the properties of this network — it gives us the key to start unlocking all manner of valuable insights.

    该网络的所有属性都编码在邻接矩阵中-它为我们提供了开始解锁各种有价值的见解的关键。

    For a start, summing any column (or row) gives you the degree of each vertex — i.e., how many others it is connected to. This is commonly denoted with the letter k.

    首先,求和任何列(或行)的总和即可得出每个顶点的度数 ,即它与多少个顶点相连。 通常用字母k表示。

    Likewise, summing the degrees of every vertex and dividing by two gives you L, the number of edges (or ‘links’) in the network. The number of rows/columns gives us N, the number of vertices (or ‘nodes’) in the network.

    同样,将每个顶点的度数相加并除以2可得到L ,即网络中边(或“链接”)的数量。 行数/列数为N ,即网络中的顶点数(或“节点”)。

    Knowing just k, L, N and the value of each cell in the adjacency matrix A lets us calculate the modularity of any given clustering of the network.

    只需知道kL,N和邻接矩阵A中每个像元的值,就可以计算模块化 网络的任何给定群集。

    Say we’ve clustered the network into a number of communities. We can use the modularity score to assess the ‘quality’ of this clustering.

    假设我们已将网络聚集到多个社区中。 我们可以使用模块化评分来评估该聚类的“质量”。

    A higher score will show we’ve split the network into ‘accurate’ communities, whereas a low score suggests our clusters are more random than insightful. The image below illustrates this.

    较高的分数将表明我们已将网络划分为“准确的”社区,而较低的分数表明我们的集群比有见地的更为随机。 下图说明了这一点。

    Modularity can be calculated using the formula below:

    模块化可以使用以下公式计算:

    That’s a fair amount of math, but we can break it down bit by bit and it’ll make more sense.

    这是相当多的数学运算,但是我们可以一点一点地分解它,这将更有意义。

    M is of course what we’re calculating — modularity.

    M当然是我们正在计算的-模块化。

    1/2L tells us to divide everything that follows by 2L, i.e., twice the number of edges in the network. So far, so good.

    1/2 L告诉我们将其后的所有内容除以2 L ,即网络中边数的两倍。 到目前为止,一切都很好。

    The Σ symbol tells us we’re summing up everything to the right, and lets us iterate over every row and column in the adjacency matrix A.

    Σ符号告诉我们我们在右边汇总所有内容,并让我们遍历邻接矩阵A中的每一行和每一列。

    For those unfamiliar with sum notation, the i, j = 1 and the N work much like nested for-loops in programming. In Python, you’d write it as follows:

    对于那些不熟悉总和表示法的人, i,j = 1N的工作方式很像编程中的嵌套for循环。 在Python中,您可以这样编写:

    sum = 0
    for i in range(1,N):
        for j in range(1,N):
            ans = #stuff with i and j as indices 
        sum += ans

    So what is #stuff with i and j in more detail?

    那么, #stuff with i and j是什么呢?

    Well, the bit in brackets tells us to subtract ( k_i k_j ) / 2L from A_ij.

    好吧,方括号中的位告诉我们从A_ij减去( k_i k_j)/ 2L

    A_ij is simply the value in the adjacency matrix at row i, column j.

    A_ij仅是第i j列的邻接矩阵中的值。

    The values of k_i and k_j are the degrees of each vertex — found by adding up the entries in row i and column j respectively. Multiplying these together and dividing by 2L gives us the expected number of edges between vertices i and j if the network were randomly shuffled up.

    k_ik_j的值是每个顶点的度数-通过分别将第i行和第j列中的条目相加得出。 如果将网络随机改组,则将它们相乘并除以2 L可得到顶点ij之间的预期边数。

    Overall, the term in the brackets reveals the difference between the network’s real structure and the expected structure it would have if randomly reassembled.

    总体而言,方括号中的术语揭示了网络的实际结构与如果随机重组将具有的预期结构之间的差异。

    Playing around with the values shows that it returns its highest value when A_ij = 1, and ( k_i k_j ) / 2L is low. This means we see a higher value if there is an ‘unexpected’ edge between vertices i and j.

    数值的计算表明,当A_ij = 1且( k_i k_j)/ 2L为低时,它将返回其最大值。 这意味着如果在顶点ij之间存在“意外”边缘,则我们看到一个更高的值

    Finally, we multiply the bracketed term by whatever the last few symbols refer to.

    最后,我们将括号中的术语乘以最后几个符号所指的内容。

    The ?c_i, c_j is the fancy-sounding but totally harmless Kronecker-delta function. Here it is, explained in Python:

    ?c _i, c _j是听起来很花哨但完全无害的Kronecker-delta函数。 在Python中进行了解释:

    def kroneckerDelta(ci, cj):
        if ci == cj:
            return 1
        else:
            return 0
            
    kroneckerDelta("A","A")
    #returns 1
    
    kroneckerDelta("A","B")
    #returns 0

    Yes — it really is that simple. The Kronecker-delta function takes two arguments, and returns 1 if they are identical, otherwise, zero.

    是的-真的就是这么简单。 Kronecker-delta函数采用两个参数,如果相同则返回1,否则返回零。

    This means that if vertices i and j have been put in the same cluster, then ?c_i, c_j = 1. Otherwise, if they are in different clusters, the function returns zero.

    这意味着,如果将顶点ij放在同一簇中,则?c _i, c _j = 1 。 否则,如果它们位于不同的群集中,则该函数将返回零。

    As we are multiplying the bracketed term by this Kronecker-delta function, we find that for the nested sum Σ, the outcome is highest when there are lots of ‘unexpected’ edges connecting vertices assigned to the same cluster.

    当我们将括号中的项乘以该Kronecker-delta函数时,我们发现对于嵌套的总和Σ ,当有很多“意外”边缘连接分配给同一聚类的顶点时,结果最高。

    As such, modularity is a measure of how well-clustered the graph is into separate communities.

    因此,模块化是衡量图表在不同社区中的聚集程度的一种度量。

    Dividing by 2L bounds the upper value of modularity at 1. Modularity scores near to or below zero indicate the current clustering of the network is really no use. The higher the modularity, the better the clustering of the network into separate communities.

    除以2L会将模块性的上限定为1。接近或低于零的模块性分数表明该网络的当前集群实际上没有用。 模块化程度越高,将网络更好地聚集到单独的社区中就越好。

    By maximising modularity, we can find the best way of clustering the network.

    通过最大程度地提高模块化,我们可以找到群集网络的最佳方法。

    Notice that we have to pre-define how the graph is clustered to find out how ‘good’ that clustering actually is.

    注意,我们必须预先定义图的聚类方式,以找出聚类的实际效果。

    Unfortunately, employing brute force to try out every possible way of clustering the graph to find which has the highest modularity score would be computationally impossible beyond a very limited sample size.

    不幸的是,在非常有限的样本量之外,采用蛮力尝试对图进行聚类以找到具有最高模块化得分的所有可能方法,在计算上都是不可能的。

    Combinatorics tells us that for a network of just eight vertices, there are 4140 different ways of clustering them. A network twice the size would have over ten billion possible ways of clustering the vertices.

    组合法告诉我们,对于只有八个顶点的网络,有4140种不同的方法将它们聚类。 两倍大小的网络将有超过一百亿种可能的顶点聚类方法。

    Doubling the network again (to a very modest 32 vertices) would give 128 septillion possible ways, and a network of eighty vertices would be cluster-able in more ways than there are atoms in the observable universe.

    将网络再次加倍(到非常适度的32个顶点)将提供128亿种可能的方式,并且与可观察的宇宙中存在的原子相比,具有80个顶点的网络将以更多的方式可集群。

    Instead, we have to turn to a heuristic method that does a reasonably good job at estimating the clusters that will produce the highest modularity score, without trying out every single possibility.

    取而代之的是,我们必须转向一种启发式方法,该方法在估计将产生最高模块性得分的集群方面做得相当好,而无需尝试每种可能性。

    This is an algorithm called Fast-Greedy Modularity-Maximization, and it’s somewhat analogous to the agglomerative hierarchical clustering algorithm describe above. Instead of merging according to distance, ‘Mod-Max’ merges communities according to changes in modularity.

    这是一种称为快速贪婪模块化最大化的算法它有点类似于上面描述的聚集层次聚类算法。 'Mod-Max'并非根据距离进行合并,而是根据模块化的变化来合并社区。

    Here’s how it goes:

    这是怎么回事:

    Begin by initially assigning every vertex to its own community, and calculating the modularity of the whole network, M.

    首先将每个顶点分配给它自己的社区,然后计算整个网络的模块化M。

    Step 1 requires that for each community pair linked by at least a single edge, the algorithm calculates the resultant change in modularity ΔM if the two communities were merged into one.

    步骤1要求,对于至少由一条边链接的每个社区对,如果将两个社区合并为一个社区,该算法将计算模块性ΔM的最终变化。

    Step 2 then takes the pair of communities that produce the biggest increase in ΔM, which are then merged. Calculate the new modularity M for this clustering, and keep a record of it.

    然后, 步骤2选取产生最大ΔM的一对社区,然后将其合并。 计算该集群的新模块性M ,并对其进行记录。

    Repeat steps 1 and 2 — each time merging the pair of communities for which doing so produces the biggest gain in ΔM, then recording the new clustering pattern and its associated modularity score M.

    重复步骤1和2-每次合并一对社区,这样做会在ΔM中产生最大的收益然后记录新的聚类模式及其相关的模块化评分M。

    Stop when all the vertices are grouped into one giant cluster. Now the algorithm checks the records it kept as it went along, and identifies the clustering pattern that returned the highest value of M. This is the returned community structure.

    所有顶点分组为一个大簇时停止 。 现在,该算法检查其保留的记录,并确定返回最大M值的聚类模式。 这是返回的社区结构。

    更细的细节 (Finer details)

    Whew! That was computationally intensive, at least for us humans.

    ew! 这是计算密集型的,至少对于我们人类而言。

    Graph theory is a rich source of computationally challenging, often NP-hard problems — yet it also has incredible potential to provide valuable insights into complex systems and datasets.

    图论是计算难题(通常是NP难题)的丰富来源,但它也具有令人难以置信的潜力,可以为复杂的系统和数据集提供有价值的见解。

    Just ask Larry Page, whose eponymous PageRank algorithm — which helped propel Google from start-up to basically world domination in less than a generation — was based entirely in graph theory.

    只需问问拉里·佩奇(Larry Page),他的同名PageRank算法完全基于图论,该算法在不到一代人的时间里就将Google从新兴企业推向了世界统治。

    Community detection is a major focus of current research in graph theory, and there are plenty of alternatives to Modularity-Maximization, which while useful, does have some drawbacks.

    社区检测是当前图论研究的主要重点,模块化最大化有许多替代方案,尽管它们很有用,但确实存在一些缺点。

    For a start, its agglomerative approach often sees small, well-defined communities swallowed up into larger ones. This is known as the resolution limit — the algorithm will not find communities below a certain size.

    首先,它的聚集方法通常会看到小型的,定义明确的社区被吞并为较大的社区。 这称为分辨率限制 -算法将找不到小于特定大小的社区。

    Another challenge is that rather than having one distinct, easy-to-reach global peak, the Mod-Max approach actually tends to produce a wide ‘plateau’ of many similar high modularity scores — making it somewhat difficult to truly identify the absolute maximum score.

    另一个挑战是,Mod-Max方法并没有产生一个清晰易懂的全球峰值,而是趋向于产生许多相似的高模块评分的宽广的“平台”,这使得真正识别绝对最大评分有些困难。

    Other algorithms use different ways to define and approach community detection.

    其他算法使用不同的方式来定义和处理社区检测。

    Edge-Betweenness is a divisive algorithm, starting with all vertices grouped in one giant cluster. It proceeds to iteratively remove the least ‘important’ edges in the network, until all vertices are left isolated. This produces a hierarchical structure, with similar vertices closer together in the hierarchy.

    Edge-Betweenness是一种分割算法,从将所有顶点分组到一个巨型簇中开始。 进行迭代地删除网络中最不重要的边缘,直到所有顶点都保持隔离。 这将产生一个层次结构,相似的顶点在层次结构中靠得更近。

    Another algorithm is Clique Percolation, which takes into account possible overlap between graph communities.

    另一个算法是Clique Percolation ,它考虑了图社区之间可能的重叠。

    Yet another set of algorithms are based on random-walks across the graph, and then there are spectral clustering methods which start delving into the eigendecomposition of the adjacency matrix and other matrices derived therefrom. These ideas are used in feature extraction in, for example, areas such as computer vision.

    另一组算法是基于整个图的随机游动 ,然后是频谱聚类方法,它们开始研究邻接矩阵和从中得出的其他矩阵的特征分解。 这些想法用于例如计算机视觉等领域的特征提取。

    It’d be well beyond the scope of this article to give each algorithm its own in-depth worked example. Suffice to say that this is an active area of research, providing powerful methods to make sense of data that even a generation ago would have been extremely difficult to process.

    为每个算法提供自己的深入工作示例将远远超出本文的范围。 可以说这是一个活跃的研究领域,它提供了强大的方法来理解数据,即使是一代人以前也很难处理这些数据。

    结论 (Conclusion)

    Hopefully this article has informed and inspired you to better understand how machines can make sense of data. The future is a rapidly changing place, and many of those changes will be driven by what technology becomes capable of in the next generation or two.

    希望本文能为您提供启发并启发您更好地了解机器如何理解数据。 未来是一个瞬息万变的地方,其中许多变化将取决于下一代技术的能力。

    As outlined in the introduction, machine learning is an extraordinarily ambitious field of research, in which massively complex problems require solving in as accurate and as efficient a way possible. Tasks that come naturally to us humans require innovative solutions when taken on by machines.

    正如导言中概述的那样,机器学习是一个非常宏大的研究领域,其中庞大的复杂问题需要以尽可能准确和有效的方式来解决。 对于人类来说,自然而然的任务需要由机器承担的创新解决方案。

    There’s still plenty of progress to be made, and whoever contributes the next breakthrough idea will no doubt be generously rewarded. Maybe someone reading this article will be behind the next powerful algorithm?

    仍有大量的进步,无论谁贡献下一个突破性的想法,无疑都会得到丰厚的回报。 也许有人读这篇文章会成为下一个强大算法的幕后推手?

    All great ideas have to start somewhere!

    所有好主意都必须从某个地方开始!

    翻译自: https://www.freecodecamp.org/news/how-machines-make-sense-of-big-data-an-introduction-to-clustering-algorithms-4bd97d4fbaba/

    层次聚类算法 算法

    展开全文
  • 在之前的系列中,大部分都是关于监督学习(除了PCA那一节),接下来的几篇主要分享一下关于非监督学习中的聚类算法(clustering algorithms)。 一、先了解一下聚类分析(clustering analysis) Cluster analysis or...

    在之前的系列中,大部分都是关于监督学习(除了PCA那一节),接下来的几篇主要分享一下关于非监督学习中的聚类算法(clustering algorithms)。

    一、先了解一下聚类分析(clustering analysis)

    Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups(clusters). it is a main task of exploratory analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. --WIKI

    聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计方法,同时也是数据挖掘的一个重要算法。聚类(cluster)分析是由若干模式(pattern)组成的,通常,模式是一个度量(measurement)的向量,或者是多维空间中的一个点。聚类分析以相似性为基础,在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。-- 百度百科

    聚类分析本身不是一种特定的算法,是用来解决一般任务的方法。它可以通过不同的算法来实现,这些算法不同之处在于它们对于集群结构的理解以及如何有效地找到这些集群。流行的集群概念包括,在一个集群的成员之间距离比较小,数据空间的密集区域,间隔或特定统计分布的组。因此,可以将聚类公式化为一个多目标优化问题。合适的聚类算法和参数的设置取决于所使用的数据集和对于聚类结果的用途。设置的参数例如要使用的距离函数,密度阈值或预计要聚类的数量。

    Process of clustering(聚类分析的过程):

    聚类分析的整个过程包括四个基本步骤

    A. Feature Selection or Extraction (特征选择和提取)

    特征选择是确定最有效的原始特征子集用于聚类的过程。特征提取是将一个或多个输入特征转换为初始显著特征的过程。聚类过程高度依赖于此步骤。对特征的轻率剔除会增加内卷involution(involution: a function, transformation, or operator that is equal to its inverse),并可能导致额外的无关紧要的簇(clusters).

    B. Clustering Algorithm Design or Selection (聚类算法的设计和选择)

    不可能定理指出,“没有一个单一的聚类算法可以同时满足数据聚类的三个基本公理,即scale-invariance (尺度不变性)、consistency (一致性) 和 richness (丰富性)。因此,不可能为在不同的科学、社交、医学等其它领域中建立一个通用的聚类方法框架。从而,通过对应用领域的认知来精确剔除该算法是非常重要的。通常,所有算法都基于不同的输入参数,例如聚类的数量,优化/构造标准,终止条件,邻近度等。额外设计或者剔除这些不同的参数和标准,以此来作为这个步骤的前提条件。

    C. Cluster Validation (聚类验证)

    将不同的聚类算法用于同一数据集可以产生不同的结果。甚至是相同的算法,不同的参数也会产生不同的聚类结果。因此,必须验证或评估该聚类方法产生的结果。评估标准分为:

    1)内部指标:内部指标是通过和它的数据进行比较来评估由聚类算法产生的聚类

    2)外部指标:外部指标通过利用已知的知识(例如:类别标签)来评估聚类结果。

    3)相对指标:顾名思义,该标准将结果与不同算法产生的其他结果进行比较。

    D. Results Interpretation 结果解析

    聚类过程的最后一步涉及聚类的展示。聚类的最终目的是为了让人们更了解原始数据,以便它们更有效地分析和解决难题。

    因为“Cluster(集群)”的概念无法精确地被定义,所以聚类的算法种类有很多,比较常见的有:

    Connectively - based clustering (hierarchical clustering)
    基于连接的聚类(层次聚类)

    在这里插入图片描述

    Centroid-based clustering – k-means
    基于中心的聚类 --例如:k-means

    在这里插入图片描述

    Distribution-based clustering – Gaussian mixture models
    基于分布的聚类 --例如:高斯混合模型

    在这里插入图片描述

    Density-based clustering – kernel density estimation
    基于密度的聚类 – 例如:核密度估计

    Grid-based clustering 基于网格的集群
    在这里插入图片描述


    二、再了解一下 connectively-based clustering 基于连接的聚类算法

    基于连接的聚类(也称为分层聚类),是基于这样的一个核心思想:即与附近的对象而不是较远的对象更为相关。该算法根据距离将对象连接起来形成簇(cluster)。可以通过连接各部分所需的最大距离来大致描述集群。在不同的距离,形成不同簇,这可以使用一个树状图来呈现。这也解析了“分层聚类”的来源,这些算法不提供数据集的单一部分,而是提供一个广泛的集群层次结构,这些集群以一定的距离合并。在树状图中,y轴标记聚类合并的距离,而对象沿x轴放置,以使聚类不混合。

    基于连接的聚类是一群方法,它们的区别在于计算距离的方式不同。除了选用距离函数之外,还需要确定要使用的连接标准(因为一个聚类包含多个对象,因此有多个候选对象可以用来计算距离)。流行的选择称为“单链接聚类”(最小对象距离),“完整链接聚类”(最大对象距离)和“UPGMA”或者“WPGMA”(“Unweighted or Weighted Pair Group Method with Arithmetic Mean”, 也称为平均链接集群)。此外,分层聚类可以是聚集性的(从单个元素开始并将其聚合为聚类)或分散性的(从完整的数据集开始并将其划分为分区)。

    分层聚类通过依次合并或拆分嵌套聚类来构建它们。聚类的这种层次结构表现为树(或者树模型)。这棵树的根是唯一的簇(cluster),聚集了所有样本,树叶是仅包含了一个样本的簇(cluster)。(还是叫cluster更形象一点)

    分层聚类涉及创建从上到下具有预定顺序的聚类。因此,可以说是有两种类型的层次聚类,即分裂聚类和聚集聚类
    在这里插入图片描述
    Divisive method 分层方法

    在divisive 或者从上至下的聚类方法中,所有的观测值被分配给了一个单一的聚类,然后将这个cluster分开至至少两个相似的clusters. 最后我们在每个聚类上进行递归,直到每个observation只有一个聚类。在某些情况下,分类算法比聚集算法产生的精度更高,但是从概念上更复杂。

    Agglomerative method 聚集方法

    在聚集或者自下而上的聚类方法中,把每个观测值分配到他自己的聚类中,然后计算每个聚类之间的相似度(例如:距离),并且结合两个最相似的聚类。最后,重复步骤2和步骤3直到仅剩下一个单一聚类。相关的算法展示如下:
    在这里插入图片描述

    在执行任何聚类之前,需要使用距离函数确定包含每个点之间距离的邻近矩阵。然后,更新矩阵以显示每个集群之间的距离。下面三个方法的不同之处在于如何测量每个集群之间的距离。

    Single linkage 最短距离

    在single linkage 层次聚类中,两个聚类之间的距离是通过在属于每个聚类中的两个点的最短的距离来定义的。例如,聚类”r” 和”s”之间的距离等于图上面两个最近点之间的距离,即那个箭头的长度。
    在这里插入图片描述
    Complete linkage

    在complete linkage 层次聚类中,两个聚类之间的距离定义为每个聚类中两个点之间的最长距离。例如,聚类”r” 和”s”之间的距离等于它们最远的两个点的长度,即下图中那个箭头的长度。
    在这里插入图片描述
    Average linkage

    在average linkage层次聚类中,两个聚类之间的距离定义为一个聚类中每个点到另一个聚类中每个点之间的平均距离。例如,集群”r”和”s”之间的距离等于每个箭头将一个集群的点连接到另一个集群的点之间的平均长度。
    在这里插入图片描述
    Ward linkage

    Ward’s 的方法旨在最大程度地降低总的集群内的方差。在每一步中,将集群间距离最小的一对集群合并。换句话说,它以最小化与每个集群相关的损失的方式来形成集群。在每个步骤中,考虑每个可能的集群对组合,并将合并之后信息损失(information loss)增加最小化的两个集群合并。这里信息损失是由Ward根据 error sum-of-squares criterion (ESS)定义的。ESS不明白的可以google或者百度哈。

    Agglomerative Clustering 对象使用了一种从下往上的方法来展示分层聚类:每个观测值开始于它自己的聚类,并且聚类依次合并在一起。链接标准决定了用于合并策略的度量:

    在sklearn中有相应的API可以直接调用:

    class sklearn.cluster.AgglomerativeClustering(n_clusters=2, *, affinity=‘euclidean’, memory=None, connectivity=None, compute_full_tree=‘auto’, linkage=‘ward’, distance_threshold=None, compute_distances=False)

    Parameters:

    N_clusters: int or None, default=2, 需要找到的聚类的数量。

    Affinity: str or callable, default=’euclidean’

    用来计算linkage(连接)的度量,欧式距离,L1,L2,manhattan, cosine,或者precomputed等。如果linkage这个参数选择的是 “ward”,那么这里只能使用’euclidean’欧氏距离。

    Connectivity: array-like, default=None

    连接矩阵。为每个样本定义遵循给定数据结构的相邻样本。
    Compute_full_tree: ‘auto’ or bool, default=’auto’

    在n_clusters处早停树结构。在和样本数量相比,聚类数量不小的情况下,非常有助于减少计算时间。

    Linkage:{‘ward’,’complete’,average’,’single’}, default=’ward’

    在计算距离时使用到的Linkage方法。

    使用的连接标准。这个连接标准决定了在不同的observation之间使用哪个距离计算方式。该算法将会合并那些最小化该标准的聚类对。

    ‘ward’:最小化要合并的集群的方差(在这种场景下类似于k-means 目标函数,但是采用了一个聚集的分层方法)。

    ‘average’:使用两组中每个观测值(observations)的距离平均值。

    ‘complete’ or ‘maximum’ linkage:使用两组的所有观测值(observations)之间的最大距离。

    ‘single’ : 使用两组的所有观测值(observations)之间的最小距离。
    在这里插入图片描述
    Distance_threshold: float, default=None

    高于这个distance_threshold的linkage distance,那些cluster 就不会被合并,低于则被合并。

    Compute_distances: bool, default=False

    即使没有使用distance_threshold,也要计算clusters之间的距离。这可以用进行树状图可视化,但是会带来计算和内存的开销。

    Attributes

    N_clusters: int,聚类的数量。

    Labels_: ndarray of shape(n_samples), 每个点的标签。

    N_leaves_:int,分层聚类中叶子的数量。

    N_connected_components_:int, 图中估计的已连接成分。

    Children_: 非叶节点的子节点。

    Distances_: 子节点中对应位置的节点之间的距离。

    自带的案例:

    from sklearn.cluster import AgglomerativeClustering
    import numpy as np
    X = np.array([[1, 2], [1, 4], [1, 0],
                  [4, 2], [4, 4], [4, 0]])
    clustering = AgglomerativeClustering().fit(X)
    
    AgglomerativeClustering()
    clustering.labels_
    
    plt.scatter(X[:,0],X[:,1],c=clustering.labels_,cmap='viridis')
    

    分类的结果:
    在这里插入图片描述
    Plot Hierarchical Clustering Dendragram:

    import numpy as np
    
    from matplotlib import pyplot as plt
    from scipy.cluster.hierarchy import dendrogram
    from sklearn.datasets import load_iris
    from sklearn.cluster import AgglomerativeClustering
    
    
    def plot_dendrogram(model, **kwargs):
        # Create linkage matrix and then plot the dendrogram
    
        # create the counts of samples under each node
        counts = np.zeros(model.children_.shape[0])
        n_samples = len(model.labels_)
        for i, merge in enumerate(model.children_):
            current_count = 0
            for child_idx in merge:
                if child_idx < n_samples:
                    current_count += 1  # leaf node
                else:
                    current_count += counts[child_idx - n_samples]
            counts[i] = current_count
    
        linkage_matrix = np.column_stack([model.children_, model.distances_,
                                          counts]).astype(float)
    
        # Plot the corresponding dendrogram
        dendrogram(linkage_matrix, **kwargs)
    
    
    iris = load_iris()
    X = iris.data
    
    # setting distance_threshold=0 ensures we compute the full tree.
    model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)
    
    model = model.fit(X)
    plt.title('Hierarchical Clustering Dendrogram')
    # plot the top three levels of the dendrogram
    plot_dendrogram(model, truncate_mode='level', p=3)
    plt.xlabel("Number of points in node (or index of point if no parenthesis).")
    plt.show()
    

    在这里插入图片描述

    展开全文
  • 层次聚类和固定宽度聚类

    千次阅读 2015-05-05 23:06:44
    //固定宽度聚类,发生在每一个节点上,对本地数据聚类。//固定宽度聚类创建一个固定半径(宽度)的超球面簇集合。//首先,随机选择任何数据点作为第一个以w为半径的簇的中心。//通常,以欧式距离计算当前这个簇的...

    以下是头文件:

     <pre name="code" class="cpp">#ifndef WSNHSCDA_H
    #define WSNHSCDA_H
    
    #include "common.h"
    
    //凡需要计算两个向量欧氏距离的类,都包含此类
    class eucideanDistanceClass
    { 
    public:
    	static double eucideanDistance( const vector<double>& f1, const vector<double>& f2 ); //计算向量之间的欧氏距离
    };
    
    
    // 测量得到的数据向量,标示一个测量值。
    // 每隔一段时间,传感节点进行测量,一个测量值有很多特征值。
    // 此类保存一次取样得到的数据。
    class dataSample{
    public:
    	dataSample():type(0)
    	{
    	
    	};
    	void operator()( dataSample & a)
    	{
    		cout<<"type = "<<a.type<<":   ";
    		vectorPrint(a.features);
    	};
    	dataSample &operator=(const dataSample& other)
    	{
    		this->type = other.type;
    		this->features = other.features;
    		return *this;
    	}
    	unsigned int size()
    	{
    		return features.size();
    	};
    	double push_back( double val )
    	{
    		features.push_back(val);
    	};
    	double & operator[](unsigned int i)
    	{
    		return features[i];
    	};
    public:
    	unsigned int type;
    	vector<double> features;
    };
    
    // 簇的总结:簇中所有向量的线性和,数据向量的个数,簇ID。
    // 由于簇要进行融合和传递,融合后还是一个簇总结,所以还需要保存节点ID和融合之前的簇的ID。
    // 此类方便于簇总结传递的管理。
    class clusterSample  
    {
    public:
    	clusterSample():featuresNum(0),clusterID(0),sensorID(0),isMerged(0)
    	{
    		return;
    	};
    	void featuresUpdate(const clusterSample &cS ,unsigned int num = 1 );//用于融合
    	void featuresUpdate(const dataSample &dS ,unsigned int num = 1 );//用于聚类
    	void operator()(clusterSample & cS)
    	{
    		cout<<"ID: "<<cS.clusterID<<" featuresNum: "<<cS.featuresNum<<" ";
    		vectorPrint<double>(cS.featuresAvg);
    	};
    public:
    	bool isMerged;
    	vector<double> featuresAvg;
    	vector<double> featuresSum;
    	unsigned int featuresNum;
    	unsigned int clusterID;//用于标示新的簇,簇ID
    	unsigned int sensorID;//用于标示新的簇,产生这个簇的节点ID
    	vector<clusterSample> mergeClusters;//仅仅用于簇的融合。保存融合之前簇的信息。
    private:
    	void featuresAvgUpdate(unsigned int size); 
    private:
    	class eucideanDist :public eucideanDistanceClass
    	{
    	
    	};
    };
    
    // 每个时间窗口的得到n个测量值。
    // 在每一个节点上需要对测量值进行固定宽度聚类。
    // 操作一个节点上的簇集合。包含原始的数据和簇信息。
    // 此类方便节点自己管理自己的簇集合和子节点发送来的簇总结。
    // 封装了关于节点对簇操作的所有逻辑,即是以节点为单位的。
    class dataCluster  
    {
    public:
    	dataCluster(vector<dataSample> & a, unsigned int sensorID = 0):dataSet(a),nodeID(sensorID)
    	{
    		return;
    	}; 
    	void fixedWidthCluster(double width);//对自身数据进行聚类
    	unsigned int size()
    	{
    		return dataSet.size();
    	};
    public:
    	static unsigned int clusterCount; //记录簇的个数
    	vector<dataSample> dataSet;//节点自身的数据
    	vector<clusterSample> clusters;//节点根据自身的数据,构造出的簇集合
    private:
    	void normalize();
    	class eucideanDist :public eucideanDistanceClass
    	{
    	
    	};
    	unsigned int nodeID;
    protected:
    	dataCluster()
    	{
    	
    	};//为sensorNode单独构造的缺省构造函数
    	friend class sensorNode;
    };
    
    //由于KNN算法结构比较复杂
    //需要在这里对KNN算法内容进行封装
    //仅仅需要在这个类里面封装的是KNN算法的逻辑部分
    //KNN算法步奏描绘如下:
    //1、每一个clusterSample包含了一个特征值的向量。
    //2、对于簇集合中的每一个簇,计算其他所有簇和这个簇的距离。
    //3、根据前K个距离,计算平均簇间距离。
    //4、并返回由前K个值算出的均值组成的向量。
    class KNNClass  
    {
    public:
    	KNNClass(vector<clusterSample> clusters,unsigned int k):clusters(clusters),k(k),AVGICD(0.0),SDICD(0.0)
    	{
    		dstMtrx.reserve(clusters.size());
    	};
    	double getAVGICD( )
    	{
    		return AVGICD; 
    	};
    	double getSDICD()
    	{
    		return SDICD; 
    	};	
    	void creatDistanceMatrix( );
    	vector<double> getICD()
    	{  
    		return ICD;
    	};
    private:
    	void cnstrctICD();
    	void calAVGICD();
    	void calSDICD();
    private:
    	class eucideanDist:public eucideanDistanceClass
    	{
    	
    	};
    	const unsigned int k;
    	vector<clusterSample> clusters;
    	vector<vector<double> > dstMtrx;
    	vector<double> ICD;
    	double AVGICD;
    	double SDICD;
    };
    
    // 在基站上进行KNN异常检测。
    // 基站自己并不搜集数据,所以将dataCluster dC一项作为。
    class BSNode 
    {
    public:
    	BSNode(unsigned int nodeID = 0):nodeID(nodeID)
    	{ 
    	
    	};
    public:
    	/*保存来自各个子节点的簇集的集合。以便于操作来自多个节点的簇集合。此时二维的。
    	*第一维是各个节点。第二维是簇集合。
    	*/
    	vector<dataCluster> clustersSet;
    	vector<clusterSample> dataSet;//将二维的来自不同节点的数据融合变为为一维的节点自身的数据
    	const unsigned int nodeID;
    private:		
    	void anormalyDetectKNN(double anorm,unsigned int k);
    private:	
    	class eucideanDist:public eucideanDistanceClass
    	{
    	
    	};
    	//保存被检测出异常的簇
    	vector<clusterSample> clustersAnormal;
    };
    
    // 基站和节点是is a的关系。
    // 每一个节点都是一个微型的基站。
    // 1、搜集数据
    // 2、对数据进行聚类
    // 3、将聚类结果送到一跳父亲节点
    // 4、需要对来自子节点的簇进行融合
    // 5、需要进行异常检测
    class sensorNode :private BSNode
    {
    public:
    	sensorNode(dataCluster &a,unsigned int nodeID):BSNode(nodeID)
    	{ 
    		dC = a; 
    	};
    	void clusterMerge(double);
    	void anormalyDetect(double anorm);
    private:
    	//继承来自于基站类的数据成员
    	//保存来自各个子节点的簇集的集合。以便于操作来自多个节点的簇集合。
    	//vector<dataCluster> clustersSet;
    	//自己节点上的数据
    	dataCluster dC;
    	class eucideanDist:public eucideanDistanceClass
    	{
    	
    	};
    };
    
    
    void WSNHSCDATESTCPP();
    
    #endif

    
    
    以下是cpp文件:

    <pre name="code" class="cpp">#include "wsnHsCDA.h"
    
    
    unsigned int dataCluster::clusterCount = 0; 
    
    //计算特征量之间的欧氏距离
    double eucideanDistanceClass::eucideanDistance( const vector<double>& f1, const vector<double>& f2 )
    {
    	vectorPrint(f1);
    	vectorPrint(f2);
    	assert( f1.size() == f2.size() );	
    	double dist = 0.0;
    	for( vector<double>::size_type i = 0; i < f1.size(); i++ )
    	{
    		dist += pow(f1[i]-f2[i],2); 
    	}
    	return sqrt(dist);
    }
    
    //固定宽度聚类,发生在每一个节点上,对本地数据聚类。
    //固定宽度聚类创建一个固定半径(宽度)的超球面簇集合。
    //首先,随机选择任何数据点作为第一个以w为半径的簇的中心。
    //通常,以欧式距离计算当前这个簇的中心和下一个待聚类数据向量的距离。
    //如果这个距离小于W,这个数据向量就属于这个簇,然后更新中心点。
    //如果距离大于w,就以这个数据向量为新的中心,构造一个新的簇。
    void dataCluster::fixedWidthCluster(double width)
    {
    	bool found = false;
    	clusterSample cs;
    	cs.featuresUpdate(dataSet[0]);
    	cs.clusterID = clusterCount;//对于新建立的簇要分配其簇ID
    	cs.sensorID = nodeID;//对于新建立的簇要分配其节点ID
    	dataSet[0].type = cs.clusterID;
    	clusters.push_back(cs); 
    	for( vector<dataSample>::size_type countD = 1; countD < dataSet.size(); countD++ ) // 遍历数据集
    	{	
    		found = false;
    		 for(vector<dataSample>::size_type countC = 0; countC < clusters.size(); countC++ )//遍历簇集
    		 {  
    			 if( eucideanDist::eucideanDistance( dataSet[countD].features,clusters[countC].featuresAvg ) < width )//加入类别
    			 { 
    				cout<<"*****dis is: "<<eucideanDist::eucideanDistance( dataSet[countD].features,clusters[countC].featuresAvg )<<endl;
    				clusters[countC].featuresUpdate(dataSet[countD]);
    				dataSet[countD].type = countC;
    				found = true;
    				break;
    			 }
    		 } 
    		 if( !found )
    		 {
    			 cout<<"not found :";
    			 vectorPrint(dataSet[countD].features);
    			 clusterSample cs;
    			 cs.featuresUpdate(dataSet[countD]);
    			 cs.featuresNum = 1;
    			 cs.clusterID = ++clusterCount;			 
    			 cs.sensorID = nodeID;
    			 dataSet[countD].type = cs.clusterID;
    			 clusters.push_back(cs); 
    		 }
    	}
    	return;
    }
    
    //簇的融合
    //当两个簇相似,就需要对其进行融合。
    //如果以簇中心距离计算的两个簇的簇间距离小于阈值w,我们就说这两个簇相似。
    //如果有两个簇是相似的,就由这两个簇产生第三个簇.
    //这个簇的中心是之前两个簇中心的均值,这个簇的数据向量的个数是之前两个簇的中和。
    //这个融合的过程递归的执行,直到再也没有融合的可能
    //操作对象:以clusterSample为数据的成员的clusters簇集合
    //输出:簇集合的扩展
    //临时变量后面接有数字标示,没有数字标示,且在方法中没有声明定义的是类成员变量。
    void sensorNode::clusterMerge(double w)
    {
    	//首先将子节点簇集进行融合
    	for( vector<dataCluster>::size_type countCSet1 = 0; countCSet1 < clustersSet.size(); countCSet1++ )//从第一个节点开始上的簇集开始
    	{
    		dataCluster dC1 = clustersSet[countCSet1];//取出第一个节点上的簇集
    		for( vector<clusterSample>::size_type countCSm1 = 0; countCSm1 < dC1.clusters.size(); countCSm1++ )//从第一个簇开始
    		{
    			clusterSample cS1 = dC1.clusters[countCSm1];//取出第一个簇集上的簇
    			if( true == cS1.isMerged )//此簇已经融合,进入到下一个簇
    			{
    				continue;
    			}
    			for( vector<dataCluster>::size_type countCSet2 = countCSet1 +1; countCSet2 < clustersSet.size(); countCSet2++)//从下一个节点开始
    			{
    				dataCluster dC2 = clustersSet[countCSet2];//取出簇集合
    				for(vector<clusterSample>::size_type countCSm2 = 0; countCSm2 < dC1.clusters.size(); countCSm2++)
    				{
    					clusterSample cS2 = dC1.clusters[countCSm2]; //取出簇
    					if( true == cS2.isMerged )
    					{
    						continue;
    					}
    					if( eucideanDist::eucideanDistance(cS1.featuresAvg,cS2.featuresAvg) < w )
    					{
    						clusterSample cs;
    						cs.featuresUpdate(cS1,cS1.featuresNum);//将两个簇sample合并为一个簇
    						cs.featuresUpdate(cS2,cS2.featuresNum);
    						dC.clusters.push_back(cs);//并将此簇加入到当前节点的簇集合中
    						cS1.isMerged = true;
    						cS2.isMerged = true;
    					}
    				}
    			}
    		}
    	}
    	//然后,融合到自己的簇集合	
    	//最后在遍历子节点发来的簇集的过程中,
    	//对没有融合的所有簇,都添加进节点自身的簇集合dC
    	for( vector<clusterSample>::size_type countCS3 = 0; countCS3 < dC.clusters.size(); countCS3++ )//从第一个簇开始(dataCluster dC)
    	{
    		if( true == dC.clusters[countCS3].isMerged )
    		{
    			continue;
    		}
    		for( vector<dataCluster>::size_type countCSet3 = 0; countCSet3 < clustersSet.size(); countCSet3++)//从第一个节点开始
    		{
    				dataCluster dC3 = clustersSet[countCSet3];//取出簇集合
    				for(vector<clusterSample>::size_type countCSm3 = 0; countCSm3 < dC3.clusters.size(); countCSm3++)
    				{
    					if( true == dC3.clusters[countCSm3].isMerged )//已经融合过的不再融合
    					{
    						continue;
    					}
    					if( eucideanDist::eucideanDistance(dC.clusters[countCS3].featuresAvg,dC3.clusters[countCSm3].featuresAvg) < w )
    					{
    						clusterSample cs;
    						cs.featuresUpdate(dC.clusters[countCS3],dC.clusters[countCS3].featuresNum);//将两个簇sample合并为一个簇
    						cs.featuresUpdate(dC3.clusters[countCSm3],dC3.clusters[countCSm3].featuresNum);
    						dC.clusters.push_back(cs);//并将此簇加入到当前节点的簇集合中
    						dC.clusters[countCS3].isMerged = true;
    						dC3.clusters[countCSm3].isMerged = true;
    					}
    					else
    					{
    						dC.clusters.push_back(dC3.clusters[countCSm3]);//并将此簇加入到当前节点的簇集合中,并不在融合
    						//那么融合后,此节点的簇集合就是dC中没有被标记isMerged的所有簇
    					}
    
    				}
    		}
    	}
    	return;
    }
    
    //对节点自身的数据进行归一化处理
    void dataCluster::normalize()
    {
    	assert( dataSet.size() ); //确保数据集不为空
    	vector<dataSample> dataSet;
    	vector<double> avg;
    	avg.reserve(dataSet[0].size());
    	vector<double> stdDiv;
    	stdDiv.reserve(dataSet[0].size());
    	for( unsigned int count1 = 0; count1 < dataSet.size(); count1++ )//求出各个特征值在各个特征向量的和。
    	{
    		for( unsigned int count2 = 0; count2 < dataSet[count1].size(); count2++ )
    		{
    			avg[count2] += dataSet[count1][count2];
    		}
    	}
    	for( unsigned int count3 = 0; count3 < avg.size(); count3++ )//求出均值。
    	{
    		avg[count3] /= dataSet.size();
    	}
    	for( unsigned int count4 = 0; count4 < dataSet.size(); count4++ )
    	{
    		for( unsigned int count5 = 0; count5 < dataSet[count4].size(); count5++ )
    		{
    			stdDiv[count5] += pow(dataSet[count4][count5]-avg[count5],2);
    		}
    	}//求出标准方差。
    	for( unsigned int count6 = 0; count6 < stdDiv.size(); count6++ )//求出均值。
    	{
    		stdDiv[count6] = sqrt(stdDiv[count6]);
    	}
    	//归一化。
    	for( unsigned int count1 = 0; count1 < dataSet.size(); count1++ )//求出各个特征值在各个特征向量的和。
    	{
    		for( unsigned int count2 = 0; count2 < dataSet[count1].size(); count2++ )
    		{
    			dataSet[count1][count2] = (dataSet[count1][count2] - avg[count2])/stdDiv[count2];
    		}
    	}
    }
    
    void clusterSample::featuresAvgUpdate(unsigned int size )
    {
    	if( featuresAvg.size() != 0 )
    	{
    		 for( vector<double>::size_type i = 0; i < featuresSum.size();i++ )
    			 featuresAvg[i] = featuresSum[i]/featuresNum;
    	}
    	else{
    		for( vector<double>::size_type i = 0; i < size; i++ )
    			 featuresAvg.push_back(featuresSum[i]/featuresNum);
    	}
    	return;
    }
    
    void clusterSample::featuresUpdate(const clusterSample &cS,unsigned int num  )
    {
    	featuresNum += num;
    	if( featuresSum.size() != 0 )
    	{
    		 for( vector<double>::size_type i = 0 ; i <  featuresSum.size(); i++ )
    			 featuresSum[i] = featuresSum[i]+cS.featuresAvg[i];
    	}
    	else{
    		for( vector<double>::size_type i = 0; i < cS.featuresAvg.size(); i++ )
    			 featuresSum.push_back(cS.featuresAvg[i]);
    	}
    	mergeClusters.push_back(cS);
    	featuresAvgUpdate(cS.featuresAvg.size());
    	return;
    }
    void clusterSample::featuresUpdate(const dataSample &dS ,unsigned int num  )
    {
    	featuresNum += num;
    	if( featuresSum.size() != 0 )
    	{
    		 for( vector<double>::size_type i = 0 ; i <  featuresSum.size(); i++ )
    			 featuresSum[i] = featuresSum[i]+dS.features[i];		 
    	}
    	else{
    		for( vector<double>::size_type i = 0; i < dS.features.size(); i++ )
    			 featuresSum.push_back(dS.features[i]);
    	}
    	featuresAvgUpdate(dS.features.size());
    	return;
    }
    
    void KNNClass::calAVGICD()
    {
    	unsigned int count = 0;
    	for( vector<double>::size_type countdM1 = 0; countdM1 < dstMtrx.size(); countdM1++ )
    	{
    		for( vector<clusterSample>::size_type countdM2 = 0; countdM2 <= dstMtrx[countdM1].size(); countdM2++ )
    		{
    			AVGICD += dstMtrx[countdM1][countdM2];
    			count++;
    		}
    	}
    	AVGICD /= (2*count); 
    }
    void KNNClass::calSDICD()
    {
    	unsigned int count = 0;
    	for( vector<double>::size_type countdM1 = 0; countdM1 < dstMtrx.size(); countdM1++ )
    	{
    		for( vector<clusterSample>::size_type countdM2 = 0; countdM2 <= dstMtrx[countdM1].size(); countdM2++ )
    		{
    			SDICD += pow(dstMtrx[countdM1][countdM2] - AVGICD,2);
    			count++;
    		}
    	}
    	SDICD = sqrt( SDICD/(count-1) );
    }
    
    void KNNClass::cnstrctICD( )
    {
    	unsigned temp = ( k > dstMtrx.size() ) ? dstMtrx.size()-1 : k ;
    
    	for( vector<double>::size_type countdM1 = 0; countdM1 < dstMtrx.size(); countdM1++ )
    	{
    		for( vector<clusterSample>::size_type countdM2 = 0; countdM2 <= temp; countdM2++ )
    		{
    			ICD[countdM1] += dstMtrx[countdM1][countdM2];
    		}
    		ICD[countdM1] /= k;
    	}
    }
    
    void KNNClass::creatDistanceMatrix( )
    {
    	for( vector<clusterSample>::size_type countcS1 = 0; countcS1 < clusters.size(); countcS1++ )
    	{
    		for( vector<clusterSample>::size_type countcS2 = countcS1 + 1; countcS2 < clusters.size(); countcS2++ )
    		{
    			dstMtrx[countcS1][countcS2] = dstMtrx[countcS2][countcS1] = 
    				eucideanDist::eucideanDistance(clusters[countcS1].featuresAvg,clusters[countcS2].featuresAvg);
    		}
    		dstMtrx[countcS1][countcS1] = 0.0;
    		sort(dstMtrx[countcS1].begin(),dstMtrx[countcS1].end());
    	}
    	cnstrctICD( );
    	calAVGICD();
    	calSDICD();
    }
    
    //在节点上执行,此处实现在节点上运行的,
    void sensorNode::anormalyDetect(double anorm)
    {
    
    	return;
    }
    
    //在基站上执行。
    //基站上汇聚有全网络搜集的数据
    //以KNN为基础,实现全局异常簇的识别。
    //并以簇为检测单位的一次检测算法。
    //论文中并没有讲明白这个平均簇间距离如何求。
    //也没有说清楚标准方差如何求。
    void BSNode::anormalyDetectKNN(double anorm,unsigned int k)
    {	
    	KNNClass knnobject(dataSet,k);
    	knnobject.creatDistanceMatrix( );
    	//求出所有簇间距离的均值。
    	//求出所有簇间距离的方差。
    	//筛选出异常簇。
    	for( vector<double>::size_type countdM1 = 0; countdM1 < knnobject.getICD().size(); countdM1++ )
    	{
    		 if(  knnobject.getICD()[countdM1] > knnobject.getAVGICD() + anorm*knnobject.getSDICD() )
    			 clustersAnormal.push_back(dataSet[countdM1]);
    	}
    	return;
    }
    
    // 以下实验数据,共计三个簇。
    // 分别为:1,2,3,4;   5,6,7,8;    9,10,11,12.
    // 当width取值为40-100之间时,可以分为三个簇。
    void WSNHSCDATESTCPP()
    {
    	
    	vector<dataSample> dataSet;
    	dataSample d1;
    	d1.features.push_back(1.0); //x
    	d1.features.push_back(2.0); //y
    	dataSample d2;
    	d2.features.push_back(1.1); //x
    	d2.features.push_back(2.1); //y
    	dataSample d3;
    	d3.features.push_back(0.5); //x
    	d3.features.push_back(2.0); //y
    	dataSample d4;
    	d4.features.push_back(1.5); //x
    	d4.features.push_back(2.9); //y
    	dataSet.push_back(d1);
    	dataSet.push_back(d2);
    	dataSet.push_back(d3);
    	dataSet.push_back(d4);
    	dataSample d5;
    	d5.features.push_back(1.0); //x
    	d5.features.push_back(112.0); //y
    	dataSample d6;
    	d6.features.push_back(10.1); //x
    	d6.features.push_back(102.1); //y
    	dataSample d7;
    	d7.features.push_back(0.5); //x
    	d7.features.push_back(132.0); //y
    	dataSample d8;
    	d8.features.push_back(5.5); //x
    	d8.features.push_back(120.9); //y
    	dataSet.push_back(d5);
    	dataSet.push_back(d6);
    	dataSet.push_back(d7);
    	dataSet.push_back(d8);
    	dataSample d9;
    	d9.features.push_back(111.0); //x
    	d9.features.push_back(2.0); //y
    	dataSample d10;
    	d10.features.push_back(121.1); //x
    	d10.features.push_back(32.1); //y
    	dataSample d11;
    	d11.features.push_back(100.5); //x
    	d11.features.push_back(2.0); //y
    	dataSample d12;
    	d12.features.push_back(111.5); //x
    	d12.features.push_back(2.9); //y
    	dataSet.push_back(d9);
    	dataSet.push_back(d10);
    	dataSet.push_back(d11);
    	dataSet.push_back(d12);
    	cout<<"数据集大小为: "<<dataSet.size()<<endl;
    	dataCluster dC(dataSet);
    	cout<<"dataCluster数据集大小为: "<<dC.dataSet.size()<<endl;;
    	dC.fixedWidthCluster(100);
    	for_each(dC.dataSet.begin(),dC.dataSet.end(),dataSample());
    	for_each(dC.clusters.begin(),dC.clusters.end(),clusterSample());
    //下面的测试内容:
    /* 1、首先模拟在各个节点上搜集数据。
     * 2、然后在本地将数据进行聚类。
     * 3、将各个聚类结果发送到(汇聚)到下一个节点,并进行融合。
     * 4、在基站上(最后的节点上)进行KNN异常检测。
     * 5、将异常检测得到的在发送到各个节点。
     * 6、各个节点分别进行异常检测。
     */
    //进行单元测试和集成测试。
    //测试数据如何组织。
    //如何将各个单元合理的
    //模拟各个节点上的数据。
    
    /* 节点对自己的数据进行聚类,并生成簇的集合。
     * 这个聚类结果将在后面用于检测节点上的异常簇。说明在节点上一异常检测是以簇为单位的。
     * 聚类的结果保存在节点上,保存格式如:《簇ID,产生簇的节点ID》
     */
    
    
    /* 将节点上产生的簇的总结发送到下一跳邻居节点。
     * 格式如:《簇的线性和,簇包含向量的个数,簇的ID》
     */
    
    
    /* 将所有簇集合汇聚到一个节点,并进行融合。
     * 形成的新的簇,需包含有融合之前簇的信息。如果这个簇被检测为异常,
     * 就可以追踪到所在节点和原始簇。
     * 融合后,形成一个新的簇集合。
     */
    
    /* 在汇聚节点上,进行KNN异常检测。
     */
    
    
    	//在各个节点上进行异常检测。
    
    
    	return;
    }


    
    

    展开全文
  • 层次聚类算法的python实现

    千次阅读 2015-07-10 10:35:26
    文章给出层次聚类算法的python实现方法,并用《数据挖掘导论》里面的具体数据进行运行,代码如下: from numpy import * from math import * from operator import * def dist(a,b):#a,b is mat c=(a-b)*(a-b).T ...
  • 为了用R来处理网络数据,我们使用婚礼数据集。
  • 随着个人手机和网络的普及,手机已经基本成为所有人必须持有的工具。 根据手机信号再地理空间的覆盖情况结合时间序列的手机定位数据可以完整的还原人群的现实活动轨迹从而得到人口空间分布于活动联系的特征信息。 ...
  • 聚类

    2020-01-20 20:59:14
    聚类 相关概念 1、无监督学习: 无监督学习是机器学习的一种...在人工神经网络中,生成对抗网络、自组织映射和适应性共振理论则是最常用的非监督式学习。 2、聚类聚类是一种无监督学习。聚类是把相似的对...
  • 聚类与神经网络

    千次阅读 2013-12-23 21:16:55
    51 C-均值算法:是动态聚类方法中的一个典型方法。其目的是将一数据集, 按自然密集程度划分成C个聚类,它的准则函数是对所有C个聚类中每个数据到其各自均值的距离平方和的总和为最小。计算距离的最简单形式是欧式...
  • k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量系统聚类法则是系统自己根据数据...其中层次聚类容易受到极值的影响,并且计算复杂速度慢不适合大样本聚类;快速聚类虽然速度快
  • 该方法首先采用自下而上的层次聚类法挖掘线路脆弱性的层次风险,并以电力系统的复杂网络特征为条件属性,以电力系统线路脆弱性为决策属性,建立系统样本决策表;然后采用基于贪婪启发式算法的ID3决策树数据挖掘法,...
  •    k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量  系统聚类法则是系统自己根据数据之间的距离...其中层次聚类容易受到极值的影响,并且计算复杂速度慢不适合大...
  • 聚类算法

    万次阅读 2016-08-04 18:50:00
    一、串行聚类算法 1.1 划分方法(partitioning method) 划分方法首先根据给定要构建划分的数目k创建一个初始划分,然后采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是...
  • 常用的聚类方法

    2019-02-20 22:38:27
    k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量 系统聚类法则是系统...其中层次聚类容易受到极值的影响,并且计算复杂速度慢不适合大样本聚类;快速聚类虽然速度快,但是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,822
精华内容 4,328
关键字:

复杂网络层次聚类