Sting

統計信息網格STING

STING是一個基於網格的多解析度聚類技術，它將空間區域劃分為矩形單元。針對不同級別的解析度，通常存在多個級別的矩形單元，這些單元形成了一個層次結構：高層的每個單元被劃分為多個低一層的單元。關於每個網格單元屬性的統計信息（例如平均值，最大值，和最小值）被預先計算和存儲。這些統計變數可以方便下面描述的查詢處理使用。高層單元的統計變數可以很容易地從低層單元的變數計算得到。這些統計變數包括：屬性無關的變數 count；屬性相關的變數 m（平均值），s（標準偏差），min（最小值），max（最大值），以及該單元中屬性值遵循的分佈類型 distribution，例如正態的，均衡的，指數的，或無（如果分佈未知）。當數據被裝載進資料庫，最底層單元的變數 count，m，s，min，和 max 直接進行計算。如果分佈的類型事先知道，distribution 的值可以由用戶指定，也可以通過假設檢驗來獲得。一個高層單元的分佈類型可以基於它對應的低層單元多數的分佈類型，用一個閾值過濾過程來計算。如果低層單元的分佈彼此不同，閾值檢驗失敗，高層單元的分佈類型被置為 none。

統計變數的使用可以以自頂向下的基於網格的方法。首先，在層次結構中選定一層作為查詢處理的開始點。通常，該層包含少量的單元。對當前層次的每個單元，計算置信度區間（或者估算其概率），用以反映該單元與給定查詢的關聯程度。不相關的單元就不再考慮。低一層的處理就只檢查剩餘的相關單元。這個處理過程反覆進行，直到達到最底層。此時，如果查詢要求被滿足，那麼返回相關單元的區域。否則，檢索和進一步的處理落在相關單元中的數據，直到它們滿足查詢要求。

與其它聚類演演算法相比，STING有幾個優點：

（1）由於存儲在每個單元中的統計信息描述了單元中數據的與查詢無關的概要信息，所以基於網格的計算是獨立於查詢的；

（2）網格結構有利於并行處理和增量更新；

（3）該方法的效率很高：STING 掃描資料庫一次來計算單元的統計信息，因此產生聚類的時間複雜度是 O（n），n 是對象的數目。

在層次結構建立后，查詢處理時間是 O（g），這裡 g 是最底層網格單元的數目，通常遠遠小於 n。由於 STING 採用了一個多解析度的方法來進行聚類分析，STING 聚類的質量取決於網格結構的最底層的粒度。如果粒度比較細，處理的代價會顯著增加；但是，如果網格結構最底層的粒度太粗，將會降低聚類分析的質量。而且，STING 在構建一個父親單元時沒有考慮孩子單元和其相鄰單元之間的關係。因此，結果簇的形狀是（isothetic），即所有的聚類邊界或者是水平的，或者是豎直的，沒有斜的分界線。儘管該技術有快速的處理速度，但可能降低簇的質量和精確性。