JP2020042488A - 情報処理装置及びプログラム - Google Patents

Abstract

【課題】異なるクラスタに分類される２つ以上のノードが含まれている場合に、確率的なクラスタリングを行うことができる情報処理装置及びプログラムを提供する。【解決手段】情報処理装置１０Ａは、複数のノード及び複数のノードを結ぶ複数のリンクの情報と、複数のノードに含まれるノード対の各々に関する正及び負の制約を含む制約情報とを取得する取得部３０と、複数のノードが分類される複数のクラスタの各々について、複数のノードの各々が各クラスタに分類される割合を示す分類割合を算出し、かつ、複数のクラスタの各々についての重要度を算出する算出部３２と、少なくともリンクの情報、制約情報、分類割合、及び重要度を用いて、複数のノードについて確率的なクラスタリングを行うための確率モデルを生成する生成部３４と、を備える。【選択図】図６

Description

本発明は、情報処理装置及びプログラムに関する。

例えば、特許文献１には、ネットワーク型のソフトクラスタリングを行う情報処理装置が記載されている。この情報処理装置は、複数のノード及び複数のノードを結ぶ複数のリンクを含むネットワークの情報と、複数のノードを複数の成分に分類する粒度とを取得する取得手段を備える。また、この情報処理装置は、複数の成分それぞれについて、複数のノードそれぞれが当該成分に分類される分類割合を、当該ノードとの間でリンクを有するノードの当該成分に関する分類割合が大きいほど大きな値となる第１の寄与と、複数の成分全体に対する当該成分が占める割合が大きいほど大きな値となる第２の寄与と、から構成される値により算出する分類割合算出手段を備える。

特開２０１６−２９５２６号公報

ところで、ノード間のリンクの度合いを確率的に表現するクラスタリング方法において、異なるクラスタに分類される２つ以上のノードが含まれている場合には、確率的なクラスタリングを行うことができない場合がある。

本発明は、異なるクラスタに分類される２つ以上のノードが含まれている場合に、確率的なクラスタリングを行うことができる情報処理装置及びプログラムを提供することを目的とする。

上記目的を達成するために、請求項１に記載の情報処理装置は、複数のノード及び前記複数のノードを結ぶ複数のリンクの情報と、前記複数のノードに含まれるノード対の各々に関する正及び負の制約を含む制約情報とを取得する取得部と、前記複数のノードが分類される複数のクラスタの各々について、前記複数のノードの各々が各クラスタに分類される割合を示す分類割合を算出し、かつ、前記複数のクラスタの各々についての重要度を算出する算出部と、少なくとも前記リンクの情報、前記制約情報、前記分類割合、及び前記重要度を用いて、前記複数のノードについて確率的なクラスタリングを行うための確率モデルを生成する生成部と、を備えている。

また、請求項２に記載の情報処理装置は、請求項１に記載の発明において、前記取得部が、前記複数のノードを分類するクラスタの大きさを定める変数である粒度と、前記制約情報の重みを定める重み変数とを更に取得し、前記生成部が、前記リンクの情報、前記制約情報、前記分類割合、前記重要度、前記粒度、及び前記重み変数を用いて、前記確率モデルを生成する。

また、請求項３に記載の情報処理装置は、請求項１又は２に記載の発明において、前記確率モデルが、前記制約情報を用いて表される制約項を含み、前記制約項が、前記ノード対の一方のノードが前記複数のクラスタの各々に帰属する確率の分布である帰属度と、前記ノード対の他方のノードが前記複数のクラスタの各々に帰属する確率の分布である帰属度との間の距離に、前記制約情報により示される値を乗じることで得られる。

また、請求項４に記載の情報処理装置は、請求項３に記載の発明において、前記制約情報が、前記ノード対に関するｎ×ｍの制約行列として表されており、前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃが、ｃ_ｎｍ＝ｃ_ｍｎであり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している。

また、請求項５に記載の情報処理装置は、請求項４に記載の発明において、前記確率モデルを最大化する場合における前記分類割合を、予め定められた非線形計画法を用いて導出する導出部を更に備えている。

また、請求項６に記載の情報処理装置は、請求項３に記載の発明において、前記制約情報が、前記ノード対に関するｎ×ｍの制約行列として表されており、前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃが、ｃ_ｎｍ＝ｃ_ｍｎ、Σ_ｎｃ_ｎｍ＝０であり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している。

また、請求項７に記載の情報処理装置は、請求項３に記載の発明において、前記制約情報が、前記ノード対に関するｎ×ｍの制約行列として表されており、前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値は、特定のノードと周囲のノードとの関係性に基づいて、前記特定のノードが前記周囲のノードに対して孤立し易いか否かを表している。

また、請求項８に記載の情報処理装置は、請求項７に記載の発明において、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が正の場合、前記特定のノードが前記周囲のノードから孤立し易く、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が負の場合、前記特定のノードが前記周囲のノードから孤立し難いことを表している。

また、請求項９に記載の情報処理装置は、請求項６〜８のいずれか１項に記載の発明において、前記確率モデルを最大化する場合における前記分類割合を、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値を用いて、解析的に導出する導出部を更に備えている。

また、請求項１０に記載の情報処理装置は、請求項６〜９のいずれか１項に記載の発明において、前記ノード対が、制約が既知のノードと、制約が未知のノードとを含み、前記制約行列Ｃにおける、制約が既知のノードと、制約が未知のノードとの間の制約の値を、前記制約行列Ｃにおける既知の各値から予測する予測部を更に備えている。

更に、上記目的を達成するために、請求項１１に記載のプログラムは、コンピュータを、請求項１〜１０のいずれか１項に記載の情報処理装置が備える各部として機能させる。

請求項１及び請求項１１に係る発明によれば、異なるクラスタに分類される２つ以上のノードが含まれている場合に、確率的なクラスタリングを行うことができる。

請求項２に係る発明によれば、粒度及び重み変数を考慮しない場合と比較して、精度良く確率的なクラスタリングを行うことができる。

請求項３に係る発明によれば、一対のノードの各々の帰属度間の距離を考慮しない場合と比較して、正及び負の制約を適切に確率的なクラスタリングに導入することができる。

請求項４に係る発明によれば、制約行列Ｃがｃ_ｎｍ＝ｃ_ｍｎの条件を満たさない場合と比較して、適切な確率モデルを生成することができる。

請求項５に係る発明によれば、非線形計画法を用いない場合と比較して、分類割合の導出を適切に行うことができる。

請求項６に係る発明によれば、制約行列Ｃがｃ_ｎｍ＝ｃ_ｍｎ、Σ_ｎｃ_ｎｍ＝０の条件を満たさない場合と比較して、適切な確率モデルを生成することができる。

請求項７に係る発明によれば、制約行列Ｃの対角線上に位置するｃ_ｎｍの値を考慮しない場合と比較して、ノードの孤立し易さを把握することができる。

請求項８に係る発明によれば、制約行列Ｃの対角線上に位置するｃ_ｎｍの値が正又は負であるかを考慮しない場合と比較して、ノードの孤立し易さを把握することができる。

請求項９に係る発明によれば、制約行列Ｃの対角線上に位置するｃ_ｎｍの値を用いない場合と比較して、分類割合の導出を適切に行うことができる。

請求項１０に係る発明によれば、制約が既知のノードと未知のノードとの間の制約の値を予測しない場合と比較して、ユーザが入力する手間を軽減することができる。

第１の実施形態に係る情報処理装置の電気的な構成の一例を示すブロック図である。 クラスタリング処理の説明に供する図である。 ネットワークのクラスタリング処理の説明に供する図である。 クラスタリング処理と制約との関係の説明に供する図である。 確率的クラスタリング処理と制約との関係の説明に供する図である。 第１の実施形態に係る情報処理装置の機能的な構成の一例を示すブロック図である。 実施形態に係るネットワーク情報の一例を示す図である。 第１の実施形態に係る情報処理プログラムによる処理の流れの一例を示すフローチャートである。 第１の実施形態に係る制約情報の一例を示す図である。 実施形態に係る制約のイメージの説明に供する図である。 第２の実施形態に係る情報処理装置の機能的な構成の一例を示すブロック図である。 第２の実施形態に係る制約情報の一例を示す図である。 第３の実施形態に係る情報処理装置の機能的な構成の一例を示すブロック図である。 第３の実施形態に係る制約情報の一例を示す図である。

以下、図面を参照して、本発明を実施するための形態の一例について詳細に説明する。

[第１の実施形態]
図１は、第１の実施形態に係る情報処理装置１０Ａの電気的な構成の一例を示すブロック図である。
図１に示すように、本実施形態に係る情報処理装置１０Ａは、制御部１２と、記憶部１４と、表示部１６と、操作部１８と、通信部２０と、を備えている。

本実施形態に係る情報処理装置１０Ａには、例えば、パーソナルコンピュータ（ＰＣ：Personal Computer）等の汎用的なコンピュータ装置が適用される。なお、情報処理装置１０Ａには、スマートフォン、タブレット端末等の携帯可能な端末装置を適用してもよい。

制御部１２は、ＣＰＵ（Central Processing Unit）１２Ａ、ＲＯＭ（Read Only Memory）１２Ｂ、ＲＡＭ（Random Access Memory）１２Ｃ、及び入出力インターフェース（Ｉ／Ｏ）１２Ｄを備えており、これら各部がバスを介して各々接続されている。

Ｉ／Ｏ１２Ｄには、記憶部１４と、表示部１６と、操作部１８と、通信部２０と、を含む各機能部が接続されている。これらの各機能部は、Ｉ／Ｏ１２Ｄを介して、ＣＰＵ１２Ａと相互に通信可能とされる。

制御部１２は、情報処理装置１０Ａの一部の動作を制御するサブ制御部として構成されてもよいし、情報処理装置１０Ａの全体の動作を制御するメイン制御部の一部として構成されてもよい。制御部１２の各ブロックの一部又は全部には、例えば、ＬＳＩ（Large Scale Integration）等の集積回路又はＩＣ（Integrated Circuit）チップセットが用いられる。上記各ブロックに個別の回路を用いてもよいし、一部又は全部を集積した回路を用いてもよい。上記各ブロック同士が一体として設けられてもよいし、一部のブロックが別に設けられてもよい。また、上記各ブロックのそれぞれにおいて、その一部が別に設けられてもよい。制御部１２の集積化には、ＬＳＩに限らず、専用回路又は汎用プロセッサを用いてもよい。

記憶部１４としては、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、フラッシュメモリ等が用いられる。記憶部１４には、本実施形態に係る確率的クラスタリング処理を行うための情報処理プログラム１４Ａが記憶される。なお、この情報処理プログラム１４Ａは、ＲＯＭ１２Ｂに記憶されていてもよい。また、記憶部１４には、確率的クラスタリング処理に用いるパラメータ群１４Ｂが記憶されている。

情報処理プログラム１４Ａは、例えば、情報処理装置１０Ａに予めインストールされていてもよい。情報処理プログラム１４Ａは、不揮発性の記憶媒体に記憶して、又はネットワークを介して配布して、情報処理装置１０Ａに適宜インストールすることで実現してもよい。なお、不揮発性の記憶媒体の例としては、ＣＤ-ＲＯＭ（Compact Disc Read Only Memory）、光磁気ディスク、ＨＤＤ、ＤＶＤ-ＲＯＭ（Digital Versatile Disc Read Only Memory）、フラッシュメモリ、メモリカード等が想定される。

表示部１６には、例えば、液晶ディスプレイ（ＬＣＤ:Liquid Crystal Display）や有機ＥＬ（Electro Luminescence）ディスプレイ等が用いられる。表示部１６は、タッチパネルを一体的に有していてもよい。操作部１８には、例えば、キーボードやマウス等の操作入力用のデバイスが設けられている。表示部１６及び操作部１８は、情報処理装置１０Ａのユーザから各種の指示を受け付ける。表示部１６は、ユーザから受け付けた指示に応じて実行された処理の結果や、処理に対する通知等の各種の情報を表示する。

通信部２０は、インターネットや、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等のネットワークに接続されており、画像形成装置や他のＰＣ等の外部機器との間でネットワークを介して通信が可能とされる。

ところで、上述したように、ノード間のリンクの度合いを確率的に表現するクラスタリング方法において、異なるクラスタに分類される２つ以上のノードが含まれている場合に、確率的なクラスタリングを行うことができない場合がある。

図２は、クラスタリング処理の説明に供する図である。
図２に示すように、クラスタとは、類似の特徴を持つデータ（ノードともいう。）のグループを意味し、多数のデータを複数のクラスタに分類することをクラスタリングという。

上記クラスタリングとは、例えば、データが人の特徴を表すベクトルデータの場合、似た特徴を持つ人のグループを見つけることである。このベクトルデータのクラスタリング方法としては、一例として、ｋ-ｍｅａｎｓ法、ＧＭＭ（Gaussian Mixture Model）法、ｗａｒｄ法等が挙げられる。

図３は、ネットワークのクラスタリング処理の説明に供する図である。
図３に示すように、ネットワークデータとは、データ（＝ノード）間のつながり（＝リンク）を表現したデータである。

上記ネットワークには、例えば、電子メールや電話でのやり取りがあった人同士を繋いで人間関係を表現したネットワークや、引用／被引用の関係にある文書同士を繋いで引用関係を表現したネットワーク等が挙げられる。このネットワークデータのクラスタリング方法としては、一例として、上述の特許文献１に記載の所謂ＭＤＭＣ（Modular Decomposition of Markov Chain）法、Ｌｏｕｖａｉｎ法、Ｉｎｆｏｍａｐ法等が挙げられる。なお、以下では、ネットワークのクラスタリング処理を確率的クラスタリング処理ともいう。

図４は、クラスタリング処理と制約との関係の説明に供する図である。
図４に示すように、データには現れない潜在的な知識を制約として与え、クラスタリング処理の精度を向上させる方法がある。具体的な方法としては、ベクトルデータの場合、一例として、ＣＯＰ（Constrained）-ｋｍｅａｎｓ法、ＨＭＲＦ（Hidden Markov Random Fields）-ｋｍｅａｎｓ法等が挙げられる。

上記制約には、正の制約と負の制約とが存在する。正の制約とは、二つのデータを同じクラスタに入れる制約である。例えば、データには現れていないが、「ｎさん」と「ｍさん」は関係が強いことが分かっている場合は、正の制約を与える。一方、負の制約とは、二つのデータを異なるクラスタに入れる制約である。例えば、「ｍさん」と「ｌさん」はデータでは近い関係になっているが、実際には関係が弱いことが分かっている場合は、負の制約を与える。

図５は、確率的クラスタリング処理と制約との関係の説明に供する図である。
図５に示すように、確率的クラスタリング処理では、正の制約はリンクの重みを大きくする等によって導入が可能とされる。一方、負の制約はリンクの重みを負にできないため、正の制約と同様には導入することができない。このため、正及び負の制約に基づいて、確率的クラスタリング処理を行うことができるようにすることが望まれている。

本実施形態に係る情報処理装置１０ＡのＣＰＵ１２Ａは、記憶部１４に記憶されている情報処理プログラム１４ＡをＲＡＭ１２Ｃに書き込んで実行することにより、図６に示す各部として機能する。

図６は、第１の実施形態に係る情報処理装置１０Ａの機能的な構成の一例を示すブロック図である。
図６に示すように、本実施形態に係る情報処理装置１０ＡのＣＰＵ１２Ａは、取得部３０、算出部３２、生成部３４、及び導出部３６として機能する。

本実施形態に係る記憶部１４には、上述したように、パラメータ群１４Ｂが記憶されており、このパラメータ群１４Ｂには、ネットワーク情報５０、制約情報５２、粒度α５４、及び重み変数５６が含まれている。

本実施形態に係る取得部３０は、パラメータ群１４Ｂから、ネットワーク情報５０、制約情報５２、粒度α５４、及び重み変数５６を取得する。なお、本実施形態では、上述のＭＤＭＣ法を適用した場合について説明するが、このＭＤＭＣ法に限定されるものではない。

ネットワーク情報５０は、複数のノード及び複数のノードを結ぶ複数のリンクの情報の一例である。ネットワーク情報５０には、一例として、相互参照を示すＨＴＭＬ（Hyper Text Markup Language ）データや、友人関係のデータ等が適用される。ネットワーク情報５０は、少なくともノード間の結び付きの関係（ノードとリンクの関係）を示すものであればよく、ノードが含む具体的な内容（ＨＴＭＬデータの内容等）を示すものでなくてもよい。

制約情報５２は、複数のノードに含まれるノード対の各々に関する正及び負の制約を含む情報である。この制約情報５２は、一例として、後述の図９に示す制約行列Ｃとして表される。

粒度α５４は、複数のノードを分類するクラスタの大きさを定める変数であり、正の実数として表される。また、重み変数５６は、制約情報５２の重みを定める変数であり、０（ゼロ）以上の実数として表される。本実施形態では、粒度α５４及び重み変数５６が記憶部１４に予め記憶されていることとしたが、ユーザが操作部１８を介して粒度α５４及び重み変数５６を入力することとしてもよい。なお、粒度α５４を含まないＭＤＭＣ法以外を適用する場合には、粒度α５４を変数ではなく、定数とすればよい。また、重み変数５６は必須ではなく、重み変数５６を含まない形態としてもよい。

図７は、本実施形態に係るネットワーク情報５０の一例を示す図である。
図７に示すネットワーク情報５０は、一例として、７つのノードと、９つのリンクの情報を含んでいる。

図７に示す各ノードには、１から７までのノード番号が付与されており、例えば、ノード番号１であるノード（以下、ノード[１]と表す。）は、ノード[２]及びノード[４]のノードとリンクを有する。本実施形態では、説明を簡単にするために、７つのノードを有するネットワークの場合を示すが、ノード数及びリンク数はこれより多くてもよく、例えば、１０万程度であってもよい。また、本実施形態では、ノード間を結ぶリンクは方向を持たないこととしているが、リンクは一方通行であってもよい。

図７に示す行列Ｔは、ノード間をリンクに沿ってランダムに遷移する場合における遷移確率を表すものである。例えば、ノード[１]を起点としてリンクに沿ってランダムに他のノードに遷移する場合、１／２の確率でノード[２]に遷移し、１／２の確率でノード[４]に遷移する。これらの遷移確率をまとめて表したものが、行列Ｔの第１列である。他の行列要素についても同様に構成されている。一般に、ノード[ｎ]とノード[ｍ]がリンクで接続されている場合にＡ_ｎｍ＝１、ノード[ｎ]とノード[ｍ]がリンクで接続されていない場合にＡ_ｎｍ＝０となる行列Ａを用いて、ノードの総数をＮとする場合に、行列Ｔは、以下に示す式（１）により表される。遷移確率の総和は１であるから、任意のノード[ｍ]について、Σ_ｎＴ_ｎｍ＝１が成り立つ。

本実施形態に係る算出部３２は、複数のノードが分類される複数のクラスタの各々について、複数のノードの各々が各クラスタに分類される割合を示す分類割合を算出し、かつ、複数のクラスタの各々についての重要度を算出する。

本実施形態に係る生成部３４は、ネットワーク情報５０、制約情報５２、上記分類割合、上記重要度、粒度α５４、及び重み変数５６を用いて、複数のノードについて確率的なクラスタリングを行うための確率モデルを生成する。なお、この確率モデルの具体的な生成方法については後述する。

本実施形態に係る導出部３６は、上記確率モデルを最大化する場合における上記分類割合を、一例として、ＥＭアルゴリズム（Expectation-Maximization algorithm）等を用いて導出する。

次に、図８を参照して、第１の実施形態に係る情報処理装置１０Ａの作用を説明する。

図８は、第１の実施形態に係る情報処理プログラム１４Ａによる処理の流れの一例を示すフローチャートである。

まず、情報処理装置１０Ａに対して、ユーザにより確率的クラスタリング処理の開始が指示されると、情報処理プログラム１４Ａが起動され、以下の各ステップを実行する。本実施形態では、ネットワークに含まれるＮ個のノードをＫ個のクラスタに分類することにより、確率的クラスタリング処理を行う。ここで、Ｎ及びＫは正の整数である。

図８のステップ１００では、取得部３０が、パラメータ群１４Ｂから、ネットワーク情報５０、制約情報５２、粒度α５４、及び重み変数５６を取得する。

図９は、第１の実施形態に係る制約情報５２の一例を示す図である。
図９に示すように、本実施形態に係る制約情報５２は、ノード対に関するｎ×ｍの制約行列Ｃとして表される。

つまり、制約行列Ｃは、行方向（横方向）にノード[ｍ]（本実施形態では、ｍ＝１、２、３、４）、列方向（縦方向）にノード[ｎ]（本実施形態では、ｎ＝１、２、３、４）とした場合に、各行列要素の値はｃ_ｎｍとして表される。本実施形態の場合、左上角の値がｃ_１１、右上角の値がｃ_１４、左下角の値がｃ_４１、右下角の値がｃ_４４に対応している。

図９に示す制約行列Ｃにおいて、ｃ_ｎｍの絶対値は、２つのノード間における制約の強さを示し、マイナスは負の制約を示す。例えば、図９に示す丸で囲むｃ_２３の値は「−１」であり、ノード[２]とノード[３]との間には負の制約がかかることを意味する。本実施形態に係る制約行列Ｃは、ｃ_ｎｍ＝ｃ_ｍｎであり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している。すなわち、

である。

次に、図８に戻り、ステップ１０２では、算出部３２が、分類割合及び重要度を算出する。具体的には、クラスタ[ｋ]について、ノード[ｎ]がクラスタ[ｋ]に分類される分類割合ｐ（ｎ｜ｋ）を算出し、クラスタ[ｋ]の重要度π（ｋ）を算出する。なお、分類割合ｐ（ｎ｜ｋ）及び重要度π（ｋ）を算出するにあたり、第ｄ番目の通過情報τ_ｄに基づいて、複数のクラスタ全体に対するクラスタ[ｋ]が占める割合γ_ｄ（ｋ）を求める。なお、第ｄ番目の通過情報τ_ｄはＮ次元のベクトルであり、τ_１、τ_２、・・・、τ_Ｄ（Ｄは整数）というＤ個のデータである。

このステップ１０２では、ネットワーク情報５０が表すネットワークのノード間をランダムに遷移する場合における定常確率分布ｐ^ｓｔ（ｎ）を算出する。定常確率分布ｐ^ｓｔ（ｎ）は、以下に示す式（３）により定められる連立Ｎ次方程式を解くことにより求められる。定常確率分布ｐ^ｓｔ（ｎ）は、行列Ｔの固有ベクトルであって、固有値が１とされる。

なお、一方通行のリンクを含むネットワークの場合、いわゆるランクシンク等の問題が発生し、定常確率分布が特定のノードにのみ値を有する場合がある。そのような場合、上記式（３）を変形し、例えば、ｐ^ｓｔ（ｎ）＝（１−ｒ）Σ_ｍＴ_ｎｍｐ^ｓｔ（ｍ）＋ｒという関係によって定常確率分布ｐ^ｓｔ（ｎ）を求めることとしてもよい。ここで、ｒは０以上１以下の実数である。ｒは、ノード間をリンクに沿わずにランダムに遷移する確率を表す。

次に、複数のノード間を複数のリンクに沿ってランダムに遷移する場合に通過するノードを示す複数の通過情報τ_ｎｄを生成する。本実施形態では、通過情報は、定常確率分布ｐ^ｓｔ（ｎ）に従って選出されたノード［ｎ］について、τ_ｎｄ＝１、かつ、ノード［ｎ］を起点としてノード［ｍ］に遷移する確率を与えるＴ_ｎｍに従って選出されたノード［ｍ］について、τ_ｍｄ＝１として生成する。このようなＮ次元ベクトルを、Ｄ回生成する。通過情報τ_ｎｄは、Σ_ｎτ_ｎｄ＝２を満たす量である。通過情報τ_ｎｄは、仮想エージェントがノード間をリンクに沿ってランダムに遷移する場合に、仮想エージェントをノード［ｎ］とノード［ｍ］とを結ぶリンク上に見出す場合を表している。

本実施形態に係る算出部３２は、逐次計算により分類割合ｐ（ｎ｜ｋ）及び重要度π（ｋ）をそれぞれ算出する。逐次計算を開始するにあたって、ｐ_０（ｎ｜ｋ）、π_０（ｋ）、γ_０（ｄ）（ｋ）を仮決めする。ここで、Σ_ｎｐ_０（ｎ｜ｋ）＝１、Σ_ｋπ_０（ｋ）＝１を満たす値を与えるものとする。ｐ_０（ｎ｜ｋ）は、ｋ＝１〜Ｋのクラスタについて、ｎ＝１〜Ｎのノードが分類される割合を示すものであるから、仮決めでは（Ｋ×Ｎ−１）個の正の実数を与えることになる。なお、”−１”はΣ_ｎｐ_０（ｎ｜ｋ）＝１の条件による。また、π_０（ｋ）は、ｋ＝１〜Ｋに分類されたネットワークのクラスタについて、重要度を示すものであるから、仮決めでは（Ｋ−１）個の正の実数を与えることになる。γ_０（ｄ）（ｋ）は、複数のクラスタ全体に対するクラスタ［ｋ］が占める割合を表す係数であり、ｄ＝１〜Ｄの通過情報τ_ｎｄに対応して定まる係数であるから、仮決めでは（Ｋ×Ｄ）個の正の実数を与えることになる。

逐次計算の第１ステップでは、第ｔ回目の逐次計算による分類割合ｐ_ｔ（ｎ｜ｋ）を計算する。ここで、ｔは正の整数であり、逐次計算の回数を表す。ｐ_ｔ（ｎ｜ｋ）は、１つ前の逐次計算により得られるｐ_ｔ−１（ｎ｜ｋ）、π_ｔ−１（ｋ）、及びγ_{ｔ−１（ｄ）}（ｋ）より算出される。例えば、仮決めの後行われる第１回目の逐次計算では、ｐ_０（ｎ｜ｋ）、π_０（ｋ）、及びγ_０（ｄ）（ｋ）を用いてｐ_１（ｎ｜ｋ）を求めることになる。

本実施形態に係る算出部３２は、以下に示す式（４）で定められる関係により第ｔ回目の逐次計算による分類割合ｐ_ｔ（ｎ｜ｋ）を算出する。

ここで、αは上述の粒度α５４であり、正の実数である。本実施形態では、粒度α５４は、αが０に近付くほど分解の粒度が細かくなり、αが無限大に近付くほど分解の粒度が粗くなるパラメータである。また、Ｄ_ｔ−１（ｋ）はγ_{ｔ−１（ｄ）}（ｋ）から定まる係数であり、Ｄ_ｔ−１（ｋ）＝Σ_ｄγ_{ｔ−１（ｄ）}（ｋ）である。

分類割合ｐ_ｔ（ｎ｜ｋ）は、ノード［ｎ］との間でリンクを有するノード（Ｔ_ｎｍ≠０であるノード［ｍ］）のクラスタ［ｋ］に関する分類割合ｐ_ｔ−１（ｍ｜ｋ）が大きいほど大きな値となる第１の寄与（右辺第一項）と、複数のクラスタ全体に対するクラスタ［ｋ］が占める割合γ_{ｔ−１（ｄ）}（ｋ）が大きいほど大きな値となる第２の寄与（右辺第二項）とから構成される値により算出される。

また、第１の寄与は、粒度α５４を粗くする、つまり、αを無限大に近付けると１に近付く第１の係数α／（α＋２Ｄ_ｔ−１（ｋ））と、ノード［ｎ］との間でリンクを有するノード（Ｔ_ｎｍ≠０であるノード［ｍ］）に関して直前に算出された分類割合ｐ_ｔ−１（ｍ｜ｋ）と、から定められる。また、第２の寄与は、粒度α５４を粗くする、つまり、αを無限大に近付けると０に近付く第２の係数１／（α＋２Ｄ_ｔ−１（ｋ））と、複数の通過情報τ_ｎｄと、複数の成分全体に対するクラスタ［ｋ］が占める割合γ_{ｔ−１（ｄ）}（ｋ）と、から定められる。なお、以下に示すように、複数のクラスタ全体に対するクラスタ［ｋ］が占める割合γ_{ｔ−１（ｄ）}（ｋ）は、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）及び重要度π_ｔ−１（ｋ）から算出される。

次に、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）及び重要度π_ｔ−１（ｋ）、並びに複数の通過情報τ_ｎｄから、複数のクラスタ全体に対するクラスタ［ｋ］が占める割合γ_ｔｄ（ｋ）を算出する。本実施形態では、以下に示す式（５）により割合γ_ｔｄ（ｋ）を算出する。なお、割合γ_ｔｄ（ｋ）は、クラスタ全体の中で重要度が相対的に大きいクラスタについて大きな値をとる。

さらに、本実施形態に係る算出部３２は、ネットワークのクラスタ［ｋ］の重要度π_ｔ（ｋ）を算出する。重要度π_ｔ（ｋ）は、複数のクラスタ全体に対するクラスタ［ｋ］が占める割合γ_ｔｄ（ｋ）が大きいほど大きな値となるように算出される。本実施形態では、以下に示す式（６）によりクラスタ［ｋ］の重要度π_ｔ（ｋ）を算出する。

上記の式（４）、式（５）、及び式（６）により、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）、重要度π_ｔ−１（ｋ）、及び割合γ_{ｔ−１（ｄ）}（ｋ）、並びに通過情報τ_ｎｄから、分類割合ｐ_ｔ（ｎ｜ｋ）、重要度π_ｔ（ｋ）、及び割合γ_ｔｄ（ｋ）が算出される。

次に、ステップ１０４では、生成部３４が、ステップ１００で取得したネットワーク情報５０、制約情報５２、粒度α５４、及び重み変数５６と、ステップ１０２で算出した分類割合ｐ_ｔ（ｎ｜ｋ）及び重要度π_ｔ（ｋ）とを用いて、複数のノードについて確率的なクラスタリングを行うための確率モデルＱ’を生成する。本実施形態では、この確率モデルＱ’は、以下に示す式（７）により算出される。

なお、Ｗは重み変数５４であり、ｃ_ｎｍは制約行列Ｃで表される制約情報５２である。Ｕ_ｎｍは制約情報５２を用いて表される制約項である。

この制約項Ｕ_ｎｍは、ノード対の一方のノードが複数のクラスタの各々に帰属する確率の分布である帰属度と、ノード対の他方のノードが複数のクラスタの各々に帰属する確率の分布である帰属度との間の距離に、制約情報５２により示される値を乗じることで得られる。ここで、ノード[ｎ]がクラスタ[ｋ]に帰属する帰属度ｐ（ｋ｜ｎ）は、ノード[ｎ]がクラスタ[ｋ]に分類される分類割合ｐ（ｎ｜ｋ）が大きいほど、大きな値となる。本実施形態では、帰属度ｐ（ｋ｜ｎ）は、以下に示す式（８）により算出される。

上記式（８）から読み取れるように、帰属度ｐ（ｋ｜ｎ）は、Σ_ｋｐ（ｋ｜ｎ）＝１を満たす。すなわち、あるノードが各クラスタに帰属する帰属度の総和は１となる。帰属度ｐ（ｋ｜ｎ）は、あるノード［ｎ］が、クラスタ［ｋ］に帰属する度合いをクラスタ全体に関して相対的に測った量である。

ここで、ノード[ｎ]の帰属度ｐ（ｋ｜ｎ）と、ノード[ｍ]の帰属度ｐ（ｋ｜ｍ）との間の距離は、一例として、ＫＬ（Kullback-Leibler）情報量を用いて、以下に示す式（９）のように表される。

従って、上記式（７）に示す制約項Ｕ_ｎｍは、上記式（９）に基づいて、以下に示す式（１０）のように記述することもできる。

上述したように、ネットワークにおける確率的クラスタリング処理では特に負の制約を直接導入することができない。このため、本実施形態では、まず各ノードについてクラスタへの帰属度を計算し、計算した帰属度に対して、正及び負の制約を付与する。この制約のイメージについて図１０を参照して説明する。

図１０は、本実施形態に係る制約のイメージの説明に供する図である。
図１０の右図に示すグラフでは、横軸にノード[ｎ]についてのクラスタ[１]への帰属度ｐ（１｜ｎ）を示し、縦軸にノード[ｎ]についてのクラスタ[２]への帰属度ｐ（２｜ｎ）を示す。

図１０に示すように、正の制約の場合、帰属度として表される確率分布を近づける方向に作用する。図１０に示す例では、ノード[ｎ]とノード[ｍ]との間には正の制約が作用している。一方、負の制約の場合、帰属度として表される確率分布を遠ざける方向に作用する。図１０に示す例では、ノード[ｍ]とノード[ｌ]との間には負の制約が作用している。

次に、図８に戻り、ステップ１０６では、導出部３６が、上述のＥＭアルゴリズムを用いて、確率モデルＱ’を最大化する場合における分類割合ｐ（ｎ｜ｋ）を導出し、本情報処理プログラム１４Ａによる一連の処理を終了する。なお、本実施形態における分類割合ｐ（ｎ｜ｋ）は、非線形計画法（Nonlinear programming method）を用いて数値的に求められる。この非線形計画法としては、一例として、主双対内点法（primal-dual interior point method）、外点ペナルティ法（exterior penalty method）、乗数法（multiplier method）等が挙げられる。

ここで、上記の実施形態では、ＭＤＭＣ法における確率モデルを適用した場合について説明したが、実施形態は、以下に示すＱの形式（Ｑの一般式）を満たす確率モデルであれば適用可能とされる。

・・・（１１）

但し、Ｔは上記式（１）で示される遷移確率を表す行列であり、πは上記式（６）で示される重要度である。αは粒度α５４であり、Ｃは上記式（２）で示される制約行列である。Ｗは重み変数５６である。｛｛ｐ（ｎ｜ｋ）｝｝は上記式（４）で示される分類割合を示す。但し、

・・・（１２）

である。

なお、上記の実施形態では、粒度α５４を変数としたが、変数αを含まないＭＤＭＣ法以外の確率モデルでは、粒度α５４を定数とし、Ｑの特殊例として導出すればよい。

このように本実施形態によれば、正及び負の制約を考慮して、精度の高い確率的クラスタリング処理が実行される。

[第２の実施形態]
上記第１の実施形態では、分類割合ｐ（ｎ｜ｋ）を、非線形計画法を用いて数値的に求める場合について説明したが、本実施形態では、分類割合ｐ（ｎ｜ｋ）を解析的に求める場合について説明する。

図１１は、第２の実施形態に係る情報処理装置１０Ｂの機能的な構成の一例を示すブロック図である。
図１１に示すように、本実施形態に係る情報処理装置１０ＢのＣＰＵ１２Ａは、取得部３０、算出部３２、生成部３４、及び導出部３８として機能する。なお、取得部３０、算出部３２、及び生成部３４については、上記第１の実施形態に係る情報処理装置１０Ａと同様であるため、ここでの繰り返しの説明は省略する。

本実施形態に係る導出部３８は、確率モデルＱ’（式（７）参照）を最大化する場合における分類割合ｐ（ｎ｜ｋ）を、制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値を用いて、解析的に導出する。

本実施形態に係る制約行列Ｃは、ｃ_ｎｍ＝ｃ_ｍｎ、Σ_ｎｃ_ｎｍ＝０であり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している。すなわち、

である。

また、重み変数Ｗは、以下に示す式（１４）を満たす。

図１２は、第２の実施形態に係る制約情報５２の一例を示す図である。
図１２に示すように、本実施形態に係る制約情報５２は、ノード対に関するｎ×ｍの制約行列Ｃとして表されるが、一方の対角線上に位置するｃ_ｎｍの値が図９に示す制約行列Ｃとは異なる。

本実施形態に係る制約行列Ｃの各値をｃ_ｎｍとした場合、制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値は、特定のノードと周囲のノードとの関係性に基づいて、特定のノードが周囲のノードに対して孤立し易いか否かを表している。つまり、制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が正の場合、特定のノードは周囲のノードから孤立し易く、制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が負の場合、特定のノードは周囲のノードから孤立し難いことを表している。

例えば、図１２に示すように、線で囲われた対角要素（ｃ_１１、ｃ_２２、ｃ_３３、ｃ_４４）の場合、ｃ_１１の値及びｃ_２２の値はいずれも−２（負）であるため、対応するノード[１]及びノード[２]は、周囲のノードから孤立し難い。一方、ｃ_３３の値は４（正）であるため、対応するノード[３]は、周囲のノードから孤立し易い。なお、ｃ_４４の値は０であるため、対応するノード[４]の孤立し易さは中立とされる。

本実施形態では、分類割合ｐ（ｎ｜ｋ）は、上述のＥＭアルゴリズムを用いて解析的に求められる。具体的には、以下に示す式（１５）を用いて求められる。但し、分類割合ｐ_ｔ（ｎ｜ｋ）は、第ｔ回目の逐次計算によることを示す。

このように本実施形態によれば、正及び負の制約を考慮して、精度の高い確率的クラスタリング処理が実行され、更に、分類割合が解析的に求められる。

[第３の実施形態]
本実施形態では、ノード対に関する制約行列Ｃの値（正及び負の値を含む）が部分的にしか与えられていない場合に、ユーザからの入力を介さずに未知の制約を予測する形態について説明する。本実施形態では、例えば、既に制約が与えられているネットワークに、新たにノードを追加してネットワークを拡張する場合等が想定される。

図１３は、第３の実施形態に係る情報処理装置１０Ｃの機能的な構成の一例を示すブロック図である。
図１３に示すように、本実施形態に係る情報処理装置１０ＣのＣＰＵ１２Ａは、取得部３０、算出部３２、生成部３４、導出部３８、及び予測部４０として機能する。なお、取得部３０、算出部３２、生成部３４、及び導出部３８については、上記第２の実施形態に係る情報処理装置１０Ｂと同様であるため、ここでの繰り返しの説明は省略する。

本実施形態に係るノード対は、制約が既知のノードと、制約が未知のノードとを含んでいる。本実施形態に係る予測部４０は、制約行列Ｃにおける、制約が既知のノードと、制約が未知のノードとの間の制約の値を、制約行列Ｃにおける既知の各値から予測する。

図１４は、第３の実施形態に係る制約情報５２の一例を示す図である。
図１４に示すように、本実施形態に係る制約情報５２は、制約が既知である４つのノードに、制約が未知である２つのノードを追加した場合の制約行列Ｃとして表される。

具体的には、制約が未知のノード[ｘ]と、制約が既知のノード[ｎ]との間の未知の制約値ｃ_ｎｘは、一例として、ＰＰＲ（Personalized Page Rank）法に基づいて、以下に示す式（１６）により求められる。

但し、Ｓ_ｎｍはＰＰＲ行列Ｓのｎ行ｍ列の行列要素である。Ｓ_ｎｘはＰＰＲ行列Ｓのｎ行ｘ列の行列要素である。Ｎは既知のノード数である。ｃ_ｎｍはノード[ｎ]とノード[ｍ]との間の既知の制約値である。なお、ＰＰＲ行列Ｓは、以下に示す式（１７）を再帰的に収束するまで計算して求める。

但し、Ｔは上記式（１）で示される遷移確率を表す行列である。Ｎは既知のノード数であり、Ｘは未知のノード数である。ｄはランダム遷移パラメータである。Ｉは（Ｎ＋Ｘ）次元の単位行列である。この単位行列Ｉは、対角成分が１、その他の成分が全て０の正方行列として表される。

このように本実施形態によれば、ノード対に関する制約行列の値（正及び負の値を含む）が部分的にしか与えられていない場合に、ユーザからの入力を介さずに未知の制約が予測される。

以上、実施形態に係る情報処理装置を例示して説明した。実施形態は、情報処理装置が備える各部の機能をコンピュータに実行させるためのプログラムの形態としてもよい。実施形態は、このプログラムを記憶したコンピュータが読み取り可能な記憶媒体の形態としてもよい。

その他、上記実施形態で説明した情報処理装置の構成は、一例であり、主旨を逸脱しない範囲内において状況に応じて変更してもよい。

また、上記実施形態で説明したプログラムの処理の流れも、一例であり、主旨を逸脱しない範囲内において不要なステップを削除したり、新たなステップを追加したり、処理順序を入れ替えたりしてもよい。

また、上記実施形態では、プログラムを実行することにより、実施形態に係る処理がコンピュータを利用してソフトウェア構成により実現される場合について説明したが、これに限らない。実施形態は、例えば、ハードウェア構成や、ハードウェア構成とソフトウェア構成との組み合わせによって実現してもよい。

１０Ａ、１０Ｂ、１０Ｃ 情報処理装置
１２ 制御部
１２Ａ ＣＰＵ
１２Ｂ ＲＯＭ
１２Ｃ ＲＡＭ
１２Ｄ Ｉ／Ｏ
１４ 記憶部
１４Ａ 情報処理プログラム
１４Ｂ パラメータ群
１６ 表示部
１８ 操作部
２０ 通信部
３０ 取得部
３２ 算出部
３４ 生成部
３６、３８ 導出部
４０ 予測部
５０ ネットワーク情報
５２ 制約情報
５４ 粒度α
５６ 重み変数

Claims (11)

1. 複数のノード及び前記複数のノードを結ぶ複数のリンクの情報と、前記複数のノードに含まれるノード対の各々に関する正及び負の制約を含む制約情報とを取得する取得部と、
   前記複数のノードが分類される複数のクラスタの各々について、前記複数のノードの各々が各クラスタに分類される割合を示す分類割合を算出し、かつ、前記複数のクラスタの各々についての重要度を算出する算出部と、
   少なくとも前記リンクの情報、前記制約情報、前記分類割合、及び前記重要度を用いて、前記複数のノードについて確率的なクラスタリングを行うための確率モデルを生成する生成部と、
   を備えた情報処理装置。
2. 前記取得部は、前記複数のノードを分類するクラスタの大きさを定める変数である粒度と、前記制約情報の重みを定める重み変数とを更に取得し、
   前記生成部は、前記リンクの情報、前記制約情報、前記分類割合、前記重要度、前記粒度、及び前記重み変数を用いて、前記確率モデルを生成する請求項１に記載の情報処理装置。
3. 前記確率モデルは、前記制約情報を用いて表される制約項を含み、
   前記制約項は、前記ノード対の一方のノードが前記複数のクラスタの各々に帰属する確率の分布である帰属度と、前記ノード対の他方のノードが前記複数のクラスタの各々に帰属する確率の分布である帰属度との間の距離に、前記制約情報により示される値を乗じることで得られる請求項１又は２に記載の情報処理装置。
4. 前記制約情報は、前記ノード対に関するｎ×ｍの制約行列として表されており、
   前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃは、ｃ_ｎｍ＝ｃ_ｍｎであり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している請求項３に記載の情報処理装置。
5. 前記確率モデルを最大化する場合における前記分類割合を、予め定められた非線形計画法を用いて導出する導出部を更に備えた請求項４に記載の情報処理装置。
6. 前記制約情報は、前記ノード対に関するｎ×ｍの制約行列として表されており、
   前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃは、ｃ_ｎｍ＝ｃ_ｍｎ、Σ_ｎｃ_ｎｍ＝０であり、ｃ_ｎｍ＞０の場合には正の制約、ｃ_ｎｍ＝０の場合には制約なし、ｃ_ｎｍ＜０の場合には負の制約を表している請求項３に記載の情報処理装置。
7. 前記制約情報は、前記ノード対に関するｎ×ｍの制約行列として表されており、
   前記制約行列をＣ、前記制約行列Ｃの各値をｃ_ｎｍとした場合、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値は、特定のノードと周囲のノードとの関係性に基づいて、前記特定のノードが前記周囲のノードに対して孤立し易いか否かを表している請求項３に記載の情報処理装置。
8. 前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が正の場合、前記特定のノードは前記周囲のノードから孤立し易く、
   前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値が負の場合、前記特定のノードは前記周囲のノードから孤立し難いことを表している請求項７に記載の情報処理装置。
9. 前記確率モデルを最大化する場合における前記分類割合を、前記制約行列Ｃの一方の対角線上に位置するｃ_ｎｍの値を用いて、解析的に導出する導出部を更に備えた請求項６〜８のいずれか１項に記載の情報処理装置。
10. 前記ノード対は、制約が既知のノードと、制約が未知のノードとを含み、
    前記制約行列Ｃにおける、制約が既知のノードと、制約が未知のノードとの間の制約の値を、前記制約行列Ｃにおける既知の各値から予測する予測部を更に備えた請求項６〜９のいずれか１項に記載の情報処理装置。
11. コンピュータを、請求項１〜１０のいずれか１項に記載の情報処理装置が備える各部として機能させるためのプログラム。