如何组群由包含的元素相似(How to group sets by similarity in co

我使用Python 2.7。我有其由连接到每个其它节点的阵列的路由。该节点由一个字符串键标识，但为了方便，我将使用数字：

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

我将创建一个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，作为例子。这是那种我使用的数据（虽然这些易于阅读简化）。

有一段时间受益于此。如果我可以删除冗余路由，我会剪掉了相当多的时间。

我会建议寻找到networkx包。它允许你创建有向图，如你所描述。为了测量2路的相似性，我建议Jaccard相似指数。这里是表示你所示的示例代码。

首先，导入一些库：图，绘图，和数字蟒蛇。然后，通过从节点编号加1的节点8.生成的连接到节点来构建路径建立有向图。所述networkx包具有内置的能力，以找到在图中从一个节点到另一个的所有路径： nx.all_simple_paths(g, start_node, end_node)

一旦有了所有路径，则可以计算出的矩阵， J ，路径之间的Jaccard相似的。你如何真正想要通过他们的相似性聚类的路径是由你。

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.        ]]