Spark 高级分析:第七章第10,11节 处理边三元组，分析过滤后的图

问题导读

1.如何求样例数据中的文件总数？
2.图过滤的规则是什么？
3.如何分析过滤后的数据？


关注最新经典文章，欢迎关注公众号



上一篇：Spark 高级分析:第七章第8,9节 度分布和过滤噪声边
http://www.aboutyun.com/forum.php?mod=viewthread&tid=25076


卡方统计量的最简单部分是T，文件总数。我们可以通过简单地计算medline RDD中的条数很容易得到：
[mw_shl_code=scala,true]val T = medline.count()[/mw_shl_code]
我们也可以比较容易地得到每个文档有多少个特征数，我们已经做了这个分析，以便在本章早些时候创建主题图，但是现在我们将得到的计数作为集群上的RDD：
[mw_shl_code=scala,true]val topicCountsRdd = topics.map(x => (hashId(x), 1)).reduceByKey(_+_)[/mw_shl_code]
一旦我们有了这个VertexRDD的计数，我们就可以创建一个新的图形，使用它作为顶点集，以及现有的边RDD：
val topicCountGraph = Graph(topicCountsRdd, topicGraph.edges)
现在我们有了计算TopicCountGraoh中每个边的卡方统计量所需的所有信息。为了进行计算，我们需要将两个顶点存储的数据（即每一个概念在文档中出现的次数）以及边（每一对概念发生在同一文档中的次数的计数）结合起来。GraphX支持这样的数据结构EdgeTriplet[VD, ED],，它具有关于顶点和边作为对象的所有属性信息，以及两个顶点的ID。topicCountGraph,上给定一个EdgeTriplet，我们可以计算出卡方统计如下：
[mw_shl_code=scala,true]def chiSq(YY: Int, YB: Int, YA: Int, T: Long): Double = {
val NB = T - YB
val NA = T - YA
val YN = YA - YY
val NY = YB - YY
val NN = T - NY - YN - YY
val inner = (YY * NN - YN * NY) - T / 2.0
T * math.pow(inner, 2) / (YA * NA * YB * NB)
}[/mw_shl_code]
然后，我们可以通过map Triplets算子来变换图边的值，它返回一个新的图，其边属性将是每个共现对的卡方统计量的值，然后得到该统计量在边上的值的分布：
[mw_shl_code=scala,true]val chiSquaredGraph = topicCountGraph.mapTriplets(triplet => {
chiSq(triplet.attr, triplet.srcAttr, triplet.dstAttr, T)
})
chiSquaredGraph.edges.map(x => x.attr).stats()
...
(count: 259920, mean: 546.97,
stdev: 3428.85, max: 222305.79, min: 0.0)[/mw_shl_code]
计算了卡方统计量值后，我们想用它来过滤出在共同出现的概念之间没有任何关系的边。从边的值分布可以看出，在数据上的卡方统计量值跨度很大。对于一个2x2列联表，其中变量之间没有关系，我们预期卡方度量的值将遵循具有一个自由度的卡方分布。具有一个自由度的卡方分布的9999个百分位数大约为19.5，所以让我们把这个值作为一个截止值来消除图中的边，只留下那些我们非常确信它们代表一个有趣的共现序列的边。我们将用subgraph方法在图上执行这个过滤，该方法采用EdgeTriplet函数来确定子图中包含哪些边：
[mw_shl_code=scala,true]val interesting = chiSquaredGraph.subgraph(
triplet => triplet.attr > 19.5)
interesting.edges.count
...
170664[/mw_shl_code]
非常严格的过滤规则去除了原始共现图中三分之一的边。这不是坏事，规则没有删除更多的边，因为我们预计，大多数共同出现的概念在图上实际上是语义相互关联的，所以他们会共同发生比纯属偶然的概率更大。在下一节中，我们将分析子图的连通度和整体度分布，通过去除这些有噪声的边来了解图的结构是否有重大的影响。
我们将重新运行子图上的连通分支算法，并使用原始图中所写的函数来检查分支数量和大小：
[mw_shl_code=scala,true]val interestingComponentCounts = sortedConnectedComponents(
interesting.connectedComponents())
interestingComponentCounts.size
...
1042
interestingComponentCounts.take(10).foreach(println)
...
(-9222594773437155629,11912)
(-6468702387578666337,4)
(-7038642868304457401,3)
(-7926343550108072887,3)
(-5914927920861094734,3)
(-4899133687675445365,3)
(-9022462685920786023,3)
(-7462290111155674971,3)
(-5504525564549659185,3)
(-7557628715678213859,3)[/mw_shl_code]
过滤出图中的第三的边导致图的连通性的微小变化：在过滤的图中存在三个附加的岛（1042对原始的1039），并且最大连接的分支的大小已经下降了三个顶点（11912对11915）。这表明，三个弱连接的概念已经修剪从最大的组成部分到单独的岛屿。即使如此，最大的连通分支仍然与以前的大小大致相同；在图中修剪第三的边并不会导致最大的分支分裂成大的数目。这表明图的连通结构对于过滤噪声边是相当稳健的。当我们查看过滤图的度分布时，我们看到了类似的事：
[mw_shl_code=scala,true]val interestingDegrees = interesting.degrees.cache()
interestingDegrees.map(_._2).stats()
...
(count: 12062, mean: 28.30,
stdev: 44.84, max: 1603.0, min: 1.0)[/mw_shl_code]
原始图的平均度约为43，滤波图的平均度下降了一点，约为28。然而，更有趣的是，最大程度顶点的大小急剧下降，从原始图中的3753下降到过滤图的1603。如果我们查看过滤图中概念和度之间的关联，我们会看到：
[mw_shl_code=scala,true]topNamesAndDegrees(interestingDegrees, topicGraph).foreach(println)
...
(Research,1603)
(Pharmacology,873)
(Toxicology,814)
(Rats,716)
(Pathology,704)
(Child,617)
(Metabolism,587)
(Rabbits,560)
(Mice,526)
(Adolescent,510)[/mw_shl_code]
我们的平方滤波准则似乎具有预期的效果：它消除了与一般概念相关的图中的边，同时保留了表示概念之间有意义和有趣的语义关系的图的其余部分的边。我们可以继续用不同的卡方滤波准则进行实验，以了解它们如何影响图中的连通度和度分布；有趣的是，找出卡方分布的值会导致图中的大连通分支破坏U。P变成更小的碎片，或者如果最大的成分会继续“融化”，就像一个巨大的冰山慢慢失去微小的碎片。

高级分析:第七章第10,11节 处理边三元组~~