如何在 MATLAB 中对连接的点进行聚类？

Question

想象我们有很多点，其中一些点连接在一起，我们想要将它们聚类。

请看下图。

如果我们有点的“连接矩阵”，我们如何将它们聚类为两组（连接点组）？

ConnectivityMatrix=
                    [1 2
                     1 3
                     2 4
                     2 3
                     2 1
                     3 1
                     3 2
                     3 4
                     4 3
                     4 2
                     5 8
                     5 7
                     5 6
                     6 5
                     6 7
                     7 6
                     7 5
                     7 8
                     8 7
                     8 5]

最终结果应该是第一组（簇）中

1,2,3,4

的节点和第二组（簇）中

5,6,7,8

的节点。

Answer 1

这里有一些代码可以帮助您入门。我基本上实现了深度优先搜索……无论如何，这是一个非常粗略的实现。

深度优先搜索是一种用于遍历树的算法。图本质上是树的一种特殊情况，其中有连接回根的叶节点。深度优先搜索的基本算法如下：

• 从树的根部开始并将其添加到堆栈中
• 对于连接到根的每个节点，将其添加到堆栈中并将其放入已访问节点列表中
• 虽然堆栈上还有一个节点...
  1. 从堆栈中弹出一个节点
  2. 查看访问过的节点列表。如果这是我们已经访问过的节点，则跳过。
  3. 否则，访问连接到我们弹出的该节点的任何节点并添加到堆栈中

如果我们有像上面这样的“断开连接”的图表，我们基本上会多次运行深度优先搜索。每次将针对一个簇。在一次深度优先搜索结果之后，我们将发现属于一个集群的节点。我们使用我们尚未触及的任何节点再次重新启动深度优先搜索，该节点将是来自我们尚未访问过的另一个集群的节点。由于您的图形结构中显然有两个集群，因此我们必须运行深度优先搜索两次。这通常称为在整个图中查找所有连接的组件。 要查找连接的组件，以下是我所做的步骤：

创建连接矩阵

1. 初始化一个布尔列表，告诉我们是否访问过图中的节点
2. 初始化一个空的簇列表
3. 初始化一个空堆栈，其中包含我们应该访问的节点。
4. 虽然我们至少需要访问一个节点......
5. 找到这样一个节点
   • 初始化我们的堆栈以包含此节点
   • 虽然我们的堆栈不为空
   • 从堆栈中弹出一个节点
     1. 如果我们已经访问过这个节点，则继续
     2. 否则标记为已访问
     3. 检索连接到该节点的所有节点
     4. 删除（4）中不在栈中的那些节点
     5. 将这些节点添加到堆栈和集群列表中
   一旦堆栈为空，我们就有了单个集群中包含的所有节点的列表。将此集群添加到最终列表中。
6. 重复 1 - 6 直到访问所有节点
话不多说，这就是代码。请记住，这还没有经过战斗考验。如果您的图形结构会产生错误，则需要您自行修复:)

ConnectivityMatrix = [1 2
                     1 3
                     2 4
                     2 3
                     2 1
                     3 1
                     3 2
                     3 4
                     4 3
                     4 2
                     5 8
                     5 7
                     5 6
                     6 5
                     6 7
                     7 6
                     7 5
                     7 8
                     8 7
                     8 5];

%// Find all possible node IDs
nodeIDs = unique(ConnectivityMatrix(:));

%// Flag that tells us if there are any nodes we should visit
nodeIDList = false(1,numel(nodeIDs));

%// Stores our list of clusters
clusterList = {};

%// Keeps track of how many clusters we have
counter = 1;

%// Stack - initialize to empty
stackNodes = [];

%// While there is at least one node we need to visit
while (~all(nodeIDList))    
    % Find any node
    stackNodes = find(nodeIDList == false, 1);
    % Initialize our stack to contain this node
    nodesCluster = stackNodes;

    %// While our stack is not empty
    while (~isempty(stackNodes))
        % Grab the node off the stack and pop off
        node = stackNodes(end);
        stackNodes(end) = [];        

        %// If we have marked this node as visited, skip
        if (nodeIDList(node))
            continue;
        end

        %// Mark as visited 
        nodeIDList(node) = true;

        %// Retrieve all nodes connected to this node
        connectedNodes = ConnectivityMatrix(ConnectivityMatrix(:,1) == node, :);
        nodesToVisit = unique(connectedNodes(:,2).');

        %// Remove those already visited
        visitedNodes = ~nodeIDList(nodesToVisit);
        finalNodesToVisit = nodesToVisit(visitedNodes);

        %// Add to cluster
        nodesCluster = unique([nodesCluster finalNodesToVisit]);

        %// Add to stack
        stackNodes = unique([stackNodes finalNodesToVisit]);                
    end

    %// Add connected components to its own cluster
    clusterList{counter} = nodesCluster;
    counter = counter + 1;
end

运行此代码后，我们可以像这样显示集群：

celldisp(clusterList)

clusterList{1} =

 1     2     3     4


clusterList{2} =

 5     6     7     8

因此，集群 #1 包含节点 1,2,3,4，而集群 #2 包含节点 5,6,7,8。 

请记住，只有当您像在图表中那样按顺序标记节点时，此代码才会起作用。您不能跳过任何标签编号（即您不能执行 1,2,4,6,9 等。这应该是 1,2,3,4,5）。

祝你好运！

Answer 2

graphconncomp

。

Answer 3

rayryeng 的回答非常好

。不过，我想指出一些细节： 如果您的节点标签不是连续的（即您有 10 个节点，最大节点标签为 20），则

“

numel(nodeIDs)
• ”可能会带来错误。您可以将“

  numel(nodeIDs)

  ”切换为“

  max(nodeIDs)

  或更大的值。”
我也相信下面的代码在使用这个功能时会带来一些问题（即一些节点丢失并成为孤立的节点）：

• connectedNodes = ConnectivityMatrix(ConnectivityMatrix(:,1) == node, :);
  nodesToVisit = unique(connectedNodes(:,2).');

  我用下面的乱码修改了简单的两行：

  connectedNodes1 = ConnectivityMatrix (ConnectivityMatrix (:,1) == node, :);
  connectedNodes2 = ConnectivityMatrix (ConnectivityMatrix (:,2) == node, :);
  AC=connectedNodes1(:,2).';
  AD=connectedNodes2(:,1).';
  ACA=reshape(AC,[],1);
  ADA=reshape(AD,[],1);
  AE= [ACA; ADA] ;
  AEA=reshape(AE,[],1);
  AEA=AEA';
  nodesToVisit = unique(AEA);

  修改这两点后，rayryeng的初始代码就没有问题了