申論題

在 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)。