- 追加された行はこの色です。
- 削除された行はこの色です。
- COBWEB へ行く。
* COBWEB [#i5c12e65]
//ここには %項目の説明を書いてください．よろしければ署名しておいてください．
概念クラスタリングとして最も著名な手法次のようなクラス分類木(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 を最大化するように選択され，クラス分類木を欲張りアルゴリズムで生成する．
>--しましま
**関連項目 [#yb05219f]
//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[category utility]]
#br
-[[概念クラスタリング]]
-[[クラスタリング]]
#br
-[[検索:COBWEB]]
**リンク集 [#e1c28076]
//関連するWWW資源があればリンクしてください．
-[[Wikipedia:COBWEB>Wikipedia:Cobweb_%28clustering%29]]
-[[Weka]]：クラスタリング手法の一つにCOBWEBが実装されている
**関連文献 [#c85622d2]
//この%項目%に関連する書籍や論文を紹介してください．
-基本文献~
D.H.Fisher "Knowledge Acquisition via Incremental Conceptual Clustering" Machine Learning, vol.2, pp.139-172 (1987)~
[[GoogleScholarAll:Knowledge Acquisition via Incremental Conceptual Clustering]]
-B.Mirkin "Reinterpreting the Category Utility Function" Machine Learning, vol.45, pp.219-228 (2001)：category utilityと，k-means法で用いられる最小2乗基準との関連~
[[GoogleScholarAll:Reinterpreting the Category Utility Function]]
-K.Wagstaff and C.Cardie "Clustering with Instance-level Constraints" Proc. of The 17th Int'l Conf. on Machine Learning, pp.1103-1110 (2000)：
COBWEBにmust-link/cannot-link制約を導入~
[[GoogleScholarAll:Clustering with Instance-level Constraints]]
-Book/人工知能学事典 5-4章
-[[Book/Data Mining - Concepts and Techniques]] 7.8.2章
-[[Book/Data Mining - Practical Machine Learning Tools and Techniques]] 6.6章 incremental clustering
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
