📊 statistics

Hierarchical Aggregation Clustering Algorithms Derived from the Bi-partial Objective Function

この論文は、一般的な双部分目的関数から導出される階層的集約クラスタリングアルゴリズムの構築原理を明らかにし、従来のアルゴリズムとの関連性を示すことで、最適化と階層的集約の間の明確な接続を初めて確立し、クラスタリングの正当性や品質評価、停止基準の提供に貢献しています。

原著者： Jan W. Owsiński

公開日 2026-02-25

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Jan W. Owsiński

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

1. 従来の方法：「ただの近所付き合い」の限界

まず、従来のクラスタリング（階層的クラスタリング）がどうやって動いていたか考えてみましょう。

学校に新しい生徒が 100 人入ってきました。先生は彼らをグループ分けしたいと思っています。

従来のやり方： 「一番仲の良い 2 人」を見つけ、グループにします。次に、そのグループと「一番仲の良い他のグループ」をくっつけます。これを繰り返して、最後に 1 つの大きなグループになるまで続けます。
問題点： この方法は「誰と誰が近いか」というルールはありますが、**「いつグループ分けを終わりにすればいいか」**という答えを持っていません。
- 100 人全員が 1 つのクラス？
- 100 個の個別のクラス？
- それとも、ちょうどいい 5 つのクラス？

従来の方法では、この「最適なグループ数」を決めるために、先生が後から「うーん、たぶん 5 つくらいが良さそう」と**外部の基準（直感や別の指標）**で決める必要がありました。まるで、料理の味見をせずにお湯を沸かし続け、後から「あ、塩を入れ忘れた」と気づくようなものです。

2. この論文の提案：「二つの欲求のバランス」

著者のオウィンスキー氏は、この問題を解決するために**「バイ・パーシャル（二重部分）目的関数」**という新しい考え方を提案しています。

これを**「クラス編成のバランス」**と例えてみましょう。

グループ分けをするとき、私たちは無意識に 2 つの欲求を持っています。

「仲の良い仲間と固まりたい」（グループ内の結束力：Similarity）
「他のグループとは距離を置きたい」（グループ間の明確な境界：Distance）

従来の方法は、この 2 つを別々に考えていましたが、この論文では**「この 2 つを天秤にかけた一つの式」**を作りました。

式の意味： 「仲の良い仲間が増える喜び」と「他のグループとの距離が広がる喜び」を足し合わせ、その合計が最大になるようにグループ分けをする、という考え方です。

3. 魔法の「重み（パラメータ r）」

ここがこの論文の一番面白い部分です。著者は、この天秤に**「重み（r）」**というパラメータを加えました。

r = 0 のとき： 「距離」だけが重要。つまり、全員バラバラの 100 個のグループ（誰も仲良くしていない状態）が正解になります。
r = 1 のとき： 「結束」だけが重要。つまり、全員が 1 つの大きなグループ（全員が仲良し）が正解になります。

ここがミソです！
著者は、「r を 0 から 1 へ少しずつ増やしていく」という実験を提案しています。

r が少し増えると、「あ、この 2 人はくっつけた方が得だ！」という瞬間が来ます。
さらに r を増やすと、「あ、この 2 つのグループもくっつけた方が得だ！」という瞬間が来ます。

このように、**「いつ、どのグループ同士をくっつけるべきか」**という順序が、この「重み（r）」の変化によって自動的に決まります。まるで、氷が溶けていくように、自然な流れでグループが形成されていくのです。

4. 従来のアルゴリズムとの関係

実は、この「重み（r）」を変えていく方法は、昔からある有名なグループ分けのルール（最短距離法や平均距離法など）と全く同じ動きをすることが証明されました。

従来の方法： 「一番近い 2 人を選んでくっつける」というルールをただ漫然と実行していた。
この論文： 「実はそのルールは、この『二重の欲求のバランス』を最適化しようとした結果、自然に生まれたものだったんだ！」と説明しました。

つまり、**「なぜそのルールが使えるのか？」という理由（正当性）**が初めて数学的に示されたのです。

5. 「いつ止めるべきか？」という答え

最大のメリットは、**「どこで止めるべきか」**が自動的にわかることです。

天秤の重み（r）を 0.5（50%）に設定したとき、つまり「結束」と「距離」が同じくらい重要だと考えたときに、最もバランスの良いグループ分けが得られます。
グループ分けの過程で、r が 0.5 を超えた瞬間、あるいはその手前で「もうこれ以上くっつけると、グループの質が落ちる」という判断が数学的に可能になります。

これにより、先生（分析者）は「たぶん 5 つくらいかな？」と推測する必要がなくなり、**「数学的に最もバランスが良いのは、この 4 つのグループです」**と自信を持って答えられるようになります。

6. まとめ：なぜこれがすごいのか？

この論文は、以下のようなことを成し遂げました。

理由の解明： 昔から使われているグループ分けのルールが、実は「仲良くしたい」と「距離を置きたい」という 2 つの欲求のバランスを最適化するためのものだったことを証明しました。
判断基準の提供： 「いつグループ分けを終わらせるか」という、長年の悩みを、この「バランスの式」を使って解決しました。
柔軟性： この考え方は、単純な距離の計算だけでなく、もっと複雑なデータ（例えば、生徒の趣味や性格まで考慮したグループ分け）にも応用できます。

一言で言うと：
「ただ闇雲にグループを作っていた従来の方法に、『なぜそうするのか？』という理由と、『どこで止めるべきか？』というゴールラインを、数学というコンパスで与えた論文」です。

これにより、データ分析の結果が、より理にかなった、納得感のあるものになることが期待されています。

論文要約：双部分的目的関数に由来する階層的集積クラスタリングアルゴリズム

著者: Jan W. Owsiński (ポーランド科学アカデミーシステム研究研究所)
タイトル: Hierarchical Aggregation Clustering Algorithms Derived from the Bi-partial Objective Function

1. 問題の背景と課題

クラスタリング（分類）は、データ分析の核心的な課題の一つであり、類似するオブジェクトを同じグループ（クラスター）に、非類似するオブジェクトを異なるグループに割り当てることを目的とする。しかし、この直感的な定義を具体的な数式化や最適化問題として定式化する際、以下の課題が存在する。

距離・近接性の定義: 個々のオブジェクト間およびクラスター間の距離測度の選択。
目的関数の欠如: 多くの階層的集積アルゴリズム（アグリゲーション法）は、直感的な「最小距離による結合」のルールに基づいており、明確な最適化対象となる「目的関数」が定義されていない。
停止条件の曖昧さ: 階層的アルゴリズムは通常、デンドログラム（樹形図）を生成するが、どこで結合を停止し、最終的なクラスター数を決定するかは、アルゴリズム自体ではなく「外部基準」に依存している。
最適性の欠如: 既存のアルゴリズムは、大域的な最適解を保証するものではなく、局所的な貪欲法（Greedy method）の集合と見なされることが多い。

2. 提案手法：双部分的目的関数（Bi-partial Objective Function）

著者は、クラスタリング問題の本質を適切に反映する「双部分的目的関数」を提案し、これに基づいて階層的集積アルゴリズムを導出する枠組みを提示する。

2.1 双部分的目的関数の定式化

目的関数 $Q(P, r)$ は、以下の 2 つの成分の重み付き和として定義される。
$Q(P, r) = r \cdot Q_S(P) + (1-r) \cdot Q_D(P)$

$P$ : 分割（パーティション）。
$Q_S(P)$ : クラスター内部の類似性（近接性）の総和を最大化する成分。
$Q_D(P)$ : クラスター間の距離（非類似性）の総和を最大化する成分（または、最小化の文脈では距離の和）。
$r \in [0, 1]$ : 両成分の重みパラメータ。

この関数は、 $r=0$ のとき（距離のみ重視）は各オブジェクトが独立したクラスター（ $n$ 個）となり、 $r=1$ のとき（類似性のみ重視）は全オブジェクトが 1 つのクラスターとなるような挙動を示す。

2.2 アルゴリズムの導出プロセス

パラメータ掃引: 重みパラメータ $r$ を 0 から 1 へ変化させる。
結合閾値の決定: 現在の分割 $P_{t-1}$ $P_{t - 1}$ から、2 つのクラスターを結合して得られる新しい分割 $P_t$ $P_{t}$ が、目的関数の値を改善（最大化または最小化）し始める $r$ $r$ の臨界値 $r_t$ $r_{t}$ を計算する。
- 具体的には、結合による内部類似性の増加量 $\Delta Q_S$ と、クラスター間距離の減少量 $\Delta Q_D$ の比率から、結合が発生する $r$ の値を導出する。
- 例： $r_t = \frac{\Delta Q_D}{\Delta Q_D + \Delta Q_S}$
貪欲な結合: 最も小さい $r$ （または最大の利益）を持つクラスター対を選択し、結合する。
停止条件: 目的関数の最適化目標（通常は $r=0.5$ 付近、または両成分のバランスが取れる点）に達した時点で結合を停止する。これにより、外部基準なしで最適なクラスター数を決定できる。

3. 主要な貢献と結果

3.1 階層的アルゴリズムと最適化の統合

従来の階層的クラスタリング（単一リンク、完全リンク、Ward 法など）は、Lance-Williams の更新式に基づいて距離行列を更新する手順として知られていたが、それがどのような目的関数の最適化に対応するかが不明確だった。
本論文は、特定の双部分的目的関数の形式を選択することで、これらの古典的なアルゴリズム（およびその変種）が、その目的関数の「部分最適化（sub-optimization）」手順として自然に導出されることを示した。

具体例: 平均リンク法（UPGMA）は、特定の距離と類似性の定義の下で、双部分的目的関数の最適化から導かれることを示した。

3.2 クラスタリングの質の評価と停止基準

アルゴリズム自体が目的関数に基づいているため、生成された各段階の分割（パーティション）に対して、その目的関数値を直接評価できる。

停止基準: $r$ の値が 0.5 を超える、あるいは目的関数の値が極小（または極大）に達した時点で結合を停止することで、データセットに固有の「最適な」クラスター数を決定できる。これにより、外部指標（シルエット係数など）への依存を排除し、アルゴリズムの内部論理一貫性を保つ。

3.3 k-means アルゴリズムへの適用

従来の k-means は、クラスター数 $k$ を事前に指定する必要があり、最適な $k$ を決めるために外部基準（AIC, BIC など）が必要だった。

本論文では、k-means の距離成分（ $Q_D$ ）に、クラスター間の類似性成分（ $Q_S$ ）を加えた双部分的目的関数を提案。
これにより、 $k$ を変数として扱い、目的関数の値を最小化する $k$ を自動的に特定できる枠組みを示した。数値実験（60 個のオブジェクト）では、データ構造に合致するクラスター数（例： $k=4$ ）で目的関数が明確な極小値を示すことが確認された。

3.4 具体的なアルゴリズム例

以下のケースにおいて、双部分的アプローチに基づく結合ルールを導出・提示した。

加法的目的関数（施設配置問題）: クラスター設置コストと距離コストのバランス。
最小距離・最大類似性: 古典的なリンク法に近い挙動。
平均距離・加法的類似性: 平均リンク法との対応。
k-means 型: クラスター中心からの距離と、クラスター間の最大類似性を組み合わせた新しい結合ルール。

4. 意義と結論

理論的正当化: 階層的集積アルゴリズムが、単なるヒューリスティックな手順ではなく、明確な最適化問題（双部分的目的関数）の近似解法として正当化された。
汎用性: 目的関数の形式（距離や類似性の定義）を変えることで、多様なクラスタリング戦略やアルゴリズムを統一的な枠組みで設計・導出できる。
実用的価値: 停止条件の明確化と、アルゴリズム固有の品質評価指標の提供により、クラスタリング結果の解釈性と信頼性が向上する。
計算コストへの対応: 階層的アルゴリズムは計算コストが高いが、本アプローチは初期段階で高速な手法（例：k-means）で粗いクラスターを形成し、後段で双部分的ルールに基づいて結合を行うハイブリッド手法との親和性が高いことを指摘している。

結論として、本論文はクラスタリングの「最適化」と「階層的結合」の間の長年のギャップを埋める理論的架け橋を提供し、より解釈可能で、データ駆動型の停止基準を持つクラスタリング手法の設計を可能にする。