什麼是基於網格的 STING 聚類？

基於網格的聚類方法使用多解析度網格資料結構。它將物件區域量化為有限數量的單元格，這些單元格形成一個網格結構，所有聚類操作都在該結構上實現。該方法的優點是其快速的處理時間，通常與資料物件的數量無關，而僅取決於量化空間中每個維度中的多個單元格。

基於網格的聚類使用多解析度網格資料結構，並使用密集的網格單元格來形成聚類。有一些有趣的方法，例如 STING、wave cluster 和 CLIQUE。

STING - 一種統計資訊網格方法。空間區域被分割成矩形單元格。存在對應於不同解析度方法的各個級別的單元格。每個高級別的單元格在下一級較低級別中被分成多個較小的單元格。每個單元格的統計資料預先計算並存儲，並且可以回答查詢。高級別單元格的規範可以簡單地從低級別單元格的規範計算出來

  • 計數、均值、標準差、最小值、最大值
  • 分佈型別 - 正態分佈、均勻分佈等。

基於統計資訊網格的方法 (STING) 採用分層方法將空間區域劃分為矩形單元格，類似於四叉樹。空間資料庫被掃描一次，併為每個單元格確定統計引數。STING 技術可以被視為一種分層方法。第一步是進行分層描述。建立的樹將區域分別劃分為象限。

建立樹的過程如下面的演算法所示。空間中的每個單元格對應於樹中的一個節點，並用屬性無關（計數）資料和屬性相關（均值、標準差、最小值、最大值分佈）資料來描述。由於樹中節點的數量小於資料庫中專案的數量，因此 STING BUILD 的複雜度為 O(n)。

演算法

輸入

D // Data to be placed in the hierarchical structure
k // Number of desired cells at the lowest level

輸出

T // Tree
STING BUILD algorithm
// Create an empty tree from top-down
   T = root node with data values initialized; // Initially only root node
   i = 1;
   repeat
      for each node in level i do
      create 4 children nodes with initial values;
   i = i +1;
   until 4i = k;
   // Populate tree from bottom-up for each item in D do
   determine leaf node j related to the position of D;
   update values of j based on attribute values in item;
   i := log4(k);
   repeat
   i: = i - 1;
   for each node j in level i do
update values of j based on attribute values in its 4 children;
until i = 1;

更新於: 2022年2月15日

4K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告