如何根据包含元素的相似性对集合进行分组

Question

我正在使用 Python 2.7。我的路线由相互连接的节点数组组成。节点由字符串键标识，但为方便起见，我将使用数字：

sample_route = [1,2,3,4,7] 
#obviously over-simplified; real things would be about 20-40 elements long

我将使用 zip 创建一个由点连接的元组对组成的 set，最终会像：

set([(1,2),(2,3),(3,4),(4,7)])

我需要一种方法来过滤掉一些非常相似的路线（比如一个或两个添加的节点），并使用那些接近重复的路线中的最小路线。我现在的计划是：

从第一条（可能是最优的）路线开始。遍历其余的路由，并使用以下公式计算其与步骤1中序列的相似度：

matching = len(value1.difference(value2)) + len(value2.difference(value1))
#value1, value2 = two compared sets

数字越小，越相似。但是 根据与其他路线的相似性对路线进行分组的好方法是什么？它们的长度都不同。我从未上过统计课程。

示例：

sets = [
  set([(1,2),(2,3),(3,4),(4,5),(5,10)]),
  set([(1,2),(2,3),(3,4),(4,6),(6,5),(5,10)]),
  set([(1,7),(7,3),(3,8),(8,7),(7,6),(6,5),(5,10)]),
  set([(1,2),(2,3),(3,4),(4,6),(6,5),(5,10)]),
  set([(1,9),(9,4),(4,5),(5,10)]),
  set([(1,9),(9,4),(4,6),(6,5),(5,10)])
]

在此示例中，分组可能类似于 [[1,2,4],[3],[5,6]]，其中 1、2 和 4 非常相似，5 和 6 相似，而 3 与其他任何一个都不相近。例如，1 到 2 的得分为 2，3 到 6 的得分为 8。这是我正在使用的数据类型（尽管这些数据经过简化后易于阅读）。

这有时间上的好处。如果我可以删除多余的路由，我将 trim 节省相当多的时间。

Answer 1

我建议查看 networkx 包。它允许您创建有向图，例如您所描述的。为了衡量两条路线的相似性，我会推荐 Jaccard similarity index。这是显示您说明的示例的代码。

首先，导入几个库：图形、绘图和数值 python。然后通过添加编号为 1 到 8 的节点来构建有向图。构建从节点到节点的连接以构建您的路径。 networkx 包具有在图中查找从一个节点到另一个节点的所有路径的内置功能：nx.all_simple_paths(g, start_node, end_node)。

获得所有路径后，您可以计算路径之间 Jaccard 相似度的矩阵 J。您实际上如何根据相似性对路径进行聚类取决于您。

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

g = nx.DiGraph()
g.add_nodes_from(range(1,8))
g.add_edges_from([(1,2),(2,3),(3,4),(4,7)]) #path 1,2,3,4,7
g.add_edges_from([(4,5),(5,7)])             #path 1,2,3,4,5,7
g.add_edges_from([(4,6),(6,7)])             #path 1,2,3,4,6,7
paths_iter = nx.all_simple_paths(g,1,7)
paths = [p for p in paths]

np.random.seed(100000)
nx.draw_spring(g, with_labels=True)
plt.show()

def jaccard(v1, v2):
    return (len(np.intersect1d(v1,v2))+0.0)/len(np.union1d(v1,v2))

J = np.zeros([len(paths),len(paths)])
for i in range(J.shape[0]):
    for j in range(i, J.shape[1]):
        J[i,j] = J[j,i] = jaccard(paths[i],paths[j])

print J

> [[ 1.          0.71428571  0.83333333]
>  [ 0.71428571  1.          0.83333333]
>  [ 0.83333333  0.83333333  1.        ]]

编辑由于您有一个度量来比较路径之间的相似性，因此请研究 k-means 聚类以将路径聚类在一起。

from scipy.cluster.vq import kmeans2

我没有足够的代码或数据从这一点开始提供帮助。

如何根据包含元素的相似性对集合进行分组

How to group sets by similarity in contained elements

python

similarity

set