<p>您可以将问题重新解释为<a href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)" rel="nofollow noreferrer">graph</a>中的问题查找<a href="https://en.wikipedia.org/wiki/Clique_problem" rel="nofollow noreferrer"><em>cliques</em></a>。通过将距离0解释为在两个节点之间创建边,可以从距离矩阵中获得图形。一旦你有了这个图,你就可以使用<a href="https://networkx.org/documentation/stable/index.html" rel="nofollow noreferrer">networkx</a>(或者其他一些图论库)在图中找到派系。图中的派系将是一组节点,其中<em>所有</em>派系中的成对距离为0</p>
<p>这是您的距离矩阵(但请注意,您的距离不满足三角形不等式):</p>
<pre><code>In [136]: D
Out[136]:
array([[ 0, 29, 27, 1, 2, 1, 2, 1, 1],
[29, 0, 2, 30, 31, 29, 31, 30, 30],
[27, 2, 0, 28, 29, 27, 29, 28, 28],
[ 1, 30, 28, 0, 0, 0, 1, 2, 0],
[ 2, 31, 29, 0, 0, 0, 2, 2, 1],
[ 1, 29, 27, 0, 0, 0, 1, 2, 0],
[ 2, 31, 29, 1, 2, 1, 0, 3, 1],
[ 1, 30, 28, 2, 2, 2, 3, 0, 2],
[ 1, 30, 28, 0, 1, 0, 1, 2, 0]])
</code></pre>
<p>将距离矩阵转换为邻接矩阵<code>A</code>:</p>
<pre><code>In [137]: A = D == 0
In [138]: A.astype(int) # Display as integers for a more compact output.
Out[138]:
array([[1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 0, 1]])
</code></pre>
<p>创建networkx图<code>G</code>,并用<a href="https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.clique.find_cliques.html#networkx.algorithms.clique.find_cliques" rel="nofollow noreferrer">^{<cd3>}</a>查找派系:</p>
<pre><code>In [139]: import networkx as nx
In [140]: G = nx.Graph(A)
In [141]: cliques = nx.find_cliques(G)
In [142]: list(cliques)
Out[142]: [[0], [1], [2], [3, 5, 8], [3, 5, 4], [6], [7]]
</code></pre>
<p>(列表中的值是索引;例如,集团<code>[2]</code>对应于标签集<code>['ind3']</code>。)</p>
<p>请注意,有两个非平凡的派系,[3,5,8]和[3,5,4],其中3和5都出现。这是距离具有此异常数据的结果:距离(ind5,ind4)=0,距离(ind4,ind9)=0,但距离(ind5,ind9)=1(即<a href="https://en.wikipedia.org/wiki/Triangle_inequality#Metric_space" rel="nofollow noreferrer">triangle inequality</a>不满足)。因此,根据您对“集群”的定义,有两种可能的非平凡集群:[ind4,ind5,ind9]或[ind4,ind5,ind6]</p>
<p>最后,请注意<a href="https://networkx.org/documentation/stable/reference/algorithms/clique.html" rel="nofollow noreferrer">networkx documentation</a>中的警告:“在图中查找最大团是NP完全问题,因此大多数算法的运行时间都是指数级的”。如果距离矩阵很大,则此计算可能需要很长时间</p>