題組內容

一、BIRCH 是一個 hierarchical clustering 方法，可以處理大量資料，以及避免雜訊(noisy)資料的問題，請簡答以下題目：

(二)此方法利用一種 tree 資料結構，請說明 internal 節點(除 pointer 之外)儲存何種資料？

詳解 (共 1 筆)

詳解 提供者：hchungw

在 BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）方法中，利用了一種稱為 CF 樹（Clustering Feature Tree）的樹狀資料結構。CF 樹的內部節點（Internal Nodes）除了指標（pointers）之外，還儲存了一些特定的資料結構，這些資料有助於有效地進行聚類操作。

CF 樹內部節點儲存的資料

內部節點除了指向子節點的指標之外，還儲存以下主要的聚類特徵（Clustering Features, CFs）：

  1. 子節點數量（Number of Child Nodes）：

    • 內部節點包含了指向其子節點的指標數量，用於管理和導航樹結構。

  2. 聚類特徵（Clustering Feature, CF）：

    • 聚類特徵是一個三元組，包含以下三個成分：
      • N：簇中資料點的數量。
      • LS（Linear Sum）：簇中所有資料點的向量和，即 ∑i=1NXi\sum_{i=1}^N X_i∑i=1N​Xi​，其中 XiX_iXi​ 是第 i 個資料點。
      • SS（Squared Sum）：簇中所有資料點的平方和，即 ∑i=1NXi2\sum_{i=1}^N X_i^2∑i=1N​Xi2​。

    聚類特徵 CF 可以幫助快速計算簇的中心、範圍和其他統計信息，而不需要遍歷所有資料點。CF 的數學表示為：

    CF=(N,LS,SS)CF = (N, LS, SS)CF=(N,LS,SS)

CF 樹內部節點的作用

內部節點的這些聚類特徵和指標主要用於以下方面：

  1. 快速聚類計算：

    • 通過儲存聚類特徵，內部節點可以快速計算簇的中心、半徑和密度等特性，這有助於加快聚類過程。

  2. 有效管理樹結構：

    • 內部節點管理子節點的指標，使得 CF 樹能夠以層次化的方式組織和儲存資料，這對於處理大規模資料集尤為重要。

  3. 縮減計算成本：

    • 使用聚類特徵，內部節點能夠減少直接對資料點進行計算的需求，降低了計算複雜度和記憶體使用量。

內部節點的範例

假設一個內部節點有兩個子節點，並且它儲存以下聚類特徵：

  • 子節點數量：2
  • 子節點指標：[Child1, Child2]
  • 聚類特徵 CF：
    • N = 100
    • LS = (200.0, 300.0)
    • SS = (4000.0, 9000.0)

這意味著該內部節點的兩個子節點共包含 100 個資料點，其向量和為 (200.0, 300.0)，平方和為 (4000.0, 9000.0)。