               

制約付きクラスタリングにおける人間の能動学習を促進するインタラクションデザイン
      山田 誠二    水上 淳貴

岡部 正幸     


国立情報学研究所／総合研究大学院大学
              



東京工業大学 大学院     !

豊橋技術科学大学 情報メディア基盤センター   " #  !    
                                                                               
        
                                                           

はじめに

クラスタリングは，データマイニングの中でも広く利用されている俯瞰的な可視化が可能な技術の一つであるが，原理的にユーザフィードバックのない教師なし学習であり，そのため自動的に生成されるクラスタがユーザを十分に満足させるものではない場合が多い．ユーザが希望するクラスタリングを得るために，ユーザフィードバックを利用してクラスタリングを実現する
制約付きクラスタリングやインタラクティブクラスタリングが提案され，研究開発が行われている !" #$ " %%  #&'．
制約付きクラスタリング（     ）!" #$'では，典型的には同じクラスタに属すべきデータペアと同じクラスタに属すべきでないデータペアに対し，それぞれ リンク，  リンクと呼ばれるペアワイズ制約が与えられ，それらの制約をすべてあるいは最大限満たすようにクラスタリングを行う．ユーザが自分の所望のクラスタリングに沿った制約をシステムに与え，制約付きクラスタリングアルゴリズムが再クラスタリングを実行して，その結果を見て再度ユーザが制約を与えるという手続きをユーザが満足するまで繰り返すのがインタラクティブ制約付きクラスタリング（図 (）である．
インタラクティブ制約付きクラスタリングは，ユーザフィードバックを有効に利用できることから，ユーザの所望に合致したクラスタリングを得るために有効な方法であるが，いくつか解決すべき問題がある．一つの大きな問題は，制約付きクラスタリングを利用するため，制約の質の影響を受けることがある．制約付きクラスタリングでは，どんな制約でも有効であるわけではなく，制約によってはほとんど役に立たない，あるいは返ってクラスタリングを阻害する場合もあることがわかっている !)   (*'．このことから，インタラクティブ制約付
きクラスタリングにおいても，有効な制約のみを人間に与えてもらうことが重要となる．
この問題は，従来の分類学習においては，いかに有効な訓練データを決定するかという能動学習（   ）の問題であり，不確実性サンプリング（  ）連絡先+ 山田 誠二，国立情報学研究所， ,-,ユーザ

制約

制約付きクラスタリング
クラスタリング
結果

図 ( インタラクティブ制約付きクラスタリング!.  /0' や 1" 21     3!4  /*' を初めとするさまざまな解決法が提案されてきた．これまでの能動学習は，計算可能なアルゴリズムとして有効な訓練データを決定するものであるが，近年人間の能動学習（56.+ 5
6
.  ）に着目する研究が始まっている !
#$'．
我々の研究対象としているインタラクティブ制約付きクラスタ
リングにおいては，人間のユーザが分類学習の訓練データに対応する制約をシステムに与えることから，本研究ではこの56. をうまく引き出すことで有効な制約の獲得を目指す．
このような背景から，本研究では人間の能動学習を引き出すインタラクションデザインを提案する．具体的には，ユーザが自分が与えた制約の効果を顕在化する機能，クラスタリング結果を複数の視点から俯瞰することができる機能を  として導入し，それらにより 56. を促進することを目指す．そして，画像データのクラスタリングにおける参加者実験により，その有効性を実験的に確認する．
関連する研究として，教師あり分類学習における計算論的能動学習がある．能動学習には様々な方法があるが，基本的には「最も判別が難しいデータ」をラベリング候補として選択するものが多い．本研究では，人間の能動学習と計算論的能動学習との比較を実験的に試みる．また，データマイニングツールの としては，例えば広く使われている  %!5 #/' において，56. を明示的に促進するような  は導入されてい               
(b)

(a)

(c)
(4)
(d)

(e)

図*56. のための 

小さいこと，およびユーザが * 種類の制約があるとその選択が難しいことを考慮して，本研究では 9 リンクのみを扱っている．
ペアワイズ制約を扱う制約付きクラスタリングのアルゴリズ
ムは，大別して，<=>? ! #(' に代表される制約をすべて満たすようにクラスタ割り当てを変更する方法と，
9 リンクのペアデータ間の距離を小さく，  リンクのデータ間の距離を大きくするように距離関数を最適化する距離学習による方法 !@ #$' がある．本研究では，計算速度の速さから <=>?  を採用し，システム自体は 96;.6"，= ，@ 4  で実装した．

ない．
人間の能動学習 56. は， らにより先駆的な研究がなされた ! #$'．彼らは，数直線上の実数値の探索において，参加者が期待利得最大と同様の考え方により二分探索を行うことを示し，56. の特徴を計算論的学習理論の観点から調べている．また，数値をイラスト化して参加者に提示するなどの可視化の工夫も行っている．
インタラクティブ機械学習 !7 #8' も，人間が訓練データにクラスのラベリングを行い，コンピュータがその訓練データに基づき分類学習を行って，その結果を提示することを繰り返す．7 らの先駆的研究では，画像のセグメンテーションのためのピクセル単位の分類学習に応用され，* 8 秒以内で学習が終わる高速な学習アルゴリズムが必須であると主張されている．最近では，単なるラベリングを超えて学習のための探索を人間側の役割とした拡張が，9   :    の研究チームにより行われている． 7%!7   #$' は，画像特徴に基づく画像検索の結果のランキング学習をインタラクティブに行っており， ;!6  ((' では，ネットワークのアラームという非常に動的な環境において，ユーザが迅速かつ正確にトリアージするための可視化を提供している．これらの研究では，56. を明示的に扱ってはいない．

 を引き出す 

図 * に，  ブラウザ上の  全体のスナップショットを示す．図 *23 にクラスタリング結果が提示され，これを眺めてユーザは，9 リンクのデータペアを選択する．その際，
図 *23 のサムネイル画像にマウスオーバーすると拡大画像が図 *23 に表示され，画像の詳細を確認できる．また，図 *23のサムネイル画像をマウスクリックすると図 *23 にそれらの画像が表示され，データペアとして選択されたことがわかる．
データペアが決まれば，図 *23 の 9 ボタン，ボタンをマウスクリックすることにより，選択されたデータペアが 9 リンクとしてシステムに渡され，その制約を基に制約付きクラスタリングが行われて，そのクラスタリング結果がユーザに再度提示される．このループが，ユーザが満足するクラスタリングが得られるなどの終了条件が成り立つまで繰り返される．データペアを選ぶ時に，ユーザは図 *2 3 にある (*通りの * 軸を自由にマウスクリックで選択でき，選択された視点からのクラスタリング結果が図 *23 に表示される．
この  は，56. を促進するために，以下の * つの機能を導入している．

  のための  のデザイン
 インタラクティブ制約付きクラスタリング
まず，56. 促進のための  デザインのベースとなるシステムとして，インタラクティブ制約付きクラスタリングシステムを採用し，オンライン実験を可能にするため，   ブラ
ウザ上でインタラクティブにユーザが制約を与えることのできる   システムとしてインタラクティブ制約付きクラスタリングを実装した．制約としては，最も広く使われているペアワ
イズ制約（9 リンクと   リンク）を対象とするが，一般に制約付きクラスタリングでは，  リンクは効果が¯ 制約の効果の顕在化：ユーザが与えたペアワイズ制約がどのような効果があったのかをユーザにわかりやすく示               

図 8 付与された制約の効果の顕在化すことで，ユーザが制約とその効果の因果関係を把握しやすくなり，その理解に基づいて次に選ぶべきデータペアを選択する 56. の促進が期待できる．顕在化のための視覚化を図 8 に示す．このように，最近に与えられた制約の影響で，所属するクラスタが変化したデータを円によって強調表示することで顕在化を実現する．

図 0 複数視点の選択ウインドウ（図 *2 3）
実験は，($ 人の参加者（男性 (0 名，女性 0 名，年齢 ($ 歳〜B* 歳）の協力を得て，* つのシステムを水準とした ( 要因
* 水準で参加者内配置で行った．参加者は，クラスタリングシステムの使い方を説明され，実験の練習を行い，制約付与について，「制約付与において離れたデータペアの制約は影響が大きい傾向がある」，「同一のデータに多くの制約を与えるとよくない」という制約付与に関する最小限の教示を受けた．
クラスタリングのパフォーマンスは，正解ラベルがわかっていることもあり，正規化相互情報量 F9 2F   9  3!# (' を用いた．F9 はシステムが把握しているのみで，参加者には一切知らされなかった．また，初期クラス
タは，制約なしのクラスタリングで F9 G #00 の単一のクラスタ結果を用いた．* 水準を各参加者に与える順序はカウンタバランスをとった．そして，F9 G (，つまり完全に正しいクラスタに達するか，B# 制約を与えた時点で試行を終了とした．
計算論的能動学習の一つである不確実 性サ ンプリ ング!.  /0' は，* クラスの分類学習を対象としており，その基本的な考えは，Dもっとも分類が困難なデータを選択するEというものである．この選択指針をペアワイズ制約の制約付きクラスタリングに適用すると， D最も分類が困難なデータE とは，D別クラスタに分類された最も距離の近いペアデータE と考えられる．よって，ここではそのような選択指針で制約付きクラスタリングにおける計算論的能動学習を実装し，提案手法との比較もおこなった．このサンプリングでは，同一のシードを使用すると選択される制約が一意に固定されてしまうため，制約のない初期 F9 が #0#〜#0/ となるようなシードをランダムに使用した．さらに，参加者実験と同様のシードを使用して，ランダムに制約の選択を行うランダムサンプリング :4も比較対象として用いた．

¯ 複数視点の選択：一般にデータは高次元ベクトルデータなので，クラスタリング結果をユーザに提示するためには，* 次元にデータを配置する必要がある．ここでは，多次元尺度構成法 !"  /&' により，* 次元配置を実現した．
そして，* 軸の固有値を最大のものから * つ選ぶだけではなく，(* 通りの固有値の組み合わせを用いて，その視点でのデータポイントをプロットした視点のサムネイル表示を図 0 のようにユーザに示した．この視点変更の機能により，クラスタリング結果を様々な視点で俯瞰することができ，例えば，離れた／近いデータ，クラスタ中心部分にあるデータなどの 56. にとって有益と考えられるデータを見つけやすくすることが可能となる．
ここでは，ユーザの判別の容易性を重視し，画像をデータとして用いた画像データのクラスタリングを行っている．画像データは，広くテストベッドとして使われている 6.;A5
½ を用いた．このデータセット中の画像は，*BC のクラス
*BC（フォルダ）に分類されており，すべての画像データにクラスラベルが付いていると見なすことができる．今回は，無作為に D
ヒトデE，Dノート =E，DバイクE の 8 つのクラスタを選択し，それぞれのクラスの画像数をリサンプリングして B# にそろえ，全体で (B# データとした．各画像は，回転，スケーリングに不変な画像特徴として広く使われている 4 7;!.  #0' により特徴を抽出し，     ! % #0' により，8## 次元のベクトル化を行った．さらに，;7> )7 などによる正規化も施した．

 評価実験

 実験方法
前節で 56. を促進するために導入した * つの機能が，本当に 56. の促進に寄与するかどうかは，直接的には評価が難しい．そこで，本研究では，それらの機能が実装されたインタラクティブ制約付きクラスタリングシステム（> ）と実装されていない同システム（> ）を用いて，参加者実験を行い，そのパフォーマンスを比較することで提案する  の効果を実験的に調べた．
$%&&'''(# ( (実験結果

パフォーマンスの評価は，F9 G ( となるまでに必要だった制約数と試行が停止するまでの最大 F9 で行った．前者は完全に正しいクラスタに達した場合の効率を評価し，後者はそうでない場合のパフォーマンスの評価と考える．> と> のこれらの評価の結果（各水準の平均と標準偏差）を図B，図 C に示す．また，> と > の結果と不確実性サンプリング 4 とランダムサンプリング :4 の結果を併せて，
表 ( に示す．
図 B，図 C の結果に，>検定を適用した結果，両評価とも& ! )&* +,&               **60

表 ( 各手法における実験結果（平均と標準偏差 4)）50

手法制約数 24)3

最大 F9 24)3

>8C( （(#/）#/C （##&）>

00C （(*(）#$8 （#(0）40&# （$B）#&/ （#(&）:4

B## （##）#C* （#(&）

40
30
20
100

図Bp-GUI

t-GUI    > J       $       %       # @6 K#&  C$0HC$/ 4 7  6 46

F9 G (# に至るまでの制約数



**

2*##&3 9

10.8!"

0.60.4

 /&' "

 ? =   =+ &  " "#       4  L      2(//&30.2!

0p-GUI

図C

t-GUI#$' : ;: 9 ?  F % : 1 : M

N+5 6B# 制約中の最大 F9! % #0'  %)

7

% @  "  + L  !)   (*' )  !7 #8' 7

,:  .   "+5>  9

7  6 ?

F    *BC0H*BC/ 2*#((3!" #$' "4)  6

 #&' " %% A ?+ :



@;

)





>+,,

@ +

?

6

       >.(  */H8$ 2*##$3   =  < 5+;

"

A?6     ?+            '$( L  **  &C(H&C$ 2*##$3!.  /0' .  )      J!. 

#0' . 

+ 6  O   )+ )   %     L  C# F  *  /(H((# 2*##031

+   ! #(' 4

6 @         >  "  !#9  4  % 5+

67 4  *$&H*/0 2(//*3? 

:  4+     ?>   %  /345  8H(* 2(//03   % !4  /*' 4  5 4 <:  5) :

!@ #$' @ = ? " )    !     " #        5I: 2*##$3!" %%+    & /+,, 01   '2  L  (( F  (  (#H($ 2*##/39>?

  

% 6  ;    -  8/H0B 2*##83

4+  7%+ :  参考文献
"!5 #/' 5 9 7 % A 5    = .

;@ 6  <    !7   #$' 7  

本稿では，ユーザにクラスタリング結果を提示して，ペアワイズ制約を与えてもらい，制約付きクラスタリングを繰り返す
インタラクティブ制約付きクラスタリングの枠組みにおいて，ユーザの能動学習を引き出すインタラクションデザインを提案した．具体的な方法として，制約の効果を顕在化する  とクラスタリング結果を様々な視点から俯瞰することができる
 の機能を導入したシステムを提案し，   システムとして実装した．
そのシステムを用いて，画像データのクラスタリングを対象とした参加者実験を行い，提案する  のないシステムとのパフォーマンスの比較から，提案する  が人間の能動学習に効果があることを実験的に検証した．

4+ (8(*H(8*# 2*#(*3 まとめ>           

 ((' 6. %    ) *        "#  !  L  (  ** 2*##03

> ，> 間に有意差が認められた（ G (0  G ##8）．
こららの結果から，ユーザは，本研究で提案した * つの新機能をもつ  を用いることで，それらの機能がない従来の よりも，より効率的に有効な制約を付与できることが示されたと言える．また，表 ( より，統計的検定は適用できないものの，従来の計算論的能動学習よりも人間の能動学習がよい性能を示すことが示唆された．

!6.  '$(  *0(H*0$ 2*##$3

4

  %> &7  B&&HB$0 2*##(3