Spark 高级分析:第七章第8,9节 度分布和过滤噪声边

问题导读

1.什么是顶点的度？为什么需要引入这个概念？
2.Graphx中内置的计算度的方法是什么？如何使用？
3.如何过滤噪声边？





上一篇：Spark 高级分析:第七章第6,7节 连通分支
http://www.aboutyun.com/forum.php?mod=viewthread&tid=25035


一个连通图可以用许多不同的方式构造。例如，可能有一个顶点连接到所有其他顶点，但其他顶点彼此没有连接。如果我们去掉了一个中心顶点，该图就会分解成单个顶点。我们也可能有这样一种情况：图中的每个顶点都连接到另外两个顶点，从而整个连接的分支形成了一个巨大的环。

图7-2 连通图中的度分布

为了进一步了解图形是如何构造的，查看每个顶点的度是有帮助的，度是一个特定顶点所属的边的数量。在无环图（即边连通自身）中，顶点的度数的总和将等于边数的两倍，因为每个边将包含两个不同的顶点。

在GraphX中，我们可以通过调用图对象上的degrees方法来获得每个顶点的度数。此方法返回整数的VertexRDD，每个整数即每个顶点的度数。让我们得到度分布和我们的概念网络的一些基本汇总统计：

[mw_shl_code=scala,true]val degrees: VertexRDD[Int] = topicGraph.degrees.cache()
degrees.map(_._2).stats()
...
(count: 12065, mean: 43.09,
stdev: 97.63, max: 3753.0, min: 1.0)[/mw_shl_code]

在度分布中有一些有趣的信息。首先，注意degrees RDD中的条目数目小于图中顶点的数目：当图包含13034个顶点时，degrees RDD只有12065个条目。有些顶点没有边连接到它们。这可能是由于MEDLINE数据中仅有一个主要主题的引用引起的，这意味着它们在我们的数据中不会有任何其他主题共存。我们可以通过重新审视原始MEDLINE RDD来证实这一点：

[mw_shl_code=scala,true]val sing = medline.filter(x => x.size == 1)
sing.count()
...
48611
val singTopic = sing.flatMap(topic => topic).distinct()
singTopic.count()
...
8084[/mw_shl_code]

在48611个MEDLINE文档中有8084个不同的主题出现。让我们移除已经在拓扑结构RDD中出现的那些主题的实例：

[mw_shl_code=scala,true]val topic2 = topicPairs.flatMap(p => p)
singTopic.subtract(topic2).count()
...
969[/mw_shl_code]

这969个主题只发生在MEDLINE文档中的单体，13034减去969是12065，degrees RDD中的条目个数。

接下来，注意，虽然平均值相对较小，但表示图中的平均顶点仅连接到其他节点的一小部分，最大值指示图中至少有一个高度连接的节点，几乎连接到图中其他节点的三分之一。

让我们更仔细地研究这些高度数顶点的概念，通过使用抽象图中的度数VertexRDD与GraphX的innerJoin方法以及相关联的函数，将概念的名称和顶点的度组合成元组。记住，innerJoin方法只返回在两个VertexRDDs中都存在的顶点，所以不具有任何共现的概念将被过滤掉。我们将编写一个函数，我们可以在以后使用它来查找具有最高度数的主题的名称。

[mw_shl_code=scala,true]def topNamesAndDegrees(degrees: VertexRDD[Int],
topicGraph: Graph[String, Int]): Array[(String, Int)] = {
val namesAndDegrees = degrees.innerJoin(topicGraph.vertices) {
(topicId, degree, name) => (name, degree)
}

val ord = Ordering.by[(String, Int), Int](_._2)
namesAndDegrees.map(_._2).top(10)(ord)
}[/mw_shl_code]

当我们打印namesAndDegrees VertexRDD前十个元素的值时，我们得到：

[mw_shl_code=scala,true]topNamesAndDegrees(degrees, topicGraph).foreach(println)
...
(Research,3753)
(Child,2364)
(Toxicology,2019)
(Pharmacology,1891)
(Adolescent,1884)
(Pathology,1781)
(Rats,1573)
(Infant,1568)
(Geriatrics,1546)
(Pregnancy,1431)[/mw_shl_code]

意料之中的是，大多数高阶顶点指的是我们在整个分析过程中看到的相同的一般概念。在下一节中，我们将使用GraphX API的一些新功能和一些老式的统计，以便从图中筛选出一些不太有趣的共现对。

在当前共现图中，基于一对概念在同一纸上出现的次数的计数来对边进行加权。这个简单的加权方案的问题在于，它不区分发生在一起的概念对，因为它们具有从概念对中产生的有意义的语义关系，因为它们对于任何类型的文档都经常发生。我们需要使用一种新的边加权方案，考虑到给定的数据中的那些概念的总体流行率，文档中的一对特定概念是多么“有趣”或“令人惊讶”。我们将使用皮尔森的卡方检验来计算这种“趣味性”的原则性方式，即测试一个特定概念的发生是否独立于另一个概念的发生。

对于任何一对概念A和B，我们可以创建一个2x2列联表，包含这些概念如何在MEDLINE文档中共同出现的计数：

在该表中，条目YY、YN、NY和NN表示概念A和B的存在/不存在的原始计数。条目Ya和NA是概念A和YB和NB的行和，是概念B的列和，并且值T是文档的总数。对于卡方检验，我们认为YY、YN、NY和NN是从未知分布中采样的。我们可以从这些值计算卡方统计量：

如果我们的样本事实上是独立的，我们预计这个统计值将从具有适当自由度的卡方分布中提取出来。其中R和C是比较两个随机变量的基数，计算自由度为(r - 1)(c - 1) = 1。一个大的卡方统计量表明变量不太可能独立，因此我们发现这对概念更有趣。更具体地，一阶卡方分布的CDF产生p值，这是我们可以拒绝变量独立的零假设的置信水平。

在这一节中，我们将使用GraphX计算我们共现图中每对概念的卡方统计量的值。

第8,9节 度分布和过滤噪声边~~~