クモの巣（クラスタリング）

COBWEBは階層的概念クラスタリングのための増分システムです。COBWEBは現在ヴァンダービルト大学のダグラス・H・フィッシャー教授によって発明されました。^[1]^[2]

COBWEBは観察結果を段階的に分類ツリーに整理します。分類ツリーの各ノードはクラス（概念）を表し、そのノードの下に分類されるオブジェクトの属性値分布を要約した確率概念によってラベル付けされます。この分類ツリーは、欠落している属性や新しいオブジェクトのクラスを予測するために使用できます。^[3]

COBWEB が分類ツリーを構築するときに使用する基本的な操作は 4 つあります。どの操作が選択されるかは、その操作を適用することによって達成される分類のカテゴリユーティリティによって異なります。操作は次のとおりです。

2 つのノードのマージ
2 つのノードをマージするとは、元のノードの子セットの結合である子を持ち、それらの下に分類されるすべてのオブジェクトの属性値分布を要約するノードでそれらのノードを置き換えることを意味します。
ノードの分割
ノードは、その子に置き換えることによって分割されます。
新しいノードの挿入
ツリーに挿入されるオブジェクトに対応するノードが作成されます。
オブジェクトを階層の下方に渡すと、
オブジェクトとノードをルートとするサブツリーに対して COBWEB アルゴリズムが効果的に呼び出されます。

COBWEBアルゴリズム

  COBWEB (ルート、レコード):
  入力: COBWEB ノードroot 、レコード
  を挿入するインスタンス。root に子がない場合 、children  := { copy ( root )}
     newcategory ( record ) \\ レコードの特徴値を持つ子を追加します。
     insert ( record , root )
     \\ ルートの統計を更新します。
  それ以外の場合はinsert ( record , root ) で、 rootの子の子に対して、insert ( record , child )
      のカテゴリ ユーティリティを計算します。
    
       best1、best2 の子を best CU で
    
      設定します。end for 
    if  newcategory ( record ) で best CU が得られる then
       newcategory ( record )
     else  if  merge ( best1、best2 ) で best CU が得られる then
       merge ( best1、best2 )
       COBWEB ( root、record )
     else if  split ( best1 ) で best CU が得られる then
       split ( best1 )
       COBWEB ( root、record )
     else 
      COBWEB ( best1、record )
     end if 
  end

外部リンク

COBWEB の Python 実装

参考文献

^フィッシャー、ダグラス (1987) 。「増分概念クラスタリングによる知識獲得」。機械学習。2 (2): 139–172。doi : 10.1007/ BF00114265。
^ フィッシャー、ダグラス H. (1987 年 7 月)。「概念クラスタリングによる推論の改善」。1987年 AAAI カンファレンス議事録。AAAI カンファレンス。ワシントン州シアトル。pp. 461–465。
^ Wayne Iba および Pat Langley。「分類と確率的概念形成のクモの巣モデル」。Emmanuel M. Pothos および Andy J. Wills (編)。分類における形式的アプローチ。ケンブリッジ: ケンブリッジ大学出版局。253～273 ページ。ISBN 9780521190480。

[1] ^フィッシャー、ダグラス (1987) 。「増分概念クラスタリングによる知識獲得」。機械学習。2 (2): 139–172。doi : 10.1007/ BF00114265。

[2] フィッシャー、ダグラス H. (1987 年 7 月)。「概念クラスタリングによる推論の改善」。1987年 AAAI カンファレンス議事録。AAAI カンファレンス。ワシントン州シアトル。pp. 461–465。

[3] Wayne Iba および Pat Langley。「分類と確率的概念形成のクモの巣モデル」。Emmanuel M. Pothos および Andy J. Wills (編)。分類における形式的アプローチ。ケンブリッジ: ケンブリッジ大学出版局。253～273 ページ。ISBN 9780521190480。