如何解决存在障碍的聚类问题?
分区聚类方法是理想的，因为它可以最小化集合与其聚类中心之间的距离。如果可以选择k均值方法，则由于存在障碍，无法找到聚类中心。
例如，聚类结果可能位于湖泊的中心。换句话说，k-中心点方法选择聚类内部的一个对象作为中心，从而保证不会出现问题。
每次选择新的中心点时，都必须重新计算每个对象与其新选择的聚类中心之间的距离。由于两个对象之间可能存在障碍，因此可以通过几何计算(例如，涉及三角测量)得出两个对象之间的距离。
如果包含大量对象和障碍物，计算成本可能会很高。可以使用图形描述来定义存在障碍的聚类问题。首先，如果点 p 和 q 的邻接直线不与某些障碍物相交，则在区域 R 中，点 p 从另一点 q 可见。
可视性图是指图 V G = (V, E)，其中障碍物的每个顶点在 V 中都有一个等效节点，并且 V 中的两个节点 v1 和 v2 在 E 中通过一条边连接，当且仅当它们定义的等效顶点彼此可见。
设 VG' = (V', E') 为通过在 V' 中插入两个额外点 p 和 q 生成的可视性图。如果 V0 中的两个点共同可见，则 E' 包含一条连接这两个点的边。
它可用于降低任意两组对象或点之间距离计算的成本，可以使用多种预处理和优化方法。有一种方法是将邻近的点组合成微簇。这可以通过首先将区域 R 三角剖分成三角形，然后将相似三角形中的邻近点组合成微簇来实现，方法 类似于 BIRCH 或 DBSCAN。
通过处理微簇而不是单个点，可以减少总计算量。之后，可以进行预计算，以构建两种类型的连接索引，这些索引取决于最短路径的计算。
VV 索引，用于某些障碍顶点对。
MV 索引，用于某些微簇和障碍顶点对。它有助于索引，从而进一步优化整体性能。
通过这种预计算和优化，可以有效地计算任意两点之间的距离(以微簇的粒度计算)。因此，聚类过程可以以类似于典型的有效k-medoids算法(包括CLARANS)的方式实现，并对海量数据集实现最佳聚类质量。
