(57)【要約】【課題】ＳＯＭの結果から新たにセル群をクラスタ化する手法を提供する。【解決手段】複数の多変量データをＳＯＭによってクラスタリングして二次元平面上にセルの形状を四角形または六角形として表示し、隣接する各セルの代表ベクトルとの類似度を計算して三次元的にデンドログラムを描写する。デンドログラムを分割する平面801に応じてＳＯＭマップ上のセル群を色分け表示802する。【選択図】図８
2006163894.tif 000002
【特許請求の範囲】
【請求項１】
複数の多変量データを二次元平面上にクラスタリングするＳＯＭ実行部と、
ＳＯＭの各セルを、隣接セルの代表ベクトルの類似度を用いて階層型にクラスタリングするデンドログラム実行部と、
前記デンドログラム実行部によって得られたデンドログラムを前記ＳＯＭ実行部によって得られたＳＯＭの上に三次元的に描画するクラスタリング結果表示部と
を有することを特徴とするクラスタリングシステム。
【請求項２】
請求項１記載のクラスタリングシステムにおいて、前記セルの形状は四角形又は六角形であることを特徴とするクラスタリングシステム。
【請求項３】
請求項１又は２記載のクラスタリングシステムにおいて、前記クラスタリング結果表示部は、前記三次元的に描画されたＳＯＭとデンドログラムを回転表示することを特徴とするクラスタリングシステム。
【請求項４】
請求項１又は２記載のクラスタリングシステムにおいて、入力手段を有し、前記クラスタリング結果表示部は、前記入力手段によって指示された位置に、前記三次元的に描画された前記デンドログラムを分割する平面を表示することを特徴とするクラスタリングシステム。
【請求項５】
請求項１又は２記載のクラスタリングシステムにおいて、デンドログラムの分割位置を決定するクラスタ結果評価部を有し、前記クラスタリング結果表示部は、前記クラスタ結果評価部が決定した分割位置に前記三次元的に描画された前記デンドログラムを分割する平面を表示することを特徴とするクラスタリングシステム。
【請求項６】
請求項４又は５記載のクラスタリングシステムにおいて、前記クラスタリング結果表示部は、前記デンドログラムの分割に対応して分割されたＳＯＭマップ上のセル群を色分けして表示することを特徴とするクラスタリングシステム。
【請求項７】
請求項１〜６のいずれか１項記載のクラスタリングシステムにおいて、前記多変量データが遺伝子やタンパク質の発現データであり、各遺伝子やタンパク質をキーとしてサンプルを次元としてとった値か、もしくは逆にサンプルをキーとして各遺伝子やタンパク質を次元としてとった値であることを特徴とするクラスタリングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング手法のＳＯＭ（自己組織化マップ）とデンドログラム（樹状図）を組み合わせることによって、クラスタリング結果を視覚的に分かり易く表示するクラスタリングシステムに関する。
【背景技術】
【０００２】
従来、複数の多変量データにおいて各データの類似度をユークリッド距離（多次元空間の単なる幾何学的な距離）やマンハッタン距離（単純な各次元の差で表された距離）を計算してグループ化する手法であるクラスタリングの一手法として、ＳＯＭ（Self Organizing Map）（T. Kohonen, “Self-Organizing Maps”, Springer 1995)が非階層的な手法の中でも特にデータを二次元平面上にマッピングする特徴を持つ手法として用いられてきた。ＳＯＭでは、距離が小さい（類似度が大きい）データが二次元平面上の近くにまとまるクラスタリング結果となる。また、特許文献１に記載のように、クラスタリング手法の中でデンドログラムという手法が各データ間の類似度を樹状図として階層的に表示する特徴を持つ手法として古くから用いられている。デンドログラムは、クラスタ間の距離をウォード法や最近隣法などの定義式を用いて、距離が小さいクラスタをまとめて樹状図（トーナメント図）を描いていく。デンドログラムの結果からは最適なクラスタに分割する位置がどこなのかが分からないため、各クラスタ内データの距離が最小で各クラスタ間距離が最大となるのを最適とする基準などに基づいた計算式が考案されてきた。
【０００３】
なお、ＳＯＭやデンドログラムといった各種クラスタリング手法を含めたデータマイニングは、近年、DNAマイクロアレイを用いた遺伝子発現解析において網羅的に解析したデータから生物学的に意味のある知見を発見するために用いられている。この場合、クラスタリングなどの多変量解析で用いられるデータは、各遺伝子をキーとしてDNAマイクロアレイを次元としてとった値か、もしくは逆にDNAマイクロアレイをキーとして各遺伝子を次元としてとった値となり、遺伝子をキーとした場合は、時系列データの実験では代謝や発生に関連した遺伝子群がクラスタとして得られることが論文等で報告されており、DNAマイクロアレイをキーとした場合は、ガンなどの疾患のサブタイプが各クラスタとして得られて、臨床診断技術に応用されることが期待されている。
【０００４】
【特許文献１】特開2004-192651号公報
【非特許文献１】T. Kohonen, “Self-Organizing Maps”, Springer 1995
【非特許文献２】J. Cybernetics. Vol.4, 1974, pp. 95-104
【非特許文献３】IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 1, No2, 1979, pp.224-227
【非特許文献４】J.Comp App.Math, Vol.20,1987,pp.53-65
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ＳＯＭをクラスタリング手法として用いる際に、実行結果として各セル内にまとめられたデータが一つのクラスタとなり、近くのセルのデータは類似していることが視覚的に分かるが、あるセルと隣接する各セルの中でどのセルが一番類似しているのかということを視覚的に判定することが難しいという問題点がある。また、ＳＯＭの初期設定で用いたセル数が最終的なクラスタリング結果としては適切でない場合が多いことから、どのセル群を一まとめにできるのかということを統計解析によって検証して視覚的に表示することが求められている。
【０００６】
本発明の目的は、ＳＯＭのクラスタリング結果に対して、セル間の類似度の大小を計算してその構造を可視化することにより、クラスタリング表示システムの使用者がＳＯＭの結果から新たにセル群をクラスタ化する手法を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明は、デンドログラムの手法をＳＯＭのクラスタリング結果に適用して、ＳＯＭマップ上に三次元的に樹状図を描画する表示システムを提供する。すなわち、複数の多変量データを入力する手段と、入力された多変量データをＳＯＭによってクラスタリングして二次元平面上にセルの形状を四角形または六角形として表示する手段と、セルの形状が四角形である場合は隣接４個で、六角形の場合は隣接６個の各セルの代表ベクトルの類似度を計算する手段と、類似度から三次元的にデンドログラムを描写する手段と、デンドログラムを分割する平面を表示して使用者が分割位置を変更できる手段を備える。デンドログラムを分割する平面は、クラスタリング結果評価手段によって自動で決定してもよい。
【発明の効果】
【０００８】
本発明によると、ＳＯＭのクラスタリング結果に対して階層的クラスタリング手法であるデンドログラムを適用することにより、三次元表示されたデンドログラムからセル間の類似度の大小やグループ化を視覚的に把握することが可能になる。また、三次元表示されたデンドログラムを平面で分割することにより、セル群を視覚的に適切な位置で再クラスタリングすることができる。さらに、従来研究されていたデンドログラムの結果に対して最適な分割位置を決定する評価基準を適用することによって、ＳＯＭのクラスタリング結果を再クラスタリングする位置を自動的に決定することが可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、本発明を実施する場合の一形態を、図面を参照して具体的に説明する。
【００１０】
図１は、本実施例のシステム構成を示している。このシステムは、クラスタリングの計算や評価および結果の表示を行う中央処理装置104、キャラクタ及びグラフィック画面を有するディスプレイ装置101、キーボード102、マウス103、クラスタリング用データ110を格納するために用いる外部記憶装置109を備える。中央処理装置104は、ＳＯＭ実行部105、デンドログラム実行部106、クラスタリング結果評価部107、クラスタリング結果表示部108を有している。ＳＯＭ実行部105、デンドログラム実行部106、クラスタリング結果評価部107、クラスタリング結果表示部108は、いずれもプログラムによって実現することができる。
【００１１】
ＳＯＭ実行部105は、クラスタリング用データとアルゴリズム設定用パラメータを受け取ってＳＯＭのクラスタリングを行う。パラメータの設定にはセルのサイズや学習回数およびセルの影響範囲の縮退を表す関数など様々なものが用いられ、本発明において特別なアルゴリズムを付加するわけではない。セルの形状を四角形かまたは六角形にするかによる隣接セル数の差異とマップの表示方法が本発明で関係してくる。デンドログラム実行部106は、距離/類似度の計算式の選択やクラスタ併合アルゴリズムの選択などをパラメータとしてデンドログラムのクラスタリングを行う。本発明においては世の中に良く知られている方法と比べて、ＳＯＭの代表ベクトルを隣接セル間のみで比較していくという違いがある。
【００１２】
クラスタリング結果評価部107は、クラスタリング結果の妥当性を評価するモジュールであり、Silhouette Index などのクラスタリング結果を評価するアルゴリズムを用いて、デンドログラムの場合はクラスタ数で範囲指定した中で最適なクラスタ分割位置を決定する。クラスタリング結果表示部108は、ＳＯＭマップ上にデンドログラムを描画する処理や立体状に表示されたデンドログラムを分割する平面を表示する処理などを行う。本発明において、発明の効果を担う部位である。
【００１３】
図２は、セルの形状を四角形にしてＳＯＭを実行した結果をイメージした図であり、セルサイズを３かける３、多変量データは4次のデータとしている。201は、四角形のセルであり、隣接セルは上下左右の4個、または設定によっては隣接セルは8個となる。202は、セル内に割り当てられた各データから求められる代表ベクトルである。計算方法は平均値や中央値などがある。例えば、DNAマイクロアレイを用いた遺伝子発現解析の場合、遺伝子方向でクラスタリングを行う場合は各遺伝子がチップ数の次数を持ったベクトルデータを持つことになる。数十枚のDNAマイクロアレイを用いて遺伝子発現解析が行われる場合が多いが、図２の例ではチップが4枚となるので、例として生後1日、2日、4日、8日の時点でのマウスの小脳の組織をサンプルとした時系列データをSOMによってクラスタリングを行ったとすると、小脳で常に発現している遺伝子群や生後初期段階のみで発現している遺伝子群などにまとめられて各セル内に配置される。図２の真ん中のセルは常に発現していない遺伝子群ということになり数千の遺伝子のデータの中央値を求めて他のセルと比較するための代表ベクトルとする。
【００１４】
図３は、セルの形状を六角形にしてＳＯＭを実行した結果をイメージした図であり、図２と同様に、セルサイズを３かける３、多変量データは4次のデータとしている。301は、六角形のセルであり、隣接セルは6個となる。302は、202と同様にセル内に割り当てられた各データから求められる代表ベクトルである。
【００１５】
図４は、デンドログラムの一般的な実行結果を表したイメージ図であり、ベクトルデータの類似度の高いものから組み合わせていくアルゴリズムとなっている。401は、樹状図と呼ばれるもので、横軸が各データの類似度を表す距離となっている。402は、各ベクトルデータであり、類似しているものが近くに集まる結果となる。
【００１６】
図５は、図２のＳＯＭのクラスタリング結果からデンドログラムを三次元的に描画したイメージ図である。501は、通常の二次元平面上に描くデンドログラムのように、各セルの代表ベクトルから類似しているデータ同士を併合していった結果、データ間の距離を高さとして表したものである。通常のデンドログラムとは異なり、併合できるのは隣接したセル同士のみとなる。502は、この三次元的なデンドログラムをマウス操作やメニュー操作などによって回転して表示できることをイメージした矢印である。三次元的なデンドログラムの回転表示は、既知の手法によって実現可能である。
【００１７】
図６は、デンドログラムの実行結果から樹状図を分割してクラスタを決定する一般的なイメージ図である。601は、樹状図を分割する位置を決めるイメージを点線で表したもので、602は樹状図と点線が交差した位置を表す黒丸であり、黒丸より右側のツリーのデータを各クラスタとしてまとめたイメージが603である。601の点線を右に移動して分割する位置を変更すれば、604のように結果として得られるクラスタ数が変化する。
【００１８】
図７は、例えばデンドログラムの分割線の移動によって得られるクラスタの中で、クラスタリング結果の妥当性を計算する各種のアルゴリズムによってクラスタ評価値を計算し、最適なクラスタ数を求めるイメージ図である。背景技術で述べたように、クラスタリング結果の妥当性を計算するアルゴリズムは、各クラスタ内データの距離が最小で各クラスタ間距離が最大となるのを最適とするなどの基準に基づいて、例えば非特許文献２に記載のDunn’s Indexや、非特許文献３に記載のDavies Bouldin Indexや、非特許文献４に記載のSilhouettes Indexのような指標が提案されている。そこで、ある指標をユーザが選択して、図６の左のクラスタ数が２となる分割位置で決定される２つのクラスタのクラスタ評価値を計算し、次は図６の右のクラスタ数が３となる場合のクラスタ評価値を計算するというように順にユーザが決めたクラスタ数の範囲でクラスタ評価値を計算して、最も妥当である最適クラスタ数（図７の場合はクラスタ数６）が求まる。
【００１９】
図８及び図9は、一般的に二次元上のデンドログラムにおいてクラスタに分割する位置を図６のように線分で決定するように、図５においてデンドログラムが描画された後にクラスタに分割する位置を平面で決定する様子を表した図である。
【００２０】
図８において、801は、デンドログラムを分割する平面である。分割平面とデンドログラムの交差する点の下にあるＳＯＭ上のユニットがクラスタを形成する。分割位置を決定する方法として、GUIによって分割平面801を上下させて視覚的に分割位置を決定する方法と、図７のようにしてクラスタ評価値を用いて自動的に分割位置を決定する方法がある。
【００２１】
802は、平面が分割した位置によって、各セルがクラスタごとに色分けされる様子を表している。図８の場合は、ＳＯＭマップ上で各セルが二つの領域に再クラスタリングされていることになる。図９は、分割平面901を図８よりも1段階下に移動した場合を示しており、902のようにＳＯＭマップ上では3つの領域に色分けされた状態で表示される。
【００２２】
図１０は、本発明の全体の処理を表すフローチャートである。
【００２３】
1001は、クラスタリング用データを入力する処理である。
【００２４】
1002は、前述のようにマップのセルの数などのパラメータを入力して決定する処理である。
【００２５】
1003は、1002で決定されたパラメータのうち、セルの形状によって隣接セルの処理などが異なるための分岐処理である。
【００２６】
1004は、1002で決定されたパラメータでＳＯＭを実行する処理である。
【００２７】
1005は、1004の結果を図２のように二次元平面状に描画する処理である。
【００２８】
1006は、前述のようにデンドログラムを実行するための類似度の計算方法やクラスタ併合アルゴリズムを選択する処理である。
【００２９】
1007は、デンドログラムを実行して、四角形のセル（併合後の多角形のセルを含む）の隣接するセルの中から代表ベクトルの距離の最も小さい値を求める処理を全てのセル（併合中は併合アルゴリズムを用いる）に対して行い、一番距離の小さいクラスタ同士を併合していく処理を繰り返していくものである。ＳＯＭ平面状で隣接するクラスタとしか距離を計算しないため、通常のデンドログラムよりも計算量は少なくてすむことになる。
【００３０】
1008は、デンドログラムの結果を三次元的に表示する処理であり、一般的なクラスタリングシステムと同様に、各枝を選択すればクラスタ間の距離をポップアップで表示する処理や、枝の高さを対数表示する処理も含む。また、デンドログラムを回転表示することで各クラスタの分布状態を確認して新知見を得る手助けとする。
【００３１】
1009は、分割位置を決定する処理であり、詳細は後述する。
【００３２】
1010は、セルの形状を六角形として、1002で決定されたパラメータでＳＯＭを実行する処理である。
【００３３】
1011は、1010の結果を図３のように二次元平面状に描画する処理である。
【００３４】
1012は、1006と同様に、デンドログラムを実行するための類似度の計算方法やクラスタ併合アルゴリズムを選択する処理である。
【００３５】
1013は、1007と同様にクラスタ併合を行っていく処理であるが、セル形状が六角形であるので隣接クラスタの判定処理が1007とは異なることになる。
【００３６】
1014は、1008と同様にデンドログラムの結果を三次元的に表示する処理であり、セル形状が六角形であるので描画処理が1008とは若干異なることとなる。
【００３７】
1015は、1009と同様に分割位置を決定する処理であり、詳細は後述する。
【００３８】
1016は、終了処理であり、クラスタリング結果を見て、前処理の変更や各種パラメータの変更を行うのであれば、図１０のマイニング処理を初めからやり直すこととなる。
【００３９】
図１１は、分割位置の決定処理であり、クラスタリング結果の評価手法から自動的に決定するか、もしくはGUIによって可視的に分割する。
【００４０】
1101は、使用者がクラスタ評価手法を用いるかどうかを選択する分岐条件である。
【００４１】
1102は、前述のように、評価の計算を行うクラスタ数の範囲とアルゴリズムを選択する処理である。
【００４２】
1103は、1102で指定したクラスタ数の範囲でクラスタ評価値を計算していき、最適なクラスタ数が求まると、自動的に最適なクラスタ数の位置に、デンドログラムを分割する平面を移動させる。
【００４３】
1104は、GUIによって分割位置を決定する処理であり、クラスタ数を指定したりマウス操作などで動的にデンドログラムを分割する平面を移動する処理である。
【００４４】
1105は、デンドログラムを分割する平面によって分割されたセルを色分けする処理である。
【図面の簡単な説明】
【００４５】
【図１】本発明のシステム構成例を示す図。
【図２】ＳＯＭの実行結果例（セルの形状が四角形）。
【図３】ＳＯＭの実行結果例（セルの形状が六角形）。
【図４】デンドログラムの実行結果例。
【図５】デンドログラムを三次元的に描画した図（セルの形状が四角形の場合）。
【図６】平面上のデンドログラムの分割位置を直線で決定した図。
【図７】最適なクラスタ数をクラスタ評価値から求めるイメージ図。
【図８】デンドログラムの分割位置を平面で決定した図（セルの形状が四角形の場合で、クラスタ数が2個）。
【図９】デンドログラムの分割位置を平面で決定した図（セルの形状が四角形の場合で、クラスタ数が３個）。
【図１０】全体のフローチャート。
【図１１】分割位置を決定するフローチャート。
【符号の説明】
【００４６】
101…ディスプレイ装置、102…キーボード、103…マウス、104…中央処理装置、105…ＳＯＭ実行部、106…デンドログラム実行部、107…クラスタリング結果評価部、108…クラスタリング結果表示部、109…外部記憶装置、110…クラスタリング用データ。
【図１】
2006163894.tif 000003
【図２】
2006163894.tif 000004
【図３】
2006163894.tif 000005
【図４】
2006163894.tif 000006
【図５】
2006163894.tif 000007
【図６】
2006163894.tif 000008
【図７】
2006163894.tif 000009
【図８】
2006163894.tif 000010
【図９】
2006163894.tif 000011
【図１０】
2006163894.tif 000012
【図１１】
2006163894.tif 000013