前言

其实读完斯坦福的这本《互联网大规模数据挖掘》，让我感觉到，什么是人工智能？人工智能就是更高层次的数据挖掘。机器学习是人工智能领域内的重要技术，同样也是在数据挖掘中的常用方法；数据挖掘中的去寻找频繁项集、相似项和基于数据挖掘的推荐系统，也是人工智能领域的重要组成部分。但区别在于，我们现在所讲的人工智能对数据的利用深化了，自然语言处理、计算机视觉、语音识别，这些传统数据挖掘中没有的技术，也被包含在了人工智能的范畴中，但其实说到底，这些技术也都还是受数据驱动的，称其为字面意义上的『数据挖掘』，也无不妥。

数据挖掘的基本概念

最为广泛接受的定义是，数据挖掘是数据『抽象模型』的发现过程。

在建模方面最重要的方向有两个，分别是：统计建模、机器学习

统计建模是统计模型的构建过程，而这个统计模型指的就是可见数据所遵从的总体分布，比如我们有了一系列数字，统计学家可能会判定这些数字符合高斯分布，并利用公式来计算该分布最有可能的参数值。统计建模的要点之一是忽略噪声。

很多数据挖掘方法中也使用了机器学习算法，机器学习的实践者将数据当成训练集来训练某类算法。机器学习擅长的典型场景是人们对数据中对的寻找目标几乎一无所知，比如，我们并不清楚到底是影片中的什么因素导致某些观众喜欢或者厌恶该影片。另一方面，当挖掘的目标能很直接的描述时，利用人的知识加上简单的判别过滤方法，效果也许会更好。

绝大多数数据建模方法可以描述为以下三种做法之一：

• 数据可以通过其可能遵从的模型来建模（最重要）
• 对数据进行简洁的近似汇总描述
• 从数据中抽取出最突出的特征来代替数据并将剩余内容忽略

寻找模型就是前面提到统计建模和机器学习方法。

在《浅谈搜索引擎基础》中介绍过的PageRank算法就是一种数据汇总形式，在这种形式的Web网页重要性挖掘中，Web的整个复杂结构可以由每个页面的PageRank归纳而成，一个Web页面的PageRank值也即一个Web结构上的随机游走模型在任意时刻处于该页的概率。

另一种重要的数据汇总形式是聚类，数据被看成是空间下的点，空间中相邻近的点将被赋予相同的类别。这些类别本身也会被概括的表示，比如通过类别质心及类别中点到质心的平均距离来描述。

然后是特征抽取，重要的特征抽取类型有两种，一个是频繁项集、一个是相似项。

频繁项集适用于多个小规模项集组成的数据，举个例子，比如我们发现某些商品会被顾客同时购买，在这种情况下，经常被同时购买的商品就组成频繁项集，当然不经常的就仅被称为项集。

另一个是相似项，很多时候，数据往往看上去相当于一系列集合，我们的目标是寻找那些共同元素比例较高的集合对。

这里简单介绍一下邦弗朗尼原理：假定人们有一定量的数据并期望从该数据中找到某个特定类型的事件。即使数据完全随机，也可以期望该类型事件会发生。

也就是说，随着数据规模的增长，任何随机数据往往都会有一些不同寻常的特征，这些特征看起来很重要，但是实际上并无卵用。

换句话说，在考察数据时，如果将某些对象视为数据的有趣特征，而这些对象中许多实例都可能会在随机数据中出现，那么这些显著的特征就不可依赖。对于那些实际中并不充分罕见的特征来说，上述观察结果限制了从这些数据特征中进行挖掘的能力。

相似项发现

一个基本的数据挖掘问题是从数据中获得『相似』项，其实这里说的『相似』更接近『重复』。

在前面的几篇文章中，我们讲过可以用TF-IDF等向量空间模型、概率检索模型以及LDA等来来判定两篇文章是否相似；如果要去重，也讲过Shingling算法和Simhash。相似和去重所解决的问题其实类似，只是相似度大小的问题。

在《浅谈搜索引擎基础》中，讲优化的Shingling算法的时候说：『优化后的Shingling算法不再采用一个哈希函数对所有的单词片段进行哈希，而是随机选择m种哈希函数，对所有的原始单词片段进行哈希，但是我们只保留每种哈希函数所有的结果里面，最小的那个，这样文档就能被转换为固定大小m的最小哈希签名』

这里先详细讲一下最小哈希签名的由来。

首先是集合的矩阵表示：

四个集合的矩阵表示

这叫做集合的特征矩阵，矩阵不同的列对应不同的集合，所有的行对应全集，如果r行中的元素存在于列c对应的集合中，那该位置就为1，否则为0，当然特征矩阵只是便于理解，并非真正的数据存储方式。

然后开始讲最小哈希，想这样一种情况，我们知道所有的行对应全集，给定一种哈希函数，如果从上到下，全集元素的排列顺序与元素哈希值从小到大的顺序相同，那是不是对于每个集合，也即每个列，从上到下，所找到的第一个1，就是该集合所有元素中，哈希结果最小的那个，也就是这种哈希函数下，该列的最小哈希。

那如果对上面的过程进行M次，也即选择M种不同的哈希函数，那我们就能得到一个M行的最小哈希签名矩阵，不同列对应不同集合，不同行对应不同的哈希函数，每个位置就是列对应的集合在行对应的哈希函数下的最小哈希。

当然我们不用对每个哈希函数，都将全集排一次序，只要始终记录最小值即可。

然后有了最小哈希签名矩阵，我们就可以依此来计算Jaccard相似度了，需要注意的是，通过最小哈希签名矩阵计算出来的Jaccard相似度，只是真实Jaccard相似度的估计值（但如果两列真实Jaccard相似度为0，那最小哈希签名矩阵总能估计出正确的结果）。

然后介绍文档的局部敏感哈希算法（Locality-Sensitive Hashing，LSH）

如果文档数量过大，即便是利用最小哈希签名矩阵的方式可以将大文档压缩成小的签名并同时保持文档对之间的预期相似度，计算起来仍然非常困难。当然，如果我们一定要计算每对文档的相似度，即便采用分布式计算的方法减少实耗时间，总计算量也是不会减少的。不过，如果我们只需要得到那些相似度超过某个下界的文档，采用LSH，就可以降低计算量，提高计算速度。

LSH的一个一般性做法是对目标项进行多次哈希处理，使得相似项会比不相似项更可能哈希到同一桶中。然后将至少有一次哈希到同一桶中的文档看成是候选对，我们只会检查候选对之前的相似度。

《浅谈搜索引擎基础》中讲过SimHash，SimHash在最后比较的那一步，就采用了LSH的思想，就像里面讲过的，将原串四等分，分组聚类，聚类其实基本等价于哈希到桶，这样就可以减少需要比较的文档数目。

LSH也可以应用于目标项的最小哈希签名矩阵，思路与SimHash类似。如果我们拥有目标项的最小哈希签名函数，那么一个有效的哈希处理方法是将签名矩阵划分成b个行条，也就是分成b部分，每个行条由r行组成。对每个行条，存在一个哈希函数能够将行条中的每r个整数组成的列向量映射到某个大数目范围的桶中，对不同行条我们使用独立的b个桶，不会出现不同行条哈希到同一个桶中的情况。

显而易见的，如果签名矩阵的两列越相同，那么在多个行条中的向量相等的可能性也越大。这里给出一张图：

横轴是文档的Jaccard相似度，纵轴是成为候选对的概率。LSH可能出现伪反例，考虑这样一种情况，两列，只有b个分量不同，但这b行就恰巧均匀分布在b个行条之中，那它就成不了候选项。

我们前面提到过很多距离，比如欧氏距离、Jaccard距离、余弦距离、编辑距离，还有用于描述两个向量中不同分量个数的海明距离，那这里要说一下，什么叫做距离测度：

• 距离非负
• 只有点到自身的距离为0，其他距离都大于0
• 距离具有对称性
• 满足三角不等式，即两边之和大于第三边

接下来介绍几种更高相似度场景下的方法。首先是相等项，相等项其实较好处理，有这么几种方法，比如我们可以直接对整篇文档进行哈希，也可以先对文档头部的少许字符进行哈希处理，然后只对进入同一桶的文档进行比较，或者对所有的文档选择某些固定随机点，并且依据此来进行哈希处理。

然后是另一种更复杂的问题，就是我们怎样在大规模集合中，发现所有具有很高Jaccard相似度的集合对，比如大于0.9

为了简化问题，我们将全集中的所有元素按照某个固定次序排列，然后通过以该顺序列出其元素来表示任一集合。对于这样的串，任一元素的出现次数都不超过一次，而且，如果两个元素出现在两个不同的串中，那么这两个元素在两个串中的先后次序相同。

对于普通的文档，可以先将文档变成shingle集合，然后分配一个固定的shingle排序方法，并最终将每篇文档表示成该次序下的shingle列表。

为了解决上面的问题，我们可以基于长度进行过滤，将所有字符串按照长度排序，然后将每个字符串s与其在列表中后面不远的另一个字符串t进行比较。假定两个字符串Jaccard距离的下界是J，那其实s与t的Jaccard相似度的最多为Ls/Lt，L是对应串的长度。如果满足Jaccard相似度J的要求，那么Ls/Lt就必须大于等于J，或者说，只挑选Ls/Lt大于等于J的两个串进行比较。

除了长度，我们还可以像搜索引擎那样建立索引，我们可以为每个字符串s，选择前p个符号组成的前缀，在该前缀中每一个符号的索引中加入字符串s。

我们还可以额外使用位置信息等，这里就不详细说了。

数据流挖掘

我们通常所理解的数据挖掘都假定是从数据库中进行挖掘，也就是说，如果真的需要数据的时候，所有的数据都可用。

但是还存在另一种假设：数据以一个或多个流的方式到来，如果不对数据进行及时的处理或者存储，数据将会永远丢失。此外，我们假定数据到来的速度实在是太快，以致将全部数据存在传统数据库并在我们选定的时间进行交互是不可能的。

数据流处理的每个算法都在某种程度上包含流的汇总过程，也即从流中抽取有用样本，过滤大部分不想要的元素。

一种很常见的对流进行汇总的方法是只观察一个定长的窗口，该窗口由最近的n个元素组成，其中n是某个给定值，通常较大。

流数据看起来很抽象，这里举几个例子，比如传感器数据，我们有100万个传感器，每个传感器都以每秒10次的速率传回数据；比如图像数据，卫星往往每天会给地球传回多个太字节的图像流数据；比如互联网及Web流量，互联网中的交换节点，Web网站收到的请求。

流查询

对流进行查询主要有两种方式，其中的一种称为固定查询。固定查询永远不变的执行并在适当的时候产生输出结果。比如对于温度传感器，当温度超过25摄氏度时输出警报，该查询只依赖最近的那个流元素。又或者，输出最近24次读数的平均值，这样只固定查询最近24个元素。

另一种查询被称为ad hoc查询，它对于当前某个或多个流仅提交一次。什么是ad hoc查询呢，ad hoc 允许终端用户自己去建立特定的、自定义的查询请求，通常是临时的，有特殊目的的，与之对应的是参数化的查询，参数化查询生成的执行计划可以重用，而ad hoc 生成的执行计划不能重用，每次都需要compile一次，消耗相当多的CPU资源。

通常应对的方式是在工作存储器上保存每个流的滑动窗口。一个滑动窗口可以是最近到达的n个流元素，也可以是在最近t个时间单位中到达的所有元素。

流抽样

一个需要解决的一般性问题是从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。

考虑这样一个问题，如果我们要回答查询：在过去一个月中典型用户所提交的重复查询的比例是多少？，并假设我们只希望存储大概1/10的流元素。

一种很显然的做法就是对每个搜索查询产生一个随机数，抽取1/10的查询问句，然后计算其中重复的比例，但这是有问题的。可以证明，以这种方法，无论如何都得不到正确的结果，因为出现次数不同的查询语句，被抽取到的概率也不同。

为了得到正确答案，我们必须要挑出1/10的用户并将他们的所有搜索查询放入样本中。我们可以将用户哈希到编号为0~9的10个桶中的一个去，取这一个桶的用户作为样本，当然桶中并不真正保存用户，实际上，桶中没有任何数据，对任何用户也不需要存储对其的结果，只要当该用户新的查询到来时，即时对其进行哈希，就可以判定该用户是否在指定的用户列表中，也即该条查询是否该被抽样出来。

更一般化的，我们的流由一系列n字段构成，这些字段的一个子集称为关键字段，我们对样本的选择也基于它来进行。假定抽样之后的样本规模为a/b，那么就可以将每个元组的关键字段哈希到b个桶中的一个，然后将其中a个桶中的元组放入样本中，就得到了a/b的样本。

还有另一个问题，如果我们选定了1/10的用户，那么随着事件的推移，他们的数据也会越来越多，而且一些新的用户也会进入到用户列表中，而存储空间是有限的，所以我们选择的比例要随事件的推移而降低。

流过滤

一个常见的流数据处理方式是选择，或称为过滤，这里主要会讲布隆过滤。

还是先举一个例子，如果我们会接收邮件流数据，但只有10亿个白名单的邮箱的邮件才对我们有价值，其他邮箱的邮件被认为是垃圾邮件，那我们怎样才能过滤掉这些邮件呢。难道每封邮件过来都要先进行10亿次比较？

我们先考虑只有一封邮件的情况，我们知道，哈希结果的比较要比直接比较字符串要快的多，所以，在只有一封邮件的情况下，我们有两种方式可以选择：一是，直接与10亿个邮箱地址比较；二是将这封邮件和10亿个邮箱地址哈希，然后比较。第一种方法主要时间花在比较上，而第二种方法主要时间花在哈希上，这样看来谁优谁劣可能还不好讲，但是考虑这样一个问题，我们不止有一封邮件，我们要处理的是一个邮件流，如果采用第一种方法，每次都要将10亿邮箱与新邮件的所属邮箱比较，但是如果采用第二种方法，那10亿邮箱其实每个只用哈希一次，后面只需要哈希新邮箱就可以了，效率要远远高于第一种。由此可以引出布隆过滤器的思想。我认为布隆过滤器的思想在于通过利用过去的计算结果来提高效率。

接下来详细介绍一下布隆过滤器，还是刚才的问题，我们有10亿白名单邮箱，要用其来过滤邮件流数据，为了便于讨论，我们假定有1GB的可用内存，1GB就是80亿个位，也就是80亿个桶，我们将这10亿个邮箱哈希到80亿个桶中，将对应的位置为1，依照上面的思想，如果新邮件进来，将其邮箱哈希，如果哈希到的桶为0，那必定不属于10亿个白名单邮箱中，但如果其对应的位置为1，也不能一定保证其就在白名单当中，但这也已经过滤掉了绝大多数不需要的邮件了。

为了降低布隆过滤器的假阳率，我们可以选用多个哈希函数（比如M个），把这10亿个邮件每个都用着M个哈希函数哈希到这80亿个桶中，只要有一个哈希函数将其哈希到了某个特定的桶中，就将对应的位置置1。这样当新的邮件到来时，我们也将其邮箱用M个哈希函数哈希，只有这个邮箱经由M个哈希函数哈希到的M位全部为1的时候，我们才会认定其可能存在于白名单中。

流中独立元素的数目统计

有这样一个问题，假定流元素选自某个全集，我们想知道某个时间段内，出现过的不同的元素数目。

一种明显的解决方法是在内存中保存当前已有的所有流元素列表，用哈希表或者搜索树来保存，以支持快速增加新元素，并检查元素是否存在。但是如果不同的元素数目太多，或者需要立即处理多个流，那么我们就无法在内存中存储所需数据。

这里介绍一种对独立元素个数进行估计的FM算法，FM算法通过将全集中的元素哈希到一个足够长的位串，就可以对独立元素个数进行估计。在讲FM算法之前，我们需要明确，哈希函数的一个重要性质是，相同元素上的哈希，结果也相同。

FM算法的基本思想是，如果流中看到的不同元素越多，那么我们看到的不同哈希值也会越多，在看到不同哈希值越多的同时，也越可能看到其中有一个值变得『异常』，比如，某个哈希值后面会以多个0结束。

任何时候在流元素上应用哈希函数时，哈希值的尾部将以一些0结束，当然也可能没有0，尾部0的数目称为尾长。假设流中目前所有已有哈希值的最大尾长为R，那么我们将使用2^R来估计到目前为止流中所看到的独立元素数目。

可以证明，如果独立元素数目远大于2^{R，那发现一个尾长至少为R的概率接近1；如果独立元素数目远小于2}R，那发现一个尾长至少为R的概率接近0；

为了取得更精确的值，我们可以使用多个哈希函数，然后取2^R的平均值或者中位数。目前最好的方法是组合起来，首先将哈希函数分成小组，每个组内取平均值，然后在所有平均值中取中位数。

因为我们只需要记录每个哈希函数对应的最大尾长，所以对空间的占用非常小。

矩估计

首先定义矩，假定一个流由选自某个全集上的元素构成，并假定该全集中的所有元素都排好序，这样我们可以通过整数i来标记该序列中的第i个元素，假设该元素出现次数为mi，那流的k阶矩就是Σ(mi)^k。

也即，0阶矩是流中所有独立元素个数，1阶矩是所有元素出现次数mi之和，2阶矩是mi的平方和，用来度量流中元素分布的非均匀性，因此有时也被称为奇异数。出现次数越均匀，奇异数越小，越不均匀，2阶矩越大。

有一种AMS算法可以用来估计二阶矩，并且所使用的空间越多，估计结果也越精确。AMS的基本做法是在流中随机选择若干个位置，分别记录下这些位置对应的元素，将其出现次数置1，然后从当前位置往后读取到流尾，统计其出现次数。对于每个元素，都计算一个二阶矩的估计值，若假定n为流长，估计值为n*(2*出现次数-1)，然后对所有元素的估计值取平均。

这样做的理论基础是，任意变量的估计值都等于流的二阶矩。我们需要注意的是，最好在任何时候都尽可能保有足够多的变量，并在流增长时丢弃某些变量，丢弃的变量会被新变量取代，但必须保证选择任意位置的概率都相同。

窗口内的计数问题

假定我们要回答这样一个问题，有一个窗口大小为N的二进制流，我们希望在任何时候都能回答『对于任意的k<=N，最近k位中有多少个1』，可以证明，如果我们想得到对于任意的k<=N，最近k位中有多少个1的精确数目，任何长度小于N位的表示方法都无法得到精确结果。

接下来介绍DGIM算法，它能够使用O(log2N)位来表示大小为N的窗口，同时能保证窗口内1的数目的估计错误率不高于50%。而且其改进算法可以能在不显著增加占用空间的前提下，将错误率降低到任意大于零的分数之内，尽管当这个分数不断下降，空间复杂度会乘以某个不断增大的常数因子。

这里先给出一个DGIM算法的划分图：

我们将整个窗口划分成多个桶（与哈希中的桶不同），每个桶包含最右部也即最近的时间戳，桶中1的数目必须是2的幂，这也是该桶的大小。

而且，桶的最右部总是为1；每个1的位置都在某个桶中；一个位置只能属于1个桶；桶的大小从最小一直变化到某个最大值，相同大小的桶只可能有1到2个；所有桶的大小都必须是2的幂；从右到左扫描，桶的大小不会减小。

那怎么利用DGIM来回答上述问题呢，如果我们需要回答『窗口中最近k位中有多少个1』，那么DGIM算法会寻找某个具有最早时间戳的桶b，它至少包含k个最近位中的一部分。最后的估计值为桶b右部所有桶的大小之和加上桶b的一半大小。

DGIM算法的空间复杂度是O((log2N)^2)

我们还要考虑DGIM的条件保持问题，每当一个一个新的位到达时，如果导致最早的桶超出了窗口，那将该桶丢弃；如果新来的位是0，那现有的桶（不包括因为超出窗口而丢弃的桶）不需要做任何改变，而如果新来的位是1，那么基于当前时间戳建立一个新的大小为1的桶，如果这导致了大小为1的桶的个数变成了3个，那就将更早的两个大小为1桶合并为一个大小为2的桶，如果这又导致大小为2的桶的个数超限，那就继续合并。

为了降低错误率，我们可以修改允许具有相同大小的桶的数目，前面是1或2，可以修改为r和r-1，这样所得到的错误率为：

如果r足够大，上述错误率可以小于任意想要的值。

衰减窗口

衰减窗口是我个人认为这一章最实用的技术，它可以用来寻找近期的最常见元素。

我们考虑一下最常见元素问题，假定我们要挖掘出当前最流行的电影，我们希望哈利波特这样虽然售出很多票，但时间过早的电影流行度较低。另一方面，一部近10周每周都售出n张票的电影会比仅上周售出2n张票但是再往前一张都票都没售出的电影的流行度要高。

我们可以把每部电影想象成一个位流，如果第i张票属于这部电影，则第i位置1，否则置0，这样我们就可以利用前面的DGIM算法去计算，一个时间段内，每部电影都卖了多少张票，然后以此来计算电影的流行程度。

当然我们可以有一种更好的方法，对问题进行重定义，不再查询窗口中1的数目，更精确的说，我们对流中已见的所有1计算一个平滑的累积值，其中采用的权重不断衰减。因此，元素在流中出现的越早，其权重也就越小。这就是我们要介绍的指数衰减窗口，其定义式如下：

我们定义c是一个很小的常数（比如10^-9），式子中的i代表位置。

为了便于理解，这里再给出一张图：

这条曲线，就是权重的衰减曲线。

我们同样的将每部电影想象成一个位流，如果第i张票属于这部电影，则第i位置1，否则置0，这里的区别在于，我们不是直接对所有的1求和，而是通过衰减求和来计算电影的流行度。前面的那个式子里，如果第i张电影票属于该电影，那a就会为1，在于权重相乘，累加起来。不同的电影不同的位流，也会计算出不同的流行度。

另外，10^-9相当于给了一个大概能容纳最近10亿次购票记录的滑动窗口。

当新的元素到达时，对每一个位流需要做的很简单，先将当前的结果乘以(1-c)，因为相当于原先的所有元素都远了一个位置，所有的权重也就多乘一个(1-c)，然后对于新元素对应的那个电影位流的计算结果，加上1，因为根据上面的公式，第0个位置对应的权重正好是1。其实在上面那个公式里面，a负责判断对应位置的权重该不该被累加，(1-c)^i就是相应位置的权重。

还有，如果流中可能的电影数目非常巨大的话，我们可以设置一个阈值，比如1/2。如果某部电影的热门程度小于该值，其得分将被丢弃。其实，设置了阈值以后，任意时间保留得分的电影的数目是有限的。

频繁项集

其实在《浅谈机器学习基础》中就讲过Apriori这种求得频繁项集的方法，以及如何利用频繁项集求得关联规则。另外还讲过FP-growth，能比Apriori更快的发现频繁项集，且只需扫描数据集两次。

另外，用于发现频繁项集的数据以购物篮模型的形式存在。

Apriori算法这里就不重复讲了（可以去看文集中对应的文章），这里专门提一下更大数据集在内存中的处理。我们知道Apriori算法在对候选项C2进行计数的时候，是需要内存最大的步骤（也即对所有满足支持度阈值的C1频繁项进行组合）。我们希望能够降低这一步的内存占用，以避免产生内存抖动（在磁盘和内存之间反复传输数据）。

这里介绍PCY算法，它主要利用了Apriori第一遍扫描中可能有大量未用内存空间这一观察结果。

这是Apriori前两遍扫描的内存占用图：

第一遍扫描，左上角是项名称到整数的映射，右边是项的计数值，剩下的空间是不使用的；第二遍扫描，已经筛选掉了支持度不足的项，只保留了足够频繁的频繁项C1，然后对所有可能的C1项进行组合，得到C2的候选，也就是图中下面的部分。

然后是PCY算法前两遍扫描的内存占用图：

PCY算法在第一遍扫描时对购物篮进行检查，且不仅对篮中的每个项的计数值加1，而且通过一个双重循环生成所有的项对。对每个项对我们将哈希结果对应的桶元素加1，而且项对本身并不会放到哈希桶中，因此它只会影响桶中的单个整数。也就是第一遍扫描时图中下面的部分。

第一遍扫描结束时，每个桶中都有一个计数值，记录的是所有哈希到该桶中的项对的数目之和，如果该桶的计数值高于支持度阈值，那么该桶称为频繁桶，我们很容易知道，频繁桶中的项对不一定是频繁项对，因为一个桶中可能有多个项对，但是非频繁桶中的项对一定不可能是频繁项。图中的Bimap每一位表示一个桶，如果该位是个频繁桶，则该位置1。

这样，在第二遍扫描的时候，我们所需要进行支持度验证的项对C2就有了两个条件，组成项对的项都是频繁项，且该项对哈希到一个频繁桶。这第二个条件就是PCY算法和Apriori算法的本质区别。

多阶段算法通过使用连续的哈希表来进一步降低PCY算法中的候选对数目，其示意图如下：

多阶段算法的第一遍扫描和PCY的一样。第一遍扫描之后，频繁桶会被识别出来并概括为一个位图，这和PCY算法的情况也一样，也就是第二张图中的Bitmap1。但是多阶段算法的第二遍扫描并不对候选对计数，而是基于另一个哈希函数再建立另一张哈希表（第三遍扫描的目的仍然是减小候选对数目而不是生成C3）。

这样，只有某个项对同时哈希到第一二张哈希表的某个频繁桶中，它才会成为我们的C2候选项，就相当于在PCY算法条件的基础上，又加了一条，也必须要哈希到第三张表的某个频繁桶中。

有时，多阶段算法中额外扫描的大多数好处可以在一次扫描中得到，PCY的这种变形算法称为多哈希算法。其示意图如下：

多哈希算法在一次扫描中同时使用两个哈希函数和两张独立的哈希表，其风险在于，每张哈希表的桶数目大概是PCY算法中的大哈希表的一半左右。只要PCY的每个桶的平均计数值远小于支持度阈值，我们就可以使用两张一半大小的哈希表，并仍然期望两张表中大部分桶都是不频繁的。

我们还要介绍有限扫描算法，虽然讲前面的PCY等算法已经尝试减小Apriori算法的内存占用，但如果数据量还是过大，就要采用有限扫描算法了，如果我们并不一定要发现所有而是只需要大部分频繁项集的话。

我们可以简单的随机化选择，抽样出来一定比例来运行前面的Apriori等算法。一种更好的有限扫描算法是SON算法，能够在两次扫描的代价下去掉所有的伪反例和伪正例。SON算法非常适合与MapReduce结合应用于并行计算环境。

SON算法的基本思路是，将输入文件分成多个组块，将每个组块看成一个样本数据。假定，每个组块站整个文件的比例为p，而s是总的支持度阈值，然后我们对于所有组块运行之前的频繁项集算法（Apriori等），设置支持度阈值为ps，并将在一个或多个组块上发现的所有频繁项集进行合并，这些项集为候选项集。容易知道，如果项集在全集上的支持度是高于s的，那它至少会在一个组块上是频繁的，也即不会存在伪反例。然后进行第二遍扫描，将所有候选项集的支持度进行统计，去掉伪正例。

除了SON算法之外，还有一种不会产生伪正例和伪反例，但也有可能不产生任何结果的Toivonen算法。

该算法首先在抽样数据集上发现频繁项集，但是采用的支持度阈值较低以保证在整个数据及上的频繁项集的丢失几率较低。下一步是检查购物篮整个文件，此时不仅要对所有样本数据集上的频繁项集计数，而且要对反例边界（那些自己还没发现频繁但是其所有直接子集都频繁的项集）上的项集计数。如果反例边界上的人以及和都在整个数据集上不频繁，那么结果是确切的。但是如果反例边界上的一个集合被发现是频繁的，那么需要在一个新的样本数据集上重复整个处理过程。

接下来的问题是发现流中的频繁项集，流和数据文件的区别在于，流元素只有到达后才可用，并且通常情况下到达速率很高以至于无法存储整个流来支持简单查询，另外，一个流会随着时间推移而不断变化，当前的频繁项也许过段时间就不再频繁。

而且流不会结束，只要某个项集反复在流中出现，它最终都会超过支持度阈值。为了解决这个问题，我们将支持度阈值看成是项集出现的购物篮所占的比例。

发现流的频繁项集需要对流进行抽样，我们可以先收集一定量的购物篮并将它存为一个文件，在该文件上执行频繁项集算法，然后这同时可以收集另外一个文件，当第一次迭代完成且收集到的新购物篮流数据数目足够时开始运行第二次迭代。

定期从流中收集新的数据进行迭代，新的迭代进行，如果任一项集的购物篮出现的比例显著低于比例阈值，则该项集可以从所有的频繁项集集合中去掉，频繁项集集合包含没有被删除的项集和新文件中发现的频繁项集。

我们希望应对这种流数据，也可以用衰减窗口，前面讲，我们可以选定一个很小的常数C，并给流窗口的倒数第i个元素赋予(1-C)^i或者e-ci的权重值，来形成流中的一个衰减窗口。

想应用衰减窗口需要对之前的算法做两项修改，第一项非常简单，就是把流元素由单个的项变成购物篮，给定的流元素可能会包含多个项。将这些项中的每一项都看成当前项，并按之前当前项的处理方式进行处理。

第二项修改要复杂一些，我们想找到所有的频繁项集而不只是单元素项集。一种处理该问题的方法是，我们借助Apriori算法的思想定下一个规则，只有在项集I的所有直接真子集都已经评分后，才对项集I开始评分，对于那些真子集为空集的，直接开始评分。

而且由于窗口不断衰减，我们将所有计数值乘以1-c并去掉那些计数值低于1/2的项集。

聚类

按照聚类算法所使用的两种不同的基本策略，我们可以将聚类算法分为两类：

• 一类称为层次式或凝聚式算法。这类算法一开始将每个点都看成一个簇。簇与簇之间按照接近度来组合，接近度可以采取不同的定义，当进一步的组合到达停止条件时停止，比如当达到预先给定的簇数目时可以停止聚类。
• 另一类算法设置点分配过程，即按照某个顺序一次考虑每个点，并将它分配到最合适的簇中。该过程通常都有一个短暂的初始簇估计阶段。一些算法允许簇合并或分裂，或允许离群点不分配到任何簇中。

接下来要介绍一下维数灾难，维数灾难的一个表现是，在高维空间下，几乎所有的点对之间的距离都差不多相等；另一个表现是，集合任意的两个向量之间都是近似正交的。这会让我们的欧氏距离和余弦距离计算方式失效。

层次聚类

层次聚类方法仅可用于规模相对较小的数据集，当层次聚类算法用于非欧空间时，如果不存在簇质心或者说簇中平均点（将簇内所有点算术平均）的时候，我们可以考虑采用簇中心点（离平均点最近的实际簇内点）来表示一个簇。

对于欧式空间，我们可以将簇之间的距离定义为其质心之间的距离，并选择具有最短距离的两个簇进行合并。如果我们事先知道数据的最佳簇数目，那直接合并到剩余到这个数目时停止合并；或者在某次最佳合并时产生一个不恰当的簇的时候停止合并，比如合并之后发现这个簇内的所有点到其质心的平均距离过大。

当然我们也可以聚到只剩一个簇，不过这样没什么意义。

对于非欧空间，簇质心的定义不存在，我们可以考虑这样几种方式来找到簇中心点，比如该点到簇中其他所有点的距离之和最小，或者是平方和最小，或者是到簇中另外一点的最大值最小。

点分配聚类

最有名的点分配聚类算法就是在《浅谈机器学习基础》中也讲过的k均值聚类算法。

当簇数目低于数据中真是的簇数目时，平均直径或其他分散度指标会快速上升。我们可以利用二分查找找到最合适的k数目。

接下来介绍BFR算法，BFR算法是k均值算法的一个变形，BFR算法的设计目的是为了在高维欧式空间中对数据进行聚类，BFR算法对簇的形状给出了一个非常强的假设，即它们必须满足以质心为期望的正态分布。一个簇的在不同维度的标准差可能不同，但是维度之间必须相互独立，如下图：

内存中除了输入组块之外还包括其他三种对象，废弃集、压缩集和留存集。

在书的原文中，几乎没有讲清楚废弃集和压缩集的区别，这里我找到了另一种解释，如图所示：

DS是废弃集、CS是压缩集、RS是留存集。字面意思是，废弃集中的所有点与质心足够接近，形成了一个簇，我们保存这个簇的简单概要信息；压缩集中的点相互接近，但并不接近任何一个已存在的质心，基本可以理解为没有质心，也不算做是簇，存放的也是这些点呃概要信息，因为不是簇，所以只是点集的概要而不是簇的概要；留存集就是即不能被分配给某个簇，也不会和其他点足够接近而被放到压缩集中，这些点会显式存在。

概括起来，如下图：

对于概要信息，我们用N-SUM-SUMSQ表示：

• 所表示的点的数目N
• 向量SUM：所有点在每一维的分量之和，即SUM[i]表示第i维上的分量和。
• 向量SUMSQ：所有点在每一维的分量的平方和。

我们的实际目标其实是将一系列点表示为它们的数目、质心和每一维的标准差。根据N-SUM-SUMSQ表示，我们可以得到：

• 第i维质心：SUM[i]/N
• 第i维的方差：SUMSQ[i]/N−SUM[i]^2/N2

然后是BFR的数据处理过程：

• 首先找到所有『充分接近』某个簇质心的点加入到该簇中。加入新的点后，DS废弃集的调整计算通过N-SUM-SUMSQ表示很容易实现，直接加上这些新加入的点的Ns,SUMs,SUMSQs 值即可。
• 剩下得即是那些并不充分接近任一个簇质心的点。我们将这些点和之前的留存集中的点一起进行聚类（use any main-memory clustering algorithm)。将聚类的点概括表示并加入到压缩集CS中，剩余的单点簇则表示为点的留存集RS。
• 通过第二步后，现在我们有了新的迷你簇，它们和上一个块的数据处理后留下的压缩集迷你簇和留存集中间可能距离很近是可以合并的。因此这一步就是将这些迷你簇和以前的压缩集的迷你簇和以前的留存集进行合并。
  （如果这是最后一块数据了，那么就将这些留存集的点和压缩集分配到距离最近的簇中，否则继续保留压缩集和留存集，等待和下一块的数据一起处理。）
• 分配给一个簇或迷你簇的点，即不再留存集中的点会和分配结果一起写出到二级存储器中。

那怎么定义充分接近呢，我们利用马氏距离，马氏距离可以表示该点到该簇质心的概率，本质上是点到簇质心的距离，并在每维通过簇的标准差进行归一化。我们选择具有最短马氏距离，且马氏距离小于某个阈值的簇加入。 这一计算利用了最开始提到的BFR算法的前提假设：每个簇都是正态分布的点构成，且点的坐标和空间坐标保持一致。

接下来讨论另一个点分配类的大规模聚类算法CURE算法（Clustering Using Representatives），仍然假定运行在欧式空间下。BFR算法对簇的分布和形状都有很强的假设条件，因此在实际使用中有许多并不满足条件的聚类情况。而本节讨论的CURE算法不需要簇满足正态分布，更不需要符合轴平行，即对簇的形状没有任何假设。CURE算法使用一些代表点的集合来表示簇而不再是质心。

其初始化过程如下：

• 首先是抽取一部分样本数据在内存中进行聚类，理论上讲，可以使用任意聚类算法，通常当两个簇具有相近点对时，建议采用层次聚类算法对这两个簇进行合并。

• 从每个簇中选择代表点，不同簇的代表点之间的距离尽量远。

  
  

• 对每个代表点向质心移动一段距离，一般是一个固定的比例（比如20%）：

  
  

通过前面对每个簇生成代表点后，重新计算其它所有点到这些代表点的距离，将距离最近的分配到该簇中。

然后简单介绍一下可以用于非欧式空间聚类的GRGPF算法，该算法也是点分配算法的一种。它能处理内存无法存放的大规模数据，并且它不要求一定要在欧式空间使用。

在GRGPF中，簇表示为簇中点的数目、簇中心点、离中心点最近的一些点集和最远的一些点集。靠近中心点的点允许我们在簇演变时修改中心点，而远离中心点的点允许我们在前档环境下对簇进行快速合并。对上述点中的每一个点，我们还要记录其ROWSUM值，即该点到簇中所有其他点的距离平方和的算术平方根。

簇的表示会组成一棵类似于B-树的树结构，其中树节点通常是磁盘块并包含许多簇有关的信息。页节点保存尽可能多的簇的表示，而内部节点上保存了其子孙节点上的簇的中心点的一个样本。数被组织成任意子树下的簇表示所对应的簇之间尽可能相近。

通过一个点集样本对簇进行初始化后，我们将每个点插入到簇中心点离他最近的那个簇。由于采用的是树结构，我们可以从根节点开始，通过选择访问子节点来找到和给定点最近的中心点样本。按照这种规则得到一条道叶节点的路径，于是我们将该点插入到此叶节点上与之最近的簇中心点所对应的簇中。

然后介绍用于流聚类的BDMO算法。 BDMO算法利用类似于DGIM算法中的桶来进行处理，虽然也要求每个桶的大小是前一个桶大小的两倍，但是并不要求桶的大小从1开始。

桶的大小和桶的时间戳都与DGIM算法中的定义相同。BDMO中桶当中只保存所含点的簇表示而不是点本身，比如簇中点的数目，簇的质心或中心点等。

假定一个桶中的元素有p个，我们可以将每个点自己看成一个簇，也可以选定k均值聚类算法（假定k<p）将这些点聚成k个簇。

桶合并与DGIM的思路相同，但细节有区别，必须要考虑是否要合并簇，如果要合并，我们要计算合并后的簇的参数。

我们不考虑对来自同一个桶的两个簇进行合并，这是因为我们假设在连续桶中簇的演变不会太多。如果流的演变较慢，那么可以预期连续的桶当中可能包含几乎相同的簇质心，所以我们会从不同的桶中找到最佳的簇进行两两匹配，并将它们两两合并。

当决定合并分别来自不同桶的两个簇时，合并后的点的数目肯定等于两个簇中的点数目之和。合并后的簇的质心是两个簇的质心的加权平均，其中权重分别是两个簇中的点数目。

我们的查询要求是返回流中最近m个点中的簇，如果我们选择能够覆盖最近m个点的最少桶集合，那么这些桶集合中不会有超过最近的2m个点。我们将这些选定桶中的所有点的质心或者中心点作为查询的应答结果返回。

Web广告

这一章主要讲Web网站上的在线广告等相关问题。

评价广告之前，有几个因素需要考虑，广告在列表中的位置将对它是否被点击有很大的影响；广告的吸引力可能取决于查询词项，即相关性；在较精确地估计出点击率之前，所有的广告都应该有展示的机会。

在处理在线广告匹配问题时，我们往往需要使用在线算法，也即我们需要在对未来一无所知时对当前每个元素进行决策。

这里举一个例子，如果我们简单的将广告分配给出现最高的广告商在不知道未来信息的状态下会出现什么情况，比如A公司投了a这个词，出价0.1元，B公司投了a和b这两个词，出价0.2元，且两家每个月的广告预算都是100。如果这个月有1000个a，500个b，最佳的情况是1000个a给A，500个b给B，这样两家的预算都正好花完，广告系统的总收益最大化了。

但是如果按照出价分配，a会优先给B公司，如果不是全部的b都出现在任意一个a前，那A的预算是花不完的，我们把a给了B，B公司的预算花完了，A的预算没花完，而且还剩下一些b没有广告投放。

很多在线算法都属于贪心算法，这类算法通过最大化当前输入元素和历史信息的某个函数，对每个输入元素都做出决策。

我们定义一下在线算法的竞争率，存在某个小于1的常数c，这个在线算法的结果至少是最优离线算法（提供未来信息做决策）的c倍，那c就是这个在线算法的竞争率。

一个最小化竞争率的在线算法的流行例子是滑雪板购买问题，假设你可以花100元买滑雪板，也可以以每天10元的价格租用滑雪板，你有可能在任意一次滑雪后由于任何原因放弃。这个算法的好坏取决于每天进行滑雪的开销，目的是最小化它。

二分图最大匹配问题

如果将广告和搜索查询匹配的问题简化，就是一个二分图的最大匹配问题，如下图：

一个匹配指的是一个由边构成的子集，对于这些边而言，任何一个节点都不会同时是两条或多条边的端点。如果左集合和右集合中的节点数目一样，所有的节点都出现在了某个匹配之中，那这个匹配叫做完美匹配。所有匹配中包含节点个数最多的匹配叫做最大匹配

这就是上面那个图的唯一完美匹配：

有一种最简单的最大匹配贪心算法，它效果并不是很好，但可以用来做参考。其工作流程是，我们可以按照任意次序来考虑边，当考虑边(x,y)时，如果x和y都不是已匹配中边的端点，则将其加入，否则跳过。在上面的问题中，这个算法的竞争率为1/2

adwords问题

现在我们考虑搜索广告中的基本问题，该问题最早在谷歌的Adwords广告系统中出现。

Adwords系统比早期的广告系统更复杂，需要考虑这样几个因素：

• 对于每条查询，谷歌显示的广告有限
• Adwords系统的用户会指定一个预算，即它们愿意在一个月内为其广告所有点击所付的费用
• 谷歌按照每条广告的期望收益来排序，而不是简单的按照广告商的出价，对于每条广告，会基于其展示的历史数据观察其点击率。最终一条广告的价值等于出价和点击率的乘积

对于adwords问题，我们需要提前知道：

• 广告商的出价集合
• 广告商-查询所对应的点击率
• 广告商的预算
• 每个查询的广告数目上限

我们先将问题进行简化来探寻更好的算法，这些简化包括：

• 每条查询只显示一个广告
• 所有广告商的预算都相等
• 所有广告的点击率都相等
• 所有的出价不是0就是1

有一种Balance算法对贪心算法做了简单改进，它在仅有两个广告商的情况下竞争率为3/4，随着广告商数目的不断增长，竞争率会下降到1-1/e（约为0.63），但不会更低。

在前面的简化条件下，Balance算法将查询分配给出价最高且剩余预算最多的广告商，考虑到出价不是0就是1，所以在算法运行过程中通常是根据剩余预算做决策，如果剩余预算相同，则可以随机选择。

当于所有广告商出价并不是非0即1这中更一般性的情况时，我们需要对Balance算法进行改进，以保证其竞争率仍然为1-1/e（约为0.63）。

我们这样做，当某个查询q到来，广告商Ai对q的出价是xi，另外假定Ai预算中的结余比例为fi，令Ψi=xi(1-e^-fi)，将q分配给具有最大Ψ值的广告商。

对于adwords问题，不存在竞争率超过1-1/e的在线算法。

前面讲的adwords问题是查询词与对查询词出价的广告商之间的匹配问题，接下来我们要处理的是文档和投标之间的匹配算法，区别在于，广告商仍然是对词出价，但我们考虑匹配的不再是查询词，而是文档，文档是一个更大的词语集合。

这种文档和词的匹配问题与搜索引擎所解决的问题看起来十分类似，但实际上，搜索引擎是以词查相关文档，但是这里是为文档找到有投标的相关词。

而且需要注意的是，投标也是一个词集，虽然比较小，并不是单个词。

对于投标，我们将投标表示成某种排序下的词语表，并为词语表添加一个状态信息，用于记录列表中从头开始已经和当前文档匹配上的词语数目。如果一个投标词语表中的所有词语都出现在文档中，不管这些词语是否和投标中同序，不管他们是否相邻，都认为投标和文档匹配。

对于投标和文档（该段中统称为文档），在匹配时，为了减少工作量，我们以低频优先的方式对词语排序。由于出现在所有文档中的不同词数目本质上是无限的，所以我们选择一种折中的方法，我们找到所有文档中最常见的n个词，比如10万或者100万，这n个词会按照频率排序，并占据每篇文档的尾部，剩下的低频词，我们假定他们频率都一样并按照词典序排在列表的前面。我们以上述的方式来表示每一篇文档，文档会按照这种低频优先的方式存储在哈希表中，其中第一个词作为哈希键。

大规模投标和文档的管理过程如下图所示：

图中存在两张哈希表（投标的哈希表索引和部分匹配的投标）和一张匹配投标表，第一张哈希表以之前讲过的顺序记录了所有投标，第二张哈希表是为了保存那些已经部分匹配的投标的副本。表之间的切换以及第二个表的循环下面会讲。

在这个过程的开始，我们将文档中的词按照同样的顺序进行排列，并去掉重复词。

对于文档的排序列表中的每个词w，进行如下操作：

• 在部分匹配哈希表中使用w作为哈希键，找到那些以w为键的投标（图中的a）
• 对这样的每个投标b，如果w是b词集中的最后一个词，将b移到已匹配投标表中（图中的b）
• 如果w不是b中的最后那个词，则对b的状态值加1，并利用比新状态值大1的位置上对应的词作为哈希键重新对b进行哈希处理（图中的c）
• 以w为哈希键检查第一个哈希表（图中的d）
• 如果该投标b词集中只有一个词，那么将它复制到已匹配投标中去（图中的e）
• 如果b中不止一个词，那么将它以状态1放到第二张部分匹配投标表中，并使用b中的第二个词作为哈希键。

然后最后输出已匹配投标表。

这样某个投标只有在其最低频词出现在文档时才会复制到第二个哈希表中。

社会网络图挖掘

社会网络中的一个很重要的问题是识别『社区』，而所谓的社区是指具有非同寻常的强连通性的节点子集（节点可以是构成网络的人或其他实体）。举例来说，同一社区的人通常互相认识，而不同社区的人很少会认识对方。

社会网络可以很自然的用图来建模，有时被称为社会图。社会图通常是无向图，比如朋友关系，但也可以是有向图，比如微博的关注关系。

有的社会现象会涉及多个不同类型的实体，那这样的图就会由多个类型的节点构成，同类节点之间不连接，描述这种信息很自然的可以采用k分图。

使用传统的聚类算法对社会网络聚类会存在不少问题，有人提出了多种发现社会网络社区的专用聚类技术，这里先介绍中介度。

一条边的中介度定义为节点对(x,y)的数目，其中(a,b)处于(x,y)的最短路径上。(a,b)的中介度高，说明它们处于两个社区之间，也就是说a和b更倾向于不属于同一社区。

为了利用边的中介度，必须要计算所有边上的最短路径数目，这里采用Girvan-Newman算法。该算法访问每个节点X一次，计算X到其他连接节点的最短路径数目。算法首先从节点X开始对图进行广度优先搜索（BFS）。在BFS表示中，每个节点的深度就是该节点到X的最短路径长度。因此处于统一深度的两个节点之间的边永远都不可能处于X到其他点的最短路径上。

GN算法的第二步是将每个节点用根节点到它的最短路径的数目在标记。首先将根基点标记为1，然后从上往下，将每个节点Y标记为其所有父节点上的标记值之和，如下图所示：

第二步是一个准备阶段，GN算法的第三步真正去求每条边的中介度。其整个计算规则如下：

• 图中的每个叶节点（叶节点指那些不存在与下层节点的边的节点）都赋予分值1（这里的分值和上面的标记值不是一个意思）
• 每个非叶节点给的分值是1加上从该节点到其下层节点的所有边的分值之和
• 下层节点根据第二步的标记值分配自己的分值给到上层节点的边

当每个节点都作为根节点计算过一遍之后，将每条边的分值求和。由于每条最短路径会重复发现两次（以这条边的不同节点为根节点），因此最后每条边的分值还要再除以2

给张图会好理解一些：

从下到上进行计算，先给A、C、G这三个叶子节点赋予分值1，然后把自己的分值向上传给边，如果就一条边，就把自己的分值全部赋予这条边，如果有多条边，按照第二步里的标记值的比例关系划分，第二步中，G上面的D和F的标记值都是1，所以这里G的分值也平分给到D和F的两条边，将边的分值求和加1得到自己的分值，再按同样的规则往上计算，直到根节点。

我们可以利用中介度来发现社区，比如优先去除掉中介度高的边。利用中介度来划分社区非常便捷，但缺点是它不可能把一个点划分到两个社区中。

我们也可以通过在社会图中寻找二分图的方式来发现社区，完全二分图包括两组节点，两组之间的所有节点对都存在边，而每组内部节点之间不存在边。任一足够密集的社区（存在很多边的节点子集）都包含一个大的完全二分图。

我们可以利用发现频繁项集的技术来发现完全二分图。我们可以选定二分图的一边看成购物篮，这一边中某个节点的购物篮是其邻接节点集合，而每个邻接节点可以看成项。一个两组节点集合大小分别为t和s的完全二分图可以看成是寻找支持度为s、大小为t的频繁项集。

更详细一点说，我们可以通过计算给定t大小项集的平均支持度，来推断出社区中存在什么样的二分图实例。

然后再说一下图划分问题。先给出一个比较好的图切割方法，叫做归一化割，归一化割的公式如下：

归一化割的本质是一种切分效果评价标准，如果我们将S和T切开，Cut(S,T)定义为连接S中节点和T中节点的边的数目，Vol(S)定义为，至少有一个端点在S中的边的数目。

我们计算切分的归一化割，找到使归一化割最小的切分。

然后再讲一下拉普拉斯矩阵，在这之前首先要介绍邻接矩阵，就是如果节点i和j之间有边，那么矩阵的第i行、第j列的元素为1，否则为0。邻接矩阵是对称阵，且对角线上对的元素均为0

然后还要介绍度数矩阵，度数矩阵是对角阵，只有对角线上有元素，第i行第i个元素给出的是第i个节点的度数。

假定某个图有邻接矩阵A和度数矩阵D，那这个图的拉普拉斯矩阵就定义为L=D-A。

那图的拉普拉斯矩阵有什么用呢，我们计算出拉普拉斯矩阵第二小的特征值对应的特征向量，然后将特征向量中的正负值对应的节点分成两组，通常能得到不错的效果。

然后是重叠社区问题，考虑这样的情况：

其实很多时候，如上图所示，多个社区交集内的边可能会更加密集，因为他们（同属于多个社区的人）有了更多认识的可能性。

针对这样的问题，有一种关系图模型的机制，该机制可以从社区生成社会网络图。一旦明白该模型的参数如何影响观察到的给定图，就可以想办法利用最大似然估计来求得参数值。社区-关系图机制中的规定如下：

• 存在给定数目的社区，存在给定数目的个体（图的节点）
• 每个社区可以拥有任意的个体集合作为成员，也就是说，个体对社区的隶属关系是模型的参数
• 每个社区C都有一个pc与之关联，该概率表示C中两个成员由于都是C中成员而通过边连接的概率。这些概率也是模型的参数
• 如果一对节点属于两个或更多社区，那么如果包含这两个节点的社区按照上一条规则判定节点间有边的话，它们之间就有边

这其实就是一个生成模型。

另外，因为对每个社区来说，存在因为该社区而导致两个成员成为朋友的概率，因此，两个节点间有边的概率是1减去所有包含两个成员的社区都不导致两者有边的概率的乘积。然后我们利用最大似然估计和梯度下降法来找到模型的最优参数。

当然，这里直接使用梯度下降会有点问题，因为如果隶属或者不隶属以0和1表示，梯度下降法是无法处理这种不连续的数据的，我们将这种隶属关系修改为隶属强度，越接近0，是成员的可能性就越低。然后就可以利用梯度下降法求解了。

然后是SimRank，SimRank也是一种链接分析算法，它可以计算多类型节点图中两个点之间的相似度，其基本思路是，让一个随机游走者从某个点出发进行游走，并且在相同节点上有一个固定的重启概率（类似于PageRank中以远程跳转来缓解链接陷阱的影响）。游走着的期望分布概率可以看成节点到起始节点的一个很好的相似度度量。如果需要得到所有节点对之间的相似度，就需要以每个节点为初始点重复上述过程。与PageRank一样，SimRank在迭代中也会有震荡，整个收敛会需要时间，但一般而言，对于任意连通的k分图来说，都会收敛。