技術資料トップへ戻るクラスタ分析は、似ているデータ同士は同じ振る舞いをするという前提のもとに、似ているデータは同じクラスタに、似ていないデータは別なクラスタにとデータをグループ化する分析である。クラスタは、そのクラス内のほかのデータとは似ているが、違うクラスタ内のデータとは似ていないようなデータの集合である。この分析では、通常、データを多次元空間内の点とみなし、距離を定義し、距離の近いものを似ているとする。距離の計算では、カテゴリデータに対しては数量化を行い距離を計算する。
クラスタ分析では分類分析と違い既存のクラスに対応する教師値が存在しない。このような学習は教師なし学習と呼ばれ、データの傾向を明らかにするのに使われる。
例えば、顧客データから、共通の行動パターンを持つ顧客を探す場合、既に顧客の行動パターンが解っている場合には、分類分析によりその顧客の行動パターンを分類するが、顧客の行動パターンが解っていない場合にはクラスタ分析を行い、顧客に存在する共通した行動パターンを探す。そして、クラスタ分析によりグループ化された顧客群を解釈する事で顧客の行動パターンに関する知識を得る。また、他のデータと似ていないデータを求めることで外れ値検出に用いることも出来る。
以下にVisual Mining Studioで提供している手法としてK-Means法、BIRCH、OPTICS、自己組織化マップ、Support Vector Machineを用いて外れ値検出を行うOne Class SVM、One Class SVM判定、階層型クラスタリングと、データ間のリンク構造からその構造を明らかにするネットワーク階層化、Clusterの良し悪しを評価するCluster Validationについて紹介する。
K-Means法はPartitioning Methodと呼ばれるクラスタリングの一種で、データを与えられたk個のクラスタに分割する。K-Means法は、クラスタの中心値をそのクラスタを代表する値とする。クラスタの中心値との距離を計算することで、データがどのクラスタに属するかを判断する。この際、最も近いクラスタにデータを配分する。全てのデータに対してクラスタにデータを配分し終わったあと、クラスタの中心値を更新する。クラスタの中心値は全ての点の平均値である。上記の操作を、全てのデータとデータが属するクラスタの中心値との距離の合計が最小になるまで(更新されなくなるまで)繰り返す。
クラスタの中心値とデータとの距離計算方法はManhattan、Euclid、Cosineの中から選択する。また、規格化オプションでは、入力データを0-1の範囲に規格化してからクラスタリングを行う。
図パラメータ設定画面
|
項目 |
内容 |
|
対象列名 |
クラスタリング分析に用いる列名 |
|
距離計遺産方法 |
多次元空間内の距離の計算方法。以下の中から選択 Mahattan Euclid Cosine |
|
クラスターの数 |
分割するクラスタ数 |
|
繰り返し最大数 |
計算の繰り返し最大数 |
|
規格化オプション |
入力データを規格化するかどうか |
|
乱数の初期値 |
乱数の初期値を設定 自動 初期値を自動設定 手動 初期値を手動設定 |
K-Means法の出力は入力データにクラスタIDが付加された表と、クラスタ情報の２つである。種類、がく長、がく幅、花びら長、花びら幅は入力データ、ClustetIDはクラスタ番号を表す。
図K-Means法出力結果
図 クラスタ情報
MathSoft, S-PLUS 2000 Guide to Statistics.
Jiawei Han and Micheline Kamber, Data Mining Concept and Techniques Academic Press, 2001.
P.S.Bradley and Usama M. Fayyad, Refining Initial Points for KeMeans Clustering, Prc. 15th International Conf. on Machine Learning, 1998.
BIRCHと呼ばれるデータ圧縮法を用いてデータを圧縮し、圧縮されたデータに対してK-Means法を用いてクラスタリングを行う。
データの圧縮は、与えられたデータからClustering Feature(CF) Tree を構築する事で行う。CF TreeのNodeはCF Vectorと子ノードへのポインタからなるTreeで、CF Vectorは
(N,LS,SS)
の三要素からなるVectorである。それぞれの意味は
Nノードに入っているデータの数
LSノードに入っているデータのVectorの和
SSノードに入っているデータのVectorの二乗和
となる。これらの定義から、CF Vectorの和はCF Vectorになる。N,LS,SSを用いる事により、以下のようにクラスターのCenter、Radius、Diameterやノード間の距離を計算出来る。
CF Treeの構築では、閾値で同一のNodeにむかどうかをチェックする。その為、閾値が小さい過ぎると、Nodeに含まれるデータ数が少なく、圧縮率が低くなり効率が悪くなる。又、閾値が大き過ぎると、Nodeに含まれるデータが多くなり過ぎ、データの詳細な情報が失われる。その為、データの分布状況に見合った閾値を指定する事が肝要である。CF Treeが作成された後、CF TreeのLeaf Nodeに対して、K-Means法を用いてクラスタリングを行う。
図 パラメータ設定画面
|
項目 |
内容 |
|
対象列名 |
分析に使用する列名 |
|
距離計算方法 |
距離の計算方法。以下の中から選択 Euclid Manhattan Cosine Inter Cluster Intra Cluster Variance Increase |
|
閾値 |
CF Tree作成の為の閾値 |
|
クラスターの数 |
分割するクラスタ数 |
|
繰り返し最大数 |
計算の繰り返し最大数 |
|
規格化オプション |
入力データを規格化するかどうか |
BIRCHの出力は入力データにクラスタIDが付加された表とクラスタ情報の２つである。種類、がく長、がく幅、花びら長、花びら幅は入力データ、ClustetIDはクラスタ番号を表す。
図 BIRCH 出力結果
図 クラスタ情報
Tian Zhang, Raghu Ramakrishnan and Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Data Bases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 103--114, Montreal, Canada, 1996.
Tian Zhang, Raghu Ramakrishnan and Miron Livny. Interactive Classification of Very Large Datasets with BIRCH. Proc. of Workshop on Research Issues on Data Mining and Knowledge Discovery (in cooperation with ACM-SIGMOD'96), June 196, Montreal, Canada.
OPTICSは、データを多次元空間内の点と見なした時に密度の濃い領域をクラスタと見なすDensity Basedなクラスタリング法である。このクラスタリング法では、K-Means法のようなPartitioning Methodと違い、分割するクラスタの個数を指定せず、その代わり、密度を測定する近傍の範囲(近傍値)、core-objectであると識別する最小のデータ数(最小データ数)を指定する。core-objectとは、自分自身の近傍値内に、最小データ数以上のデータが含まれるようなデータ点の事である。クラスタの構築は、core-object同士を繋げていく(閾値内に入っているcore-object同士を同一のクラスタに属すると見なす)事で行う。どのcore-objectとも繋がらないデータはnoiseであると見なされる。
この方法では、全てのデータに対して近傍の探索を行う。その為、効率の良い近傍探索法が必要になる。ここでは、事前にM-Treeと呼ばれる探索木を構築し、それに対してRange Queryを行うことで近傍の探索を行う。出力は、Ordered FileとCluster Fileの二種類のファイルが有る。Ordered Fileでは、データID,reachability,core distance,ClusterIDをreachabilityの小さい順に並べたものを出力する。Cluster Fileは入力データにクラス識別子を付加したファイルを出力する。reachabilityからクラスタへの分割は閾値を用いて行う。Ordered Fileにおいて、閾値以上のreachabilityで分けられたデータは別のクラスタに属すると判定する。core distanceは、データがcore objectである時、core objectである為の最小の距離で、core objectでなければ定義されない。reachabilityは、データから見た一番近いcore objectへの距離とcore distanceとの大きい方で、core objectでなければ定義されない。この方法では、Partitioning Methodのクラスタリングに比べて複雑な形状のクラスタの識別が行えるが、全てのデータ点に対して近傍の探索を行うので、計算時間がかかる。
図 パラメータ設定画面
|
項目 |
内容 |
|
距離関数 |
距離の計算方法。以下の中から選択 Euclid Manhattan Cosine |
|
近傍値 |
密度を測定する近傍の値 |
|
最小データ数 |
core-objectであると識別する最小のデータ数 |
|
閾値 |
reachabilityの閾値 |
|
対象列選択 |
分析の対象列を選択 |
|
規格化オプション |
入力データを規格化するかどうか |
OPTICSの出力は以下の通り。
Ordered File
idは入力データのid、reachabilityはcore objectへの距離、core distanceはそのデータのcore distance、ClusterIDはクラスタ番号を表す。
Cluster File
種類、がく長、がく幅、花びら長、花びら幅は入力データ、ClusterIDはクラスタ番号を表す。
◇ Ordered File
図 Ordered File出力結果
◇Cluster File
図 Cluster File出力結果
◇Ordered FileとCluster Fileの関係
図 （上）Ordered File reachability （下）グラフ2次元プロット
Mihael Ankerst, Markus M. Breuning, Hans-Peter Kriegel and Jorg Sander. OPTICS:Ordering Points To Identify the Clustering Structure. Proc. ACM SIGMOD Int. Conf. on Management of Data, Philadelphia, PA, 1999.
Paolo Ciaccia, Marco Patella and Pavel Zezula. M-Tree: An Efficient Access Method for Similarity Search in Metric Space. Proc. of the 23rd VLDB Conf. Athens, Greece, 1997.
Nick Roussopoulos, Stephen Kelley and Federic Vincent. Nearest Neighbor Queries. Proc. of ACM-SIGMOD, pages 71-79, May 1995.
出力層が２次元の配置をしている階層型のNeural Networkを用いて競合学習を行い、ベクトル量子化を行う。2次元のマップ状の出力層のUnitをPrototype Vectorと呼ぶ。マップの配置の仕方はRectangularかHexagonalを選択できる。競合学習では、入力データと最も近いPrototype vector（Winner）を探索し、そのVectorと近傍のVectorとを変化させる。距離計算はManhattan、Euclid、Cosineを選択できる。その際、カテゴリデータは数量化して距離を計算する。変化させる近傍系にはBubbleとGaussianが選択できる。Bubbleでは、指定した近傍範囲内にいる全てのVectorを同じ重みで変化させる。Gaussianでは、Winnerを中心としたGauss分布を仮定し、その値を重みとして近傍のVectorを変化させる。Gauss分布の分散は近傍系のパラメータで指定する。学習は繰り返し処理で行われるので、その最大数を指定する。学習はBatch学習法を用いている。また、マップの初期値はRandomかLinearを選択できる。Randomではランダムに初期化を行い、Linearでは主成分分析を行い、第1主成分、第2主成分を用いて初期化を行う。
図 パラメータ設定画面
|
項目 |
内容 |
|
マップサイズ |
マップのサイズを指定 |
|
Latticeタイプ |
RectangularかHexagonalを選択 |
|
Map初期化方法 |
RandumかLinearを選択。Linearでは主成分を用いた初期化を行う |
|
距離関数 |
Codebook Vectorとの距離の計算方法を選択 Manhattan Euclid Cosine |
|
近傍系 |
競合学習を行うときの近傍の形を選択 |
|
繰り返し最大数 |
繰り返しの最大数を指定 |
|
近傍関数のパラメータ |
近傍系でGaussianを選択した場合、分散の値を指定 |
|
規格化を行う |
入浴データを規格化するかどうかを指定 |
|
対象列 |
分析対象列を選択 |
自己組織化マップの出力は以下のとおり。
◇結果ファイル
入力データがマップ上のどのPrototype Vectorに対応するかを表すファイル
PositionX、PositionYがマップ上の位置を表す。
図 自己組織化マップ出力
◇マップファイル
Prototype Vectorのデータ
図 Mapファイル
Mapデータはマップ上のそれぞれのPrototype Vectorの値を出力する。Prototype Vectorの値として、近傍のVectorとの距離情報、それそれの軸の値が存在する。
自己組織化マップの図は下図のようになる。表示軸では、Mapデータのどの要素を用いて図を表示するかを選択する。花びら長の値で2次元マップを描くと図のようになる。この図では花びら長の値の大きいVectorの色が赤くなっており、小さいVectorの色は青くなっている。
表示ラベルでは、Map上のVectorを代表する値をどの軸で表示するかを選択する。
図 自己組織化マップ
T.Kohonen, Self-Organizing Maps(Third Edition),Springer, 2001.
Support Vector Machine(SVM)を用いて外れ値検出を行う。このSVMは通常のSVMと違い教師値が無い。データを多次元空間内の点とみなしたときに、データ集合の領域を求め、その領域に入っていないデータを外れ値と見做す。Gaussianカーネルを用いると入力空間で他の点から孤立している点は原点付近に写像される性質を用い、原点とデータ集合を分ける超平面を求める。この分析では、原点と超平面との距離が最小になるデータ点との距離(マージンと呼ぶ)を最小化するようにパラメータを最適化する。超平面(線形モデル)による分析が適切ではない場合、非線型写像により別な空間(Feature Space)へ写像し、その空間内での超平面による分析を行う。これは元の空間での超曲面(非線型モデル)による分析になっている。Support Vector Machineによる分析には空間内の内積のみ現れるので、写像した空間内での内積のみ定義されていればよい。その内積を表す関数をカーネル関数とよぶ。カーネル関数とそのパラメータは問題に応じてユーザが指定する。カーネル関数の定義を以下に示す。
超平面や超曲面による分析が可能ではない場合(データ集合のマージンが正にならない場合)、Slack変数を導入し制約条件をゆるめて解く。このとき、通常のSVMと異なり新たにνというパラメータを導入して解く。最適化問題は以下のように定式化する。
このνはKKT条件
からsupport vectorの数をコントロールするパラメータになっている。
図 パラメータ設定画面
|
項目 |
内容 |
|
対象列選択 |
分析対象列を選択する |
|
カーネル関数 |
カーネル関数を以下の中から選択する Linear Gaussian Polynomial Sigmoid |
|
カーネル関数のパラメータ |
カーネル関数のパラメータを指定する Linear なし Gaussian σ２ Polynomial d Sigmoid θ |
|
ν値 |
νの値を指定する |
One Class SVMの出力は以下の通り
種類、がく長、がく幅、花びら長、花びら幅は入力データで、外れ値が外れ値であるかどうかをあらわす。Trueであればデータ集合に含まれる点で、Falseであれば外れ値である。
SVM出力はOne Class SVMの出力を表す。
図 One Class
SVM 出力
B.Schlkoph, J.C.Platt, J.Shaew-Taylor, A.J.Smola and R.C.Williamson, Estimating the Support of High-Dimensional Distribution, Neural Computation, 13, 2001.
B.Schlkoph, A.J.Smola, R.C.Williamson and P.L.Platt, New Support Vector Algorithm, Neural Computation, 1999.
B.Schlkoph and A.J.Smola, Learning With Kernel, MIT Press, 2002.
One Class SVMで作成したモデルを用いて外れ値検出を行う。
One Class SVMの出力は以下の通り
種類、がく長、がく幅、花びら長、花びら幅は入力データで、外れ値が外れ値であるかどうかをあらわす。Trueであればデータ集合に含まれる点で、Falseであれば外れ値である。
SVM出力はOne Class SVMの出力を表す。
図 出力結果
B.Schlkoph, J.C.Platt, J.Shaew-Taylor, A.J.Smola and R.C.Williamson, Estimating the Support of High-Dimensional Distribution, Neural Computation, 13, 2001.
B.Schlkoph, A.J.Smola, R.C.Williamson and P.L.Platt, New Support Vector Algorithm, Neural Computation, 1999.
B.Schlkoph and A.J.Smola, Learning With Kernel, MIT Press, 2002.
擬集型の階層型クラスタリングを行う。このアルゴリズムでは、最初の状態ではデータはずべて独立したクラスタであると見做し、距離の近いものからクラスタをマージして行き、全てのデータが一つのクラスタにマージされるまで繰り返す。
個々のデータ間の距離はManhattan、Euclud、Cosineの中から選択することが可能である。クラスタ間の距離は以下の基準から選択する。
◇最近隣法
最も近いデータが近いクラスタをマージする。
◇最遠隣法
最も遠いデータが近いクラスタをマージする。
◇中心法
中心値が近いクラスタをマージする。マージするクラスタをa,bとし、マージ後のクラスタをcとし、それ以外のクラスタをxとしたとき、cとxとの距離は、以下のようになる。
◇平均法
平均値が近いクラスタをマージする。マージするクラスタをa,bとし、マージ後のクラスタをcとし、それ以外のクラスタをxとしたとき、cとxとの距離は、以下のようになる。
◇メジアン法
中央値が近いクラスタをマージする。マージするクラスタをa,bとし、マージ後のクラスタをcとし、それ以外のクラスタをxとしたとき、cとxとの距離は、以下のようになる。
◇Ward法
偏差の平方和を最小化するようにマージする。マージするクラスタをa,bとし、マージ後のクラスタをcとし、それ以外のクラスタをxとしたとき、cとxとの距離は、以下のようになる。
◇最小探索木
結合の強いNodeを連結していきTree構造を構築する
◇Modularity
Networkの分割の良さを表す指標であるmodularity（Q）を用いてクラスタリングする。Modularityの定義は
ここでeijはクラスタiとjの間に張られているリンクのfractionで、eiiはクラスタi内に張られているリンクのfractionである。また、ai、bjはそれぞれ
となっている。また、eijは以下の等式を満たす。
図 パラメータ設定画面
|
項目 |
|
|
対象列名 |
|
|
距離計算方法 |
Manhattan Euclid Cosine |
|
分析方法 |
最近隣法 最遠隣法 中心法 平均法 メジアン法 Ward法 最小全域木 Modularity |
|
クラスタ数 |
|
|
閾値 |
出力データはTreeデータとPartitionデータ、非類似度データである。それぞれ以下のようになる。Treeデータはノード間のリンク情報をあらわし、Partitionデータはクラスタ情報をあらわす。非類似度データはデータ間の距離を表す。
図 Treeデータ 図 Partitionデータ
図 非類似度データ
出力画面は下図のようになる。
図 デンドログラム
MathSoft, S-PLUS 2000 Guide to Statistics.
Jiawei Han and Micheline Kamber, Data Mining Concept and Techniques Academic Press, 2001.
要素間の関連性が類似度という形で与えられたデータから、その要素をNodeとし、その類似度をLinkの強さとするNetworkとみなし、そのNetworkをクラスタリングすることでネットワークの構造を探索する。クラスタリングは階層型クラスタリングを行う。階層型クラスタリングでは、似ているNodeをマージしていく。Nodeの類似度/非類似度は選択可能で、類似度の場合は類似度行列の値が大きいほど似ているとし、非類似度の場合は小さいほど似ているとなる。Node間の距離の定義は最近隣法、最遠隣法、中心法、平均法、メジアン法、Ward法、最小探索木、Modularityの中から選択する。Node間の距離の定義の詳細は階層型クラスタリングの項を参照。
図 パラメータ設定画面
|
最近隣法 最遠隣法 中心法 平均法 メジアン法 Ward法 最小全域木 Modularity |
|
|
類似度/非類似度 |
Node間のリンクの大きさが類似度か非類似度かを選択する。 |
出力データはTreeデータとPartitionデータである。それぞれ以下のようになる。Treeデータはノード間のリンク情報をあらわし、Partitionデータはクラスタ情報をあらわす。
図 Treeデータ
図 Patritionデータ
出力画面は下図のようになる。
この画面上では入力されたNetworkのリンクの様子と階層型クラスタリングの結果を木構造で表した様子を表示している。また、階層型クラスタリングの結果を用い、クラスタ数を変えたときの様子をノードの色の違いで表現している。分割するクラスタ数は動的に変更することが可能である。
図 クラスタ数変更スライダー
Community structure in social and
biological networks, Michelle Girvan and M. E. Newman, Proc. Natl. Acad. Sci.
USA (2002).
Fast algorithm for detecting community structure in network, M. E. Newman,
Preprint cond-mat/0309508 (2003).
S-PLUSによる統計解析 W.N.Venables
and B.D.Riplay著 伊藤幹夫・大津泰介・戸瀬信之・中東雅樹 訳 Splinger東京
クラスタの結果を評価する。クラスタリングとは、データに潜む構造を取り出すことであるが、これはデータの特徴を少数のテンプレートを用いて表現するとも言える。この様な立場からクラスタを評価すると、クラスタの評価は、いかに情報損失を少なく元のデータを再現できているかということになる。その為、分散などの指標を用いて評価することになるが、分散だけでは単純すぎクラスタ数が異なる場合の比較が上手く出来ない。クラスタリングの結果を評価する指標には大きくInternalと呼ばれるものとExternalと呼ばれるものがある。Internalとは、クラスタリングの結果(クラスタID)のみを用いてクラスタリングを評価することで、Externalとは、クラスタリングの結果以外のクラス情報を用いてクラスタリングの結果を評価する方法である。Internalな指標にも幾つかのカテゴリが存在するが大きく分けると以下の３つになる。
l Compactness
クラスタリングの結果、コンパクトなクラスが出来たかどうかで評価する。評価指標にはintra-clusterを用いる。
l Connectedness
近くのデータが同一のクラスタに属するかというconectednessの概念を用いて評価する。この指標は言ってみれば密度ベースのクラスタリングの評価のようなものである。
l Separation
個々のクラス同士が上手く分かれているかどうかで評価する指標である。これはinter-clusterを用いて評価することになる。
クラスタを評価する際に使用する対象列、Validation Index、距離計算方法はユーザが指定する。Validation Indexの定義を以下に示す。
Validation Indexは大きく、分散を用いる方法と、Scatter Matrixを用いる方法、それ以外の方法に分けられる。
【分散を用いる方法】
SSWは、所謂、郡内平方和で、以下の式で定義される。
ここで、μiはクラスタの中心値で、xijがそれぞれのクラスタに含まれるデータを表す。
SSBは群間平方和で、以下の式で定義される。
ここで、niはクラスタサイズ、μが全体の平均値である。
SSTは総平方和で、以下の式で定義される。
ここでμは全データの中心値である。これらを用いた指標として以下のものがある。
l Calinski and Harabasz Validation
この指標は、SSW、SSBを用いて以下のように定義される。
ここでnはレコード数、kはクラスタ数である。群間分散が大きく、郡内分散が小さいほうが良いので、この指標は大きな方がよい。
l Hartigan Validation
この指標はSSW、SSBを用いて以下のように定義される。
郡内分散が小さく、群間分散が大きい方がよいので、この指標は大きな方がよい。
l Ratkowsky and Lance Validation
この指標はSSW、SSBを用いて以下のように定義される。
ここで、varSSBは全ての変数のSSBで、SSTは全ての変数の全平方和である。この指標は大きな方がよい。
l Ball and Hall
SSWを用いて以下のように定義される。
ここでkはクラスタ数である。郡内分散が小さい方が良いのでこの指標は小さい方が良い。
【Scattering Matrixを用いる方法】
Scatter Matrix Tとは、全体の分散共分散行列のことである。Scatter Matrix Wとは、クラスタ毎に分散共分散行列を求め、それらを足し合わせたものである。これらを用いた指標として以下のものがある。
l Scott and Symons Validation
Scattering Matrixを用いて以下のように定義される。
ここでｎはデータ数、｜・｜は行列のdeterminantである。
l Marriot Validation
Scattering Matrixを用いて以下のように定義される。
ここでkはクラスタ数である。
【その他の方法】
これらの手法では、Inter ClusterとIntra Clusterの距離を用いて指標を構築している。これ以外にもこれらの指標を組み合わせで別な指標を計算することも可能である。最初に紹介したグループの群間分散や郡内分散も、これらの指標の特殊なケースとして取り扱うことも可能である。
l Dunn’s Validity Index
クラスタがコンパクトにまとまり、他のクラスタとよく分かれているかという指標で、下記のように定義される。
d(ci,cj)はクラスタciとcjとの距離（inter cluster distance）である。d(ck)はintra cluster distanceである。この式では、クラスタ間の距離を最大化し、クラスタ内の距離の最大値を最小化するようなものを採用する。よって、この指標が最も大きくなるKの値を採用する。
l Davies-Bouldin Validity Index
Cluster ScatterとCluster Separationの比を見る指標になっており、以下のように定式化される。
ここで、Sn(Qi)はクラスタの中心値と、そのクラスタに含まれるデータの距離の平均値、SSWiとも表現出来る。S(Qi,Qj)はクラスタ間の距離をクラスタの中心値で測ったものである。よって、もしクラスタがコンパクトにまとまり、クラスタ間が綺麗に分かれるときは、この指標は小さくなる。
l C index
クラスタのSimilarityを見る指標で以下のように定義される。
ここでdwはクラスタ内に含まれる全てのデータ間の距離の和である。min(dw)は全てのデータ間の距離の小さい方から上記の計算のペア分の和、max(dw)は全てのデータ間の距離の大きい方から上記の計算のペア分の和である。min(dw)の距離の小さなペアが全て同一のクラスタであれば分子は0になるので、綺麗にクラスタされていればこの値は小さくなる。
l Likelihood Validation
クラスタリングの結果を混合モデルと考えると、クラスタの中心値はそれぞれの変数が1になる確率を表す。それゆえ、対数尤度のマイナスを計算することが出来、クラスタの結果を評価する指標として用いることが出来る。
対数尤度の定義から、この指標は以下のように書ける。
ここで、P(x)はデータの確率分布をあらわす。この確率分布を計算する方法が不明。
論文では、クラスタの中心値で1になるような混合モデルを考えて計算すると有り、以下のように計算している。
l Silhouette Validation Method
クラスタのsilhouette widthを定義し、それによりクラスタが良く分かれているかどうかを判断する。silhouetteの定義は以下の通りである。
ここで、a(i)はi番目のデータと、それと同じクラスタに含まれるデータ間の平均距離である。b(i)はi番目のデータと、それと違うクラスタに含まれるデータ間の平均の距離である。このクラスタは、iの含まれるクラスタに一番近いクラスタである。（平均の距離が最小のクラスタとの距離である。）
silhouetteの定義から、この量は-1から１の間の値を取る。もしsilhouetteが1なら、適切なクラスタに分けられており、0なら、他のクラスタに分かれた方がよく、-1なら間違ってクラスタリングされていることを表す。よって、全体のsilhouetteの平均値が大きければ、良いクラスタであると見做す。
これらの指標を用いることで最適なクラスタ数を決定することも可能である。
図 パラメータ設定画面
|
項目 |
説明 |
|
Validation Index |
クラスタの評価指標を以下の中から選択 Calinski Hartigan Ratkowsky BallHall Scott Marriot Dunn DB CIndex Silhouette Likelihood |
|
Intra Cluster |
クラスタ内の距離計算方法を以下の中から選択 Complete Average Centroid |
|
Inter Cluster |
クラスタ間の距離計算方法を以下の中から選択 Single Complete Average Centroid Ave ToCenter Hausdorff |
|
Distance |
距離計算方法を以下の中から選択 Manhattan Euclid Cosine |
|
規格化 |
規格化を行なうかどうか |
|
クラスタ番号列 |
クラスタIDが振られている列 |
|
対象列 |
分析対象列 |
出力データは以下の通りである。
図 出力結果
A dendrite method for clustering analysis. R. B. Calinski and J. Harabasz, Communications in Statistics (1974).
Clustering Algorithms. J. A. Hartigan, New York Willy (1975).
A criterion for determinig the number of groups in a classification. D. A. Ratkowskt and G. N. Lance, Australian Computer Journal (1978).
A novel method of data analysis and pattern classification. G. H. Ball and D. J. Hall, NTIS Tech Rep No.AD699616,Stanford Research Institute (1965).
Clustering Methon based on likelihood ratio criteria. A. J. Scott and M. J. Symons, Biometrics (1971).
Practical problems in a method of cluster analysis. F. H. Marriot, Biometrics (1971).
A general statistical framework for assessing categorical clustering in free recall. L. J. Hurbert and L. R. Levin, Phycologiacal Bulletin (1976).
A cluster separation measure. D. L. Davies and D. W. Bouldin, Transaction on Pattern Analysis and Machine Intelligence (1979)