在networkx图上执行贪婪层次聚类
项目描述
[](https://travis-ci.org/MSeal/agglom_cluster)
# hac
用于networkx图的层次聚类工具
## 聚类
实现了由以下论文描述的算法
"网络中社区结构检测的快速算法"
M. E. J. Newman. 2004
http://arxiv.org/pdf/cond-mat/0309508v1.pdf
该算法高效地聚类大量节点，是可用的最佳扩展聚类算法之一。它依赖于从networkx图的基础构建和切割潜在的聚类树状图。评估每个可能的元素配对，并按聚类质量（参见论文参考）增加的顺序进行聚类。这种方法贪婪的方面在于避免回溯。对树状图的每一轮遍历都假设先前的遍历是整体质量的局部最小值。考虑到合理的边关联，这是一个相对安全的假设，大大提高了算法的速度。
有关贪婪Newman的扩展和准确性的问题，请参阅相关论文。
此实现在每个迭代中选择最佳的聚类配对时使用堆
- 一种原始实现考虑了图中所有的“n”条边（O(n)）
- 堆将此搜索显著减少（O(log(n)）
## 安装
pip install agglomcluster
## 依赖
networkx -- 支持的绘图库
## 示例
import networkx as nx
from hac import GreedyAgglomerativeClusterer
clusterer = GreedyAgglomerativeClusterer()
# 这个聚类调用是大多数重负载发生的地方
karate_dendrogram = clusterer.cluster(nx.karate_club_graph())
karate_dendrogram.clusters(1)
井号 => [set(range(34))]
karate_dendrogram.clusters(2)
井号 => [set([0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21]),
set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31])]
karate_dendrogram.clusters(3)
井号 => [set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]),
set([1, 2, 3, 7, 9, 12, 13, 17, 21]),
set([0, 4, 5, 6, 10, 11, 16, 19])]
我们可以要求树状图选择最佳的聚类数量
karate_dendrogram.clusters()
井号 => [set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]),
set([1, 2, 3, 7, 9, 12, 13, 17, 21]),
set([0, 4, 5, 6, 10, 11, 16, 19])]
karate_dendrogram.labels()
# => { 0: 2, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 0, 9: 1, 10: 2, 11: 2,
12: 1, 13: 1, 14: 0, 15: 0, 16: 2, 17: 1, 18: 0, 19: 2, 20: 0, 21: 1, 22: 0,
23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 0, 29: 0, 30: 0, 31: 0, 32: 0, 33: 0 }
我们还可以强制某些节点始终被聚类在一起
forced_clusters = [set([33,0]), set([32,1])]
forced_karate_dendrogram = clusterer.cluster(nx.karate_club_graph(), forced_clusters=forced_clusters)
forced_karate_dendrogram.clusters()
井号 => [set([0, 33, 9, 11, 12, 14, 15, 17, 18, 19, 21, 26, 29]),
set([32, 1, 2, 3, 7, 8, 13, 20, 22, 30]),
set([23, 24, 25, 27, 28, 31]),
set([16, 10, 4, 5, 6])]
## 问题
* 实际的模块化得分与维基百科页面上的例子中的模块化得分不完全匹配（广泛使用和调查表明它不会影响结果的质量，只是使与参考文献论文的精确结果匹配变得困难）
- http://en.wikipedia.org/wiki/Modularity_(networks)
* 不处理不连通的组件（除非它们是大小为1的组件）
* 节点重命名很乱（增加了可哈希节点的依赖性）
* 使用树状图遍历用于两个不同的目的，这些目的没有明确定义/命名
## 局限性
* 聚类图内的节点必须是可哈希元素
* 不适用于有向图（待办事项：在无向图上操作）
* 不适用于负图（待办事项：添加此功能）
## TODO
* 将问题移动到github问题并从README中移除
* 考虑使用scikit稀疏矩阵进行树状图生成作为优化
* 将聚类过程转换为多线程/进程版本
* 考虑与scikit AgglomerativeCluster的接口/功能一致性
* 为聚类器添加除原始定义的质量之外的评估函数选项
* 几个方法需要文档说明
## 类
### GreedyAgglomerativeClusterer
用于生成表示聚类图的Dendrogram对象。使用 `.cluster()` 处理图。
### Dendrogram
聚合聚类的结果。使用 `.clusters()` 和 `.labels()` 获取所需的聚类结果。此外，此类还有一些内置的绘图方法 `.plot()` 和 `.plot_quality_history()`。
## 性能
近似性能在高性能机器上自然图大小上运行
节点 | 边 | 时间 | 内存
1000 | 6000 | 1.5 s | 28 MB
10000 | 80000 | 350 s | 2.5 GB
待办事项：更多大小
## 作者
作者：Matthew Seal
过去的作者/贡献者：Ethan Lozano, Zubin Jelveh
# hac
用于networkx图的层次聚类工具
## 聚类
实现了由以下论文描述的算法
"网络中社区结构检测的快速算法"
M. E. J. Newman. 2004
http://arxiv.org/pdf/cond-mat/0309508v1.pdf
该算法高效地聚类大量节点，是可用的最佳扩展聚类算法之一。它依赖于从networkx图的基础构建和切割潜在的聚类树状图。评估每个可能的元素配对，并按聚类质量（参见论文参考）增加的顺序进行聚类。这种方法贪婪的方面在于避免回溯。对树状图的每一轮遍历都假设先前的遍历是整体质量的局部最小值。考虑到合理的边关联，这是一个相对安全的假设，大大提高了算法的速度。
有关贪婪Newman的扩展和准确性的问题，请参阅相关论文。
此实现在每个迭代中选择最佳的聚类配对时使用堆
- 一种原始实现考虑了图中所有的“n”条边（O(n)）
- 堆将此搜索显著减少（O(log(n)）
## 安装
pip install agglomcluster
## 依赖
networkx -- 支持的绘图库
## 示例
import networkx as nx
from hac import GreedyAgglomerativeClusterer
clusterer = GreedyAgglomerativeClusterer()
# 这个聚类调用是大多数重负载发生的地方
karate_dendrogram = clusterer.cluster(nx.karate_club_graph())
karate_dendrogram.clusters(1)
井号 => [set(range(34))]
karate_dendrogram.clusters(2)
井号 => [set([0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21]),
set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31])]
karate_dendrogram.clusters(3)
井号 => [set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]),
set([1, 2, 3, 7, 9, 12, 13, 17, 21]),
set([0, 4, 5, 6, 10, 11, 16, 19])]
我们可以要求树状图选择最佳的聚类数量
karate_dendrogram.clusters()
井号 => [set([32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]),
set([1, 2, 3, 7, 9, 12, 13, 17, 21]),
set([0, 4, 5, 6, 10, 11, 16, 19])]
karate_dendrogram.labels()
# => { 0: 2, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 0, 9: 1, 10: 2, 11: 2,
12: 1, 13: 1, 14: 0, 15: 0, 16: 2, 17: 1, 18: 0, 19: 2, 20: 0, 21: 1, 22: 0,
23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 0, 29: 0, 30: 0, 31: 0, 32: 0, 33: 0 }
我们还可以强制某些节点始终被聚类在一起
forced_clusters = [set([33,0]), set([32,1])]
forced_karate_dendrogram = clusterer.cluster(nx.karate_club_graph(), forced_clusters=forced_clusters)
forced_karate_dendrogram.clusters()
井号 => [set([0, 33, 9, 11, 12, 14, 15, 17, 18, 19, 21, 26, 29]),
set([32, 1, 2, 3, 7, 8, 13, 20, 22, 30]),
set([23, 24, 25, 27, 28, 31]),
set([16, 10, 4, 5, 6])]
## 问题
* 实际的模块化得分与维基百科页面上的例子中的模块化得分不完全匹配（广泛使用和调查表明它不会影响结果的质量，只是使与参考文献论文的精确结果匹配变得困难）
- http://en.wikipedia.org/wiki/Modularity_(networks)
* 不处理不连通的组件（除非它们是大小为1的组件）
* 节点重命名很乱（增加了可哈希节点的依赖性）
* 使用树状图遍历用于两个不同的目的，这些目的没有明确定义/命名
## 局限性
* 聚类图内的节点必须是可哈希元素
* 不适用于有向图（待办事项：在无向图上操作）
* 不适用于负图（待办事项：添加此功能）
## TODO
* 将问题移动到github问题并从README中移除
* 考虑使用scikit稀疏矩阵进行树状图生成作为优化
* 将聚类过程转换为多线程/进程版本
* 考虑与scikit AgglomerativeCluster的接口/功能一致性
* 为聚类器添加除原始定义的质量之外的评估函数选项
* 几个方法需要文档说明
## 类
### GreedyAgglomerativeClusterer
用于生成表示聚类图的Dendrogram对象。使用 `.cluster()` 处理图。
### Dendrogram
聚合聚类的结果。使用 `.clusters()` 和 `.labels()` 获取所需的聚类结果。此外，此类还有一些内置的绘图方法 `.plot()` 和 `.plot_quality_history()`。
## 性能
近似性能在高性能机器上自然图大小上运行
节点 | 边 | 时间 | 内存
1000 | 6000 | 1.5 s | 28 MB
10000 | 80000 | 350 s | 2.5 GB
待办事项：更多大小
## 作者
作者：Matthew Seal
过去的作者/贡献者：Ethan Lozano, Zubin Jelveh
