(57)【要約】【課題】負の値を含むベクトルデータを、計算量を抑えてクラスタリングする。【解決手段】制御部１０は、複数の成分がベクトルで表現されるベクトルデータを取得し、取得したベクトルデータをパラメトリック手法によりクラスタリングする。制御部１０は、取得したベクトルデータを表すデータ点と、パラメトリック手法によるクラスタリングにより得られた各クラスタの平均をノードとする二部ネットワークを生成し、データ点のノードと、パラメトリック手法によるクラスタリングにより得られたクラスタの平均のノードとを結ぶリンク重みを算出する。制御部１０は、生成した二部ネットワークにおけるリンクを介するノード間の遷移確率を算出したリンク重みに応じて決定し、ノード間の遷移の確率過程の繰り返し計算を実行することにより、ノードのクラスタリングを行う。【選択図】図１
2019020806.tif 000002
【特許請求の範囲】
【請求項１】
複数の成分がベクトルで表現されるベクトルデータを取得する取得手段と、
前記ベクトルデータをパラメトリック手法によりクラスタリングする第１クラスタリング手段と、
前記ベクトルデータを表すデータ点と前記第１クラスタリング手段により得られた各クラスタの特徴点をノードとする二部ネットワークを生成する生成手段と、
前記データ点のノードと、前記特徴点のノードとを結ぶリンク重みを算出する算出手段と、
前記二部ネットワークにおけるリンクを介するノード間の遷移確率を前記リンク重みに応じて決定し、前記ノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノードのクラスタリングを行う第２クラスタリング手段と
を備える情報処理装置。
【請求項２】
前記第１クラスタリング手段は、ｋ平均法でクラスタリングを行い、
前記第１クラスタリング手段により得られたクラスタの中心を前記特徴点とする
請求項１に記載の情報処理装置。
【請求項３】
前記リンクの重みを、前記特徴点と前記データ点との間のユークリッド距離が短いほど正の値として大きくする活性化関数により算出する
請求項２に記載の情報処理装置。
【請求項４】
前記データ点をｘn、前記特徴点をｍkとした場合、前記ユークリッド距離を式（１）により算出する、
請求項３に記載の情報処理装置。
【数１】
2019020806.tif 000019
【請求項５】
前記第１クラスタリング手段は、Ｋ−ｍｅｄｏｉｄｓ法でクラスタリングを行い、
前記第１クラスタリング手段により得られたクラスタの代表点を前記特徴点とする
請求項１に記載の情報処理装置。
【請求項６】
前記第１クラスタリング手段は、混合ガウスモデルによりクラスタリングを行い、
複数のガウス分布の各々を前記特徴点とし、
前記データ点の前記クラスタへの寄与度を前記リンク重みとする
請求項１に記載の情報処理装置。
【請求項７】
前記混合ガウスモデルは、前記ベクトルデータの分布を楕円体で近似する
請求項６に記載の情報処理装置。
【請求項８】
前記第２クラスタリング手段は、前記クラスタの重要度を算出し、
重要度が予め定められた条件を満たすクラスタを抽出する
請求項１から請求項７のいずれか一項に記載の情報処理装置。
【請求項９】
前記算出手段は、
前記特徴点と前記データ点との間のユークリッド距離を算出し、
前記データ点との前記ユークリッド距離が近い順に、予め定められた個数の前記特徴点のノードを選択し、
選択した特徴点のノードと前記データ点との前記リンク重みを正の値とし、選択した特徴点以外の特徴点のノードと前記データ点との前記リンク重みを０とする
請求項１に記載の情報処理装置。
【請求項１０】
コンピュータを、
複数の成分がベクトルで表現されるベクトルデータを取得する取得手段と、
前記ベクトルデータをパラメトリック手法によりクラスタリングする第１クラスタリング手段と、
前記ベクトルデータを表すデータ点と前記第１クラスタリング手段により得られた各クラスタの特徴点をノードとする二部ネットワークを生成する生成手段と、
前記データ点のノードと、前記特徴点のノードとを結ぶリンク重みを算出する算出手段と、
前記二部ネットワークにおけるリンクを介するノード間の遷移確率を前記リンク重みに応じて決定し、前記ノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノードのクラスタリングを行う第２クラスタリング手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
発明者は、クラスタリングについて、「マルコフ連鎖のモジュール分解」に基づいて、ネットワークから重なりと階層を持つクラスタ構造を検出する方法を特許文献１にて提案した。マルコフ連鎖のモジュール分解に基づくクラスタリング（コミュニティ抽出）の計算では、ネットワークの各ノードが持つ確率がリンクを経由して他のリンクに遷移（ランダムウォーク）するというモデルで各ノードの確率の変化を繰り返し計算し、定常状態に達したときの情報に基づき、各ノードがどのクラスタに属するのかを判定した。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１３−１６８１２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
二種類のノードから構成されるネットワーク（以下、二部ネットワーク）で扱うベクトルデータは、文書の特徴表現の場合だけでなく、例えば、各種の測定による物理量や、各種診断における検査値を表す場合も考えられる。この場合、例えば、温度の値は、ゼロあるいはマイナスの値となることもあるが、文書の特徴表現とは異なり、値の大小は、ノードとデータ点を結ぶリンクの重みを表すものとはならないため、このようなベクトルデータを二部ネットワークで表現しようとする場合、値の大小からリンクの重みを得る方法は採用できない。
【０００５】
また負の値を含むベクトルデータを扱うクラスタリングの方法としては、例えばデータ間の相対的な位置関係に基づいて行うノンパラメトリックな方法があるが、この場合、事前にデータペア間の距離を求める必要があり、データ数が多くなると計算量が増え、クラスタリングに時間がかかることとなる。
【０００６】
本発明は、負の値を含むベクトルデータを、ノンパラメトリックな方法よりも少ない計算量でクラスタリングする技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の請求項１に係る情報処理装置は、複数の成分がベクトルで表現されるベクトルデータを取得する取得手段と、前記ベクトルデータをパラメトリック手法によりクラスタリングする第１クラスタリング手段と、前記ベクトルデータを表すデータ点と前記第１クラスタリング手段により得られた各クラスタの特徴点をノードとする二部ネットワークを生成する生成手段と、前記データ点のノードと、前記特徴点のノードとを結ぶリンク重みを算出する算出手段と、前記二部ネットワークにおけるリンクを介するノード間の遷移確率を前記リンク重みに応じて決定し、前記ノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノードのクラスタリングを行う第２クラスタリング手段とを備える。
【０００８】
本発明の請求項２に係る情報処理装置においては、前記第１クラスタリング手段は、ｋ平均法でクラスタリングを行い、前記第１クラスタリング手段により得られたクラスタの中心を前記特徴点とする。
【０００９】
本発明の請求項３に係る情報処理装置においては、前記リンクの重みを、前記特徴点と前記データ点との間のユークリッド距離が短いほど正の値として大きくする活性化関数により算出する。
【００１０】
本発明の請求項４に係る情報処理装置においては、前記データ点をｘn、前記特徴点をｍkとした場合、前記ユークリッド距離を式（１）により算出する。
【数１】
2019020806.tif 000003
【００１１】
本発明の請求項５に係る情報処理装置においては、前記第１クラスタリング手段は、Ｋ−ｍｅｄｏｉｄｓ法でクラスタリングを行い、前記第１クラスタリング手段により得られたクラスタの代表点を前記特徴点とする。
【００１２】
本発明の請求項６に係る情報処理装置においては、前記第１クラスタリング手段は、混合ガウスモデルによりクラスタリングを行い、複数のガウス分布の各々を前記特徴点とし、前記データ点の前記クラスタへの寄与度を前記リンク重みとする。
【００１３】
本発明の請求項７に係る情報処理装置においては、前記混合ガウスモデルは、前記ベクトルデータの分布を楕円体で近似する。
【００１４】
本発明の請求項８に係る情報処理装置においては、前記第２クラスタリング手段は、前記クラスタの重要度を算出し、重要度が予め定められた条件を満たすクラスタを抽出する。
【００１５】
本発明の請求項９に係る情報処理装置においては、前記算出手段は、前記特徴点と前記データ点との間のユークリッド距離を算出し、前記データ点との前記ユークリッド距離が近い順に、予め定められた個数の前記特徴点のノードを選択し、選択した特徴点のノードと前記データ点との前記リンク重みを正の値とし、選択した特徴点以外の特徴点のノードと前記データ点との前記リンク重みを０とする。
【００１６】
本発明の請求項１０に係るプログラムは、コンピュータを、複数の成分がベクトルで表現されるベクトルデータを取得する取得手段と、前記ベクトルデータをパラメトリック手法によりクラスタリングする第１クラスタリング手段と、前記ベクトルデータを表すデータ点と前記第１クラスタリング手段により得られた各クラスタの特徴点をノードとする二部ネットワークを生成する生成手段と、前記データ点のノードと、前記特徴点のノードとを結ぶリンク重みを算出する算出手段と、前記二部ネットワークにおけるリンクを介するノード間の遷移確率を前記リンク重みに応じて決定し、前記ノード間の遷移の確率過程の繰り返し計算を実行することにより、前記ノードのクラスタリングを行う第２クラスタリング手段として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明の請求項１に係る情報処理装置によれば、負の値を含むベクトルデータを、計算量を抑えてクラスタリングすることができる。
本発明の請求項２に係る情報処理装置によれば、ノンパラメトリックの手法でクラスタリングを行う構成と比較して、早くクラスタリングを行うことができる。
本発明の請求項３に係る情報処理装置によれば、リンクの重みを負の値とせずにクラスタリングを行うことができる。
本発明の請求項４に係る情報処理装置によれば、ベクトルデータに負の値が含まれていても、リンクの重みが負の値にならないようにすることができる。
本発明の請求項５に係る情報処理装置によれば、クラスタの中心に最も近いデータを特徴点とすることができる。
本発明の請求項６に係る情報処理装置によれば、混合ガウスモデルを用いない構成と比較して、特徴点の数を少なくすることができる。
本発明の請求項７に係る情報処理装置によれば、クラスタリングの計算量を抑えることができる。
本発明の請求項８に係る情報処理装置によれば、重要なクラスタを抽出することができうる。
本発明の請求項９に係る情報処理装置によれば、クラスタリングの精度を良くすることができる。
本発明の請求項１０に係るプログラムによれば、負の値を含むベクトルデータを、計算量を抑えてクラスタリングすることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態に係る情報処理装置の構成を示した図。
【図２】制御部１０が行う処理の流れを示したフローチャート。
【図３】二部ネットワークの一例を示した図。
【図４】制御部１０が行う処理の流れを示したフローチャート。
【発明を実施するための形態】
【００１９】
［実施形態］
図１は、本発明に係る情報処理装置１の構成の一例を示した図である。情報処理装置１は、コンピュータ装置であり、制御部１０、記憶部１１、操作部１２、表示部１３および通信部１４を備える。
【００２０】
通信部１４は、通信回線に接続されており、他のコンピュータ装置と通信を行う通信インターフェースの機能を有する。表示部１３は、ディスプレイ装置であり、制御部１０が行った処理の結果を表示する。操作部１２は、例えば情報処理装置１を操作するためのキーボードやマウス等である。
【００２１】
記憶部１１は、データを永続的に記憶する記憶装置を含み、データ点を表すベクトルデータを記憶する。ここで記憶されるベクトルデータは、数２のように実数値である複数の成分で表現されるデータである。複数の各成分は、例えば、画像形成装置内の各種センサの測定値（実数値）を表し、負の値を含むことができる。複数の各成分においては、例えば温度センサの測定値が含まれ、測定値は、正の値だけでなくゼロや負の値をとることがある。
【００２２】
【数２】
2019020806.tif 000004
【００２３】
データ全体がＮ個のデータ点ｘ1、・・・、ｘnからなるとき、これを数３に示したＮ×Ｄの設計行列で表す。
【００２４】
【数３】
2019020806.tif 000005
【００２５】
また、記憶部１１は、制御部１０が実行するプログラムを記憶する。記憶部１１が記憶するプログラムは、ベクトルデータからクラスタリングを行うプログラムである。記憶部１１に記憶されるプログラムは、通信部１４により電気通信回線を介して取得したものや、コンピュータ読み取り可能な記録媒体から取得したものであってもよい。
【００２６】
制御部１０は、ＣＰＵ（Central Processing Unit）とＲＡＭ（Random Access Memory）を備えており、記憶部１１に記憶されているプログラムを実行する。記憶部１１に記憶されているプログラムを制御部１０が実行すると、取得部１０１、第１クラスタリング部１０２、生成部１０３、算出部１０４、第２クラスタリング部１０５が実現し、ベクトルデータに対してクラスタリングを行う機能が実現する。
【００２７】
本発明に係る取得手段の一例である取得部１０１は、記憶部１１からベクトルデータを取得する。本発明に係る第１クラスタリング手段の一例である第１クラスタリング部１０２は、パラメトリックな方法でベクトルデータをクラスタリングする。本発明に係る生成手段の一例である生成部１０３は、ベクトルデータの個々のデータ点と、第１クラスタリング部１０２によるクラスタリングで得た個々のクラスタの平均をノードとする二部ネットワークを生成する。本発明に係る算出手段の一例である算出部１０４は、二部ネットワークにおける個々のデータ点のノードと、クラスタの平均のノードとを結ぶリンクの重みを算出する。本発明に係る第２クラスタリング手段の一例である第２クラスタリング部１０５は、生成部１０３が生成した二部ネットワークにおけるリンクを介するノード間の遷移確率を前記リンク重みに応じて決定し、ノード間の遷移の確率過程の繰り返し計算を実行することにより、二部ネットワークのノードのクラスタリングを行う。
【００２８】
図２は、プログラムを実行した制御部１０が行う処理の流れを示したフローチャートである。まず制御部１０（取得部１０１）は、記憶部１１に記憶されているベクトルデータを取得する（ステップＳＡ１）。次に制御部１０（第１クラスタリング部１０２）は、取得したベクトルデータを予め定められた方法でクラスタリングする（ステップＳＡ２）。ここでベクトルデータをクラスタリングする方法は、パラメトリックなクラスタリング方法であり、例えば、ｋ平均法（Ｋ−ｍｅａｎｓ法）である。ｋ平均法は、ベクトルデータを情報処理装置１のユーザが指定したＫ個の個数のクラスタに分割する。ｋ平均法でベクトルデータを分割し、数４の式によりＫ個のクラスタの中心ｍkが、各クラスタに属するベクトル点の平均として得られる。この中心ｍkは、クラスタの仮の中心でクラスタの特徴点となる。数４の式においてＣkは、クラスタｋ（ｋ＝１，・・・，Ｋ）を表し、Ｎkは、クラスタｋに属する要素（データ点）の個数を表す。ｋ平均法でクラスタリングを行い、中心ｍkをクラスタの特徴点とすることにより、ここでパラメトリックなクラスタリングを行わない構成と比較して、精度よく特徴点をデータ分布が局所的に密になっている部分の中心として選ぶこととなる。
【００２９】
【数４】
2019020806.tif 000006
【００３０】
ステップＳＡ２の処理においては、各クラスタにおけるデータ点が特定のモデルに従って分布すると仮定し、各クラスタにおいてデータ点が球状あるいは楕円状に分布すると仮定する。パラメトリックなクラスタリング方法の場合、ノンパラメトリックな方法のように全てのデータペア間の距離を求める必要がないため、ノンパラメトリックな方法と比較すると少ない計算量でクラスタリングが行われる。
【００３１】
制御部１０は、ステップＳＡ２の処理を行うことにより、各クラスタの平均で特徴点となる中心ｍkを特徴ノードとして特定する。制御部１０（生成部１０３）は、特徴ノードを特定すると、個々のデータ点と、ステップＳＡ２で得た個々のクラスタ平均をノードとする二部ネットワークを生成する（ステップＳＡ３）。二部ネットワークとは、二部グラフとも呼ばれ、ノードの集合が２つの部分集合に分割されており、同じ部分集合内のノード同士の間にリンクがないネットワーク（グラフ）のことである。二部ネットワークの一例を図３に例示する。図３では、三角形がデータ点に対応するデータ点ノードｎを表し、円形がクラスタの平均に対応する特徴ノードｍを表す。また、データ点ノードｎと特徴ノードｍを結ぶ直線がリンクである。
【００３２】
次に制御部１０（算出部１０４）は、データ点ノードｎと特徴ノードｍを結ぶリンクの重みｗnkを算出する（ステップＳＡ４）。ここで制御部１０は、例えば、数５に示したクラスタの平均ｍkを中心とする活性化関数を通じて重みｗnkを定める。数５の（１）の式は、各クラスタの中心ｍkと各データ点ｘnとの間のユークリッド距離である。数５の（２）の式は、データ点のノードｎと特徴ノードｍとを結ぶリンクの重みを、ユークリッド距離が短いほど正の値として大きくする活性化関数である。数５の式により、ベクトルデータの成分あるいは特徴点の成分に負の値があってもリンクの重みｗnkを正または０にし、負の値にならないようにすることができる。
【００３３】
【数５】
2019020806.tif 000007
【００３４】
次に制御部１０（第２クラスタリング部１０５）は、ステップＳＡ３で生成した二部ネットワークを対象として、ネットワークのモジュール分解の手法によるコミュニティ分解を行う（ステップＳＡ５）。このネットワークのモジュール分解は、次の数６の式で表現される。
【００３５】
【数６】
2019020806.tif 000008
【００３６】
数６の式において、ｐ（ｎ）はノードｎが持つ確率（そのノードにランダムウォーカーが存在する確率）である。またπkは、クラスタｋの事前確率であり、そのクラスタｋの重要度を示す。πkのｋについての総和は１である。またｐ（ｎ｜ｋ）は、クラスタｋにおけるノードｎの確率である。Ｋはクラスタｋの総数である。数６の式は、ノードｎの確率ｐ（ｎ）が、各クラスタｋにおける当該ノードｎの確率ｐ（ｎ｜ｋ）の組み合わせに分解できることを表している。
【００３７】
制御部１０（第２クラスタリング部１０５）が行う具体的な計算手法は、特願２０１７−０３４８８８に記載された方法と同様でよい。以下では、具体的な計算処理として、特願２０１７−０３４８８８に記載された方法に基づく処理の例を、図４のフローチャートを用いて説明する。
【００３８】
図４の手順では、まず制御部１０は、生成した二部ネットワークについての遷移確率行列Ｔnmを生成する（ステップＳＢ１）。遷移確率行列Ｔnmは、ネットワーク内のノードｍからノードｎへリンクを辿ってエージェント（言い換えれば、ノードｍが持つ確率値）が遷移（ランダムウォーク）する確率（即ち遷移確率）を行列として表現したものである。本実施形態においては、制御部１０は、例えばノードから出る１以上のリンクを、ステップＳＡ４で設定した重みｗnkに応じた確率でエージェントが選択するとみなして遷移確率行列Ｔnmを求める。即ち、制御部１０は、重みｗnkの値が大きいほど、そのリンクについての遷移確率の値を高くする。遷移確率行列については、更に特開２０１３−１６８１２７号公報、特開２０１６−０２９５２６号公報、特開２０１６−２１８５３１号公報も参照されたい。
【００３９】
次に、制御部１０は、定常リンク確率を計算する（ステップＳＢ２）。この計算では、まずステップＳＢ１で得られた二部ネットワークの遷移確率行列Ｔnmを用いて、その二部ネットワークにおける確率遷移（ランダムウォーク）の定常状態において各ノードが持つ確率（定常状態のノード確率）を計算する。この計算では、例えば次の数７の式の計算を定常状態となるまで繰り返す。
【００４０】
【数７】
2019020806.tif 000009
【００４１】
数７の式において、ｐt（ｎ）は、離散的な時刻ｔにおいてノードｎが持つ確率である。数７の式を繰り返し計算して定常状態となったときのｐt（ｎ）が、ノードｎの定常状態でのノード確率ｐstead（ｎ）である。
【００４２】
次に制御部１０は、各ノードｎの定常状態でのノード確率ｐstead（ｎ）から、定常状態でのリンク確率を次の数８の式に従って計算する。
【００４３】
【数８】
2019020806.tif 000010
【００４４】
リンク確率とは、ノード確率ｐt（ｎ）に対してそのノードから出るリンクｌ（エル）の遷移確率を乗じたものである。リンクｌについての定常状態のリンク確率（数８の式の左辺）は、そのリンクｌの起点のノードの定常状態のノード確率に対して、遷移確率行列Ｔnmに含まれる、そのリンクｌの起点ノードから終点ノードへの遷移確率を乗じたものである。
【００４５】
特開２０１６−０２９５２６号公報および特開２０１６−２１８５３１号公報では、Ｄ回の仮想的な観測で得られる観測データである通過情報τn(d)（ｄは１からＤまでの整数。ｎはノードの識別番号）を学習データとして用いた。これに対して以下に説明する例では、観測回数Ｄが十分大きい(ノード数Ｎよりもはるかに多い)という妥当な想定の下、τn(d)の代わりに実リンクｌに関する通過情報として、数９の式を用いる。
【００４６】
【数９】
2019020806.tif 000011
【００４７】
ここでｎはノードの識別番号である。またδはクロネッカーのδである。即ち、数９の式が定義するノードｎの実リンクｌに関する通過情報(学習データ)は、そのノードｎがその実リンクｌの終点ノード（terminal end of link l）または起点ノード（initial end of link l）に一致する場合に値が１となり、それ以外の場合は値が０となる。制御部１０は、二部ネットワークの情報からこのような通過情報を学習用のデータとして生成する。生成した通過情報は、後述するＥＭ（Expectation Maximization）アルゴリズムの計算で用いる。
【００４８】
また、本実施形態では、特開２０１６−０２９５２６号公報での仮想的な観測の各回ｄにおける複数のクラスタ（成分）全体に対するクラスタｋが占める割合γ(d)（ｋ）の代わりに、実リンクｌに関して後述する数１１の（３）の式で定義される割合γlk（チルダ付き）を用いる。
【００４９】
また、このような観測回数ｄから実リンクの番号ｌへの置き換えにより、関数の総和の表現は以下のように置き換えられる。
【００５０】
【数１０】
2019020806.tif 000012
【００５１】
後述する数１１の（１）の式の右辺第２項は、特開２０１６−０２９５２６号公報等に説明した同様の式に対してこのような置き換えを行ったものである。
【００５２】
図４の手順の説明に戻ると、次に制御部１０は、確率ｐt（ｎ｜ｋ）および重要度πknew、および割合γlkの初期値を仮決めし、繰り返し回数のカウンタｇの値を０に初期化する（ステップＳＢ３）。確率ｐt（ｎ｜ｋ）は、クラスタｋにおけるノードｎの確率である。また、重要度πknewは、クラスタｋの重要度である。またγlkは、リンクｌにおける、複数のクラスタ全体に対するクラスタｋが占める割合である。
【００５３】
次に制御部１０は、下記の数１１の（１）、（２）および（３）の式を用いてＥＭアルゴリズムの繰り返し計算を行う。
【００５４】
【数１１】
2019020806.tif 000013
【００５５】
すなわちまず制御部１０は、（３）の式を用いて割合γlkを計算する（ステップＳＢ４）（ＥＭアルゴリズムのＥステップ）。この計算の最初の繰り返しでは、ステップＳＢ３で仮決めした初期値を用いる。
【００５６】
次に制御部１０は、現在の確率ｐt（ｎ｜ｋ）および重要度πknewを一時刻前の値ｐt-1（ｎ｜ｋ）および重要度πkoldとする置き換えを行う（ステップＳＢ５）。そして、（１）の式および（２）の式に従って、確率ｐt（ｎ｜ｋ）および重要度πknewを計算する（ステップＳＢ６）（ＥＭアルゴリズムのＭステップ）。より詳しくは、ステップＳＢ６では、まず（２）の式に従って新たな重要度πknewを計算し、その後、この新たな重要度を用いて（１）の式の計算を行うことで、確率ｐt（ｎ｜ｋ）を求める。ここでαは、正の実数であって、クラスタの大きさを定めるパラメータであり、予め定めた値を用いればよい。
【００５７】
そして、制御部１０は、繰り返し計算の回数のカウンタｇをインクリメントし（ステップＳＢ７）、そのカウンタｇが予め定めた値Ｇに達したかどうかを判定し（ステップＳＢ８）、達していなければステップＳＢ４〜ＳＢ７の処理を繰り返す。値Ｇは、本実施形態の計算手法においてステップＳＢ４〜ステップＳＢ６の計算が収束するのに必要な繰り返し回数であり、実験や経験的知識等により予め定めておく。
【００５８】
制御部１０は、ステップＳＢ８で、カウンタｇが値Ｇに達したと判定した場合は、繰り返し計算が収束したものとして、図４の処理を終了する。制御部１０は、ステップＳＢ８の判定結果がＹｅｓとなった後、数１２の式に従ってノードｎのクラスタｋへの所属度γ（ｋ｜ｎ）を計算する（ステップＳＡ６）。
【数１２】
2019020806.tif 000014
【００５９】
この式のうちπkおよびｐ（ｎ｜ｋ）は、ＥＭアルゴリズムの計算（ステップＳＢ４〜ステップＳＢ６）の繰り返しにより最終的に求められたπknewおよびｐt（ｎ｜ｋ）である。数１２の式は、πkおよびｐ（ｎ｜ｋ）から、ベイズの定理により、ノードｎがクラスタｋに所属する度合い（所属度）を示すγ（ｋ｜ｎ）を計算する式である。制御部１０は、このようにして求めた所属度γ（ｋ｜ｎ）をクラスタリング結果として出力する（ステップＳＡ７）。所属度γ（ｋ｜ｎ）は、ノードｎのソフトクラスタリングの結果を表す情報である。
【００６０】
なお、別の例として、制御部１０は、求めた所属度γ（ｋ｜ｎ）を予め定めた閾値で二値化したものをクラスタリング結果として出力してもよい。このクラスタリング結果は、ノードｎが、所属度γ（ｋ｜ｎ）の値が閾値以上となるクラスタｋに対して所属する（二値化結果の値が１）ことを表す。定めた閾値の値によっては、ノードｎについて二値化結果が１となるクラスタｋが複数ある場合もあるが、これは一種のソフトクラスタリングの結果とみなせる。
【００６１】
また制御部１０は、繰り返し計算で用いたｋ＝１〜Ｋ（クラスタ総数）のＫ個のクラスタ全部についてのクラスタリング結果のうち、重要ないくつかのクラスタについてのクラスタリング結果のみを抽出し、最終的なクラスタリング結果として出力してもよい。重要なクラスタは、重要度πkに基づき判定すればよい。例えば、繰り返し計算が収束したときに得られた最終的な重要度πkが予め定めた閾値以上となるクラスタｋを重要なクラスタとして抽出したり、その重要度πkが上位から所定順位以内にあるクラスタｋを重要なクラスタとして抽出したりすればよい。
【００６２】
なお、ステップＳＢ８における収束の判定では、図４に例示した方法の代わりに、特開２０１３−１６８１２７号公報、特開２０１６−０２９５２６号公報および特開２０１６−２１８５３１号公報で説明したものと同様の、繰り返し毎の評価値Ｑｔの変化量が微小な値（閾値未満）となったときに、繰り返し計算が収束したと判定してもよい。
【００６３】
［変形例］
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限定されることなく、他の様々な形態で実施可能である。例えば、上述の実施形態を以下のように変形して本発明を実施してもよい。なお、上述した実施形態および以下の変形例は、各々を組み合わせてもよい。
【００６４】
上述した実施形態においては、重みｗnkのパラメータを、データから求める構成としてもよい。例えば、制御部１０は、数５の式のパラメータｄk2を数１３の式に従って求めてもよい。
【００６５】
【数１３】
2019020806.tif 000015
【００６６】
数１３の式において、Ｃkは、ステップＳＡ２においてｋ平均法で求めたクラスタを表し、Ｎkは、Ｃkに属するデータ点の数を表す。この構成によれば、数５の活性化関数のパラメータをベクトルデータから得ることができる。
【００６７】
上述した実施形態においては、リンクの重みを数５の式で求めているが、リンクの重みを求める方法は、実施形態の方法に限定されるものではない。例えば、逆べき関数である数１４の式によりリンクの重みｗnkを求めてもよい。数１４の式においては、Ｃは、Ｃ＞０の定数であり、γ＞０である。
【００６８】
【数１４】
2019020806.tif 000016
【００６９】
また、データ点ｘnとのユークリッド距離が近い順に予め定められたＭ個の特徴ノードを選び、選んだノードとデータ点との間のリンクの重みを例えばｗnk＝１として正の値とし、選んだ特徴ノード以外の特徴ノードとデータ点とのリンクの重みをｗnk＝０としてもよい。本発明においては、複数の特徴点（あるいは、それらに対応する特徴ノード）を選ぶ必要があり、クラスタリングの精度はこれらをどのように選ぶかに依存する。データ点の分布が密なところに特徴点を選ぶのは、クラスタリングの精度を良くする方法の一つである。本変形例によれば、特徴点をデータ分布が局所的に密になっている部分の中心として選ぶため、クラスタリングの精度が良くなる。
【００７０】
上述した実施形態においては、ステップＳＡ２において、ベクトルデータをｋ平均法でクラスタリングしているが、ステップＳＡ２においてベクトルデータをクラスタリングする方法は、ｋ平均法に限定されるものではない。例えば、ｋ平均法に替えて、Ｋ−ｍｅｄｏｉｄｓ法でクラスタリングしてもよい。Ｋ−ｍｅｄｏｉｄｓ法は、ベクトルデータをユーザが指定したＫ個のクラスタに分割する点ではｋ平均法と同様であるが、クラスタの中心をデータ点の平均で定める替わりに、各クラスタに属するデータ点の中からそのクラスタの代表点を定める。ｋ平均法でクラスタリングを行った場合、特徴点は、データ点と必ずしも一致しないが、Ｋ−ｍｅｄｏｉｄｓ法でクラスタリングした場合、データ分布が局所的に密になっている部分の中心に最も近いデータ点を特徴点として選ぶこととなる。
【００７１】
そして、Ｋ−ｍｅｄｏｉｄｓ法でクラスタリングして得られたクラスタｋの代表点をｒkとし、Ｋ個のクラスタの代表点のそれぞれに特徴ノードを対応させる。代表点は、クラスタ内の点であり、その点以外のクラスタ内の点との非類似度の総和が最少となる点とする。そして、ステップＳＡ２においてＫ−ｍｅｄｏｉｄｓ法でクラスタリングを行った場合、ステップＳＡ４で求めるリンクの重みｗnkを数１５の式により算出する。数１５の（１）の式は、各クラスタの代表点ｒkと各データ点ｘnとの間のユークリッド距離である。数１５の（２）の式は、データ点のノードｎと特徴ノードｒとを結ぶリンクの重みを、ユークリッド距離が短いほど正の値として大きくする活性化関数である。なお、リンクの重みは、ベクトルデータをＫ−ｍｅｄｏｉｄｓ法でクラスタリングした場合、逆べき関数である数１５の（３）の式により求めてもよい。数１５の（３）式においては、Ｃは、Ｃ＞０の定数であり、γ＞０である。また、ベクトルデータをＫ−ｍｅｄｏｉｄｓ法でクラスタリングした場合、データ点ｘnとの距離が近い順に予め定められたＭ個の特徴ノードを選び、選んだノードとデータ点との間のリンクの重みを例えばｗnk＝１として正の値とし、選んだ特徴ノード以外の特徴ノードとデータ点とのリンクの重みをｗnk＝０としてもよい。
【００７２】
【数１５】
2019020806.tif 000017
【００７３】
また、ステップＳＡ２においては、混合ガウスモデルを用いてベクトルデータをクラスタリングしてもよい。混合ガウスモデルについては、例えば、Bishop, C.M. Pattern Recognition and Machine Learning (Springer)の9章を参照されたい。混合ガウスモデルを用いてベクトルデータをクラスタリングする方法では、Ｋ個のガウス分布が得られる。制御部１０は、得られたＫ個のガウス分布のそれぞれに特徴ノードを対応させる。そして、ステップＳＡ２において混合ガウスモデルを用いてベクトルデータをクラスタリングした場合、ステップＳＡ４で求めるリンクの重みｗnkを数１６の式により算出する。数１６の式は、ガウス分布に対応する特徴ノードｋとデータ点のノードｎとの間のリンクの重みを、データ点ｘnのクラスタｋへの寄与度として定めている。そして、例えば、寄与度γnkをリンクの重みｗnkとする。
【００７４】
【数１６】
2019020806.tif 000018
【００７５】
混合ガウスモデルは、データの分布の濃淡を、局所的に楕円体で近似する。楕円体の各軸の長さは、例えば、データに合わせて情報処理装置１のユーザが操作部１２で指定することにより設定される。一方、ｋ平均法あるいはＫ−ｍｅｄｏｉｄｓ法は、局所的なデータの分布が球であると仮定している。混合ガウスモデルを用いた場合の方がより特徴点の数を少なくなり、特徴点の数が少なくなることにより、クラスタリングの計算量が抑えられる。
【符号の説明】
【００７６】
１…情報処理装置、１０…制御部、１１…記憶部、１２…操作部、１３…表示部、１４…通信部、１０１…取得部、１０２…第１クラスタリング部、１０３…生成部、１０４…算出部、１０５…第２クラスタリング部。
【図１】
2019020806.tif 000020
【図２】
2019020806.tif 000021
【図３】
2019020806.tif 000022
【図４】
2019020806.tif 000023