バーチ

BIRCH ( balanced iterative refined and clustering using hierarchies )は、特に大規模なデータセットに対して階層的クラスタリングを実行するために使用される教師なしデータマイニングアルゴリズムです。 ^{[1]また、修正を加えると、}期待値最大化アルゴリズムを使用してk-means クラスタリングやガウス混合モデリングを高速化するために使用することもできます。^{[2] BIRCH の利点は、与えられたリソースセット (メモリと}時間の制約)に対して最高品質のクラスタリングを生成するために、入ってくる多次元メトリックデータポイントを段階的かつ動的にクラスタリングできることです。ほとんどの場合、BIRCH ではデータベースを 1 回スキャンするだけで済みます。

発明者は、BIRCH は「データベース分野で提案された、基礎となるパターンの一部ではないデータ ポイントである「ノイズ」を効果的に処理する最初のクラスタリング アルゴリズム」であると主張しています^{[1] 。これは}DBSCANより 2 か月早いものです。BIRCH アルゴリズムは、2006 年に SIGMOD 10 年間のテスト賞を受賞しました^[3]。

以前のクラスタリング アルゴリズムは、非常に大規模なデータベースでは効率が悪く、データセットが大きすぎてメイン メモリに収まらない場合を適切に考慮していませんでした。その結果、追加の IO (入力/出力) 操作のコストを最小限に抑えながら、高いクラスタリング品質を維持するには、多くのオーバーヘッドが発生しました。さらに、BIRCH の前身のほとんどは、各「クラスタリング決定」ですべてのデータ ポイント (または現在存在するすべてのクラスター) を均等に検査し、これらのデータ ポイント間の距離に基づいてヒューリスティックな重み付けを実行しません。

これは、すべてのデータ ポイントと現在存在するクラスターをスキャンせずに、各クラスタリング決定を行うという点でローカルです。データ スペースは通常均一に占有されているわけではなく、すべてのデータ ポイントが同じように重要というわけではないという観察を活用します。使用可能なメモリを最大限に活用して、I/O コストを最小限に抑えながら、可能な限り細かいサブ クラスターを導き出します。また、これは、事前に データ セット全体を必要としない増分方式でもあります。

BIRCH アルゴリズムは、実数値ベクトルとして表されるN 個のデータ ポイントのセットと、必要なクラスター数Kを入力として受け取ります。このアルゴリズムは 4 つのフェーズで動作し、そのうち 2 番目のフェーズはオプションです。

最初のフェーズでは、データ ポイントからクラスタリング機能 ( ) ツリー、つまり次のように定義される 高さバランスの取れたツリー データ構造 を構築します。${\displaystyle CF}$

• N個のd次元データポイントの集合が与えられた場合、集合のクラスタリング特徴 は3つの として定義され、ここで ${\displaystyle CF}$${\displaystyle CF=(N,{\overrightarrow {LS}},SS)}$
  • ${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}$線形和です。
  • ${\displaystyle SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}}$データポイントの二乗和です。
• クラスタリング機能は、 CF ツリーに編成されます。CF ツリーは、2 つのパラメータ^{[説明が必要]} 分岐係数 としきい値を持つ高さ調整されたツリーです。各非リーフ ノードには、最大で の形式のエントリが含まれます。ここで、 は、その番目の子ノードと、関連付けられたサブクラスタを表すクラスタリング機能へのポインタです。リーフ ノードには、最大で の形式のエントリが含まれます。また、すべてのリーフ ノードを連結するために使用される 2 つのポインタ prev と next もあります。ツリーのサイズは、パラメータ によって異なります。ノードは、サイズ のページに収まる必要があります。および は、によって決定されます。したがって、パフォーマンス チューニングのために変更できます。リーフ ノードの各エントリは単一のデータ ポイントではなくサブクラスタであるため、これはデータセットの非常にコンパクトな表現です。${\displaystyle B}$${\displaystyle T}$${\displaystyle B}$${\displaystyle [CF_{i},child_{i}]}$${\displaystyle child_{i}}$${\displaystyle i}$${\displaystyle CF_{i}}$${\displaystyle L}$${\displaystyle [CF_{i}]}$${\displaystyle T}$${\displaystyle P}$${\displaystyle B}$${\displaystyle L}$${\displaystyle P}$${\displaystyle P}$

2 番目のステップでは、アルゴリズムは初期ツリーのすべてのリーフ エントリをスキャンして、外れ値を削除し、混雑したサブクラスターをより大きなサブクラスターにグループ化しながら、より小さなツリーを再構築します。このステップは、BIRCH の元のプレゼンテーションではオプションとしてマークされています。 ${\displaystyle CF}$${\displaystyle CF}$

ステップ 3 では、既存のクラスタリング アルゴリズムを使用して、すべてのリーフ エントリをクラスタ化します。ここでは、凝集型階層クラスタリング アルゴリズムが、ベクトルで表されるサブクラスタに直接適用されます。また、ユーザーが希望するクラスタ数またはクラスタの希望する直径しきい値を指定できる柔軟性も提供されます。このステップの後、データの主要な分布パターンを捉えたクラスタ セットが取得されます。ただし、オプションのステップ 4 で処理できる、軽微で局所的な不正確さが存在する可能性があります。ステップ 4 では、ステップ 3 で生成されたクラスタの重心がシードとして使用され、データ ポイントが最も近いシードに再配分されて、新しいクラスタ セットが取得されます。ステップ 4 では、外れ値を破棄するオプションも提供されます。つまり、最も近いシードから遠すぎるポイントは外れ値として扱うことができます。 ${\displaystyle CF}$

クラスタリング機能のみが与えられている場合、基礎となる実際の値がわからなくても同じ測定値を計算できます。 ${\displaystyle CF=[N,{\overrightarrow {LS}},SS]}$

• 重心:${\displaystyle {\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}}$
• 半径：${\displaystyle R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}}$
• クラスター間の平均リンク距離:${\displaystyle CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]}$${\displaystyle CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]}$${\displaystyle D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}}$

多次元の場合、平方根は適切なノルムに置き換える必要があります。

BIRCH は距離 DO から D3 を使用して最も近いリーフを見つけ、次に半径 R または直径 D を使用して、データを既存のリーフに吸収するか、新しいリーフを追加するかを決定します。

残念ながら、 BIRCH で項を使用することに関連する数値的な問題があります。などの他の距離で または を減算すると、壊滅的な相殺が発生して精度が低下し、場合によっては結果が負になることもあります (その場合、平方根は未定義になります)。^[2]この問題は、代わりに BETULA クラスター機能を使用することで解決できます。BETULA クラスター機能は、分散 を計算する数値的により信頼性の高いオンライン アルゴリズムに基づいて、カウント、平均、偏差の二乗和を格納します。これらの機能では、同様の加法性定理が成り立ちます。偏差の二乗のベクトルまたは行列を格納する場合、結果として得られる BIRCH CF ツリーは、k 平均法クラスタリングや階層的凝集型クラスタリングの他に、期待値最大化アルゴリズムを使用したガウス混合モデリングを高速化するためにも使用できます。 ${\displaystyle SS}$${\displaystyle {\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}}$${\displaystyle D_{2}}$${\displaystyle CF=(N,\mu ,S)}$${\displaystyle N}$${\displaystyle \mu }$

線形和と二乗和を保存する代わりに、各クラスター特徴における平均と平均からの二乗偏差を保存することができる。^[4]ここで ${\displaystyle CF'=(N,\mu ,S)}$

• ${\displaystyle n}$ノードの重み（ポイント数）
• ${\displaystyle \mu }$ノード中心ベクトル（算術平均、重心）
• ${\displaystyle S}$平均からの偏差の二乗の合計です（アプリケーションに応じて、ベクトルまたはメモリを節約するための合計のいずれかになります）

ここでの主な違いは、S が原点ではなく中心を基準に計算されることです。

1つのポイントをクラスターフィーチャにキャストすることができます。2つのクラスターフィーチャを組み合わせるには、 ${\displaystyle x}$${\displaystyle CF_{x}=(1,x,0)}$${\displaystyle CF_{AB}=CF_{A}+CF_{B}}$

• ${\displaystyle N_{AB}=N_{A}+N_{B}}$
• ${\displaystyle \mu _{AB}=\mu _{A}+{\frac {N_{B}}{N_{AB}}}(\mu _{B}-\mu _{A})}$（平均値の増分更新）
• ${\displaystyle S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})\circ (\mu _{B}-\mu _{AB})}$それぞれ要素ごとの積を用いたベクトル形式で
• ${\displaystyle S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})^{T}(\mu _{B}-\mu _{AB})}$スカラー二乗偏差の合計を更新する

これらの計算では、2 つの類似した 2 乗値の減算を回避する、数値的により信頼性の高い計算 (分散 のオンライン計算を参照) が使用されます。重心は、単にノード中心ベクトル であり、ユークリッド距離やマンハッタン距離などを使用した距離計算に直接使用できます。半径は に簡略化され、直径は に簡略化されます。 ${\displaystyle \mu }$${\displaystyle R={\sqrt {{\frac {1}{N}}S}}}$${\displaystyle D={\sqrt {{\frac {2}{N-1}}S}}}$

BIRCHアルゴリズムで使用されるさまざまな距離D0からD4を次のように計算できます。^[4]

• ユークリッド距離とマンハッタン距離はCF中心を用いて計算される。${\displaystyle D_{0}=\|\mu _{A}-\mu _{B}\|}$${\displaystyle D_{1}=\|\mu _{A}-\mu _{B}\|_{1}}$${\displaystyle \mu }$
• クラスター間距離${\displaystyle D_{2}={\sqrt {{\frac {1}{N_{A}}}S_{A}+{\frac {1}{N_{B}}}S_{B}+{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}}$
• クラスター内距離${\displaystyle D_{3}={\sqrt {{\frac {2}{N_{AB}(N_{AB}-1)}}\left(N_{AB}(S_{A}+S_{B})+N_{A}N_{B}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}\right)}}}$
• 分散増加距離${\displaystyle D_{4}={\sqrt {{\frac {N_{A}N_{B}}{N_{AB}}}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}}$

これらの距離は、選択したリンクに応じて、階層的クラスタリングの距離行列を初期化するためにも使用できます。正確な階層的クラスタリングと k-means クラスタリングを行うには、ノードの重みも使用する必要があります。 ${\displaystyle N}$

CFツリーはデータセットの圧縮された要約を提供しますが、葉自体は非常に貧弱なデータクラスタリングしか提供しません。2番目のステップでは、例えば、葉をクラスタリングすることができます。

1. k-means クラスタリングでは、葉はポイントの数 N によって重み付けされます。
2. k-means++は、以前に選択された中心に比例してクラスター機能をサンプリングし、BETULA クラスター機能となります。${\displaystyle S+N\min _{i}||\mu -c_{i}||}$${\displaystyle c_{i}}$${\displaystyle (N,\mu ,S)}$
3. ガウス混合モデリングでは、分散 S も考慮することができ、リーフが共分散を格納する場合は共分散も格納されます。
4. 階層的凝集型クラスタリングでは、リンクはBIRCH距離に対するリンクの等価性を使用して初期化できます。^[5]

• ELKIにはBIRCH と BETULA が含まれています。
• scikit-learnにはBIRCHの限定版が含まれており、D0距離と静的閾値のみをサポートし、クラスタリングステップでは葉の重心のみを使用します。^[6]