发明名称 |
一种基于图计算技术的大规模数据聚类方法 |
摘要 |
本发明公开了一种基于图计算技术的大规模数据聚类方法。本方法为:1)从待处理图数据的所有顶点中选取N个顶点作为候选聚类中心;2)设置每一候选聚类中心的簇标签值,然后根据一加权无向图G将候选聚类中心合并,将属于同一聚类簇的候选聚类中心划分到同一集合中;3)候选聚类中心将包含自己当前簇标签值以及权重的消息传递给相邻顶点;收到消息的顶点根据簇标签值将本次迭代收到的所有消息分成不同的类别,然后生成新的消息并在下一迭代时传递给相邻顶点;4)迭代结束后,对于每一顶点,计算具有相同标签类型的边的权重之和,得到每一顶点最后的结果值;将具有相同结果值的顶点聚为一类。本发明节约了时间和存储开销。 |
申请公布号 |
CN104951505A |
申请公布日期 |
2015.09.30 |
申请号 |
CN201510260191.X |
申请日期 |
2015.05.20 |
申请人 |
中国科学院信息工程研究所;国家计算机网络与信息安全管理中心 |
发明人 |
周薇;马宏远;包秀国;程工;刘纬;刘春阳;王卿;韩冀中;庞琳;李雄;刘玮;贺敏 |
分类号 |
G06F17/30(2006.01)I |
主分类号 |
G06F17/30(2006.01)I |
代理机构 |
北京君尚知识产权代理事务所(普通合伙) 11200 |
代理人 |
司立彬 |
主权项 |
一种基于图计算技术的大规模数据聚类方法,其步骤为:1)从待处理图数据的所有顶点中选取N个顶点作为候选聚类中心,得到一候选聚类中心列表;2)设置每一候选聚类中心的簇标签值,然后根据一加权无向图G将所述候选聚类中心进行合并,将属于同一聚类簇的候选聚类中心划分到同一集合中,将顶点聚为k类;其中,N大于k,同一集合中的候选聚类中心采用同一标签;3)根据该加权无向图G,每个候选聚类中心将包含自己当前簇标签值以及权重的消息传递给相邻顶点;收到消息的顶点根据消息中的簇标签值将本次迭代收到的所有消息分成不同的类别,然后生成新的消息并在下一迭代过程中将其传递给相邻顶点;4)迭代结束后,对于每一顶点,计算具有相同标签类型的边的权重之和,得到每一顶点最后的结果值;然后将图数据中具有相同结果值的顶点聚为一类。 |
地址 |
100093 北京市海淀区闵庄路甲89号 |