近傍法と形式概念解析を用いた制約付きクラスタリング

近傍法と形式概念解析を用いた制約付きクラスタリング

Constained Clustering via Nearest Neighbor Search

and Formal Concept Analysis

米田 友花

1∗

_{杉山 麿人}

2

_{鷲尾 隆}

1

Yuka Yoneda

1

Mahito Sugiyama

2

Takashi Washio

1

1

_{大阪大学 産業科学研究所}

1

_{The Institute of Scientific and Industrial Research, Osaka University}

2

_{国立情報学研究所}

2

_{National Institute of Informatics}

Abstract: We propose a constrained hierarchical clustering method that can take into account background knowledge of cluster memberships. We focus on must-link constraints, which are a set of pairs of data points that are in the same cluster. We use the following two-step procedure: In the first stage, we binarize data points based on nearest neighbor search and calculate logical disjunction of pairs of binarized data points given as must-links. In the second stage, we apply Formal Concept Analysis (FCA) to the binary data and obtain the hierarchical structure of clusters. We empirically show that our method can effectively achieve constrained hierarchical clustering.

1

はじめに

階層クラスタリング（hierarchical clustering）[1] は， 樹形図（dendrogram）と呼ばれる木構造によってデー タのクラスタを表現する手法であり，獲得した木構造 は関係推論や他の機械学習のタスクにおけるさらなる 分析に使うことができる．樹形図において，ノードは 各クラスタ，葉は各データ点に対応しており，樹形図 からクラスタの包含関係を解釈できる．そのため，言 語処理 [2] から人間行動解析 [3] まで，多変量データに 対し広く使用され，長年にわたり研究されている手法 である． 一般的な階層クラスタリング手法は教師なし学習で あり，データのラベル情報を用いずにクラスタの階層 構造を出力する. これに対して，分析者が要求する条 件を満たすクラスタを見つけるため，分析者の持つ事 前知識である教師情報を利用できる制約付きクラスタ リング（constrained clustering） [4] の研究が行われ ている．制約付きクラスタリングとは，制約として入 力データに一部の教師情報を与えた上で，クラスタリ ングアルゴリズムを適用する手法である．既存の手法 として，制約として与えられた 2 つのデータ点の距離 にペナルティ項を付けた距離を最適化する方法 [5] や， データ点全体の集合から制約に相当するコスト関数を ∗_{大阪大学 産業科学研究所} 〒 567-0047  大阪府茨木市美穂ケ丘 8-1 E-mail: [email protected] 更新しながら階層構造を獲得する方法 [6] などがある． 本稿では，同じクラスタに属するデータ点の組を教 師情報として利用する must-link 制約（must-link

con-straints）付き階層クラスタリングを実現する．提案手 法では，まず入力の連続値データを近傍法に基づいて 2 値化する．獲得した 2 値データに対して，must-link 制 約に対応する 2 値ベクトルの組に，それらの論理和を 代入する．must-link 制約を 2 値ベクトル間の論理和に よって実現することで，must-link 制約付き階層クラス タリングが達成できる．そして，形式概念解析（Formal Concept Analysis） [7] を 2 値データに適用すること で，クラスタの階層構造を獲得する．形式概念解析は， 代数的アプローチによって重複するクラスタを発見し， 2 値データが持つ階層的構造を抽出することができる 手法である [8, 9]． 本稿は以下のように構成されている．まず，2 節で提 案手法について述べる．そして，3 節で提案手法の評 価実験の結果を示し，結果を考察する．最後に 4 節で 本研究の結論と今後の課題について述べる．

2

提案手法

提案手法の概要について述べる．提案手法は 2 つの 段階からなり，第 1 段階は近傍法と must-link 制約を 用いた 2 値データの生成，第 2 段階は形式概念解析で ある． 人工知能学会研究会資料 SIG-FPAI-B803-10

第 1 段階では，連続値をとるデータを近傍法に基づ いて 2 値化し，must-link 制約に対応する 2 値ベクトル の論理和を計算することで，must-link 制約を取り込ん だ 2 値データに変換する．第 2 段階では，第 1 段階で 生成した 2 値データに形式概念解析 [7] を適用する．形 式概念解析を適用することによって，データ点の集合 同士の関係性を解析することができる [9] ため，元の 特徴空間において連続値をとるデータ点のクラスタの 階層構造が獲得できる．提案手法の疑似コードをアル ゴリズム 1 に示す．各段階の詳細については，2.1 節と 2.2 節に記載する． 提案手法への入力は，ラベルのない連続値ベクトル の集合 D であり，D は n 個のデータ点の集合 D = {d1, d1, . . . , dn} と書ける．それぞれのデータ点 diは m 次元の連続値ベクトルであり，di= (d1i, d 2 i, . . . , d m i )∈ Rm_{と書ける．また，must-link 制約として入力する教} 師情報 Φ⊆ Π は，データ集合 D に対して，真のクラス タの集合_{C = {C1}, C2, . . . , CP} が存在するとき，あり 得るすべての must-link 制約 Π の部分集合であり，Π は Π = ∪ p∈{1,2,...,P } {(i, j) | di, dj ∈ Cp} (1) と書ける．つまり，教師情報 Φ は，同じクラスタに属 するデータ点の組のインデックス集合である．

2.1

近傍法と must-link 制約を用いた

2 値データの生成

近傍法と must-link 制約を用いた 2 値化について説 明する．まず，近傍法を用いた 2 値化では，m 次元の 連続値ベクトル di ∈ Rmを n 次元の 2 値ベクトル zi∈ {0, 1}nに変換する．ここで，n とはデータ集合 D に含まれるデータ点の数である．変換後の 2 値ベクトル ziでの j 番目の特徴は，データ点 djがデータ点 diの 近傍であるかどうかを表している．つまり，データ集合 D⊂ Rm_{と変数 k∈ N が与えられたとき，各データ点} di∈ D が 2 値ベクトル zi= (zi1, z 2 i, . . . , z n i)∈ {0, 1} n に変換される．各要素 zj i は zj_i =      1 dj が diから k 番目までに 近いデータ点である場合 , 0 その他の場合 (2) と定義する．したがって，近傍法を用いて 2 値化すると， 元の特徴空間におけるデータ点同士の距離の関係性が 保存される．この考え方は，スペクトルクラスタリン グにおける k 近傍グラフにおいて用いられている [10]． そして，must-link 制約を用いて，制約を考慮した 2 値データを生成する．2 値ベクトル群 z1, z2, . . . , znを アルゴリズム 1 提案手法のアルゴリズム 入力： データ集合 D，近傍数 k，教師情報 Φ 出力： 概念束_L 1: for all i = 1 to n do 2: for all j = 1 to n do 3: データ点 di，djの間の距離を計算する 4: end for 5: for all j = 1 to n do 6: if di と dj の距離が k 番目までに短いとき then 7: zj_i = 1 8: else 9: zj_i = 0 10: end if 11: end for 12: end for 13: for all i, i′ ∈ {1, 2, . . . , n} do 14: if (i, i′)∈ Φ then 15: z′_i, z′_i′ ← zi∨ zi′ 16: else 17: z′_i, z′_i′ ← zi, zi′ 18: end if 19: end for 20: Λ← {z′1, z′2, . . . , z′n} 21: 飽和アイテム集合マイニングを Λ に適用し， 飽和な属性集合を獲得する 22: 飽和な属性集合から，概念束L を形成する 獲得したあと，must-link 制約としてデータ点の組のイ ンデックス集合 Φ を参照する．Φ に含まれるインデッ クスの組 (i, j)∈ Φ に対して，2 値ベクトル ziと zjの 論理和_{∨ を計算し代入することで，z}′ iと z′i′を獲得す る．すなわち，(i, i′)∈ Φ に対して， z′_i = z′_i′= zi∨ zi′ (3) とする．ここで，論理和_{∨ は 2 値ベクトルの要素ごと} にとり，u = zi∨ zi′（ただし，u∈ {0, 1}n）とすると， uj = { 1 z_ijまたは zj i′が 1 のとき 0 z_ijも zj i′も 0 のとき (4) となる．したがって，近傍法を用いて 2 値化したあと， must-link 制約に対応する 2 値ベクトルの集合 Λ = {z′ 1, z′2, . . . , z′n} を出力する．

2.2

形式概念解析の適用

形式概念解析について説明する．2 値データの Λ に形 式概念解析を適用し，提案手法の出力である階層構造

L を獲得する．形式概念解析は，2 値ベクトル集合から 概念（concept）の階層構造を獲得する手法である．概 念とは，2 値データ点の対象集合 A⊂ {z1, z2, . . . , zn} と属性を表すインデックス集合 B⊂ {1, 2, . . . , n} の組 からなる．そして，写像′を A′={j ∈ {1, 2, . . . , n} | ∀zi∈ A, zij= 1}, B′={zi∈ Λ | ∀j ∈ B, z j i = 1} (5) としたとき，A′ = B かつ B′ = A を満たす組 (A, B) を概念と定義する．概念 (A, B) において，対象集合 A がクラスタに対応し，属性集合 B は，飽和（closed） であることが知られている [11]．飽和な属性集合とは， それ以上属性を増やすと 2 値データにおける出現回数 が下がる集合のことである．したがって，提案手法で は，2 値データから属性の飽和集合を取り出し，対応 する対象集合を探索することで，クラスタの階層構造 を形成する． 飽和な属性集合は，頻出飽和アイテム集合を発見す るアルゴリズムを適用することによって獲得できる．提 案手法では，LCM [12, 13]1_{と呼ばれるアルゴリズムを} 適用した．LCM アルゴリズムは，飽和アイテム集合を 線形時間で列挙することができる手法として知られて いる．LCM アルゴリズムで得た飽和な属性集合LSか ら，対応する対象集合_LGを獲得でき，概念束L を形 成できる．ここで，_LGとLSは LG={A | (A, B) ∈ L}, LS={B | (A, B) ∈ L} (6) と書ける．2 値ベクトル ziは元の連続値データ diを 表しているため，_LGは入力データの階層構造と捉える ことができる．

2.3

動作例

ここで，提案手法の動作例を示す．入力する連続値 データは，図 1 のような n = 4，m = 2 のデータで， k = 1 のとき，近傍法を用いた 2 値化によって獲得す るデータは，表 1 のようになる．教師情報を考慮せず に形式概念解析を適用したとき，獲得するクラスタの 階層構造は図 2 のようになる．一方，表 1 のデータに おいて，d1と d3が同じクラスタに属するという教師 情報がある場合，対応する 2 値ベクトルの論理和を計 算することで，表 2 のような 2 値データを得る．そし て，表 2 に形式概念解析を適用すると，図 3 のような 階層構造を獲得する．図 2 と図 3 を比較すると，d1と d3に対応する z′1と z′3が必ず同じクラスタに属するよ うになることが分かる． 1 http://research.nii.ac.jp/~uno/codes-j.htm ᘌ ჿ  ᘌჿ G G G G 図 1: 入力の連続値データ 表 1: 図 1 を k = 1 で 2 値化したデータ 1 2 3 4 z1 1 0 1 0 z2 1 1 0 0 z3 0 0 1 1 z4 0 0 1 1

3

評価実験

提案手法を実データに適用して性能評価を行い，そ の結果について考察する．

3.1

実験方法

実験の評価指標として，Dendrogram purity （DP） [14] を用いた．DP は，階層クラスタの質を評価する標準 的な評価指標である [15]．データの集合 D ={d1, d2, . . . , dn} が与えられ，データの集合における真の分割が C = {C1, C2, . . . , CP} であるときを考える．ただし， ∪ Ci∈{1,...,P }Ci = D かつ Ci∩ Cj =∅ を満たす．ま た，階層クラスタリング手法によって獲得したクラス タの集合を_{H と書く．関数 LCA(di}, dj)∈ H を，H に あるデータ点 diと djのどちらもを含む最小のクラス タと定義する．また，関数 pur(F, G) を F, G⊆ D を満 たすクラスタの組に対して，pur(F, G) =|F ∩ G|/|F | と定義する．加えて，同じクラスタに属するデータ点 の組の総数を Q とする．つまり， Q =| {(di, dj)| di, dj∈ Cp（ただし Cp∈ C）} | (7) を満たす．以上の定義から，階層構造_{H の DP である} DP (H) を DP (H) = 1 |Q| P ∑ p=1 ∑ di,dj∈Cp pur(LCA(di, dj), Cp) (8) と定義する．この定義から，DP は典型的な階層クラス タリング手法で獲得する階層構造も，提案手法によっ て獲得する階層構造もどちらも評価できることが分か

]]]

]]

]]

]

]]]]

∅

]

図 2: 形式概念解析を表 1 に適用した結果 表 2: 表 1 に must-link 制約{(1, 3)} を取り込んだ 2 値化データ 1 2 3 4 z′₁ 1 0 1 1 z′₂ 1 1 0 0 z′₃ 1 0 1 1 z′4 0 0 1 1 る．DP は 0 から 1 の値をとり，大きい値であるほど， 階層構造の質が高いことを示す． また，実験では，UCI レポジトリ [16]2_{から 6 つの実} データを準備し，それらの詳細は表 3 にまとめた．そ れぞれの実データに対し，提案手法と比較手法を適用 し，獲得した階層構造の DP とクラスタ数を記録した． そして比較手法には，標準的な階層クラスタリング 手法であるウォード法 [17] を用いた．この手法は，ク ラスタ同士の類似度においてクラスタ内のデータの広 がりを考慮しているため，外れ値に有用な手法である ことが知られている [18]．本実験では，Python 言語の 標準的なライブラリである scipy3_{によって実装されて} いるものを用いた．

3.2

実験結果と考察

実験結果を示し，その考察をする．提案手法を評価 するために，3 種類の実験を行った． 実験 1 では，まず入力に教師情報がない場合に，適 切な k を設定したときの DP と，その時のクラスタ数 を測定した．実データに対する実験結果を表 4 にまと めた．表 4 では，提案手法とウォード法の DP につい て，高い方を太字で示している．適切な k は，それぞ れのデータにおけるデータ点の密集度と次元が影響す ると考えられる．表 4 における DP の比較から，ほと んどのデータにおいて，提案手法で獲得する階層構造 が，ウォード法のそれより質が高いことが分かる．これ は，ウォード法を代表とする従来の階層クラスタリン 2_{https://archive.ics.uci.edu/ml/index.php} 3_{https://scipy.org/}

]ܣ



]ܣ

]ܣ

]ܣ

]ܣ

]ܣ

]ܣ



]ܣ

]ܣ

]ܣ

]ܣ

]ܣ

]ܣ

∅

図 3: 形式概念解析を表 2 に適用した結果 表 3: 実データの詳細，ただし P は真のクラスタ数を 示す Name n m P parkinsons 195 22 2 vertebral 310 6 2 breast cancer 569 10 2 wine red 1,599 11 2 ctg 2,126 21 2 seismic bumps 2,584 14 2 グ手法は，互いに素なクラスタ同士を併合するアルゴ リズムであることに対し，提案手法は飽和な属性集合 からクラスタを検出するアルゴリズムであり，重複す るクラスタの検出が可能であるためと考えられる．実 データ seismic bumps においては，どちらの手法も高 い DP であることから，真のクラスタ同士が離れてい ると考えられる．一方で，表 4 におけるクラスタ数を 比較すると，提案手法の方が膨大である．これは，提 案手法の第 2 段階における形式概念解析の適用で，飽 和集合を利用しているためと考える．形式概念解析を 適用する 2 値データ Λ がスパースでない場合は飽和な 属性集合が多くなり，飽和アイテム集合が多くなる． 実験 2 では，提案手法で獲得した階層構造をより詳細 に評価するために，最小サポート（minimum support） を定めることで，提案手法のクラスタ数をウォード法 と同程度にし，そのときの DP を比較した．実験 1 と同 じように，教師情報がない場合を考える．最小サポー トとは，ある集合が 2 値データ内に出現する最低限の 回数のことで，より頻出する集合のみを抽出したいと きに与える．つまり，最小サポートを設定することで， LCM アルゴリズムによって飽和頻出アイテム集合を 探索し，データの階層構造を獲得した．最小サポート を大きくすることで，得られるクラスタ数は減少する． 実データに対する実験結果を表 5 にまとめた. 表 5 で は，提案手法とウォード法の DP について，高い方を 太字で示している．ただし，同程度のクラスタ数とは， 同じオーダーのクラスタ数であるときとしている．表 4 と表 5 における提案手法の DP を比較すると，最小

表 4: 実データにおいて適切な k を与えたときの DP とクラスタ数 Name クラスタ数 Dendrogram purity

提案手法 ウォード法 提案手法 ウォード法 parkinsons 263,189 393 0.828 0.738 vertebral 503,476,064 619 0.872 0.686 breast cancer 3,142 1,137 0.869 0.771 wine red 24,412,834 3,199 0.849 0.845 ctg 1,426,981 4,251 0.800 0.765 seismic bumps 91,059 5,167 0.931 0.943 サポートを設定し，クラスタ数を抑えることで，いず れのデータに対しても DP が減少している．クラスタ 数を抑えるために，最小サポートを設定したとき，概 念 (A, B) における B が飽和頻出アイテム集合に対応 するため，頻出になるほど，B の要素数は少なくなる． 式 5 から，より頻出な飽和集合 B における A は要素数 は多くなる．つまり，最小サポートを設定することは， 大きなクラスタを抽出することに相当する．大きなク ラスタからなる階層構造を獲得するため，式 8 の DP の定義より，最小サポートを設定したときに DP が低 くなると考えられる． 実験 3 では，教師情報量の変化に対する提案手法の DP とクラスタ数の変化を測定した．ここで教師情報 量とは，割合_{|Φ|/|Π| を表す．同じ真のクラスタに属す} るデータ点の組合せの総数は，データ数 n で真のクラ スタ数が P のとき，∑P p=1 (np 2 ) と書ける．ただし，np は真のクラスタ Cpに属するデータ点の個数である．実 験の結果を表 6 にまとめた．実験 3 では実験 2 と同様 に，クラスタ数の変動による DP の変化をなるべく減 らすために，適切な最小サポートを設定している．こ のため，表 5 の DP と表 6 の教師情報が 0 %のときの DP は異なる値となっている．表 6 から，6 つの実デー タでは，教師情報を与えるほど DP が上昇しているた め，提案手法では教師情報を考慮できることが分かる． これは，論理和を用いて must-link 制約を取り込むこ とで，与えられたデータ点の組が必ず同じクラスタに 属するためと考えられる．

4

結論と課題

本稿では，must-link 制約付き階層クラスタリングを 実現した．提案手法では，まず，連続値データを近傍 法を用いて 2 値化し，教師情報に対応する 2 値ベクト ルの論理和を計算することで 2 値データを獲得した． 形式概念解析を 2 値データに適用し，元の特徴空間に 対応するクラスタの階層構造を獲得した．実験による 性能評価の結果，教師情報がない場合に，提案手法は ウォード法よりも質の高い階層構造を獲得できること が分かった．また，提案手法は must-link 制約を効率的 に利用できることが分かった． 今後の課題として，提案手法のさらなる有用性を詳 細に評価するために，既存の階層クラスタリング手法に 制約を加えた場合と比較する必要がある．例えばウォー ド法に対し must-link 制約を取り入れるためには，初 期のクラスタ状態をすべてのデータ点がそれぞれのク ラスタであるという入力の代わりに，must-link 制約に 対応するデータ点の組を初期のクラスタ状態として入 力する方法などが考えられる．

参考文献

[1] O. Maimon and L. Rokach, editors. Data Mining

and Knowledge Discovery Handbook. Springer,

2005.

[2] P. F. Brown, P. V. deSouza, R. L. Mercer, V. J. D. Pietra, and J. C. Lai. Class-based n-gram models of natural language. Computational

Linguistics, 18(4):467–479, 1992.

[3] F. Zhou, F. D. l. Torre, and J. K. Hodgins. Hi-erarchical aligned cluster analysis for temporal clustering of human motion. IEEE Transactions

on Pattern Analysis and Machine Intelligence,

35(3):582–596, 2013.

[4] K. Wagstaff, C. Cardie, S. Rogers, and S. Schr¨odl. Constrained k-means clustering with background knowledge. In Proceedings of

the 18th International Conference on Machine Learning, pages 577–584, 2001.

[5] S. Miyamoto and A. Terami. Constrained ag-glomerative hierarchical clustering algorithms with penalties. In 2011 IEEE International

Con-ference on Fuzzy Systems (FUZZ-IEEE 2011),

表 5: 実データにおけるクラスタ数を同程度にしたときの DP とクラスタ数 Name クラスタ数 Dendrogram purity

提案手法 ウォード法 提案手法 ウォード法 parkinsons 863 393 0.740 0.738 vertebral 857 619 0.721 0.686 breast cancer 183 1,137 0.841 0.771 wine red 4,366 3,199 0.849 0.845 ctg 9,945 4,251 0.772 0.765 seismic bumps 9,910 5,167 0.930 0.943 表 6: 実データにおいて，教師情報量の増加に対する提案手法の DP Dendrogram purity

教師情報量 (%) parkinsons vertebral breast cancer wine red ctg seismic bumps 0 0.740 0.673 0.862 0.849 0.750 0.930 1 0.801 0.773 0.881 0.858 0.788 0.931 5 0.814 0.807 0.888 0.860 0.789 0.931 10 0.829 0.812 0.900 0.860 0.790 0.931

[6] V. Chatziafratis, R. Niazadeh, and M. Charikar. Hierarchical clustering with structural con-straints. In Proceedings of the 35th International

Conference on Machine Learning, 2018.

[7] B. A. Davey and H. A. Priestley. Introduction to

Lattices and Order. Cambridge University Press,

2 edition, 2002.

[8] P. Valtchev, R. Missaoui, and R. Godin. For-mal concept analysis for knowledge discovery and data mining: The new challenges. In Concept

Lattices, volume 2961 of LNCS, pages 352–371,

2004.

[9] M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis. Mining gene expression data with pattern structures in formal concept analysis.

In-formation Sciences, 181:1989–2001, 2011.

[10] U. von Luxburg. A tutorial on spectral clus-tering. Statistics and Computing, 17(4):395–416, 2007.

[11] N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Efficient mining of association rules using closed itemset lattices. Information

Sys-tems, 24(1):25–46, 1999.

[12] T. Uno, T. Asai, Y. Uchida, and H. Arimura. An efficient algorithm for enumerating closed pat-terns in transaction databases. In Discovery

Sci-ence, volume 3245 of LNCS, pages 16–31, 2004.

[13] T. Uno, M. Kiyomi, and H. Arimura. Lcm ver. 2: Efficient mining algorithms for fre-quent/closed/maximal itemsets. In FIMI, 2004. [14] K. A. Heller and Z. Ghahramani. Bayesian

hi-erarchical clustering. In Proceedings of the 22nd

International Conference on Machine Learning,

pages 297–304, 2005.

[15] A. Kobren, N. Monath, A. Krishnamurthy, and A. McCallum. A hierarchical algorithm for ex-treme clustering. In Proceedings of the 23rd ACM

SIGKDD International Conference on Knowl-edge Discovery and Data Mining, pages 255–264,

2017.

[16] M. Lichman. UCI machine learning repository, 2013.

[17] J. H. Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American

Statistical Association, 58(301):236–244, 1963.

[18] G. W. Milligan and M. C. Cooper. A study of standardization of variables in cluster analysis.