每行和每列的交点处的值表示对应的顶点对之间是否存在边。比如说，在 Medium 和 Twitter 之间有一条边，所以它们的行列交点是 1。类似地，Medium 和 PayPal 之间没有边，所以它们的行列交点是 0.
是的，就是那么简单。克罗内克 δ 函数与两个参数，若何这两个参数相等则返回 1，若何不等，则返回 0.
也就是说，如不雅顶点 i 和 j 已经被放进了同一个聚类，那么δc_i, c_j = 1;不然它们不在同一个聚类，函数返回 0.
除以 2L 将模块性的上限值设置成了 1。模块性接近或小于 0 表示该收集的当前聚类没有效处。模块性越高，该收集聚类成不合集团的程度就越好。经由过程是模块性最大年夜化，我们可以找到聚类该收集的最佳办法。
留意我们必须预定义图的聚类方法，才能找到评估一个聚类有多好的办法。不幸的是，应用暴力计算的方法来测验测验各类可能以寻找最高模块性分数的聚类方法须要大年夜量计算，即使在一个有限大年夜小的样本上也是弗成能的。
组合学(combinatorics)告诉我们对于一个仅有 8 个顶点的收集，就存在 4140 种不合的聚类方法。16 个顶点的收集的聚类方法将跨越 100 亿种。32 个顶点的收集的可能聚类方法更是将跨越 128 septillion(10^21)种;如不雅你的收集有 80 个顶点，那么其可聚类的方法的数量就已经跨越了可不雅测宇宙中的原子数量。
是以，我们必须乞助于一种启发式的办法，该办法在评估可以产生最高模块性分数的聚类上效不雅优胜，并且并不须要测验测验每一种可能性。这是一种被称为 Fast-Greedy Modularity-Maximization(快速贪婪模块性最大年夜化)的算法，这种算法在必定程度上类似于膳绫擎描述的 agglomerative hierarchical clustering algorithm(集聚层次聚类算法)。只是 Mod-Max 并不根据距离(distance)来融合集团，而是根据模块性的改变来对集团进行融合。
下面是其工作方法：
第 1 步请求每个集团对(community pair)至少被一条单边链接，如不雅有两个团砼融合到了一路，该算法就计算由此造成的模块性改变 ΔM。
第 2 步是取 ΔM 出现了最大年夜增长的集团对，然后融合。然后为这个聚类枷⒚鹇的模块性 M，并记录下来。
反复第 1 步和 第 2 步——每一次都融合集团对，如许最后获得 ΔM 的最大年夜增益，然跋文录新的聚类模式及其响应的模块性分数 M。
A_ij 就是指该邻居矩阵中第 i 行、第 j 列的值。
当所有的顶点都被分构成了一个巨型聚类时，就可以停止了。然后该算法会检查这个过程中的记录，然后找到个中返回了最高 M 值的聚类模式。这就是返回的集团构造。
起首初始分派每个顶获得其本身的集团，然后计算全部收集的模块性 M。
更多细节：
集团检测(community detection)是如今图论一一个热点的研究范畴，也存在很多可替代 Modularity-Maximization(尽管很有效，但也出缺点)的办法。
起首，它的集合方法大年夜指定尺寸的小集团开端，逐渐转向越来越大年夜的。这被称为分辨率极限(resolution limit)——该算法不会搜刮特定尺寸以下的集团。另一个挑衅则是超出一个明显波峰的表示，Mod-Max 办法趋势于制造一个由很多高模块化分数构成的「高原」，这有时会导致难以肯定最大年夜分数。
哇!这个过程真是有太多计算了，至少对我们仁攀类而言是如许。图论中存在很多计算难题，经常是 NP-hard 问题——但其也在为复杂体系和数据集供给有价值的看法上具有出色的潜力。Larry Page 就知道这一点，其有名的 PageRank 算法就是完全基于图论的——该算法在赞助谷歌在不到十年之内大年夜创虻公司成长为近乎世界主宰的过程中立下了汗马功绩。
其他算法应用不合的方法来肯定集团。Edge-Betweenness 是一个决裂算法，把所有顶点聚合到一个大年夜集群中。它会持续迭代去除收集中「最不重要」的边沿数据，直到所有顶点都被分开为止。这一过程产生了层级构造，个中类似的顶点在构造中互相接近。
另一种算法是 Clique Percolation，它推敲了图集团之间可能的重叠。而别的一些算法基于图中的随机游动，还有谱聚类(spectral clustering)算法：大年夜邻居矩阵及派生矩阵的特点分化开端。这些办法被应用于特点提取义务，如计算机视觉。
给出每个算法的深刻应用实例超出了本介绍的商量范围。大年夜数据中提取可用信息的有效办法在数十年前照样难以触及的事物，但如今已经成为了异常活泼的研究范畴。
结论
欲望本文能对你有所启发，让你更好地舆解机械若何懂得大年夜数据。将来是高速变革的，个中典范多变更将会由下一代或两代中有才能的技巧所驱动。
就像导语提到的，机械进修是一个异常有前景的研究范畴，个中有大年夜量复杂的问题须要以精确、有效的方法解决。对仁攀类来说易如反掌的义务在由机械完成的时刻就须要立异性的解决筹划。
在此范沉闼楝我们如有大年夜量的义务须要完成，无论谁为下一?重大年夜冲破供献力量，无疑都邑获得大方的回报。或许正在浏览这篇文┞仿的某小我就会成为下一?强大年夜的算法创造者?所有巨大年夜设法主意都是大年夜零开端的。
【编辑推荐】
- 若何构建用于检测信用卡欺骗的机械进修模型？
- 机械进修的本质就是数理统计？谜底可能没这么简单
- 5个开源Python库，让机械进修更简单
- 机械进修大年夜用户社交媒体资估中窥得的五种机密
- 机械进修难在哪
推荐阅读
一、概述当前机械人广泛应用于焊接、装配、搬运、喷漆及打磨等范畴，义务的复杂程度赓续增长，而用户对产品的质量、效力的寻求越来越高。在这种情势下，机械人的编程方法、编程效力和质量>>>详细阅读
本文标题：机器理解大数据的秘密：聚类算法深度详解
地址：http://www.17bianji.com/lsqh/34643.html
1/2 1
网友点评
精彩导读
科技快报
品牌展示