概念クラスタリング

概念クラスタリングは、1980 年にRyszard S. Michalskiによって定義され(Fisher 1987、Michalski 1980)、主に 1980 年代に開発された、教師なし分類のための機械学習パラダイムです。生成されたクラスごとに概念記述を生成する点で、通常のデータクラスタリングと区別されます。ほとんどの概念クラスタリング手法は、階層的なカテゴリ構造を生成できます。階層の詳細については、「分類」を参照してください。概念クラスタリングは、形式的な概念分析、決定木学習、混合モデル学習と密接に関連しています。

概念クラスタリングとデータクラスタリング

概念クラスタリングは明らかにデータクラスタリングと密接に関連しています。ただし、概念クラスタリングでは、クラスターの形成を駆動するのはデータの固有の構造だけでなく、学習者が使用できる記述言語も駆動します。したがって、一般的な概念記述言語がその特定の規則性を記述できない場合、学習者はデータ内の統計的に強力なグループ化を抽出できない可能性があります。ほとんどの実装では、記述言語は特徴結合に限定されていますが、COBWEB (以下の「COBWEB」を参照) では、特徴言語は確率的です。

公開されたアルゴリズムのリスト

概念クラスタリングには、かなりの数のアルゴリズムが提案されています。以下にいくつかの例を示します。

CLUSTER/2 (Michalski & Stepp 1983)
クモの巣(フィッシャー 1987)
サイラス（コロドナー 1983）
ガロワ (カルピネート & ロマーノ 1993)、
GCF (タラベラ＆ベジャール 2001)
INC (ハジカディック & ユン 1989)
反復（ビスワス、ワインバーグ、フィッシャー 1998）、
ラビリンス (トンプソン&ラングレー 1989)
SUBDUE（ジョニエ、クック＆ホルダー 2001）。
UNIMEM (レボウィッツ 1987)
WITT（ハンソン＆バウアー1989）、

概念クラスタリングに関するより一般的な議論とレビューは、次の出版物に記載されています。

ミハルスキ（1980）
ジェナーリ、ラングレー、フィッシャー（1989）
フィッシャー＆パッツァーニ（1991）
フィッシャー＆ラングレー（1986）
ステップ＆ミハルスキ（1986）

例: 基本的な概念的クラスタリングアルゴリズム

このセクションでは、概念クラスタリングアルゴリズム COBWEB の基本について説明します。さまざまなヒューリスティックと「カテゴリの良し悪し」またはカテゴリ評価基準を使用するアルゴリズムは他にも多数ありますが、COBWEB は最もよく知られているものの 1 つです。他の方法については参考文献を参照してください。

知識表現

COBWEB データ構造は階層 (ツリー) であり、各ノードは特定の概念を表します。各概念はオブジェクトのセット (実際にはマルチセットまたはバッグ) を表し、各オブジェクトはバイナリ値のプロパティリストとして表されます。各ツリーノード (つまり、概念) に関連付けられたデータは、その概念内のオブジェクトの整数プロパティ数です。たとえば (図を参照)、概念に次の 4 つのオブジェクト (オブジェクトの繰り返しが許可されます) が含まれているとします。 $C_{1}$

[1 0 1]
[0 1 1]
[0 1 0]
[0 1 1]

たとえば、3 つのプロパティはとなります[is_male, has_wings, is_nocturnal]。この場合、この概念ノードに格納されるのはプロパティカウントです[1 3 3]。これは、概念内のオブジェクトの 1 つが男性であり、オブジェクトの 3 つに羽があり、オブジェクトの 3 つが夜行性であることを示します。概念の説明は、ノードのプロパティのカテゴリ条件付き確率 (尤度) です。したがって、オブジェクトがカテゴリ (概念) のメンバーである場合、それが男性である尤度はです。同様に、オブジェクトに羽がある尤度とオブジェクトが夜行性である尤度 (またはその両方) はです。したがって、概念の説明はと簡単に表すことができ、これは-条件付き特徴尤度、つまりに対応します。 $C_{1}$ $1/4=0.25$ $3/4=0.75$ [.25 .75 .75] $C_{1}$ $p(x|C_{1})=(0.25,0.75,0.75)$

右の図は、5 つの概念を持つ概念ツリーを示しています。はルート概念で、データセット内のすべての 10 個のオブジェクトが含まれています。概念とはの子であり、前者は 4 つのオブジェクトを含み、後者は 6 つのオブジェクトを含みます。概念は、概念、、の親でもあり、それぞれ 3 つ、2 つ、1 つのオブジェクトを含みます。各親ノード (相対的に上位の概念) には、その子ノード (相対的に下位の概念) に含まれるすべてのオブジェクトが含まれていることに注意してください。 Fisher (1987) の COBWEB の説明では、ノードには属性の総数のみ (条件付き確率やオブジェクトリストではない) が格納されると示されています。確率は、必要に応じて属性の数から計算されます。 $C_{0}$ $C_{1}$ $C_{2}$ $C_{0}$ $C_{2}$ $C_{3}$ $C_{4}$ $C_{5}$

COBWEB言語

COBWEB の記述言語は、完全に確率的であるため、あらゆる概念を記述できるため、ゆるい意味でのみ「言語」です。ただし、概念が表す可能性のある確率範囲に制約が課されると、より強力な言語が得られます。たとえば、少なくとも 1 つの確率が 0.5 からを超えて異なる概念のみを許可するとします。この制約の下では、の場合、学習者はのような概念を構築できません。ただし、のような概念は、少なくとも 1 つの確率が 0.5 からを超えて異なるため、アクセス可能になります。したがって、このような制約の下では、従来の概念言語のようなものが得られます。すべての機能、つまり概念内のすべての確率が 0 または 1 でなければならないという制限的なケースでは、結果は結合に基づく機能言語になります。つまり、表現できるすべての概念は、機能 (およびその否定) の結合として記述でき、この方法で記述できない概念は表現できません。 $\alpha$ $\alpha =0.3$ [.6 .5 .7][.6 .5 .9] $\alpha$ $\alpha =0.5$

評価基準

Fisher (1987) の COBWEB の説明では、階層の品質を評価するために彼が使用した尺度は、Gluck と Corter (1985) のカテゴリユーティリティ(CU) 尺度であり、彼はこれを論文で再導出しています。この尺度の動機は、Quinlan が決定木学習のために導入した「情報ゲイン」尺度と非常に似ています。特徴ベースの分類の CU は、特徴変数とクラス変数間の相互情報量と同じであることが以前に示されており (Gluck & Corter、1985 年、Corter & Gluck、1992 年)、この尺度の方がはるかによく知られているため、ここではカテゴリの「良さ」の尺度として相互情報量を使用します。

私たちが評価したいのは、オブジェクトを特定の階層的分類構造にグループ化することの全体的な有用性です。一連の可能な分類構造が与えられた場合、そのうちの 1 つが他のものより優れているかどうかを判断する必要があります。

参考文献

Biswas, G.; Weinberg, JB; Fisher, Douglas H. (1998). 「Iterate: データマイニングのための概念的クラスタリングアルゴリズム」. IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews . 28 (2): 100–111. doi :10.1109/5326.669556.

Carpineto, C.; Romano, G. (2014) [1993]. 「ガロア: 概念クラスタリングへの順序理論的アプローチ」.第 10 回国際機械学習会議議事録、アマースト。pp. 33–40。ISBN 978-1-4832-9862-7。

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

フィッシャー、ダグラス H. (1996)。「階層的クラスタリングの反復最適化と簡素化」。人工知能研究ジャーナル。4 : 147–178。arXiv : cs /9604103。Bibcode : 1996cs ...... 4103F。doi :10.1613/jair.276。S2CID 9841360 。

フィッシャー、ダグラス H.、ラングレー、パトリック W. (1986)。「概念クラスタリングと数値分類法との関係」。ゲイル、WA (編)。人工知能と統計。マサチューセッツ州レディング: アディソン・ウェスレー。pp. 77–116。ISBN 978-0-201-11569-7. OCLC 12973461.

フィッシャー、ダグラス H.; パッツァーニ、マイケル J. (2014) [1991]。「概念学習の計算モデル」。フィッシャー、DH、パッツァーニ、MJ、ラングレー、P. (編)。概念形成: 教師なし学習における知識と経験。サンマテオ、カリフォルニア州: モーガンカウフマン。pp. 3–43。doi : 10.1016 /B978-1-4832-0773-5.50007-9。ISBN 978-1-4832-2116-8。

Gennari, John H.; Langley, Patrick W.; Fisher, Douglas H. (1989). 「増分概念形成モデル」.人工知能. 40 (1–3): 11–61. doi :10.1016/0004-3702(89)90046-5.

Hanson, SJ; Bauer, M. ( 1989). 「概念的クラスタリング、分類、および多形性」。機械学習。3 (4): 343–372. doi : 10.1007/BF00116838。

Jonyer, I.; Cook, DJ; Holder , LB ( 2001). 「グラフベースの階層的概念クラスタリング」。機械学習研究ジャーナル。2 : 19–43。doi :10.1162/153244302760185234。

Lebowitz, M. (1987). 「増分概念形成の実験」.機械学習. 2 (2): 103–138. doi : 10.1007/BF00114264 .

Michalski, RS (1980)。「概念クラスタリングによる知識獲得: データを結合概念に分割するための理論的枠組みとアルゴリズム」(PDF)。国際政策分析情報システムジャーナル。4 : 219–244。

Michalski, RS; Stepp, RE (1983)。「観察からの学習: 概念クラスタリング」(PDF)。Michalski, RS、Carbonell, JG、Mitchell, TM (編)。機械学習: 人工知能アプローチ。パロアルト、カリフォルニア州: Tioga。pp. 331–363。ISBN 978-0-935382-05-1. OCLC 455234543.

Stepp, RE; Michalski, RS (1986)。「概念クラスタリング: 構造化オブジェクトの目標指向分類の発明」( PDF)。Michalski, RS、Carbonell, JG、Mitchell, TM (編)。機械学習: 人工知能アプローチ。ロサンゼルス、カリフォルニア州: Morgan Kaufmann。pp. 471–498。ISBN 0-934613-00-1。

Talavera, L.; Béjar, J. (2001). 「確率的概念による一般性に基づく概念クラスタリング」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 23 (2): 196–206. doi :10.1109/34.908969.

外部リンク

概念クラスタリングの参考文献
COBWEB の Python 実装