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

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

请看下图。

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

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在第二组（集群）中。

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

深度优先搜索 http://en.wikipedia.org/wiki/Depth-first_search是一种用于遍历树的算法。图本质上是树的一种特殊情况，其中存在连接回根的叶节点。深度优先搜索的基本算法如下：

• 从树的根开始并将其添加到堆栈中
• 对于连接到根的每个节点，将其添加到堆栈中并将其放入已访问节点列表中
• While there is still a node on the stack...
  1. 从堆栈中弹出一个节点
  2. 检查访问过的节点列表。如果这是我们已经访问过的节点，则跳过。
  3. 否则，访问连接到我们弹出的该节点的任何节点并将其添加到堆栈中

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

要查找连接的组件，我执行了以下步骤：

1. 创建连接矩阵
2. 初始化一个布尔列表，告诉我们是否访问过图中的节点
3. 初始化一个空的簇列表
4. 初始化一个空堆栈，其中包含我们应该访问的节点。
5. While there is at least one node we need to visit...
   • 找到这样一个节点
   • 初始化我们的堆栈以包含该节点
   • While our stack is not empty
     1. 从堆栈中弹出一个节点
     2. 如果我们已经访问过这个节点，则继续
     3. 否则标记为已访问
     4. 检索与该节点连接的所有节点
     5. 删除(4)中不在栈中的节点
     6. 将这些节点添加到堆栈和集群列表中
6. 一旦堆栈为空，我们就有了单个集群中包含的所有节点的列表。将此集群添加到最终列表中。
7. 重复 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）。

祝你好运！