COBWEB

概念クラスタリングとして最も著名な手法次のようなクラス分類木(classification tree)を生成するクラスタリングアルゴリズム

COBWEBが生成するクラス分類木は,葉ノードは各対象に相当,中間ノードはその下の部分木に分類された対象で構成されたクラスタに相当.

対象を記述するi番目の属性を \(A_i\),そのj番目の属性値を \(V_{ij}\) とする. 分類木のルートからの階層数をレベルとよび,あるレベルで n個のクラスタ \(C_1,\ldots,C_n\) に分割されているとする.このとき category utility は次式: \[\frac{1}{n}\sum_{k=1}^n \Pr(C_k)\Bigl\{\sum_i \sum_j \Pr(A_i{=}V_{ij}|C_k)^2-\sum_i \sum_j \Pr(A_i{=}V_{ij})^2\Bigr\}\] COBWEBはこの category utility を最大化する.

category utility は,クラスタ内で属性値が同じになるクラスタのまとまりと,属性値が与えられたときにそのクラスタ内での対象の属性値の予測しやすさ(似た属性値のクラスタが他にない)との和を最適化する. 概念クラスタリングでは,概念記述の良さも重視するが,COBWEBでは後者の予測のしやすさを記述の良さと考える.

クラスタの生成はオンライン学習で行われ,既存クラスタへの分類,新規クラスタの生成,クラスタの併合,またはクラスタの分割のいずれかの操作が,category utility を最大化するように選択され,クラス分類木を欲張りアルゴリズムで生成する.

--しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:10:53