(57)【要約】【課題】主体が持つ素性群を表す特徴表現のベクトル同士の距離に基づくクラスタリングよりも、より正確なクラスタリング結果を得る。【解決手段】取得部１４０は、多数の主体について、その主体の各素性の値を示した生の特徴表現の情報を取得する。二部ネットワーク生成部１４２は、各主体及び各素性をそれぞれノードとし、主体に対応するノードとその主体が持つ素性に対応するノードとをリンクで結んだ二部ネットワークを生成する。クラスタリング計算部１４４は、この二部ネットワークを対象に、マルコフ連鎖のモジュール分解に基づく計算を実行することで、それらノードをクラスタリングする。【選択図】図１
2018142095.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
各主体が持つ各素性を表す入力データを取得する手段、
前記入力データに含まれる前記各主体及び前記各素性をそれぞれノードとし、前記主体に対応するノードと、その主体が持つ各素性に対応する各ノードと、をリンクで結んだ二部ネットワークを生成する生成手段、
前記二部ネットワークにおけるリンクを介するノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノード群のクラスタリングを行うクラスタリング手段、
として機能させるためのプログラム。
【請求項２】
前記コンピュータを、
前記クラスタリング手段による前記クラスタリングの結果を用いて、前記各主体につき、クラスタリングの観点でのその主体の特徴を表す主体クラスタ特徴データを生成する主体特徴生成手段、
として更に機能させるための請求項１に記載のプログラム。
【請求項３】
前記コンピュータを、
前記クラスタリング手段による前記クラスタリングの結果を用いて、前記各素性につき、クラスタリングの観点でのその素性の特徴を表す素性クラスタ特徴データを生成する素性特徴生成手段、
として更に機能させるための請求項１又は２に記載のプログラム。
【請求項４】
前記コンピュータを、
前記入力データに含まれない新たな主体について、前記新たな主体が持つ各素性を表すデータが入力された場合に、前記入力データに対する前記クラスタリングの結果を用いて前記素性特徴生成手段が生成した前記各素性の前記素性クラスタ特徴データを用いて、クラスタリングの観点での前記新たな主体の特徴を表す特徴データを生成する手段、
として更に機能させるための請求項３に記載のプログラム。
【請求項５】
前記クラスタリング手段は、前記確率過程における各ノードの初期値を、前記主体に対応するノード群の初期値の合計と前記素性に対応するノードの初期値の合計とが実質的に等しいという条件を満たすように設定し、設定した各ノードの初期値を用いて前記繰り返し計算を実行する、こと特徴とする請求項１〜４のいずれか１項に記載のプログラム。
【請求項６】
前記クラスタリング手段は、前記確率過程の繰り返し計算として、離散時間モデルではなく連続時間モデルを用いて計算を行う、ことを特徴とする請求項１〜４のいずれか１項に記載のプログラム。
【請求項７】
各主体が持つ各素性を表す入力データを取得する手段と、
前記入力データに含まれる前記各主体及び前記素性をそれぞれノードとし、前記主体に対応するノードと、その主体が持つ各素性に対応する各ノードと、をリンクで結んだ二部ネットワークを生成する生成手段と、
前記二部ネットワークにおけるリンクを介するノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノード群のクラスタリングを行うクラスタリング手段と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び情報処理装置に関する。
【背景技術】
【０００２】
主体（分析の対象）についての生データからその主体が持つ各素性の値を機械的に抽出し、それら各素性の値の組をその主体の特徴を表す特徴表現として用いることがよく行われている。例えば、文書の特徴表現として、その文書における各単語の出現頻度を表すベクトルを用いる等の例はよく知られている。
【０００３】
また、生データから得た主体の特徴表現をクラスタリングする分析手法もよく用いられる。従来のクラスタリング手法では、主体の生データから得た特徴表現をベクトルと見なし、ベクトル空間内での特徴表現ベクトル同士の距離に基づきクラスタリングを行うことが一般的である。
【０００４】
また発明者らは、特許文献１、２、３にて「マルコフ連鎖のモジュール分解」に基づいて、ネットワークから重なりと階層を持つクラスタ構造を検出する方法を提案した。マルコフ連鎖のモジュール分解に基づくクラスタリング（コミュニティ抽出）の計算では、ネットワークの各ノードが持つ確率がリンクを経由して他のリンクに遷移（ランダムウォーク）するというモデルで各ノードの確率の変化を繰り返し計算し、定常状態に達したときの情報に基づき、各ノードがどのクラスタに属するのかを判定した。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−１６８１２７号公報
【特許文献２】特開２０１６−０２９５２６号公報
【特許文献３】特開２０１６−２１８５３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特徴表現のベクトル同士の距離に基づくクラスタリングでは、ベクトルが含む成分（すなわち素性）同士に関係があってもその関係はクラスタリングに反映されないので、ベクトルベースのクラスタリングでは、主体のクラスタリングが正確に行われない場合がある。例えば、人が過去に購入した食品のリストをその人の特徴表現のベクトルとしてクラスタリングを行う場合、果物好きで果物を他種類の食品よりも多く購入している人が２人いたとしても、それら２人が購入した果物がまったく異なれば、それら２人は、果物好きとして同一クラスタに分類されるのではなく、別々のクラスタに分類されてしまう可能性がある。
【０００７】
本発明は、主体が持つ素性群を表す特徴表現のベクトル同士の距離に基づくクラスタリングよりも、より正確なクラスタリング結果を得ることができる方式を提供することを目的とする。
【課題を解決するための手段】
【０００８】
請求項１に係る発明は、コンピュータを、各主体が持つ各素性を表す入力データを取得する手段、前記入力データに含まれる前記各主体及び前記各素性をそれぞれノードとし、前記主体に対応するノードと、その主体が持つ各素性に対応する各ノードと、をリンクで結んだ二部ネットワークを生成する生成手段、前記二部ネットワークにおけるリンクを介するノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノード群のクラスタリングを行うクラスタリング手段、として機能させるためのプログラムである。
【０００９】
請求項２に係る発明は、前記コンピュータを、前記クラスタリング手段による前記クラスタリングの結果を用いて、前記各主体につき、クラスタリングの観点でのその主体の特徴を表す主体クラスタ特徴データを生成する主体特徴生成手段、として更に機能させるための請求項１に記載のプログラムである。
【００１０】
請求項３に係る発明は、前記コンピュータを、前記クラスタリング手段による前記クラスタリングの結果を用いて、前記各素性につき、クラスタリングの観点でのその素性の特徴を表す素性クラスタ特徴データを生成する素性特徴生成手段、として更に機能させるための請求項１又は２に記載のプログラムである。
【００１１】
請求項４に係る発明は、前記コンピュータを、前記入力データに含まれない新たな主体について、前記新たな主体が持つ各素性を表すデータが入力された場合に、前記入力データに対する前記クラスタリングの結果を用いて前記素性特徴生成手段が生成した前記各素性の前記素性クラスタ特徴データを用いて、クラスタリングの観点での前記新たな主体の特徴を表す特徴データを生成する手段、として更に機能させるための請求項３に記載のプログラムである。
【００１２】
請求項５に係る発明は、前記クラスタリング手段は、前記確率過程における各ノードの初期値を、前記主体に対応するノード群の初期値の合計と前記素性に対応するノードの初期値の合計とが実質的に等しいという条件を満たすように設定し、設定した各ノードの初期値を用いて前記繰り返し計算を実行する、こと特徴とする請求項１〜４のいずれか１項に記載のプログラムである。
【００１３】
請求項６に係る発明は、前記クラスタリング手段は、前記確率過程の繰り返し計算として、離散時間モデルではなく連続時間モデルを用いて計算を行う、ことを特徴とする請求項１〜４のいずれか１項に記載のプログラムである。
【００１４】
請求項７に係る発明は、各主体が持つ各素性を表す入力データを取得する手段と、前記入力データに含まれる前記各主体及び前記素性をそれぞれノードとし、前記主体に対応するノードと、その主体が持つ各素性に対応する各ノードと、をリンクで結んだ二部ネットワークを生成する生成手段と、前記二部ネットワークにおけるリンクを介するノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノード群のクラスタリングを行うクラスタリング手段と、を有する情報処理装置である。
【発明の効果】
【００１５】
請求項１又は７に係る発明によれば、主体が持つ素性群を表す特徴表現のベクトル同士の距離に基づくクラスタリングよりも、より正確なクラスタリング結果を得ることができる。
【００１６】
請求項２に係る発明によれば、クラスタリングの観点での主体の新たな特徴を示すデータを生成することができる。
【００１７】
請求項３に係る発明によれば、クラスタリングの観点で素性の特徴を示すデータを生成することができる。
【００１８】
請求項４に係る発明によれば、新たな主体についてのデータが入力された場合に、その主体についてのデータを二部ネットワークに反映させて確率過程の繰り返し計算を行うよりも少ない計算負荷で、その新たな主体についての特徴データを求めることができる。
【００１９】
請求項５に係る発明によれば、主体に対応するノード群と素性に対応するノード群との間で確率の値が交互に行き来することによる繰り返し計算の収束のしにくさを、主体のノード群と素性のノード群との初期値を単にランダムに決める場合よりも、緩和することができる。
【００２０】
請求項６に係る発明によれば、主体に対応するノード群と素性に対応するノード群との間で確率の値が交互に行き来することによる繰り返し計算の収束のしにくさを、離散時間モデルを用いる場合よりも、緩和することができる。
【図面の簡単な説明】
【００２１】
【図１】実施形態の装置構成の例を示す図である。
【図２】生データから求められた生の特徴表現の例を示す図である。
【図３】主体と素性の二部ネットワークの例を示す図である。
【図４】クラスタリング計算部が実行する処理の例を示す図である。
【図５】主体についてのクラスタリング結果の一例を示す図である。
【図６】特徴表現生成部が生成する特徴表現の例を示す図である。
【図７】確率スイッチの問題を説明するための図である。
【図８】変形例の装置構成の例を示す図である。
【図９】素性特徴記憶部に記憶される素性の特徴表現の例を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、図面を参照しながら説明する。
【００２３】
図１は、本発明の実施形態に係る情報処理装置１の構成図である。情報処理装置１は、記憶部１０、入力部１２、特徴表現処理部１４、分析部１６を含む。
【００２４】
記憶部１０は、例えばRAM（Random Access Memory）やROM（Read Only Memory）を含む。記憶部１０は、特徴表現処理部１４が実行するプログラムを格納するとともに、特徴表現処理部１４のワークメモリとしても機能する。なお、記憶部１０に格納される特徴表現処理部１４が実行するプログラムは、電気通信回線を介して提供されるものであってもよいし、半導体記憶素子等のコンピュータで読み取り可能な情報記憶媒体に格納されて提供されるものであってもよい。
【００２５】
本実施形態に係る情報処理装置１の記憶部１０には、生データから抽出された生の特徴表現のデータ（以下「生表現」と呼ぶ）が記憶される。
【００２６】
生データは、分析の対象となる個々の主体の特徴となる素性（属性）の情報を含んだデータであり、データの内容やデータ形式等に制限はない。例えば、電子文書（以下単に文書と呼ぶ）等のテクスト型データは生データの一例である。この場合、例えば、個々の文書を分析対象の主体とし、その文書が含む個々の単語をその主体の個々の素性と捉える。また、各人の購買履歴を記録したデータベースのような関係型データやコンテクスト型データも生データの一例である。購買履歴データベースの場合、各人がそれぞれ分析対象の主体であり、そのデータベースに記録されたその主体が購買した各商品がその主体が持つ個々の素性である。なお、生データから得られるどの情報項目を主体及びその主体の素性とするかは、分析目的に応じて適宜定める事項であり、以上に説明したのはあくまで一例に過ぎない。
【００２７】
生表現は、生データから抽出された主体及び素性の対応関係を示す情報である。図２に、文書群から抽出した生表現の一例を示す。図２の生表現は、主体である個々の文書の文書ＩＤ（識別情報）に対応付けて、素性である個々の単語がそれぞれその文書に含まれる（値「１」）か含まれない（値「０」）かを表している。これは、個々の主体（文書）の特徴を各素性（単語）の値からなるベクトルで表現したものである。同様に、購買履歴データから得られる生表現の例としては、例えば、人のＩＤに対して、各商品をその人が購入したか否かを示すベクトルを対応付けたデータを用いてもよい。
【００２８】
なお、図２の例において素性の値として、主体が当該素性を含むか否かの二値データを用いたが、これは一例に過ぎない。素性の値の定め方は、分析の目的に応じて適宜定める事項である。例えば文書の素性の値として、図２のような二値データを用いる代わりに、その素性（単語）がその文書に現れる頻度に対応する値を用いてもよい。
【００２９】
生データからの生表現の生成は従来技術を用いて可能であり、本実施形態では、生成された生表現が記憶部１０に用意されているものとする。もちろん、分析を行う際に、本実施形態の装置又は別の装置が生データから生表現を生成してもよい。
【００３０】
入力部１２は、例えばキーボードやマウス等であり、ユーザの指示を特徴表現処理部１４に伝達する。
【００３１】
特徴表現処理部１４は、例えばＣＰＵ（Central Processing Unit）を含んでおり、記憶部１０に格納されるプログラムを実行することにより、生表現から各主体の新たな特徴表現を生成するための処理を実行する。この新たな特徴表現の生成は、生表現に対するクラスタリングにより行う。すなわち、生表現が表す主体をクラスタリングし、これにより得られる各主体の所属するクラスタの情報を、その主体の新たな特徴とする。本実施形態では、生表現から生成したネットワークに対して、特許文献１〜３等で提案したネットワークのモジュール分解によるクラスタリングを行うことで、主体のクラスタリングを実現する（詳細は後述）。
【００３２】
分析部１６は、特徴表現処理部１４が生成した特徴表現を用いて、主体の分析を行う。分析部１６が行う分析は、従来の手法でよいので、説明は省略する。
【００３３】
特徴表現処理部１４について更に詳しく説明する。
【００３４】
従来のクラスタリングは、生表現が表す各主体の特徴、すなわち素性の値のベクトルを、ベクトル空間内での当該主体の位置とし、互いの位置の近さにより主体群を複数のクラスタに分けた。しかし、このような特徴ベクトル同士の距離に基づくクラスタリングは、前述の通り、そのベクトルが持つ個々の素性同士の関係がクラスタリングに反映されない。
【００３５】
また、生表現は、非常にスパース（疎な）であることが多く、非常にスパースなベクトルをベクトルの距離に基づいて正しくクラスタリングすることは難しい。例えば、twitter（登録商標）に投稿されたツイートを分析する場合、それらツイート群に含まれる単語は非常に多様（例えば数千から数万語）であり、それら多様な単語をベクトルの成分（素性）とした場合、個々のツイートにはそれら単語のうちの限られたもの（高々数十語）しか含まれない。したがって、個々のツイートを表す特徴表現のベクトルは、そのツイートが含む限られた各単語についてのみ０より大きい値（例えば１）を持ち、その他の大多数の単語については値が０である、非常にスパースなものとなる。
【００３６】
また、従来のベクトルの距離に基づくクラスタリングは、ベクトル間の距離に依存しすぎているといえる。すなわち、ベクトル同士の近さは、ベクトルの生成等のためにどのような前処理を行うかによって変わるので、距離のみに依存したクラスタリングでは信頼性の高い結果を得ることができない。
【００３７】
そこで、特徴表現処理部１４は、生表現に対してベクトルの距離に基づくクラスタリングを行う代わりに、生表現から主体及び素性をそれぞれノードとする二部ネットワークを構成し、その二部ネットワークに対して、ネットワークのモジュール分解によるクラスタリングを行う。
【００３８】
特徴表現処理部１４は、機能的に、取得部１４０、二部ネットワーク生成部１４２、クラスタリング計算部１４４及び特徴表現生成部１４６を含む。
【００３９】
取得部１４０は、記憶部１０から生表現のデータを取得する。
【００４０】
二部ネットワーク生成部１４２は、その生表現のデータから、主体と素性をそれぞれノードとする二部ネットワークを生成する。二部ネットワークとは、二部グラフとも呼ばれ、ノードの集合が２つの部分集合に分割されており、同じ部分集合内のノード同士の間にリンクがないネットワーク（グラフ）のことである。二部ネットワーク生成部１４２は、主体のノード群と素性のノード群とを別々の部分集合とする二部ネットワークを生成する。
【００４１】
図２に例示した生表現データから生成される二部ネットワークを図３に例示する。図３では、正方形が主体である文書を示すノードであり、円形が素性である単語を示すノードである。そして、主体のノードと素性のノードを結ぶ直線分がリンクである。この二部ネットワークは、例えば、図２に例示する生表現において、値が１である文書と単語のノード間をリンクで結ぶことにより生成される。この二部ネットワークでは、値が０である文書と単語のノード間にはリンクがない。
【００４２】
なお、生表現が持つ素性の値が図２のように二値の値ではなく、例えば単語の出現頻度のように正の多値の値である場合でも、素性が正値を持つ主体と素性のノード同士をリンクで結び、素性の値が０である主体と素性のノード間にはリンクを設けないことで、二部ネットワークを構成すればよい。この場合、多値の値は、リンクの強さを示す情報として利用してもよい。リンクの強さは、例えば、後述するクラスタリングの計算において、そのリンクを介した遷移の確率（すなわち後述の遷移確率行列Ｔnm）に反映させてもよい（リンクの強さが大きいほど、そのリンクについての遷移確率の値を高くする等）。
【００４３】
クラスタリング計算部１４４は、二部ネットワーク生成部１４２が生成した二部ネットワークを対象として、ネットワークのモジュール分解の手法によるクラスタリングの計算を行う。このネットワークのモジュール分解は、次の式１で表現される。
【数１】
2018142095.tif 000003
【００４４】
式１において、ｐ（ｎ）はノードｎが持つ確率（そのノードにランダムウォーカーが存在する確率）である。またπkは、クラスタ（コミュニティ）ｋの事前確率であり、そのクラスタｋの重要度を示す。πkのｋについての総和は１である。またｐ（ｎ｜ｋ）は、クラスタｋにおけるノードｎの確率である。Ｋはクラスタｋの総数である。式１は、ノードｎの確率ｐ（ｎ）が、各クラスタｋにおける当該ノードｎの確率ｐ（ｎ｜ｋ）の組み合わせに分解できることを表している。
【００４５】
クラスタリング計算部１４４が用いる具体的な計算手法は、例えば、特許文献１〜３に例示されるものと同様でよい。以下では、具体的な計算処理として、特許文献２及び３に記載された方式と同様の考え方に基づく処理の例を、図４を参照して説明する。
【００４６】
図４の手順では、まずクラスタリング計算部１４４は、二部ネットワーク生成部１４２が生成した二部ネットワークについての遷移確率行列Ｔnmを生成する（Ｓ１０）。ここで、遷移確率行列Ｔnmは、ネットワーク内のノードｍからノードｎへリンクを辿ってエージェント（言い換えれば、ノードｍが持つ確率値）が遷移（ランダムウォーク）する確率（すなわ遷移確率）を行列として表現したものである。例えばエージェントがノードから出る１以上のリンクを等確率で選択するとみなした場合、遷移確率行列は、ネットワーク情報が示すネットワークの構造、すなわちノード間がどのようにリンクされているか、のみに依存する。もちろん、ネットワークの構造以外の情報（例えばノードの重要度やリンクの強さ）を考慮に入れて遷移確率行列Ｔnmを求めることもできるが、この場合も遷移確率行列Ｔnmはネットワーク情報に基づく点は同様である。なお、二部ネットワークの場合、同じ部分集合に属するノード同士の間にはリンクがないので、遷移確率行列Ｔnmにおける同じ部分集合内のノード同士の間の遷移確率は０となる。遷移確率行列については、更に特許文献１〜３も参照されたい。
【００４７】
次に、クラスタリング計算部１４４は、定常リンク確率を計算する（Ｓ１２）。
【００４８】
この計算では、まずＳ１０で求められた二部ネットワークの遷移確率行列Ｔnmを用いて、その二部ネットワークにおける確率遷移（ランダムウォーク）の定常状態において各ノードが持つ確率（定常状態のノード確率）を計算する。この計算では、例えば次の式２の計算を定常状態となるまで繰り返す。
【数２】
2018142095.tif 000004
【００４９】
式２において、ｐt（ｎ）は、離散的な時刻ｔにおいてノードｎが持つ確率である。式２を繰り返し計算して定常状態となったときのｐt（ｎ）が、ノードｎの定常状態でのノード確率ｐstead（ｎ）である。
【００５０】
次にクラスタリング計算部１４４は、各ノードｎの定常状態でのノード確率ｐstead（ｎ）から、定常状態でのリンク確率を次の式３に従って計算する。
【数３】
2018142095.tif 000005
【００５１】
リンク確率とは、ノード確率ｐt（ｎ）に対してそのノードから出るリンクｌ（エル）の遷移確率を乗じたものである。リンクｌについての定常状態のリンク確率（式３の左辺）は、そのリンクｌの起点のノードの定常状態のノード確率に対して、遷移確率行列Ｔnmに含まれる、そのリンクｌの起点ノードから終点ノードへの遷移確率を乗じたものである。
【００５２】
特許文献２及び３では、Ｄ回の仮想的な観測で得られる観測データである通過情報τn (d)（ｄは１からＤまでの整数。ｎはノードの識別番号）を学習データとして用いた。これに対して以下に説明する例では、観測回数Ｄが十分大きい(ノード数Ｎよりもはるかに多い)という妥当な想定の下、τn(d)の代わりに実リンクｌに関する通過情報
【数４】
2018142095.tif 000006
を用いる。ここでｎはノードの識別番号である。またδはクロネッカーのδである。すなわち、式４が定義するノードｎの実リンクｌに関する通過情報(学習データ)は、そのノードｎがその実リンクｌの終点ノード（terminal end of link l）又は起点ノード（initial end of link l）に一致する場合に値が１となり、それ以外の場合は値が０となる。クラスタリング計算部１４４は、二部ネットワークの情報からこのような通過情報を学習用のデータとして生成する。生成した通過情報は、後述するＥＭアルゴリズムの計算で用いる。
【００５３】
また、この例では、特許文献２等での仮想的な観測の各回ｄにおける複数のクラスタ(成分)全体に対するクラスタｋが占める割合γ(d)（ｋ）の代わりに、実リンクｌに関して後述する式（ＩＩＩ）で定義される割合γlk（チルダ付き）を用いる。
【００５４】
また、このような観測回数ｄから実リンクの番号ｌへの置換えにより、関数の総和の表現は以下のように置き換えられる。
【数５】
2018142095.tif 000007
【００５５】
後述する式（Ｉ）の右辺第２項は、特許文献２等に説明した同様の式に対してこのような置き換えを行ったものである。
【００５６】
図４の手順の説明に戻ると、次にクラスタリング計算部１４４は、確率ｐt（ｎ｜ｋ）及び重要度πknew、及び割合γlkの初期値を仮決めし、繰返し回数のカウンタgの値を０に初期化する（Ｓ１４）。確率ｐt（ｎ｜ｋ）は、クラスタｋにおけるノードｎの確率である。また、重要度πknewは、クラスタｋの重要度である。またγlkは、リンクｌにおける、複数のクラスタ全体に対するクラスタｋが占める割合である。
【００５７】
次にクラスタリング計算部１４４は、次に示す式（Ｉ），（ＩＩ），（ＩＩＩ）を用いてＥＭ（Expectation and Maximization）アルゴリズムの繰り返し計算を行う。
【数６】
2018142095.tif 000008
【００５８】
すなわちまずクラスタリング計算部１４４は、割合γlkを、式（ＩＩＩ）を用いて計算する（Ｓ１６）（ＥＭアルゴリズムのＥステップ）。この計算の最初の繰り返しでは、Ｓ１４で仮決めした初期値を用いる。
【００５９】
次にクラスタリング計算部１４４は、現在の確率ｐt（ｎ｜ｋ）及び重要度πknewを一時刻前の値ｐt-1（ｎ｜ｋ）及び重要度πkoldとする置き換えを行う（Ｓ１８）。そして、式（Ｉ）及び（ＩＩ）に従って、確率ｐt（ｎ｜ｋ）及び重要度πknewを計算する（Ｓ２０）（ＥＭアルゴリズムのＭステップ）。より詳しくは、Ｓ２０では、まず式（ＩＩ）に従って新たな重要度πknewを計算し、その後、この新たな重要度を用いて式（Ｉ）の計算を行うことで、確率ｐt（ｎ｜ｋ）を求める。ここでαは、正の実数であって、クラスタの大きさを定めるパラメータであり、予め定めた値を用いればよい。
【００６０】
そして、クラスタリング計算部１４４は、繰り返し計算の回数のカウンタｇを１インクリメントし（Ｓ２２）、そのカウンタｇが予め定めた値Ｇに達したかどうかを判定し（Ｓ２４）、達していなければＳ１６〜Ｓ２２の処理を繰り返す。値Ｇは、本実施形態の計算手法においてＳ１６〜Ｓ２１の計算が収束するのに必要な繰返し回数であり、実験や経験的知識等により予め定めておく。
【００６１】
Ｓ２４で、カウンタｇが値Ｇに達したと判定した場合は、繰り返し計算が収束したものとして、処理を終了する。
【００６２】
Ｓ２４の判定結果がＹｅｓとなった後、クラスタリング計算部１４４は、次式に従ってノードｎのクラスタｋへの所属度γ（ｋ｜ｎ）を計算する。
【数７】
2018142095.tif 000009
この式のうちπk及びｐ（ｎ｜ｋ）は、ＥＭアルゴリズムの計算（Ｓ１６〜Ｓ２０）の繰り返しにより最終的に求められたπknew及びｐt（ｎ｜ｋ）である。この式は、πk及びｐ（ｎ｜ｋ）から、ベイズの定理により、ノードｎがクラスタｋに所属する度合い（所属度）を示すγ（ｋ｜ｎ）を計算する式である。
クラスタリング計算部１４４は、このようにして求めた所属度γ（ｋ｜ｎ）をクラスタリング結果として出力する。所属度γ（ｋ｜ｎ）は、ノードｎのソフトクラスタリングの結果を表す情報である。
【００６３】
また、別の例として、クラスタリング計算部１４４は、その所属度γ（ｋ｜ｎ）を予め定めた閾値で二値化したものをクラスタリング結果として出力してもよい。このクラスタリング結果は、ノードｎが、所属度γ（ｋ｜ｎ）の値が閾値以上となるクラスタｋに対して所属する（二値化結果の値が１）ことを表す。定めた閾値の値によっては、ノードｎについて二値化結果が１となるクラスタｋが複数ある場合もあるが、これは一種のソフトクラスタリングの結果とみなせる。このような二値化したクラスタリング結果の例を図５に示す。この例では、例えば、主体ＩＤ＝１の主体は、クラスタＩＤ＝Ｃ２、Ｃ４の２つのクラスタに属すると判定されている。主体ＩＤはノードの番号ｎに対応し、クラスタＩＤはクラスタの番号ｋに対応する。
【００６４】
またクラスタリング計算部１４４は、繰り返し計算で用いたｋ＝１〜Ｋ（クラスタ総数）のＫ個のクラスタ全部についてのクラスタリング結果のうち、重要ないくつかのクラスタについてのクラスタリング結果のみを抽出し、最終的なクラスタリング結果として出力してもよい。重要なクラスタは、重要度πkに基づき判定すればよい。例えば、繰り返し計算が収束したときに得られた最終的な重要度πkが予め定めた閾値以上となるクラスタｋを重要なクラスタとして抽出したり、その重要度πkが上位から所定順位以内にあるクラスタｋを重要なクラスタとして抽出したりすればよい。
【００６５】
なお、Ｓ２８における収束の判定では、図４に例示した方法の代わりに、特許文献１〜３で説明したものと同様の、繰り返し毎の評価値Ｑｔの変化量が微小な値（閾値未満）となったときに、繰り返し計算が収束したと判定してもよい。
【００６６】
図４の手順は、特許文献２及び３の計算手法と同様の手法を用いたものであったが、二部ネットワークのクラスタリングに特許文献１の計算手法と同様の手法を用いてもよい。また、特許文献１〜３の手法はいずれもネットワーク上でのノード間の確率の遷移を離散的なマルコフ連鎖として取り扱うものであったが、離散的なマルコフ連鎖の代わりに、連続時間マスター方程式等のような連続的なマルコフ過程をベースとした計算手法をもちいてもよい。
【００６７】
このようにしてクラスタリング計算部１４４によるクラスタリングが完了すると、そのクラスタリング結果を用いて特徴表現生成部１４６が、各主体についての新たな特徴表現を生成する。
【００６８】
特徴表現生成部１４６は、例えば、クラスタリング計算部１４４から得たクラスタリング結果における個々の主体に関する情報を、その主体の新たな特徴表現として生成する。この例では、例えば、図５のクラスタリング結果に応じて、主体ＩＤ＝１の主体の新たな特徴表現をベクトル（０，１，０，１，・・・，０）とする（ベクトルの成分数はＫ個）。なお、クラスタリング結果が、クラスタに属するか否かの二値ではなく、クラスタに属する度合い（例えば前述の所属度γ（ｋ｜ｎ））の数値（０以上１以下の実数）である場合も同様に、そのクラスタリング結果における個々の主体に関する情報を、その主体の新たな特徴表現として用いてよい。
【００６９】
また、別の例では、特徴表現生成部１４６は、図６に例示する結合表現を、主体についての新たな特徴表現として生成してもよい。この結合表現は、生表現と追加表現を結合したものである。このうちの追加表現は、クラスタリング計算部１４４から得たクラスタリング結果における個々の主体に関する情報である。
【００７０】
特徴表現生成部１４６が生成した各主体についての新たな特徴表現のデータは分析部１６に供給される。分析部１６は、それら各主体の特徴表現を用いて、個々の主体やそれら主体同士の関係の分析を実行する。
【００７１】
なお、クラスタリング計算部１４４の計算によれば、素性についてもクラスタリング結果が得られる。そこで特徴表現生成部１４６は、素性のクラスタリング結果から、素性の特徴表現を生成してもよい。生成する素性の特徴表現は、例えば、主体の追加表現と同様、素性がそれぞれ各クラスタに属するか否か、又は各クラスタにそれぞれどの程度属するか（まったく属さない場合は値が０）、を示す情報（例えばベクトル表現）である。
【００７２】
以上に説明したように、本実施形態では、与えられた生表現から、主体及び素性をそれぞれノードした二部ネットワークを構成し、この二部ネットワークに対してノード間の確率の遷移の過程の繰り返し計算を行うことで、それらノードのクラスタリングを行う。
【００７３】
もともとの生表現に素性同士の関連を示すデータは明示的には含まれないので、二部ネットワークには素性のノード同士を直接結ぶリンクはない。しかし、素性のノードは、その素性を持つ主体のノードとリンクでつながっており、その主体のノードを介して、その主体が持つ他の素性のノードと間接的に繋がっている。互いに関連する主体同士は共通の素性を持っている蓋然性が高く、逆に互いに関連する素性同士は共通の主体に属している蓋然性が高い。このため、本来関連性の強い素性のノード同士は、多くの主体ノードを介して２リンクの距離で接続されている蓋然性が高く、それらノード同士の間に直接のリンクがなくても、二部ネットワークのクラスタリングにより同じクラスタに分類されやすい。したがって、関連性の強い主体同士が共通の素性を持たない場合でも、クラスタリングの計算において、その素性と同じクラスタに分類される蓋然性が高い他の素性を介する確率の遷移により、それら主体同士の関連度合いが顕在化され、それら主体同士が同じクラスタに分類されやすくなる。このように、本実施形態の手法では、ベクトルの距離に基づくクラスタリング手法では計算に入れることができなかった素性間の関連性を、クラスタリングに反映させることが可能になる。
【００７４】
また、上述した主体と素性の二部ネットワークを構成し、これをクラスタリングするという方法によれば、上述のメカニズムにより、主体とその主体が持たない素性との関連性もクラスタリング結果に反映される。したがって、生表現自体がスパースであっても、ベクトル同士の距離に基づくクラスタリングより、妥当性の高いクラスタリング結果が得られる。
【００７５】
また、上述した主体と素性の二部ネットワークのクラスタリングは、ベクトル間の距離を用いるものではないので、クラスタリング結果はベクトル間の距離に依存しすぎることはない。
【００７６】
＜確率スイッチに対する対処＞
さて、二部ネットワークにマルコフ連鎖の繰り返し計算では、主体のノードが持つ確率は次のステップで必ず素性のノードに遷移し、素性のノードが持つ確率は次のステップで必ず主体のノードに移動する。このため、計算の繰り返しステップ毎に主体のノード群と素性のノード群との間で確率が行ったり来たりすることとなり、計算が非常に収束しづらい（あるいは収束しない）。
【００７７】
例えば、図７に示す例は、初期の時点で二部ネットワークの主体ノードの部分集合ＳAに属するノードが持つ確率の合計Ｐ（ＳA）が０．９９であり、素性ノードの部分集合ＳBに属するノードが持つ確率の合計Ｐ（ＳB）が０．０１である場合を示している。この初状態からマルコフ連鎖の計算を１ステップ進めると、Ｐ（ＳA）＝０．０１、Ｐ（ＳB）＝０．９９となり、更に１ステップ進めると、Ｐ（ＳA）＝０．９９、Ｐ（ＳB）＝０．０１となる。以降、部分集合毎の確率の合計値が、２つの部分集合の間で行ったり来たりする。個々のノードの確率は、リンクされた別のノードからの確率の遷移に応じて個別に変化するものの、部分集合毎の合計値はステップ毎に大きく偏った値となり、その偏りが保存される。この偏りが、個々のノードの確率が収束することを妨げる。
【００７８】
このような問題を、確率スイッチと呼ぶこととする。以下では、この確率スイッチの問題を解決するための手法を提案する。
【００７９】
第１の手法は、マルコフ連鎖の繰り返し演算に用いるノードの確率の初期値を、主体ノードの確率の合計値と、素性ノードの確率の合計値とが等しくなるように設定することである。
【００８０】
より具体的には、例えば、クラスタリング計算部１４４は、上述の図３の手順のＳ１２におけるノード確率の定常状態の計算（式２の繰り返し）における各ノードｎの確率ｐt（ｎ）の初期値ｐ0（ｎ）を、主体ノード群の初期値の合計と、素性ノード群の初期値の合計とが等しい（すなわち合計値が共に０．５となる）という拘束条件を満たすように決定する。
【００８１】
また別の例では、クラスタリング計算部１４４は、図４の手順のＳ１４で、確率ｐt（ｎ｜ｋ）の初期値を、主体ノード群についての合計と素性ノード群についての合計が等しくなるという拘束条件の下で仮決めする。
【００８２】
また、各ノードｎの確率ｐt（ｎ）の初期値と、確率ｐt（ｎ｜ｋ）の初期値の両方について、主体ノード群についての合計と素性ノード群についての合計が等しくなるという拘束条件に従って決めてもよい。
【００８３】
このように初期値を設定することで、主体ノードの部分集合と素性ノードの部分集合との間に確率の偏りがなくなるので、上述した確率スイッチによる収束の妨げが解消又は緩和される。
【００８４】
ここでは、主体ノードの確率初期値の合計と、素性ノードの確率初期値の合計とが等しくなるように初期設定を行うとしたが、それら合計同士が完全に等しくなくてもよく、それら合計同士が実質的に等しいとみなせる程度に近ければ足りる。ここで「実質的に等しい」とは、二部ネットワークについての上述のＥＭアルゴリズムの計算が許容範囲の繰返し回数以内で収束する程度に、主体ノードの確率初期値の合計と素性ノードの確率初期値の合計との差が小さいことを意味する。
【００８５】
確率スイッチの問題に対処する第２の手法は、クラスタリングの計算において、時間的に離散的なマルコフ連鎖のモデルの代わりに、時間的に連続的なマルコフ過程のモデルに基づく計算を用いることである。連続的なマルコフ過程の計算モデルの例には、例えば連続時間マスター方程式がある。
【００８６】
連続時間マスター方程式を用いた場合のノードｎの確率の時間変化は、次の式５により表される。
【数８】
2018142095.tif 000010
【００８７】
この式５から次の式６が得られる。
【数９】
2018142095.tif 000011
【００８８】
ここでΔｔは、０より大きく１より小さい微小時間である。なお、式６においてΔｔ＝１とすると、上述の離散的なマルコフ連鎖の場合の式２と同じ式となる。
【００８９】
この式６において、次式に示すディリクレ分布を想定する。
【数１０】
2018142095.tif 000012
【００９０】
この場合、ＥＭアルゴリズムの計算式（Ｉ’）〜（ＩＩＩ’）は次のようになる。
【数１１】
2018142095.tif 000013
【００９１】
式中のγ（ｋ｜ｌ）及びτ（ｎ｜ｌ）は、上述の（Ｉ）式におけるγlk及びτn(l)にそれぞれ対応する。
【００９２】
クラスタリング計算部１４４は、図４の処理手順のＳ１６及びＳ２０において、上述した式（Ｉ’）〜（ＩＩＩ’）を用いた計算を行い、この計算をＧ回繰り返す。
【００９３】
上述の離散マルコフ連鎖の例（式（Ｉ）〜（ＩＩＩ））では、時間間隔Δｔ＝１ごとに、すべてのノードが持つ確率が一斉に遷移するために、上述の確率スイッチの問題が生じた。これに対してこの連続時間マスター方程式に基づく計算（式（Ｉ’）〜（ＩＩＩ’））では、時間間隔１の間にすべてのノードの確率が遷移するものの、全ノードの確率が同じタイミングで一斉に遷移するのではなく、微小な時間間隔Δｔごとばらばらに遷移する。したがって、上述した確率スイッチの問題は解消又は緩和される。
＜新たな生データからの主体の特徴表現の簡易的な計算＞
【００９４】
以上に説明した二部ネットワークのクラスタリング及びこれに基づく特徴表現の生成は、マルコフ連鎖等の繰り返し計算を行う必要があるため、計算のために長い時間がかかる。したがって、いったんクラスタリングの結果が得られた後、新たな生データ（あるいはこれに基づく生表現）が追加される度にその生データを二部ネットワークに組み込んでクラスタリングを行うのでは、計算に多大の時間がかかってしまう。そこで、以下では、いったん得られたクラスタリングの結果を利用して、その後に追加された生データに対する特徴表現を簡易的に計算する変形例を示す。
【００９５】
図８に、この変形例の情報処理装置１の構成を例示する。この変形例の情報処理装置１では、特徴表現処理部１４に素性特徴記憶部１５０及び特徴表現簡易計算部１５２の機能が追加されている。また特徴表現生成部１４６は、主体特徴生成部１４７及び素性特徴生成部１４８の機能を備える。その他の点は、図１に示した上記実施形態の情報処理装置１と同様である。
【００９６】
主体特徴生成部１４７は、クラスタリング結果における個々の主体に関する情報（例えば図５に例示したもの）を、クラスタに関する主体の特徴表現として生成する。生成する特徴表現は、図６に例示した追加表現に相当する。特徴表現生成部１４６は、この追加表現を、生表現とは異なる主体の新たな特徴表現として出力してもよいし、生表現と結合して結合表現（図６参照）を生成し、この結合表現を主体の新たな特徴表現として出力してもよい。
【００９７】
素性特徴生成部１４８は、クラスタリング計算部１４４による各素性のクラスタリング結果から、各素性について、その素性の特徴表現を生成する。この特徴表現は、主体の追加表現（図６参照）と同様、素性がそれぞれ各クラスタに属するか否か、又は各クラスタにそれぞれどの程度属するか（まったく属さない場合は値が０）、を示す情報（例えばベクトル表現）であってよい。
【００９８】
素性特徴記憶部１５０は、素性特徴生成部１４８が生成した各素性の特徴表現のデータを記憶する。ここで、素性特徴記憶部１５０には、大量の生表現のデータからクラスタリング計算部１４４の上述のＥＭアルゴリズムによる学習により求められた各素性の特徴表現が既に記憶されているものとする。
【００９９】
特徴表現簡易計算部１５２は、その学習の後に新たに１以上の主体に関する生表現が情報処理装置１に入力された場合に、この情報処理装置１に新たに入力された生表現に含まれる主体についての新たな特徴表現を、素性特徴記憶部１５０に記憶された素性の特徴表現を用いて、それら各主体についての新たな特徴表現を計算する。
【０１００】
特徴表現簡易計算部１５２が行う計算は、次の式７に基づく。
【数１２】
2018142095.tif 000014
【０１０１】
ここで、τは主体の生表現であり、ωは学習により求められた素性の特徴表現である。この式の左辺は、主体の生表現がベクトルτであるという条件の下でのクラスタｋの確率（条件付き確率）を示す。この条件付き確率ｐ（ｋ｜τ）は、主体τがクラスタｋに属する度合いと捉えてよく、上述した実施形態でのノードｎ（主体τに対応）がクラスタｋに属する度合いを示す所属度γ（ｋ｜ｎ）と実質的に等しい。この変形例ではこれを主体τのクラスタリング結果に基づく特徴表現とする。式７は、その条件付き確率ｐ（ｋ｜τ）が、素性の生表現がベクトルωであるという条件の下でのクラスタｋの確率ｐ（ｋ｜ω）と、主体の生表現がベクトルτであるという条件の下での素性ωの確率ｐ（ω｜τ）と、の積をωについて総和したものと実質的に等しいことを示している。このうちｐ（ｋ｜ω）は、素性ωがクラスタｋに属する度合いと捉えてよく、これは素性ωのクラスタリング結果に基づく特徴表現であり、この値として素性特徴記憶部１５０に記憶された各素性の特徴表現が利用可能である。またｐ（ω｜τ）は、主体τが持つ各素性ωの値を、合計が１になるように規格化することで求めればよい。
【０１０２】
以下、具体例を用いて説明する。例えば、主体τの生表現が次の式８で表される場合を考える。
【数１３】
2018142095.tif 000015
【０１０３】
この主体τの生表現のベクトルを規格化することで、上述の式９に示すように確率ｐ（ω｜τ）が求められる。
【０１０４】
ここで、主体τの生表現のベクトルの３，６，８番目の成分に対応する素性ω3、ω6、ω8の特徴表現（素性特徴記憶部１５０に記憶されたもの）が次に示すものであったとする。これら特徴表現は、式７における確率ｐ（ｋ｜ω）に対応する。
【数１４】
2018142095.tif 000016
【０１０５】
この場合、式７より、主体τの特徴表現ｐ（ｋ｜τ）は、ｐ（ｋ｜ω）とｐ（ω｜τ）の積のωについての総和であり、次のように計算される。
【数１５】
2018142095.tif 000017
【０１０６】
以上説明したように、この変形例によれば、学習の結果求められた素性の特徴表現を用いることで、その学習の後に入力された生表現が表す主体の新たな特徴表現（クラスタに関する特徴表現）が生成される。
【０１０７】
以上、本発明の実施形態を説明した。以上に例示した情報処理装置１は、コンピュータに上述の各機能を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、フラッシュメモリやＳＳＤ（ソリッドステートドライブ）、ＨＤＤ（ハードディスクドライブ）や等の固定記憶装置を制御するコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカルエリアネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバス等を介して接続された回路構成を有する。それら各機能の処理内容が記述されたプログラムがネットワーク等の経由でフラッシュメモリ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。
【符号の説明】
【０１０８】
１  情報処理装置、１０  記憶部、１２  入力部、１４  特徴表現処理部、１６  分析部、１４０  取得部、１４２  二部ネットワーク生成部、１４４  クラスタリング計算部、１４６  特徴表現生成部、１４７  主体特徴生成部、１４８  素性特徴生成部、１５０  素性特徴記憶部、１５２  特徴表現簡易計算部。
【図１】
2018142095.tif 000018
【図２】
2018142095.tif 000019
【図３】
2018142095.tif 000020
【図４】
2018142095.tif 000021
【図５】
2018142095.tif 000022
【図６】
2018142095.tif 000023
【図７】
2018142095.tif 000024
【図８】
2018142095.tif 000025
【図９】
2018142095.tif 000026