如何解决包含障碍物的聚类问题？

分区聚类方法是可取的，因为它最小化了集合与其聚类中心之间的距离。如果可以选择k-means方法，那么在存在障碍物的情况下，聚类中心可能不可用。

例如，聚类中心可能位于湖中心。换句话说，k-medoids方法选择集群内的一个对象作为中心，从而保证不会出现此类问题。

每次选择一个新的中心点时，都需要重新计算每个对象与其新选择的聚类中心之间的距离。由于两个对象之间可能存在障碍物，因此两个对象之间的距离可以通过几何计算（例如，涉及三角测量）来推导。

如果包含大量的对象和障碍物，计算成本可能会很高。包含障碍物的聚类问题可以使用图形描述来定义。首先，如果连接点p和点q的直线不与任何障碍物相交，则点p从区域R中的另一个点q可见。

可见性图是图VG = (V, E)，其中每个障碍物的顶点在V中都有一个等效节点，并且V中的两个节点v₁和v₂当且仅当它们所定义的等效顶点彼此可见时，才由E中的边连接。

令VG’ = (V’, E’)是由VG生成的可见性图，通过在V’中插入两个附加点p和q生成。E’包括在V0中添加两个点的边，如果这两个点彼此可见。

它可以用来降低任何两组对象或点之间距离计算的成本，可以使用多种预处理和优化方法。一种方法是将靠近在一起的点分组到微集群中。这可以通过首先将区域R三角剖分，然后使用类似于BIRCH或DBSCAN的方法，将相似三角形中的附近点组合到微集群中来完成。

通过处理微集群而不是单个点，可以减少计算量。之后，可以实现预计算以构建两种类型的连接索引，这取决于最短路径的计算：

• VV索引，用于某些障碍物顶点对。

• MV索引，用于某些微集群和障碍物顶点对。这些索引有助于进一步优化整体性能。

通过这种预计算和优化，可以有效地计算任意两点（在微集群粒度级别）之间的距离。因此，聚类过程可以以类似于典型的有效k-medoids算法（包括CLARANS）的方式实现，并为大型数据集实现最佳聚类质量。

Ginni

更新于：2022年2月17日

142 次浏览

开启你的职业生涯

完成课程获得认证

开始学习