資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究如何解決包含障礙物的聚類問題？
分割槽聚類方法是可取的，因為它最小化了集合與其聚類中心之間的距離。如果可以選擇k-means方法，那麼在存在障礙物的情況下，聚類中心可能不可用。
例如，聚類中心可能位於湖中心。換句話說，k-medoids方法選擇叢集內的一個物件作為中心，從而保證不會出現此類問題。
每次選擇一個新的中心點時，都需要重新計算每個物件與其新選擇的聚類中心之間的距離。由於兩個物件之間可能存在障礙物，因此兩個物件之間的距離可以通過幾何計算（例如，涉及三角測量）來推導。
如果包含大量的物件和障礙物，計算成本可能會很高。包含障礙物的聚類問題可以使用圖形描述來定義。首先，如果連線點p和點q的直線不與任何障礙物相交，則點p從區域R中的另一個點q可見。
可見性圖是圖VG = (V, E)，其中每個障礙物的頂點在V中都有一個等效節點，並且V中的兩個節點v1和v2當且僅當它們所定義的等效頂點彼此可見時，才由E中的邊連線。
令VG’ = (V’, E’)是由VG生成的可見性圖，透過在V’中插入兩個附加點p和q生成。E’包括在V0中新增兩個點的邊，如果這兩個點彼此可見。
它可以用來降低任何兩組物件或點之間距離計算的成本，可以使用多種預處理和最佳化方法。一種方法是將靠近在一起的點分組到微叢集中。這可以透過首先將區域R三角剖分，然後使用類似於BIRCH或DBSCAN的方法，將相似三角形中的附近點組合到微叢集中來完成。
透過處理微叢集而不是單個點，可以減少計算量。之後，可以實現預計算以構建兩種型別的連線索引，這取決於最短路徑的計算：
VV索引，用於某些障礙物頂點對。
MV索引，用於某些微叢集和障礙物頂點對。這些索引有助於進一步最佳化整體效能。
透過這種預計算和最佳化，可以有效地計算任意兩點（在微叢集粒度級別）之間的距離。因此，聚類過程可以以類似於典型的有效k-medoids演算法（包括CLARANS）的方式實現，併為大型資料集實現最佳聚類質量。
142 次瀏覽
