想象我们有很多点,其中一些点连接在一起,我们想要将它们聚类。
请看下图。
如果我们有点的“连接矩阵”,我们如何将它们聚类为两组(连接点组)?
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
的节点。
这里有一些代码可以帮助您入门。我基本上实现了深度优先搜索……无论如何,这是一个非常粗略的实现。
深度优先搜索是一种用于遍历树的算法。图本质上是树的一种特殊情况,其中有连接回根的叶节点。深度优先搜索的基本算法如下:
如果我们有像上面这样的“断开连接”的图表,我们基本上会多次运行深度优先搜索。每次将针对一个簇。在一次深度优先搜索结果之后,我们将发现属于一个集群的节点。我们使用我们尚未触及的任何节点再次重新启动深度优先搜索,该节点将是来自我们尚未访问过的另一个集群的节点。由于您的图形结构中显然有两个集群,因此我们必须运行深度优先搜索两次。这通常称为在整个图中查找所有连接的组件。 要查找连接的组件,以下是我所做的步骤:
创建连接矩阵
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)。
祝你好运!
。不过,我想指出一些细节: 如果您的节点标签不是连续的(即您有 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的初始代码就没有问题了