TOP > 国内特許検索 > 情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体 > 明細書

明細書 :情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成29年11月24日(2017.11.24)
発明の名称または考案の名称 情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体
国際特許分類 G06F  17/30        (2006.01)
FI G06F 17/30 350C
国際予備審査の請求 未請求
全頁数 29
出願番号 特願2016-570732 (P2016-570732)
国際出願番号 PCT/JP2016/051909
国際公開番号 WO2016/117698
国際出願日 平成28年1月22日(2016.1.22)
国際公開日 平成28年7月28日(2016.7.28)
優先権出願番号 2015011853
優先日 平成27年1月23日(2015.1.23)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , ST , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JP , KE , KG , KN , KP , KR , KZ , LA , LC , LK , LR , LS , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT , TZ , UA , UG , US
発明者または考案者 【氏名】原 一夫
【氏名】鈴木 郁美
出願人 【識別番号】504202472
【氏名又は名称】大学共同利用機関法人情報・システム研究機構
個別代理人の代理人 【識別番号】100106909、【弁理士】、【氏名又は名称】棚井 澄雄
【識別番号】100188558、【弁理士】、【氏名又は名称】飯田 雅人
【識別番号】100161207、【弁理士】、【氏名又は名称】西澤 和純
【識別番号】100141139、【弁理士】、【氏名又は名称】及川 周
審査請求 未請求
要約 情報処理装置は、複数のデータにより構成される第1データセット内の処理対象データと、検索対象データとしてのクエリとの間の類似度を算出する第1算出部と、前記第1データセット内の一部のデータにより構成される第2データセットを、前記処理対象データごとに特定する特定部と、前記特定部が特定する前記第2データセットから、前記処理対象データごとの基準を算出する第2算出部と、前記第1算出部が算出する前記類似度と、前記第2算出部が算出する基準とを用いて、前記処理対象データごとにスコアを算出する第3算出部と、を含む。
特許請求の範囲 【請求項1】
複数のデータにより構成される第1データセット内の処理対象データと、検索対象データとしてのクエリとの間の類似度を算出する第1算出部と、
前記第1データセット内の一部のデータにより構成される第2データセットを、前記処理対象データごとに特定する特定部と、
前記特定部が特定する前記第2データセットから、前記処理対象データごとの基準を算出する第2算出部と、
前記第1算出部が算出する前記類似度と、前記第2算出部が算出する基準とを用いて、前記処理対象データごとにスコアを算出する第3算出部と、
を含む情報処理装置。
【請求項2】
前記クエリについて、前記第1データセットから第1の所定数のデータを、前記スコアに基づいて抽出する抽出部
をさらに備える請求項1に記載の情報処理装置。
【請求項3】
前記特定部は、前記第1データセット内のデータと前記処理対象データとの間の類似度に基づいて、前記第2データセットを特定する
請求項1又は請求項2に記載の情報処理装置。
【請求項4】
前記特定部は、前記第1データセット内のデータと前記処理対象データとの間の類似度が高い順に第2の所定数のデータを抽出することにより、前記第2データセットを特定する
請求項1から請求項3のいずれか一項に記載の情報処理装置。
【請求項5】
前記第2の所定数とは、前記第1データセット内の2つのデータの全ての組み合わせにおける類似度に基づいて、前記第1データセット内の各々のデータに対して当該類似度が高い順に第1の所定数のデータを抽出する場合に、前記処理対象データが抽出される回数と、前記処理対象データと当該処理対象データの基準との間の類似度と、の間の相関が最大になる数である
請求項4に記載の情報処理装置。
【請求項6】
前記第2の所定数とは、前記第1データセット内の2つのデータの全ての組み合わせにおける類似度に基づいて、前記第1データセット内の各々のデータに対して当該類似度が高い順に第1の所定数のデータを抽出する場合に、前記処理対象データが抽出される回数に関する分布の歪度が最小になる数である
請求項4に記載の情報処理装置。
【請求項7】
前記第1算出部は、内積と、コサインと、距離と、カーネルとのうちの少なくともいずれか1つに基づいて前記類似度を算出する
請求項1から請求項6のいずれか一項に記載の情報処理装置。
【請求項8】
情報処理装置が、
複数のデータにより構成される第1データセット内の処理対象データと、検索対象データとしてのクエリとの間の類似度を算出する第1ステップと、
前記第1データセット内の一部のデータにより構成される第2データセットを、前記処理対象データごとに特定する第2ステップと、
前記第2ステップにおいて特定した前記第2データセットから、前記処理対象データごとの基準を算出する第3ステップと、
前記第1ステップにおいて算出した前記類似度と、前記第3ステップにおいて算出した基準とを用いて、前記処理対象データごとにスコアを算出する第4ステップと、
を含む情報処理方法。
【請求項9】
コンピュータに、
複数のデータにより構成される第1データセット内の処理対象データと、検索対象データとしてのクエリとの間の類似度を算出する第1ステップと、
前記第1データセット内の一部のデータにより構成される第2データセットを、前記処理対象データごとに特定する第2ステップと、
前記第1ステップにおいて特定した前記第2データセットから、前記処理対象データごとの基準を算出する第3ステップと、
前記第1ステップにおいて算出した前記類似度と、前記第3ステップにおいて算出した基準とを用いて、前記処理対象データごとにスコアを算出する第4ステップと、
を実行させるためのプログラム。
【請求項10】
コンピュータに、
複数のデータにより構成される第1データセット内の処理対象データと、検索対象データとしてのクエリとの間の類似度を算出する第1ステップと、
前記第1データセット内の一部のデータにより構成される第2データセットを、前記処理対象データごとに特定する第2ステップと、
前記第1ステップにおいて特定した前記第2データセットから、前記処理対象データごとの基準を算出する第3ステップと、
前記第1ステップにおいて算出した前記類似度と、前記第3ステップにおいて算出した基準とを用いて、前記処理対象データごとにスコアを算出する第4ステップと、
を実行させるためのプログラムを記録したコンピュータ読み取り可能な非一時記憶媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体に関する。詳しくは、高次元又は/及び大規模データセットに対するk近傍検索で発生するハブを軽減する類似度演算システム及び類似度演算方法に関する。
2015年1月23日に、日本に出願された特願2015-11853号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【0002】
k近傍法は実装が簡素であるにもかかわらず分類や情報検索で有効であるために多くの分類システムや情報検索システムで用いられている。しかし、データセット内のデータが高次元空間に存在するとみなせる場合(例えばデータが多数の属性を持つベクトルとして表現される場合)、他のデータのk近傍に頻出するデータ(ハブと呼ばれる)が出現し、結果としてk近傍法の性能は低下する。このハブの現象は、Radovanovicら(非特許文献1参照)により、ごく最近発見されたデータの高次元性にまつわる現象である。一方、発明者らは「(グローバル)センタリング」、すなわち、原点をデータセットの平均(グローバルセントロイド)に移動することにより、k近傍法におけるハブの影響を軽減できることを発表した(非特許文献2参照)。ハブはデータセットの平均の近くに位置するデータであり、センタリングはハブを軽減するのに有効である。
【先行技術文献】
【0003】

【非特許文献1】Radovanovic,M;Nanopoulos,A.;and Ivanovic,M.2010a,“Hubs in space:Popular nearest neighbors in high-dimensional data.” Journal of Machine Learning Research 11:2487-2531,2010年
【非特許文献2】鈴木郁美、原一夫、新保仁「k近傍法でハブを軽減する類似度尺度」、情報処理学会研究報告、自然言語処理研究会、2012-NL-209、No.11、pp.1-8、2012、2013年
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、次元dがさほど大きくなくても、データ数nが大きくなると、例えばn=10,000、d=500、異種のハブが存在することが解った。そして、かかるハブはセンタリングでは軽減できないという問題があった。
本発明は、次元数が大きいときだけでなく、データ数が大きいときに出現するハブを軽減できる情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【0005】
本発明の第1の態様に係るハブを軽減する類似度演算システム1は、例えば図7に示すように、検索先となる高次元及び/又は大規模データセット、及び、検索対象データとしてのクエリqを設定するデータセット・クエリ設定部11と、データセット・クエリ設定部11にて設定されたクエリq及びデータセット内の各データxについて、ベースとする類似度尺度を用いて、クエリqと各データxとの類似度Sim(x;q)を演算するベース類似度スコア演算部12と、前記設定されたデータセット内の各データxについて、データセット内の他のデータのk近傍への出現回数N(x)を計算するハブ度演算部13と、ハブ度演算部13で各データxに対して計算された出現回数N(x)を用い、各データの近傍に入るデータの集合の要素がデータセット全体を一様にカバーせず局在化する度合いに応じて、各データの近傍に入るデータからなるローカルな部分集合の中心としてのローカルセントロイドcκ(x)を計算すると共に、各データについてローカルセントロイドcκ(x)を用いた類似度演算により各データのペナルティスコアとして用いるローカルアフィニティLocalAffinity(x)を計算することによりローカライズドセンタリングの前工程を実行するペナルティスコア演算部14と、ベース類似度スコア演算部12にて計算されたクエリと各データとの類似度Sim(x;q)とペナルティスコア演算部14にて計算されたローカルアフィニティLocalAffinity(x)を用い、各データに対して総合スコアを計算することによりローカライズドセンタリングの後工程を実行する総合スコア演算部15とを備える。
【0006】
ここにおいて、高次元及び/又は大規模データセットとは、次元数が大きい(あるいは次元数が大きいとみなせる)及び/又はデータ数が大きいデータセットをいう。例えば、生命情報学分野では、機能未知の配列データの機能を、機能既知の配列データに対する相同性を頼りに予測しようとするが、検索先として使用される機能既知のDNAの塩基配列あるいはタンパク質のアミノ酸配列のデータベースは、過去数十年間に世界中の研究成果を集めた膨大な数の配列データを格納する、大規模なデータセットである。また、DNAの塩基配列あるいはタンパク質のアミノ酸配列の相同性検索アルゴリズムとして広く使われるブラスト(BLAST:Basic Local Alignment Search Tool)は、個々の配列データを特徴付ける属性として、配列内に出現しうるあらゆる部分配列(及びその組み合わせ)を用いるため、配列データを本質的に高次元データとみなして扱う。ここでの高次元及び/又は大規模データセットとは、ハブが発生するあらゆるデータセットを意味する。なぜなら、現在までに報告されているハブは、データセットが高次元である場合と、データセットが大規模である場合に限られて発生しているからである。敢えて数値化するとすれば例えば、高次元は人間の直感で理解が難しくなる4次元以上をいい、大規模はデータ数100以上をいい、1000以上が好ましい。なお、後者のハブは、本発明者らにより発見されたハブである。
【0007】
また、ここでのデータセットとは、検索対象データ(クエリ)に対する類似データの検索先となるデータ集合をいう。例えば、生命情報学分野における配列の相同性検索においては、データセットとして用いられるのは、過去に世界中の研究成果として蓄積された塩基配列データ又はアミノ酸配列データからなる配列データ集合群、又はそれらの部分集合である。
また、ここでの類似度尺度とは、2つのデータの類似性を測る尺度として使用できるものすべてを含む。典型的には、内積、コサイン、距離である。内積は2つのベクトルデータのスカラー積であり、コサインは長さ1に規格化された2つのベクトルデータの内積である。さらに、内積の一般化とみなせる(機械学習分野で主に呼ばれるところの各種の)カーネルも含む。距離の典型は、2つのベクトルデータ間のユークリッド距離(lノルム)であるが、ユークリッド距離を一般化した距離(マンハッタン距離やlノルムなど)も含む。さらに、ドメインの知識を持つ人間が各タスクの目的に応じて適宜定めた類似度スコア計算方法(BLASTなど)が出力する類似度も、ここでの類似度尺度に含まれる。
【0008】
また、「ベースとする類似度尺度」は、ベース類似度スコア演算部にて類似度Sim(x;q)を計算するとき、及びペナルティスコア演算部にてローカルアフィニティLocalAffinity(x)を計算するときに使用される類似度尺度である。類似度Sim(x;q)を計算するとき及びローカルアフィニティLocalAffinity(x)を計算するときに使用される類似度尺度として、上記全ての類似度尺度を使用できる。また、高次元及び/又は大規模データセットを検索先とする場合、ベース類似度スコア演算部にて計算されるスコアである類似度Sim(x;q)はハブを発生させ易い。そこで、ベース類似度スコア演算部にて計算されるスコアをそのまま用いず、ハブに成り易い程度に応じて各データに対してペナルティスコアを計算し、ベースとするスコアからペナルティスコアを差し引いた総合スコアを用いる。すなわち、ハブに成り易いデータの総合スコアを小さくすることで、ハブに成り易いデータを他のデータのk近傍に入りにくくするものである。
【0009】
また、ハブ度演算部13は、データセット内の各データxに対し、他のデータのk近傍に出現する回数N(x)を計算する。さらに、N(x)の分布の歪度を計算する。k近傍になるとは、類似度が高い方からk番目以内になることをいう。また、N(x)が大きいほど、データxがハブであることを意味する。さらに、N(x)の分布の歪度は、SNk=E〔(N-μNk/σNk〕(E〔 〕は期待値を計算するオペレータ、μNkとσNkはそれぞれN(x)の分布の平均と分散である)と計算する。N(x)の分布の歪度が大きいほど、データセットにハブが存在することを意味する。
また、大規模なデータセット、すなわち、データ数nが大きいデータセットにおいては、各データxについてその近傍に入るデータの集合を考えたとき、その集合がデータセット全体を一様にカバーせず、データセットに局在する部分集合を形成し易い、という事実がある。そこで、ローカルセグメントサイズκをパラメタとし、各データに対してそのκ近傍に入るデータをローカルな部分集合として定め、このローカルな部分集合の中心としてローカルセントロイドcκ(x)を定義する。また、各データの近傍に入るデータの集合の要素がデータセット全体を一様にカバーせず局在化する度合いに応じて、ローカルセントロイドcκ(x)を計算するのは、ハブ度演算部13で各データxに対して計算された出現回数N(x)に応じてペナルティを与えるためである。なお、ローカルセントロイドは各データにより異なるが必ず存在するとみなしてよい。したがって、ローカルセントロイドの有無を判断する必要はない。
具体的には、ローカルセントロイドcκ(x)は例えば、式(2A)で求められる(段落0031参照)。パラメタκにより隣接データの範囲が変わるので、ローカルセントロイドcκ(x)も変わり得る。ローカライズドセンタリングとは、ハブ度と相関が高くなるようなローカルなセントロイドを見つけ出し、ローカルなセントロイドとの類似度をペナルティとして与えることをいう。例えば、式(5)が使用される(段落0037参照)。類似度尺度にはベースとする類似度尺度を使用できる。ここでは、ローカライズドセンタリングは、先にローカルアフィニティを計算し、その後総合スコアを計算することにより実行される。すなわち、ベース類似度スコア演算部にて計算されるスコア(ベースとするスコア)から、ハブに成り易い程度に応じて各データに対して付与するペナルティスコア(ローカルアフィニティ)を計算し、ベースとするスコアからペナルティスコアを差し引いた総合スコアを計算することにより実行される。
また、ローカルアフィニティとは、各データx∈Dについて、xとそのκ近傍(κNNすなわちκ-Nearest-Neighbor)に属するデータ間の平均類似度として定義される(段落0031、式(2)参照)。また、ペナルティスコアとして用いるとは、ローカルセントロイドcκ(x)近傍のデータの類似度スコアを低くするために用いることをいい、ここでは、ローカルアフィニティをペナルティスコアとして差し引いている。
【0010】
本態様のように構成すると、ローカルセントロイドという新しい概念に基づいて計算されるローカルアフィニティが、データのハブ度と高い相関を持つため、それをペナルティスコアとして用いることにより、次元数が大きいときだけでなく、データ数nが大きいときに出現するハブをも軽減できる。なお、既存手法において用いられたグローバルセントロイドでは、次元数dが大きいときに生じるハブは軽減できるがデータ数nが大きいときに生じるハブを軽減できなかった。
【0011】
本発明の第2の態様に係るハブを軽減する類似度演算システム1は、第1の態様において、ベースとする類似度尺度として、内積、コサイン、距離、内積の一般化とみなせるカーネル、又は、ドメインの知識を持つ人間が各タスクの目的に応じて適宜定めた類似度スコア計算方法が出力する類似度尺度を用いる。
ここにおいて、内積の一般化とみなせるカーネルとは、機械学習分野で主に呼ばれるところの各種のカーネルをいう。また、ドメインの知識を持つ人間が各タスクの目的に応じて適宜定めた類似度スコア計算方法が出力する類似度にはBLASTなどが含まれる。
本態様のように構成すると、内積、コサイン、距離、カーネル、BLASTスコア等は演算が簡素で扱いやすく、また、ローカルアフィニティをペナルティスコアとして用いるローカライズドセンタリングによりハブを軽減できる実績が得られている。なお、ローカライズドセンタリングによりハブが軽減しさえすれば、その他の類似度尺度も使用できる。
【0012】
本発明の第3の態様に係るハブを軽減する類似度演算システム1は、第1ないし第3のいずれかの態様において、ペナルティスコア演算部14は、ローカルアフィニティLocalAffinity(x)を計算する際のパラメタであるローカルセグメントサイズκを、出現回数N(x)とローカルアフィニティLocalAffinity(x)との相関が最大になるように定める。
【0013】
ここにおいて、ローカルアフィニティは、各データx∈Dについて、xとそのκ近傍(κはローカルセグメントサイズであり、ローカルアフィニティを定めるパラメタである)に属するデータ間の平均類似度として定義され、明細書中の式(2)で表される(段落0031参照)。
本態様のように構成すると、ローカルセグメントサイズκを適切に定めることができる。
【0014】
本発明の第4の態様に係るハブを軽減する類似度演算方法は、例えば図8に示すように、検索先となる高次元及び/又は大規模データセット、及び、検索対象データとしてのクエリの設定を行うデータセット・クエリ設定工程(S101)と、データセット・クエリ設定工程(S101)にて設定されたクエリとデータセット内の各データについて、ベースとする類似度尺度を用いてクエリと各データとの類似度を計算するベース類似度スコア演算工程(S102)と、設定されたデータセット内の各データについて、データセット内の他のデータのk近傍への出現回数N(x)を計算するハブ度演算工程(S103)と、ハブ度演算工程(S103)で各データに対して計算された、出現回数N(x)を用い、各データの近傍に入るデータの集合の要素がデータセット全体を一様にカバーせず局在化する度合いに応じて、各データの近傍に入るデータからなるローカルな部分集合の中心としてのローカルセントロイドcκ(x)を計算すると共に、各データについてローカルセントロイドcκ(x)を用いた類似度演算により各データのペナルティスコアとして用いるローカルアフィニティLocalAffinity(x)を計算することによりローカライズドセンタリングの前工程を実行するペナルティスコア演算工程(S106)と、ベース類似度スコア演算工程(S102)にて計算されたクエリと各データとの類似度Sim(x;q)とペナルティスコア演算工程(S106)にて計算されたローカルアフィニティLocalAffinity(x)を用い、各データに対して総合スコアを計算することによりローカライズドセンタリングの後工程を実行する総合スコア演算工程(S107)とを備える。
【0015】
ここにおいて、ローカライズドセンタリングは前工程と後工程からなる。
本態様のように構成すると、(次元数dが大きいときに生じるハブは軽減できるがデータ数nが大きいときに生じるハブを軽減できない既存手法で用いられたグローバルセントロイドに対し)本発明が新たに導入するローカルセントロイドという概念に基づいて計算されるローカルアフィニティは各データのハブ度と高い相関を持つため、それをペナルティスコアとして用いることにより、次元数が大きいときだけでなく、データ数nが大きいときに出現するハブをも軽減できる。
【0016】
本発明の第5の態様に係るハブを軽減する類似度演算方法は、第4の態様において、ベースとする類似度尺度として、内積、コサイン、距離、内積の一般化とみなせるカーネル、又は、ドメインの知識を持つ人間が各タスクの目的に応じて適宜定めた類似度スコア計算方法が出力する類似度これらに基づいて作成された類似度尺度を用いる。
このように構成すると、内積、コサイン、距離、カーネル、BLASTスコア等は演算が簡素で扱いやすく、また、ローカルアフィニティをペナルティスコアとして用いるローカライズドセンタリングによりハブを軽減できる実績が得られている。なお、ローカライズドセンタリングによりハブが軽減する限りは、その他の類似度尺度も使用できる。
【0017】
本発明の第6の態様に係るハブを軽減する類似度演算方法は、第4又は第5の態様において、ペナルティスコア演算工程(S106)は、ローカルアフィニティLocalAffinity(x)を計算する際のパラメタであるローカルセグメントサイズκを、出現回数N(x)とローカルアフィニティLocalAffinity(x)との相関が最大になるように定める。
このように構成すると、ローカルセグメントサイズκを適切に定めることができる。
【0018】
本発明の第7の態様に係るプログラムは、第4ないし第6のいずれかの態様におけるハブを軽減する類似度演算方法をコンピュータに実行させるためのプログラムである。
【0019】
本発明の第8の態様に係る記録媒体は、第7の態様におけるプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【0020】
本発明の一態様によれば、次元数dが大きいときに出現するハブのみならず、データ数nが大きいときに出現するハブを軽減できる情報処理装置、情報処理方法、プログラム、及び非一時記憶媒体を提供できる。
【図面の簡単な説明】
【0021】
【図1】高次元人工データセット(d=4000)におけるハブを説明するための第1図である。図1は、センタリング(グローバルセンタリング)前のN10(k=10のとき、各データが他のデータのk近傍に出現する回数)の分布を示す図である。
【図2】高次元人工データセット(d=4000)におけるハブを説明するための第2図である。図2は、センタリング(グローバルセンタリング)後のN10(k=10のとき、各データが他のデータのk近傍に出現する回数)の分布を示す図である。
【図3】高次元人工データセット(d=4000)におけるハブを説明するための第3図である。図3は、各データのN10とグローバルアフィニティ(データセットの平均への類似度)との関係(グローバルセンタリング前)を示す散布図である。
【図4】大規模人工データセット(n=10000)におけるハブを説明するための第1図である。図4は、センタリング(グローバルセンタリング)前のN10の分布を示す図である。
【図5】大規模人工データセット(n=10000)におけるハブを説明するための第2図である。図5は、センタリング(グローバルセンタリング)後のN10の分布を示す図である。
【図6】大規模人工データセット(n=10000)におけるハブを説明するための第3図である。図6は、各データのN10とグローバルアフィニティ(データセットの平均への類似度)との関係(グローバルセンタリング前)を示す散布図である。
【図7】データ数n及び次元数dを変数として、生成した様々な人工データセットを用いて作成した、N10分布の歪度の等高線第1図である。図7は、センタリング(グローバルセンタリング)前の等高線図である。数値が高いほど、当該データセットにハブが多く存在することを示す。なお、等高線図における+マークは、生成したデータセット(のデータ数nと次元数d)に対応する。
【図8】データ数n及び次元数dを変数として、生成した様々な人工データセットを用いて作成した、N10分布の歪度の等高線第2図である。図8は、センタリング(グローバルセンタリング)後の等高線図である。数値が高いほど、当該データセットにハブが多く存在することを示す。
【図9】図7、8と同じ人工データセットを用いたときの、ローカライズドセンタリング後のN10分布の歪度の等高線図である。
【図10】図7、8と同じ人工データセットを用いたときの、グローバル対ローカルアフィニティ比を示す等高線図である。
【図11】図4-6と同じ大規模人工データセット(n=10000)を用いたときの、各データのN10とローカルアフィニティ(ローカルセントロイドへの類似度)の相関(ローカライズドセンタリング前)を示す散布図である。
【図12】図4-6と同じ大規模人工データセット(n=10000)を用いたときの、ローカライズドセンタリング後のN10分布を示す図である。
【図13】図1-3と同じ高次元人工データセット(d=4000)を用いたときの、各データのN10とローカルアフィニティ(ローカルセントロイドへの類似度)の相関を示す散布図である。
【図14】実施例1におけるハブを軽減する類似度演算システムの構成例を示す図である。
【図15】実施例1におけるハブを軽減する類似度演算方法の処理フロー例を示す図である。
【図16】実世界データセットに対する、データ数nとN10分布の歪度との関係を示す折れ線グラフである。(i)はグローバルセンタリングやローカライズドセンタリングを施す前の折れ線グラフ(比較のベースライン)である。(ii)はグローバルセンタリング後、(iii)はローカライズドセンタリング後の折れ線グラフである。(iv)はグローバル対ローカルアフィニティ比の折れ線グラフである。使用データセットはWebKBである。
【図17】実世界データセットに対する、データ数nとN10分布の歪度との関係を示す折れ線グラフである。(i)はグローバルセンタリングやローカライズドセンタリングを施す前の折れ線グラフ(比較のベースライン)である。(ii)はグローバルセンタリング後、(iii)はローカライズドセンタリング後の折れ線グラフである。(iv)はグローバル対ローカルアフィニティ比の折れ線グラフである。使用データセットはReuters-52である。
【図18】実世界データセットに対する、データ数nとN10分布の歪度との関係を示す折れ線グラフである。(i)はグローバルセンタリングやローカライズドセンタリングを施す前の折れ線グラフ(比較のベースライン)である。(ii)はグローバルセンタリング後、(iii)はローカライズドセンタリング後の折れ線グラフである。(iv)はグローバル対ローカルアフィニティ比の折れ線グラフである。使用データセットはTDT2-30である。
【図19】実世界データセットに対する、データ数nとN10分布の歪度との関係を示す折れ線グラフである。(i)はグローバルセンタリングやローカライズドセンタリングを施す前の折れ線グラフ(比較のベースライン)である。(ii)はグローバルセンタリング後、(iii)はローカライズドセンタリング後の折れ線グラフである。(iv)はグローバル対ローカルアフィニティ比の折れ線グラフである。使用データセットは20Newsgroupsである。
【図20】図16-19で使用したのと同じ実世界データセットを用いて行った、k近傍法による多クラス分類の精度、及び、N10分布の歪度を示す表形式の第1図である。
【図21】図16-19で使用したのと同じ実世界データセットを用いて行った、k近傍法による多クラス分類の精度、及び、N10分布の歪度を示す表形式の第2図である。
【図22】図16-19で使用したのと同じ実世界データセットを用いて行った、k近傍法による多クラス分類の精度、及び、N10分布の歪度を示す表形式の第3図である。
【図23】図16-19で使用したのと同じ実世界データセットを用いて行った、k近傍法による多クラス分類の精度、及び、N10分布の歪度を示す表形式の第4図である。
【発明を実施するための形態】
【0022】
図面を参照して以下に本発明の実施の形態について説明する。なお、各図において、互いに同一又は相当する部分には同一符号を付し、重複した説明は省略する。

【0023】
〔高次元データセット中でのハブ〕
ハブは高次元空間での最近傍検索に係る現象として知られている。D⊂Rをd次元空間上のデータセットとする。N(x)は、データx∈DがDに含まれる他データのk近傍に含まれる回数を示すものとする。次元dが増加すると、Nの分布の形状は右に長い尾を引くように変化する。すなわち、少数のデータが予期しない高いN値を持つ。このようなデータをハブという。ここで、テキスト文書集合を模した人工データセット(各データが一つのテキスト文書に対応する)を用いて、ハブの出現を例示する。テキスト文書集合を模したデータセットDを生成するに際し、テキスト文書の表現として通常用いられるバッグオブワーズ「bag-of-words」モデルによって、非負値を要素として持つd次元ベクトルを、各テキスト文書を模したベクトルデータとして生成する。n=│D│を生成するデータ数とするとき、まずn個のベクトルを生成し、これらをゼロベクトルとして初期化する。次に、各次元i=1,・・・,dについて、対数正規分布LogNorm(5,1)(5,1はそれぞれ、平均、分散に係るパラメタ)に従う実数を生成し、端数を丸めた整数nを得る。そして、データセットDのn個のベクトルから一様分布に従ってn個のべクトルを選び、選ばれたベクトルの第i成分を0でない値に置換する。具体的には、〔0,1〕の一様分布に従う値(0~1の間の実数)に置換する。最後に、全てのベクトルを長さが1になるように正規化する。ここでは、一例として、類似度尺度として内積を使用するが、全てのベクトルの長さが1に等しいため、内積はコサインに等しい。なお、上述したように、類似度尺度としては、内積、コサイン、距離等の別の尺度をベースとしてもよく、いずれの尺度を用いるかは、ユーザにより選択可能としてもよい。

【0024】
図1-3は高次元データセット(d=4000)におけるハブを説明するための図である。図1、2はそれぞれセンタリング(グローバルセンタリング)前後のN10(k=10のとき、各々のデータが他のデータのk近傍に出現する回数)の分布を示す図である。図において、ハブ、すなわち、極端に大きなN10値を持つデータの存在を確認できる。
データセットにどの程度ハブが存在するかを、Radovanovicら(Radovanovic,M;Nanopoulos,A.;and Ivanovic,M.2010a,Hubs in space:Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research 11:2487-2531)に従って、N分布の歪度 SNk=E〔(N-μNk/σNk〕によって評価する。ここにE〔 〕は期待値を計算するオペレータ、μNkとσNkはそれぞれN分布の平均と分散である。歪度は分布の対称性の程度を測るための標準尺度である。その値はガウス分布のような対称な分布では0であり、長い右又は左の尾を持つ分布については正又は負である。図1の人工データセットにおいては、SN10は大きな正値4.45である。
図3はN10とデータセットのグローバルセントロイド(データセットの平均)への類似度(すなわち、後述するグローバルアフィニティ)との関係(グローバルセンタリング前)を示す散布図である。図が示すように、それらの間に強い相関が存在する。このように、高次元データセットでは、グローバルセントロイドに類似するデータがハブになる。更なる例としては上記Radovanovicらを参照されたい。

【0025】
〔ハブ軽減法としてのセンタリング〕
グローバルセンタリング(単にセンタリングともいう)とは、特徴空間の原点をデータセットのグローバルセントロイド(平均)に移動する変換をいう。グローバルセントロイドcは次式で表される。
c=(1/│D│)Σx∈D
センタリングは、データセットの観測バイアスを除去する古典的技術であるが、最近、発明者らによって、ハブを除く効果を持つことが確認された(Suzuki,I.;Hara,K.;Shimbo,M.;Saerens,M.;and Fukumizu,K.2013.“Centering similarity measures to reduce hubs.” In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, 613-623.)センタリングの重要な意義は、データとグローバルセントロイドc間の類似度(内積)を一定(実際にはゼロ)にすることである。具体的には、与えられたクエリq∈Rとデータx∈Dの内積
Sim(x,q)≡<x,q>
は、センタリング後、次の様に変化する。
SimCENT(x,q)≡<x-c,q-c>
ここで、q=cと置換すると、任意のx∈Rに対して、
SimCENT(x,c)=0
となる。

【0026】
このことは、グローバルセントロイドに特別に高い類似度を持つデータはもはや存在しないことを意味する。ここで期待されるのは、図1と図3で使用したデータセット(グローバルセントロイドに類似するデータがハブとなっていた)に対する、センタリングによるハブ軽減の効果である。期待されたとおり、このデータセットについてのN10分布の歪度SN10は、センタリング前の4.45から、センタリング後に0.27に減少する。実際、センタリング後の図2で見られるN10分布はほぼ対称である。

【0027】
〔大規模データセット中でのハブ〕
しかしながら、(グローバル)センタリングではハブが軽減されない場合がある。さほど高次元ではないが、データ数が大きい次元数d=500、データ数n=10000として前記と同様に人工データセットDを生成し、この人工データセットに出現するハブについて以下に説明する。

【0028】
図4-6は上記データセットにおけるハブを説明するための図である。図4、5はそれぞれ(グローバル)センタリング前後のN10(k=10のとき、各々のデータが他のデータのk近傍に出現する回数)の分布を示す図である。図6はN10とグローバルセントロイドへの類似度(すなわち、後述するグローバルアフィニティ)との関係(センタリング前)を示す散布図である。
このデータセットではN10分布の歪度SN10はセンタリング前に5.88、センタリング後に5.82である。つまり、センタリングによりハブはさほど軽減されない。図4及び図5に示されるように、N10分布の形状はセンタリング前後でほぼ同一である。さらに、図6の散布図に示されるように、このデータセットにおいてはセンタリング法が成功するために必要とされる条件(大きなN値を持つデータ、すなわち、ハブはグローバルセントロイドと高い類似度を持つ)を満たさない。

【0029】
データセットを、データ数nを100~10000、次元数dを100~4000の範囲で変えて生成し、各データセットについて、N10分布の歪度を計算する。各nとdの組み合わせについて、10個のデータセットを生成し、平均の歪度を計算する。

【0030】
図7、8は、データ数n及び次元数dを変数としたN10分布の歪度の等高線図である。図7はセンタリング前、図8はセンタリング後の等高線図である。高い値はハブの存在を意味する。+マークは生成したデータセット(のデータ数nと次元数d)に対応する。図7を見ると、ハブは左上と右下の領域のデータセットで発生していることが分かる。他方、図8によれば、左上の領域のハブはセンタリング後に消え、右下の領域のハブはセンタリングしても消えず、センタリング前と殆ど同程度残ることが分かる。
何故、右下の領域のデータセットでは、(グローバル)センタリングによってハブが軽減されないのかを調査するために、各データの特徴を調べるための2つの量、ローカルアフィニティとグローバルアフィニティを導入する。

【0031】
ローカルアフィニティ LocalAffinity(x)は、各データx∈Dについて、xとそのκ近傍(κNNすなわちκ-Nearest-Neighbor)に属するデータ間の平均類似度として定義され、次のように計算される。
LocalAffinity(x)
≡(1/κ)Σx’∈κNN(x)<x,x’>=<x,cκ(x)> (2)
ここに、ローカルセグメントサイズκは、各データxに対してローカルセントロイドを計算するために使用する隣接データの範囲を定めるパラメタである。
そして、次式が定めるcκ(x)を、データxのローカルセントロイドと呼ぶ(式において、kNNではなくκNNが使われることに注意)。
κ(x)=(1/κ)Σx’∈κNN(x)x’ (2A)

【0032】
グローバルアフィニティ GlobalAffinity(x)は、各データx∈Dについて、xとD中の全てのデータ間の平均類似度として定義される。
GlobalAffinity(x)
≡(1/│D│)Σx’∈D<x,x’>=<x,c> (3)
ここに、データセットのグローバルセントロイド(データセットの平均)は、
c=(1/│D│)Σx’∈Dx’である。
上式から解るように、xのグローバルアフィニティは単純にxとcの類似度である。もし、Dが非負値を要素として持つベクトルデータの集合であるなら、全てのx∈Dについて、
LocalAffinity(x)≧GlobalAffinity(x)≧0
である。ここで、例えばテキスト文書は通常、(tf-idf重み付け)ワードカウントベクトル、すなわち非負値を要素として持つベクトルとして表現されるため、上記不等式が成り立つ。さらに、κ=│D│なら、次式が成立する。
LocalAffinity(x)=GlobalAffinity(x)

【0033】
次に、グローバル対ローカルアフィニティ比
LocalAffinity(x)/GlobalAffinity(x)
について説明する。
各データxが非負ベクトルとして表されるデータセットDにおいては、あらゆるデータx∈Dに対して、この比は〔0,1〕に入る。この比は、D中でデータxがどの程度ローカル化しているかの指標となる。すなわち、(あるκ≪│D│に対して)比が0に近いなら、xは近傍データと特別に高い類似度を持つ、つまりxはローカル化されている局在データの集合を持っている。比がκに関わりなく1に近いなら、xは特別に高い類似度を持つデータをD中に持たない、つまりxはローカル化されていない。

【0034】
図9、10はローカライズドセンタリングに係る図(その1)である。データ数と次元数を変えた(図7-8に使用したのと同じ)様々なデータセットを用いて作成された。図9はローカライズドセンタリング後のN10分布の歪度を示す等高線図である。図10はグローバル対ローカルアフィニティ比を示す等高線図である。
ローカライズドセンタリングとは、ハブ度と相関が高くなるようなローカルなセントロイドを見つけ出し、ローカルなセントロイドとの類似度をペナルティとして与えることをいう。ローカライズドセンタリングは、例えば、先にローカルアフィニティを計算し、その後総合スコアを計算することにより実行される。
グローバル対ローカルアフィニティ比は個々のデータに対して定義されるので、データセットに対するグローバル対ローカルアフィニティ比として、データセット中の全データのグローバル対ローカルアフィニティ比の平均を用いた(ローカルセグメントサイズはκ=20に固定)。これを図8と比較すると、(グローバル)センタリング後に歪度が軽減されず大きいままである右下の領域は、図10ではグローバル対ローカルアフィニティ比が小さい領域に対応する。このことは、この領域のデータセットにおいてはデータがローカル化していることを示す。このようなデータセットにおいては、ローカルアフィニティがグローバルアフィニティよりハブを軽減するために関連性が高いということを示唆する。

【0035】
図11、12はローカライズドセンタリングに係る図(その2)である。図4-6で使用した大規模データセット(n=10000)について、図11はN10とローカルアフィニティの相関(ローカライズドセンタリング前)を示す散布図である。図12はローカライズドセンタリングを適用した後のN10の分布を示す図である。
図11が示すように、N10とローカルアフィニティ(すなわち、ローカルセントロイドへの類似度)との間に強い相関が観察された。これは図6で示したN10とグローバルアフィニティ(すなわちグローバルセントロイドへの類似度)との間の弱い相関と対照的である。そして、図12が示すように、ローカライズドセンタリング後にN10の分布の歪度が小さくなること(ハブが軽減されること)が観察された。

【0036】
図13は、図1-3で用いた高次元データセットについて、N10と、ローカルアフィニティの相関を示す散布図である。図13を見ると、高次元データセット(d=4000)においてもN10はローカルアフィニティと強く相関する。これらの結果は、ローカルアフィニティは、大規模データセットだけでなく高次元データセットにおいても、ハブを軽減するための指標となり得ることを示す。

【0037】
〔提案方法:ローカライズドセンタリング〕
以上の所見から、ローカルアフィニティはハブを軽減するための指標となり得る。そこで、ローカルアフィニティに基づくハブ軽減の新たな方法「ローカライズドセンタリング」を提案する。それは、高次元データセットと大規模データセットの両方に効果がある。
ローカライズドセンタリングを、グローバルセンタリングによる式(1)とのアナロジーで説明する。データセットDに属するデータxとクエリqとの類似度を計算する上で、xに依存しない項は、異なるxに対して一定である。よって、式(1)から、次式が導かれる。
SimCENT(x;q)
≡<x-c,q-c>=<x,q>-<x,c>+constant (4)
言い換えれば、センタリング法では、もともとの類似度スコア<x,q>から、グローバルアフィニティ<x,c>が、ペナルティ項として差し引かれる。同様にローカライズドセンタリングと称する提案方法では、もともとの類似度スコアからxのローカルアフィニティをペナルティ項として差し引く。
SimLCENT(x;q)≡<x,q>-<x,cκ(x)> (5)

【0038】
式(5)はローカルセグメントサイズを定めるパラメタκを含む。パラメタκは、例えば、N(x)とローカルアフィニティ<x,cκ(x)>との相関が最大になるように定める。もしκ=│D│であれば、提案方法はグローバルセンタリングと同一になる。式(5)への変換後、任意のデータx∈Dはそのローカルセントロイドcκ(x)と一定の類似度(実際はゼロ)を持つ。その理由は、式(5)にq=cκ(x)を代入すると、次式が導かれるからである。
SimLCENT(x;cκ(x))=0
言い換えれば、変換後にはローカルセントロイドとの類似度が特別高くなるデータは存在しない。ローカルセントロイドと高い類似度を持つデータがハブになるという、前記の所見を考慮すれば、この変換がハブを軽減することが期待される。実際、この期待は図12のデータセットに対しては成立している。

【0039】
ローカライズドセンタリングはデータ数nと次元数dを変えた他のデータセットでもハブを軽減する。図9にローカライズドセンタリング後のN10分布の歪度の等高線図を示す。図より、ローカライズドセンタリングは両タイプのハブ、すなわち、大規模データセットに生じるハブ(等高線図の右下の領域に対応する)と、高次元データセットに生じるハブ(左上の領域に対応する)の、どちらのハブも軽減できることが分かる。高次元データセットに対しても、ローカライズドセンタリング(式(5))はグローバルセンタリング(式(4))と同様に効果的である。このようなデータセットでは、図10の左上領域に示したように、グローバル対ローカルアフィニティ比は1に近いからである。このことは、この領域のデータセットの殆どのデータについて、<x,cκ(x)>≒<x,c>を意味し、したがって、式(5)は式(4)と殆ど同じになる。
式(5)はさらに拡張できる。式(5)の右辺の第2項はペナルティ項として説明できる、すなわち、ペナルティ項はxがどの程度のハブであるかを表し、それに応じて類似度スコアを小さくするために使用される。式(5)の拡張は、たとえば式(6)あるいは(7)のように、ペナルティの程度をコントロールするためのパラメタγの導入により行う。
SimγLCENT(x;q)≡<x,q>-<x,cκ(x)>γ (6)
SimγLCENT(x;q)≡<x,q>-γ<x,cκ(x)> (7)
パラメタγは、N分布の歪度がもっとも小さくなるように選択すればよい。
【実施例1】
【0040】
〔システム構成〕
図14に本実施例における類似度演算システム1(情報処理装置の一例)のシステム構成を例示する。類似度演算システム1は、データセット・クエリ設定部11、ベース類似度スコア演算部12、ハブ度演算部13、ペナルティスコア演算部14、総合スコア演算部15、演算結果整理・分類部16、制御部17、表示部18、入出力部19、記憶部20を備える。
データセット・クエリ設定部11は検索対象データ(クエリ)とデータセットの設定を行う。本実施例で扱うデータセットは、例えば、テキスト文書データセットや、DNAの塩基配列あるいはタンパク質のアミノ酸配列のデータセット等で、高次元又は/及び大規模データを有する。操作者が例えば、コンピュータ10の表示部18の設定画面のクエリ入力欄とデータセット入力欄にクエリとデータセット名を入出力部19のマウスやキーボードを用いて入力し、類似度演算システム1が類似度演算に用いるクエリとデータセットであると認識するように、検索対象データ(クエリ)とデータセットを設定する。
ベース類似度スコア演算部12(第1算出部の一例)は、データセット・クエリ設定部11にて設定されたクエリと設定されたデータセット内の各データについて、ベースとする類似度尺度を用いてクエリとの類似度を演算する。ベースとする類似度尺度として、内積、コサイン、距離等を使用できる。内積、コサイン、距離と異なり、データが明にベクトル表現されていることを前提としない類似度尺度であっても使用できる。例えば、塩基配列間の類似度尺度であるBLASTスコアや、文字列間の類似度尺度となるストリングカーネル、グラフ間の類似度尺度となるグラフカーネルなどを、ベースとする類似度尺度として使用できる。
【実施例1】
【0041】
ハブ度演算部13はハブ度として出現回数及び歪度を演算する。すなわち、データセット内の各データxについて、他データのk近傍(ベースとする類似度尺度により決定される)への出現回数N(x)を演算する出現回数演算部131、出現回数の分布の歪度を演算する歪度演算部132を有する。分布の歪度は、SNk=E〔(N-μNk/σNk〕(E〔 〕は期待値を計算するオペレータ、μNkとσNkはそれぞれNk分布の平均と分散である)で表される。
【実施例1】
【0042】
ペナルティスコア演算部14(特定部、第2算出部の一例)は、各データxのローカルセントロイドcκ(x)=(1/κ)Σx’∈κNN(x)x’の計算に用いる隣接データの範囲であるローカルセグメントサイズを定めるパラメタκを決定するローカルセグメントサイズ決定部141、各データxのローカルセントロイドを計算するローカルセントロイド演算部142を有する。ローカルセグメントサイズは、例えば、ローカルアフィニティ、すなわち、ローカルセントロイドとの類似度<x,cκ(x)>と、他データのk近傍に含まれる回数N(x)との相関が最大となるようにパラメタκを定める。隣接データの範囲とは出現回数N(x)の大きいデータの近傍データが局在化されている範囲で、ローカルセグメントサイズ内をいう。なお、κが固定されていれば、ローカルセントロイドは各データに対して1つだけ存在する。なお、ローカルセントロイドは各データにより異なるが必ず存在するとみなしてよい。したがって、ローカルセントロイドの有無を判断する必要はない。このように、ペナルティスコア演算部14は、各データxごとに隣接データを特定し、各データの基準座標ともいえるローカルセントロイドを算出する。
ペナルティスコア演算部14は、さらに、各データxに対し、ローカルセントロイド演算部142で演算されたローカルセントロイドcκ(x)を用い、ローカルアフィニティ、すなわち、ローカルセントロイドとの類似度<x,cκ(x)>を、各データxのペナルティスコアとして演算する、ローカルアフィニティ演算部143を有する。ローカルアフィニティの演算はローカライズドセンタリングの前工程を形成する。
総合スコア演算部15(第3算出部の一例)は、各データxに対し、ベース類似度スコア演算部12においてベースとする類似度尺度を用いて演算されたクエリとの類似度から、ローカルアフィニティ演算部143で演算されたペナルティスコアを差し引きすることにより、総合スコアを演算する。このように、総合スコア演算部15は、ベース類似度スコア演算部12が演算する類似度と、ペナルティスコア演算部14が算出するローカルセントロイドとに基づいて、各データxごとに総合スコアを算出する。総合スコアの演算はローカライズドセンタリングの後工程を形成する。
【実施例1】
【0043】
演算結果整理・分類部16(抽出部の一例)は、各データxに対して総合スコア演算部15で計算した総合スコアを、大きい順に整理する総合スコア順整理部161と、この整理結果を用いてk近傍法により分類する分類部162を有する。分類は、総合スコアが大きいk個のデータの分類ラベルを用いた(スコア重み付き)多数決により行う。つまり、分類部162は、クエリについて、総合スコアが大きい順にデータセットからk個のデータを抽出し、分類を行う。これにより、類似度演算システム1は、クエリに対応する分類ラベルを特定することができる。
【実施例1】
【0044】
制御部17は類似度演算システム1及びその各部11~16を制御して、類似度演算システム1としての機能を発揮させる。
以上のデータセット・クエリ設定部11から制御部17はコンピュータ10内に実現可能であり、本実施例でもそのようにしている。ただし、ベース類似度スコア演算部12では、BLASTのような汎用のアルゴリズムが提供する類似度演算を利用しても良い。この場合でも、ベース類似度スコア演算部12は演算結果を取り込み、記憶部20に記憶させる機能を保有する。
表示部18は、類似度演算システム1各部11~16の入力結果、演算結果、記憶部20の記憶内容、入出力操作時の案内画面等を表示する。入出力部19は、キーボード、マウス、マイクロフォン等の入力機器、プリンタ、スピーカー等の出力機器を有し、操作者はこれら入出力機器を用いて適宜入出力できる。
【実施例1】
【0045】
記憶部20は、類似度演算システム1各部11~16の入力結果、演算結果、演算途中の情報、類似度演算システム1を動作させるのに必要なプログラム及び情報を記憶する。記憶部20は、データセット・クエリ情報記憶部21、ベース類似度スコア情報記憶部22、出現回数・歪度情報記憶部23、ローカルセグメントサイズ情報記憶部24、ローカルセントロイド情報記憶部25、ペナルティスコア情報記憶部26、総合スコア情報記憶部27、分類情報記憶部28、プログラム記憶部29及び一時記憶部30を有する。
【実施例1】
【0046】
データセット・クエリ情報記憶部21は、検索先データセット、検索対象データ(クエリ)に関して、データセット・クエリ設定部11による設定結果を記憶する。ベース類似度スコア情報記憶部22は、ベース類似度として用いる類似度の計算アルゴリズム(内積、コサイン、距離等の計算アルゴリズムや、BLASTのような汎用の類似度計算アルゴリズムを含む)や、ベース類似度スコア演算部12による類似度演算結果等を記憶する。出現回数・歪度情報記憶部23は、ハブ度演算部13での演算結果、すなわち、出現回数演算部131により演算された各データが他のデータのk近傍に出現する回数(各データのハブ度)、及び、歪度演算部132により演算された出現回数分布の歪度(データセットのハブ度)を記憶する。
【実施例1】
【0047】
ローカルセグメントサイズ情報記憶部24は、ローカルセグメントサイズ決定部141で決定されたローカルセグメントサイズκを、ローカルセントロイド情報記憶部25は、ローカルセントロイド演算部142で演算された各データのローカルセントロイドに関する情報を記憶する。ペナルティスコア情報記憶部26は、ローカルアフィニティ演算部143で演算された各データのペナルティスコアを記憶する。総合スコア情報記憶部27は、総合スコア順整理部161による総合スコア順の整理結果等を記憶する。分類情報記憶部28は、分類部162によるk近傍法を用いたクエリの分類結果を記憶する。プログラム記憶部29は、類似度演算システム1及びその各部11~16のデータの流れ、演算、分類を実行させるためのプログラム、類似度演算システム1及びその各部11~16を制御するために必要なプログラム、類似度演算システム1の起動に必要なプログラム等を記憶する。一時記憶部30は、演算途中の情報等を一時的に記憶する。
【実施例1】
【0048】
〔処理フロー〕
図15に本実施例における類似度演算の処理フロー例を示す。まず、データセット・クエリ設定部11にて高次元又は/及び大規模データについて、検索対象クエリと検索先データセットを設定する(データセット・クエリ設定工程:S101)。例えば、生命情報学分野における配列の相同性検索では、世界中の研究成果として蓄積された機能既知のDNAの塩基配列あるいはタンパク質のアミノ酸配列のデータセット、及び、検索対象クエリとなる機能未知の塩基配列やアミノ酸配列が設定され、データセット・クエリ情報記憶部21に記憶される。次に、データセット・クエリ設定工程(S101)にて設定されたクエリとデータセット内の各データについて、ベース類似度スコア演算部12にてベースとする類似度尺度を用いてクエリとデータの類似度を演算する(ベース類似度スコア演算工程:S102)。ベースとする類似度尺度として、生命情報学分野における配列の相同性検索では、BLASTアルゴリズムが出力するスコアが用いられるが、一般には内積、距離、コサイン等が使用される。演算されたベース類似度スコアはベース類似度スコア情報記憶部22に記憶される。
【実施例1】
【0049】
次に、ハブ度演算部13にて、各データのハブ度、及び、データセットのハブ度を演算する(ハブ度演算工程:S103)。すなわち、出現回数演算部131では、各データxのハブ度を、データセット内の他のデータのk近傍への出現回数N(x)を演算する。歪度演算部132では、N(x)の分布の歪度を演算する。出現回数演算部131及び歪度演算部132により作成された出現回数分布図及び歪度(図1、2、4、5、12参照)が参照される。ハブが存在すれば、出現回数分布図に大きいN(x)を持つデータが現われ、大きい歪度が観測される。出現回数N(x)及び歪度は、出現回数・歪度情報記憶部23に記憶される。
【実施例1】
【0050】
次に、ローカルセグメントサイズ決定部141にて、ローカルセグメントサイズκを決定し(ローカルセグメントサイズ決定工程:S104)、κの値はローカルセグメントサイズ情報記憶部24に記憶する。そして、決定されたκを用い、ローカルセントロイド演算部142にて、各データxのローカルセントロイドcκ(x)を演算し(ローカルセントロイド演算工程:S105)、cκ(x)はローカルセントロイド情報記憶部25に記憶する。さらに、演算されたcκ(x)を用い、ローカルアフィニティ演算部143にて、各データxのローカルアフィニティをcκ(x)とxの類似度として計算し(ペナルティスコア演算工程:S106)、これを各データのペナルティスコアとしてペナルティスコア情報記憶部26に記憶する。ローカルアフィニティの演算はローカライズドセンタリングの前工程を形成する。
【実施例1】
【0051】
次に、総合スコア演算部15にて、ベース類似度スコア情報記憶部22及びペナルティスコア情報記憶部26に記憶された各データに対するベース類似度スコア及びペナルティスコアを用い、各データに対する総合スコアを演算する(総合スコア演算工程:S107)。ここでは、ベース類似度スコアからペナルティスコアを差し引くことにより、総合スコアを得る。総合スコアの演算はローカライズドセンタリングの後工程を形成する。ローカライズドセンタリングは前工程と後工程からなる。データセットのデータは、総合スコア演算工程(S107)での演算結果に基づいて、演算結果整理・分類部16にて整理・分類される(演算結果整理工程:S108)。典型的には、総合スコアの大きい順に整理(ランク付け)され、総合スコア情報記憶部27にランキングが記憶される。さらに、検索対象クエリを分類する場合には、k近傍法を用いて(総合スコアが大きいk個のデータの分類ラベルの投票により)検索対象クエリの分類ラベルの予測を行う(分類工程:S109)。予測結果は、分類情報記憶部28に記憶される。
【実施例1】
【0052】
〔実世界データを用いた実験〕
本発明による手法(ローカライズドセンタリング)は、(人工データではなく)実世界データセットに対してハブを軽減する効果を持つかどうか、さらに、ハブを軽減する結果としてタスクの精度を向上するかどうかを調べるために、多クラス分類タスクのベンチマークとして用いられる実世界のテキスト文書データセットに対してローカライズドセンタリングを適用する。使用するテキスト文書データセットは、図16はWebKB、図17はReuters-52、図18はTDT2-30、図19は20Newsgroupsである。実験を通して、テキスト文書の分類タスクにおいて標準的なデータ表現であるtf-idf重み付きbag-of-wordsベクトル表現を用い、標準的な類似度尺度(ベースライン)としてコサインを用いる。
【実施例1】
【0053】
〔ハブの軽減〕
最初の実験では、ローカライズドセンタリングが大規模データセットに生じるハブを軽減するかどうかを調べた。データセット全体からn個のデータをランダムに選択し、データ数nのサブセットを生成した。データ数nを100から4000の範囲で動かし、各nについてサブセットの生成を10回行った。各サブセットに対してN10分布の歪度を計算し、各nについて平均歪度(10回の平均)を計算した。そして、グローバルセンタリング(センタリング)後及びローカライズドセンタリング後の平均歪度を比較した。
【実施例1】
【0054】
図16-19は、データ数nとN10分布の平均歪度との関係を示す図である。(i)はグローバルセンタリング又はローカライズドセンタリングを施す前の折れ線グラフ(比較のベースライン)である。(ii)はグローバルセンタリング後、(iii)はローカライズドセンタリングの折れ線グラフである。使用した4つのデータセットを通して、同じ傾向が観察された。すなわち、データ数nの増加につれて、ベースラインではN10分布の平均歪度は増加し、ハブが増大する。一方、グローバルセンタリングによって、平均歪度はやはり増加するが、平均歪度はベースラインよりやや小さい。他方、ローカライズドセンタリングでは、データ数nに関わらず、平均歪度はほぼ同じ小さい値のままで変化しない。まとめると、グローバルセンタリングはデータ数nが小さい(約500より小さい)ときに効果が見られるが、データ数nが大きいときには否である。他方、ローカライズドセンタリングは、データ数nが大きくてもハブの発生を低いレベルに維持する。
さらに、式(2)及び式(3)を用い、各データセットについてグローバル対ローカルアフィニティ比を計算し、図16-19にその折れ線グラフを(iv)として示した。すると、人工データセットで観察されたのと同じ傾向が明確に観察された。すなわち、グローバル対ローカルアフィニティ比が小さいとき、グローバルセンタリングはハブを軽減しないが、ローカライズドセンタリングはハブを軽減する。
【実施例1】
【0055】
〔k近傍分類の精度〕
このように、ローカライズドセンタリングによりハブが軽減することは確認がされたが、次の実験では、このハブ軽減がk近傍分類精度を改善するかどうかを調べた。タスクはテストデータとしてのテキスト文書の分類ラベルを訓練データとしてのテキスト文書の分類ラベルを用いて予測することである。リーブワンナウトleave-one-out交差検証法(全データから一つをテストデータとして、残りを訓練データとして用い、訓練データを使ってテストデータの分類ラベルを予測することを、全データに亘ってデータ数だけ繰り返し、予測の正解率を評価値とする)によりパフォーマンスを評価した。
【実施例1】
【0056】
ベースラインとなるコサイン(COS)、及び、コサインを変形した5つの類似度尺度を試した。グローバルセンタリング(標準的なセンタリング)(CENT)、ローカライズドセンタリング(LCENT)、コミュートタイムカーネル(CT)、ミューチュアルプロキシミティ(MP)及ローカルスケーリング(LS)である。コミュートタイムカーネルは、グラフラプラシアンに基づくグラフノード間の類似度を定めるためにSaerensらにより発表され(Saerens,M.;Fouss,F.;Yen,L.;and Dupont,P.2004.“The principal components analysis of graph,and its relationships to spectral clustering.” In Proceedings of the 15th European Conference on Machine Learning(ECML’04),371-383.2004年)、後に発明者らによりハブ軽減に効果があることが示された(Suzuki,I.;Hara,K.;Shimbo,M.;Matsumoto,Y.;and Saerens,M.2012.“Investigating the effectiveness of Laplacian-based kernels in hub reduction.” In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.2012年)。ミューチュアルプロキシミティ(Schnitzer,D.;Flexer,A.;Schedl,M.;and Widmer,G.2012.“Local and global scaling reduce hubs in space.” Journal of Machine Learning Research 13(1):2871-2902.2012年)とローカルスケーリング(Zelnik-Manor,L.and Perona,P.2005.“Self-tuning spectral clustering.” In Advances in Neural Information Processing Systems 17. MIT Press. 1601-1608.2005年)はデータ間の近傍関係を対称化しようと試みるものである。
【実施例1】
【0057】
図20-23に実験結果を示した。LCENTあるいはLSが精度の項目において最良のパフォーマンスを達成した。CENTはコサインに対して歪度と精度をわずかに改善するのみに留まったが、対照的にLCENTはコサインに対して歪度と精度を大きく改善した。
【実施例1】
【0058】
以上により、本実施例によれば、次元数が大きいときだけでなく、データ数が大きいときに出現するハブを軽減できる類似度演算システム及び類似度演算方法を提供できる。
【実施例2】
【0059】
本実施例では、同一データセットについて検索を行う場合、ペナルティスコア情報記憶部26に記憶されているペナルティスコアを用いることにより、検索処理を早められる。あるいは、前処理としてオフラインに各データに対するペナルティスコアを計算しておき、ペナルティスコア情報記憶部26に記憶しておくことで、検索処理を早められる。その他のシステム構成及び処理フローは実施例1と同様であり、実施例1と同様に次元数が大きいときだけでなく、データ数が大きいときに出現するハブを軽減できる類似度演算システム及び類似度演算方法を提供できるという効果を奏する。
【実施例3】
【0060】
本実施例では、実施例1で説明した総合スコアを示す式(6)、(7)のペナルティスコアを調整する例について説明する。
SimγLCENT(x;q)≡<x,q>-<x,cκ(x)>γ (6)
SimγLCENT(x;q)≡<x,q>-γ<x,cκ(x)> (7)
式(6)、(7)の右側の第2項はペナルティスコアである。パラメタγはN分布の歪度を最も軽減するように調整され得る。その他のシステム構成及び処理フローは実施例1と同様であり、実施例1と同様に次元数が大きいときだけでなく、データ数が大きいときに出現するハブを軽減できる類似度演算システム及び類似度演算方法を提供できるという効果を奏する。
【実施例4】
【0061】
本実施例では、ベースとする類似度尺度として、これまで説明に用いてきた内積ではなく,ユークリッド距離(lノルム)を用いた場合の、ハブ軽減方法について説明する。ここでは、クエリqと各データxとの類似度Sim(x;q)をユークリッド距離(sqrt(||x-q||))の2乗にマイナス符号を付した値として定義する。すなわち、
Sim(x;q)≡-||x-q|| (8)
である。
これを類似度尺度として用いて発生するハブは、ローカルセントロイドcκ(x)を用い、次のように類似度スコアを補正することによって、軽減できる。
SimLCENT(x;q)
≡-||x-q||+||x-cκ(x)|| (9)
さらに、類似度スコアを調整する右辺第2項に、次のようにパラメタγを付加してもよい。
SimγLCENT(x;q)
≡-||x-q||+(||x-cκ(x)||γ (10)
SimγLCENT(x;q)
≡-||x-q||+γ||x-cκ(x)|| (11)
【実施例5】
【0062】
本実施例では、各データのベクトル表現が与えられず、機械学習分野で呼ばれるところのカーネルやBLASTスコアなどのようにデータ間の類似度だけが、ベースとする類似度尺度として与えられる場合の、ハブ軽減方法について説明する。まず、クエリqと各データxとの類似度が、BLASTスコアにより定義されているとする。すなわち、
Sim(x;q)≡BLASTスコア(x;q) (12)
とする。ここで、BLASTスコアを類似度尺度として用いて発生するハブは、次のようにスコアを補正することによって、軽減できる。
SimLCENT(x;q)
≡BLASTスコア(x;q)-(1/κ)Σx’∈κNN(x)x’BLASTスコア(x;x’) (13)
上記ではBLASTスコアを例に用いて説明したが、ベースとする類似度尺度としてその他の類似度(カーネルなど)を用いる場合は、上記BLASTスコアの部分を、用いる類似度(カーネルなど)が定めるスコアに置き換えればよい。すなわち、
SimLCENT(x;q)
≡Sim(x;q)-(1/κ)Σx’∈κNN(x)x’Sim(x;x’) (14)
とすれば、任意の類似度尺度Sim(x;q)に対して、ハブを軽減できる。ここで、κ=n=|D|でも良く、さらに、実施例3、4と同様に、ペナルティスコアを調整するためのパラメタγを導入しても良い。
【実施例6】
【0063】
本実施例では、ローカルセグメントサイズκの値を、データセット内で一定としない場合について説明する。例えば、ローカルセグメントサイズκの値は、データセット内のデータxごとに異なっていてよい。この場合、κの値は、データxの近傍におけるデータの密集度に基づいて定めてもよい。具体的には、データxのハブ度、すなわち、データセット内の他のデータのk近傍への出現回数N(x)が大きくなる程、κの値も大きくなるようにしてもよい。これにより、データセット内に複数のデータのクラスター(局所集合)が存在し、各クラスターを構成するデータ数が大きく異なる場合であっても、各データxに対応するローカルセントロイドcκ(x)を、データxが属するクラスターの中心付近に設定することができる。したがって、類似度演算システム1は、ハブの発生を抑制し、k近傍法の精度を向上させることができる。
【実施例6】
【0064】
次に、変形例に係る類似度演算システム1について説明する。
上述した実施例では、一例として、類似度演算システム1がローカルセントロイドcκ(x)に基づいて、ペナルティスコアを算出する場合について説明したがこれには限られない。類似度演算システム1は、ローカルセントロイドcκ(x)に基づいてボーナススコアを算出してもよい。類似度尺度として内積を用いる場合、内積は大きければ大きい程、2つのデータが類似することを表す。したがって、内積を用いる場合には、ローカルアフィニティLocalAffinity(x)はペナルティとして算出される。他方、類似度尺度として、距離を用いる場合、距離は小さければ小さい程、2つのデータが類似することを表す。したがって、距離を用いる場合には、ローカルアフィニティLocalAffinity(x)はボーナスとして算出される。このように、ローカルアフィニティLocalAffinity(x)に係るペナルティ、ボーナスの概念は、類似度尺度等に応じて異なる。つまり、ローカルアフィニティLocalAffinity(x)とは、スコアの補正に用いられるパラメタであり、その物理的な意味付けは、システムの構成に応じて異なるパラメタである。
【実施例6】
【0065】
また、上述した実施例では、一例として、データセット、クエリを構成するデータとして塩基配列データやアミノ酸配列データを用いる場合について説明したが、これには限られない。例えば、上述した配列データの他にも、マイクロアレイデータ等の生命科学分野のデータが用いられてもよい。また、生命科学分野に限られず、音声データ、画像データ、テキストデータ等の任意の種類のデータが用いられてよい。
【実施例6】
【0066】
なお、ローカルセグメントサイズκの値は、任意の方法で設定されてよい。例えば、塩基配列データやアミノ酸配列データは、データ空間において、比較的、データ数の小さなクラスターが大量に発生し、これらがハブ発生の原因となる場合がある。そこで、この場合には、ローカルセグメントサイズκの値は、例えば、10以下の比較的小さな値としてもよい。このように、データ空間においてデータ数の小さなクラスターが大量に発生している場合には、ローカルセグメントサイズκとして、相対的に小さな値を設定する。これにより、類似度演算システム1は、演算量を低減しつつ、ハブを軽減することができる。これに対して、データ空間においてデータ数の大きなクラスターが多く発生している場合には、ローカルセグメントサイズκの値を、相対的に大きな値としてもよい。これにより、データxがクラスターの外縁部に位置していたとしても、データxごとのローカルセントロイドcκ(x)をクラスターの中心に近づけることができるため、効率よくハブを軽減することができる。また、ローカルセグメントサイズκの値は、kの値に基づいて定められてもよい。例えば、ローカルセグメントサイズκの値は、kの値の2倍程度としてもよい。また、ローカルセグメントサイズκの値は、システムごとに予め定められていてもよい。また、ローカルセグメントサイズκの値は、データxのハブ度、すなわち、データセット内の他のデータのk近傍への出現回数N(x)に関する分布の歪度が最小になる数としてもよい。
【実施例6】
【0067】
また、上述した実施例では、一例として、k近傍法を用いる場合について説明したが、これには限られない。例えば、k近傍法を用いる代わりにイプシロン近傍法を用いてもよい。この場合、隣接データの範囲は、データセット内のデータのうち、データxとの類似度が所定の値よりも高いデータとしてもよい。
【実施例6】
【0068】
また、本発明の一態様は、以上の実施例のフローチャート等に記載の類似度演算方法を含むコンピュータに実行させるためのプログラムとしても実現可能である。プログラムは情報検索装置の内蔵記憶部に蓄積して使用してもよく、外付けの記憶装置に蓄積して使用してもよく、インターネットからダウンロードして使用しても良い。また、当該プログラムを記録した記録媒体としても実現可能である。
【実施例6】
【0069】
以上、本発明の一態様に係る実施の形態について説明したが、実施の形態は以上の例に限られるものではなく、本発明の趣旨を逸脱しない範囲で、種々の変更を加え得ることは明白である。例えば、上述の各実施例において説明した各構成は、特定の機能を発揮するのに不要である場合には、省略することができる。また、上述した各実施例において説明した各構成は、複数の装置に分散して備えられても良いし、1つの構成としてまとめられてもよい。
例えば、データセットがインターネット検索におけるWeb文書集合のように、データセットの次元数は明らかではないがデータ数が膨大であることが明白である場合、本発明の適用によりハブを軽減できる効果が認められるならば、本発明が提供する類似度演算システム及び類似度演算方法は有効である。また、以上の実施例では検索対象がクエリと同一である場合について説明したが、クエリが検索対象と関連性が深いキーワードであっても良い。また、データセットが膨大なときには、データセットが複数の記憶装置に分散して記憶されても良い。また、システム構成では、ローカルセントロイド情報記憶部25とペナルティスコア情報記憶部26をまとめて1つにしても良い。また、処理フローではデータセット・クエリ設定工程(S101)とベース類似度スコア演算工程(S102)とを同時に行っても良い。また、k近傍法のパラメタkは目的、状況に応じて適宜定めることができる。
【産業上の利用可能性】
【0070】
本発明は類似度演算及び情報分類に利用される。
【符号の説明】
【0071】
1 類似度演算システム
10 コンピュータ
11 データセット・クエリ設定部
12 ベース類似度スコア演算部
13 ハブ度演算部
14 ペナルティスコア演算部
15 総合スコア演算部
16 演算結果整理・分類部
17 制御部
18 表示部
19 入出力部
20 記憶部
21 データセット・クエリ情報記憶部
22 ベース類似度スコア情報記憶部
23 出現回数・歪度情報記憶部
24 ローカルセグメントサイズ情報記憶部
25 ローカルセントロイド情報記憶部
26 ペナルティスコア情報記憶部
27 総合スコア情報記憶部
28 分類情報記憶部
29 プログラム記憶部
30 一時記憶部
131 出現回数演算部
132 歪度演算部
141 ローカルセグメントサイズ決定部
142 ローカルセントロイド演算部
143 ローカルアフィニティ演算部
161 総合スコア順整理部
162 分類部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22