我怎样才能聚集在MATLAB连接的点？ [英] How can I cluster points which are connected in 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]
最终结果应该是af中 1,2,3,4 的节点在第二组（集群）中第一组（集群）和 5,6,7,8 的节点。
这是一些让你开始的代码。我基本上实现了Depth First Search ...这是一个非常粗糙的实现。
-first_searchrel =nofollow>深度优先搜索是一种用于遍历树的算法。图本质上是树的特殊情况，其中有叶节点连接回根。 Depth First Search的基本算法如下：- 从树的根开始并将其添加到堆栈中
- 对于连接到根节点的每个节点，将其添加到堆栈并将其放置在访问节点列表中
- 虽然节点上还有一个节点堆栈...
- 弹出堆栈中的节点
- 检查访问节点列表。如果这是我们已经访问过的节点，请跳过。
- 否则，请访问连接到此节点的任何节点，我们弹出并添加到堆栈中。
- 弹出堆栈中的节点
如果我们有断开连接多次搜索。每次都将用于一个群集。在一个深度优先搜索结果之后，我们将发现属于一个群集的节点。我们再次使用尚未触及的任何节点重新启动深度优先搜索，这将是来自另一个未访问的群集的节点。由于在图形结构中显然有两个集群，我们必须运行深度优先搜索两次。这通常被称为在整个图表中查找所有连接的组件。
要查找连接组件，以下是我所做的步骤：
- 创建一个连接矩阵
- 初始化一个布尔表，告诉我们是否有访问图中的一个节点
- 初始化一个空集群列表
- 初始化一个包含我们应该访问的节点的空栈。 b $ b
- 尽管至少有一个节点需要访问...
- 找到这样的节点
- 初始化我们的堆栈包含此节点
- 虽然我们的堆栈不是空的
- 从堆栈中弹出一个节点
- 如果我们访问了此节点，请继续
- 否则标记为已访问
- 检索连接到此节点的所有节点
- 删除不在（4）中的堆栈中的节点
- 将这些节点添加到堆栈和群集list
- 初始化我们的堆栈包含此节点
- 一旦堆栈为空，我们有一个列表包含在单个群集中的节点。
- 重复1 - 6，直到我们访问所有节点
- 初始化一个布尔表，告诉我们是否有访问图中的一个节点
毫不迟疑，这是代码。请记住，这不是战斗测试。如果你有图表结构会产生一个错误，那么你可以自己修改：）
$ pre $ 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];
％//查找所有可能的节点ID
nodeIDs = unique（ConnectivityMatrix（:)）;
％//标志告诉我们是否有任何节点应该访问
nodeIDList = false（1，numel（nodeIDs））;
％//存储我们的群集列表
clusterList = {};
％//跟踪我们有多少个群
counter = 1;
％//堆栈 - 初始化为空
stackNodes = [];
％//尽管至少有一个节点需要访问
（〜all（nodeIDList））
％查找任何节点
stackNodes = find（ nodeIDList == false，1）;
％初始化我们的堆栈以包含此节点
nodesCluster = stackNodes;
％//虽然我们的堆栈不是空的
while（〜isempty（stackNodes））
％从堆栈中取出节点并弹出
node = stackNodes （结束）;
stackNodes（end）= [];
％//如果我们已经将此节点标记为visited，则跳过
if（nodeIDList（node））
continue;
end
％//标记为拜访
nodeIDList（node）= true;
％//检索连接到此节点的所有节点
connectedNodes = ConnectivityMatrix（ConnectivityMatrix（：，1）== node，:);
nodesToVisit = unique（connectedNodes（：，2）。'）;
％//删除那些已经访问过的
visitedNodes =〜nodeIDList（nodesToVisit）;
finalNodesToVisit = nodesToVisit（visitedNodes）;
％//添加到群集
nodesCluster = unique（[nodesCluster finalNodesToVisit]）;
％//添加到堆栈
stackNodes = unique（[stackNodes finalNodesToVisit]）;
end
％//将连接的组件添加到它自己的集群
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）。
祝你好运！
Imagine we have many points which some of them are connected together and we want to cluster them.
Please take a look at the following figure.
If we have the "connectivity matrix" of points, how we can cluster them in two group (groups of connected points)?
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]
The final result should be nodes of 1,2,3,4 in a first group(cluster) and nodes of 5,6,7,8 in a second group (cluster).
Here is some code to get you started. I basically implemented Depth First Search... a very crude implementation of it anyway.
Depth First Search is an algorithm that is used for the traversal of trees. Graphs are essentially a special case of trees where there are leaf nodes that connect back to the root. The basic algorithm for Depth First Search is as so:
- Start at the root of the tree and add this to a stack
- For each node that is connected to the root, add this onto the stack and place this in a list of visited nodes
- While there is still a node on the stack...
- Pop off a node off the stack
- Check the visited nodes list. If this is a node we have already visited, skip.
- Else, visit any nodes that are connected to this node we popped off and add to the stack
If we have disconnected graphs like what you have above, we basically run Depth First Search multiple times. Each time will be for one cluster. After one Depth First Search result, we will discover nodes that belong to one cluster. We restart Depth First Search again with any node that we have not touched yet, which will be a node from another cluster that we have not visited. As you clearly have two clusters in your graph structure, we will have to run Depth First Search two times. This is commonly referred to as finding all connected components in an overall graph.
To find the Connected Components, here are the steps that I did:
- Create a connectivity matrix
- Initialize a Boolean list that tells us whether or not we have visited a node in your graph
- Initialize an empty cluster list
- Initialize an empty stack that contains which nodes we should visit.
- While there is at least one node we need to visit...
- Find such a node
- Initialize our stack to contain this node
- While our stack is not empty
- Pop off a node from the stack
- If we have visited this node, continue
- Else mark as visited
- Retrieve all nodes connected to this node
- Remove those nodes that are not on the stack in (4)
- Add these nodes to the stack and the cluster list
- Once the stack is empty, we have a list of all of the nodes contained in a single cluster. Add this cluster to a final list.
- Repeat 1 - 6 until we visit all nodes
Without further ado, this is the code. Bear in mind this is not battle tested. If you have graph structures that will generate an error, that'll be on your own to fix :)
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
Once we have run this code, we can display our clusters like so:
celldisp(clusterList)
clusterList{1} =
1 2 3 4
clusterList{2} =
5 6 7 8
As such, cluster #1 contains nodes 1,2,3,4 while cluster #2 contains nodes 5,6,7,8.
Bear in mind that this code will only work if you sequentially label your nodes as you did in your diagram. You can't skip any label numbers (i.e. you can't do 1,2,4,6,9, etc. This should be 1,2,3,4,5).
Good luck!
这篇关于我怎样才能聚集在MATLAB连接的点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
