Go语言视频零基础入门到精通

admin

分类：索引（1） 简介python代码实现存在问题参考文章：

http://www.lxway.com/619051121.htm

其实这个算法也可以作为聚类算法来用，计算出两两样本之间的相似度，作为这个算法里边的权重，可以去掉值很低的，然后进行聚类。我们假设一个图有m个节点n条边，label propagation的复杂度是O(kn) （不确定）k是迭代次数。在一般情况下，n远远小于m2因此是个和图规模线性关系的算法。如果聚类最后一步采用这种方法，那么计算两两相似度得到图结构，需要O(m2)应该是主要开销。
之前也介绍过这个算法：

http://blog.csdn.net/lgnlgn/archive/2011/01/29/6168756.aspx

算法叫label propagation，基本思想很简单，就是一个节点的所在类别由与其相连的节点共同决定，实际就是类标的马尔科夫随机游走过程。计算的时候需要迭代多次，每个节点选择它邻接节点类标数最多的那一个。
原版算法在选择类标时候过于严格，只选一个；其实很容易想到，可以有各种扩展的办法，比如选若干个，分别赋予隶属度，这样每个节点可以属于多个类别，类别差距大的，可以确定成一个。
具体地就是
首先：每个节点把自己的类标传播到邻居；然后：每个节点根据邻居传过来的消息作出选择
很容易看到，这两步都可以同步地进行，因此非常适合用MapReduce的框架完成，很多图算法基于随机游走模型的，其实都适用，如pagerank。
我简单实现了一个Python的版本，虽然是mapreduce的思路，但是纯粹的顺序执行。代码不多 直接贴了，随便建立一个文本文件 每行记录一个节点id，它的邻居节点和权重 tuple，如下
1,((2,1),(3,1),(4,1))
2,((1,1),)
3,((1,1),(4,1))
4,((1,1),(3,1))
代码里面解析直接用了eval方法 所以格式得注意保证。这个算法是无向图的，因此边要多写一次，例如(1,4) 在(4,1)也要写一份。

1. [code]from itertools import imap
2. global gdata_file
3. global label_vector
4. global group_map
5. path = "d:/data/graph.txt"
6. def getMaxId():
8.     return max(imap(lambda x:eval(x)[0],file(path,"r").xreadlines()))+1
9. def mapFunc(line):    ##voting
11.     node,edges = eval(line.strip())
13. ##    edges = ((node,1),) + edges
15.     labels = label_vector[node]
17.     if labels:
19.         return [(edge+(labels,)) for edge in edges]
21.     else:
23.         return [(edge+({node:1},)) for edge in edges]
25. def mergeMap(a,b,weight):##merge b to a
27.     for k,v in b.iteritems():
29.         g = a.get(k)
31.         if g:
33.             a[k] = g + v * weight
35.         else:
37.             a[k] = v * weight
39.     return a
43. def reduceFunc(map_phrase): ##merge
45.     tmp = {}
47.     for map_results in map_phrase:
49.         for map_result in map_results:
51.             l = tmp.get(map_result[0])
53.             if l:
55.                 mergeMap(l,map_result[2],map_result[1])
57.             else:
59.                 tmp[map_result[0]] = mergeMap(dict(),map_result[2],map_result[1])
63.     return tmp
67. def select(m): ##select top k labels
69.     u = sorted(m.items(),key = lambda x:x[1],reverse=True)
71.     if len(u) >=3 and ((u[0][1] - u[1][1]) > (u[1][1] - u[2][1])):
73.         uu = u[:2]
75.     else:
77.         uu = u[:3]
79.     s = sum([x[1] for x in uu])
81.     return dict( [(x[0],(x[1]+0.0)/s) for x in uu])
85. def close():
87.     print label_vector
91. label_vector = [None] * getMaxId()
93. group_map = {}
97. if __name__ == "__main__":
99.     for loop in xrange(7):
101.         gdata_file = file(path,"r")
103.         map_phrase = map(mapFunc, gdata_file.xreadlines())
105.         group_map = reduceFunc(map_phrase)
107.         gdata_file.close()
111.         for k,v in group_map.iteritems():
113.             label_vector[k] = select(v)
117.     close()

复制代码

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117[/code]每次map是一个解析图结构的过程，将节点类标投得到每个邻居，reduce过程就是简单地把所有结果合并。从main开始，迭代多次，每次节点保留隶属度最大的2~3个节点，作为下一次计算的依据，最后close方法用来整理输出。我还有个疑问，就是向邻居投票的时候，需要包含自己的类标吗？这个我在map阶段注释掉了熟悉python的话看起来不难，代码写得非常业余和不规范。另外只测试能跑和简单的正确性检查