(57)【要約】【課題】  複数の情報の相関を抽出する場合、情報の数が増えることで、相関計算の対象となる情報の組み合わせ数が多くなり、相関の計算量が膨大になってしまう。【解決手段】  データ列を含む複数の情報の相関を抽出する方法であって、コンピュータが、前記データ列から、一部のビットを選択し、選択された前記一部のビットに基づいて、前記複数の情報の相関を判定し、判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出する。【選択図】  図３
2015022613.tif 000002
【特許請求の範囲】
【請求項１】
データ列を含む複数の情報の相関を抽出する方法であって、コンピュータが、
前記データ列から、一部のビットを選択し、
選択された前記一部のビットに基づいて、前記複数の情報の相関を判定し、
判定の結果に応じて、前記データ列における前記一部のビット以外のビットに基づいて、前記複数の情報の相関を抽出する
ことを特徴とする相関抽出方法。
【請求項２】
前記コンピュータは、
前記判定の結果に応じて、前記複数の情報の相関を抽出するための相関計算の対象となる情報のペアを、前記複数の情報における組み合わせから除外する
ことを特徴とする請求項１に記載の相関抽出方法。
【請求項３】
前記コンピュータは、
前記判定の結果に応じて相関が高いと予測される情報について、前記データ列における前記一部のビット以外のビットに基づいて、前記相関が高いと予測される情報の相関を計算し、
前記相関の計算の結果に基づいて、特定の情報の組み合わせを登録し、
前記データ列から、他の一部のビットを選択し、
前記他の一部のビットに基づいて前記複数の情報の相関を抽出する場合に、登録されている前記特定の情報の組み合わせであれば相関の計算をしない
ことを特徴とする請求項１に記載の相関抽出方法。
【請求項４】
前記ビットは前記複数の情報において定められた属性であり、前記データ列は複数の前記属性の値により構成され、
前記コンピュータは、
前記複数の属性から、一部の属性を選択することで、前記データ列から前記一部のビットを選択し、
選択された前記一部の属性に基づいて前記複数の情報をグループに分類することで、前記選択された前記一部のビットに基づいて前記複数の情報の相関を判定し、
同じグループに分類された情報の相関の計算に基づいて、前記複数の情報の相関を抽出する
ことを特徴とする請求項１〜３の何れか１項に記載の相関抽出方法。
【請求項５】
前記コンピュータが、
前記複数の情報を、前記選択された前記一部の属性についての値の組み合わせに従って、前記グループに分類し、
前記組み合わせに含まれる値において、特定の属性についての値が異なると、情報の相関の差が所定以上になる場合には、前記特定の属性が含まれる確率が高くなるように、前記複数の情報の各々について、前記複数の属性から、他の一部の属性を選択して、
選択された前記他の一部の属性に基づいて、前記複数の情報の相関を抽出する
ことを特徴とする請求項４に記載の相関抽出方法。
【請求項６】
前記コンピュータが、
前記複数の情報を、前記選択された前記一部の属性についての値の組み合わせに従って、前記グループに分類し、
前記同じグループに分類された情報の数が所定数以上になるグループであって、当該グループに分類された情報の相関の差が所定以下になる場合には、当該グループを特定するための値の組み合わせの一部が含まれる確率が小さくなるように、前記複数の属性から、他の一部の属性を選択し、
選択された前記他の一部の属性に基づいて、前記複数の情報の相関を抽出する
ことを特徴とする請求項４又は５に記載の相関抽出方法。
【請求項７】
前記コンピュータが、
前記複数の属性についての値を離散化する
ことを特徴とする請求項４〜６の何れか１項に記載の相関抽出方法。
【請求項８】
前記複数の情報の各々は、前記複数の属性毎に値が登録されたレコードであり、
前記コンピュータは、
前記選択された前記一部の属性についての値の組み合わせをインデックスにし、
同じインデックスになるレコードどうしを、前記同じグループに分類する
ことを特徴とする請求項４〜７の何れか１項に記載の相関抽出方法。
【請求項９】
データ列を含む複数の情報の相関を抽出する装置であって、
前記データ列から、一部のビットを選択する選択部と、
選択された前記一部のビットに基づいて、前記複数の情報の相関を判定する判定部と、
判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出する抽出部と
を有することを特徴とする相関抽出装置。
【請求項１０】
データ列を含む複数の情報の相関を抽出するためのプログラムであって、コンピュータに、
前記データ列から、一部のビットを選択させ、
選択された前記一部のビットに基づいて、前記複数の情報の相関を判定させ、
判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相関抽出方法、相関抽出装置、及び、プログラムに関する。
【背景技術】
【０００２】
大規模なデータを解析することにより、その大規模なデータから新たな知識を取り出すデータマイニングが知られている。データマイニングにより、例えば、膨大な数のＩＣカードに記憶された電車の乗車歴の各々を使用して、人々の移動履歴が解析される。この解析により、同じ時間帯に同じ場所に移動する人の傾向など、例えば、マーケティングに役立つ可能性のある知識が抽出されることが期待される。また、膨大なデータを解析する例として、例えば、各地に設置された気象センサにより得られる風速や降雨量といった気象データの時間変化を使用して、各地の気象の相関を計算する場合がある。そして、この相関に従い、例えば、似た天候の地域の抽出や、短期局所的な天候予測が行われる。
【０００３】
ところで、文字列のペアを見つけるために、文字列のうちのｄ個の文字を選んでこれらをマスクし、残りの文字を使用して、文字列どうしの相関を計算する技術が知られている。この技術では、ｄ個の文字の選び方の各々に対応するマスクパターン全てについて、文字列どうしの相関計算が試行される。
【０００４】
また、レコードの相関関係を効率よく抽出するために、複数のレコードをレコード群中の変数でソートしてから、レコードどうしの相関を算出する技術が知られている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】津田  宏浩、田部井  靖生、清水  佳奈、伊東  純一、富井  健太郎、杉山  将、宇野  毅明、“複合ソート法による高速な全ペア類似度探索”、［online］、２０１１年８月３日、［２０１３年６月１７日検索］、インターネット＜URL：http://www-erato.ist.hokudai.ac.jp/html/php/symposium3_docs/MSM_tsuda.pdf＞
【特許文献】
【０００６】
【特許文献１】特開２００６−３３８２６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
複数の情報の相関を抽出する場合、情報の数が増えることで、相関計算の対象となる情報の組み合わせ数が多くなり、相関の計算量が膨大になってしまう。
【０００８】
本願は、相関が高い情報の組み合わせを抽出する際の計算量を低減させる方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
開示の相関抽出方法は、データ列を含む複数の情報の相関を抽出する方法であって、コンピュータが、前記データ列から、一部のビットを選択し、選択された前記一部のビットに基づいて、前記複数の情報の相関を判定し、判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出する。
【発明の効果】
【００１０】
本開示の一側面によれば、相関が高い情報の組み合わせを抽出する際の計算量を低減できる。
【図面の簡単な説明】
【００１１】
【図１】実施例の相関抽出装置のハードウェア構成の例。
【図２】実施例の相関抽出装置の機能ブロックの例。
【図３】実施例の相関抽出方法における処理の例。
【図４】実施例の相関抽出方法における処理の他の例。
【図５】実施例の相関抽出方法にかかるデータの例。
【図６】実施例の相関抽出方法にかかるデータの他の例。
【図７】実施例の相関抽出方法における処理の他の例。
【図８】実施例の相関抽出方法における処理の他の例。
【図９】実施例の相関抽出方法にかかるデータの他の例。
【図１０】実施例の相関抽出方法にかかるデータの他の例。
【発明を実施するための形態】
【００１２】
図１に、実施例の相関抽出装置のハードウェア構成の例が示される。実施例の相関抽出装置の一例であるサーバ１は、ＣＰＵ２、メモリコントローラ３、メモリ４、メモリバス５、ＩＯバスコントローラ６、ＮＩＣ７、及びＩＯバス８を含み、ＩＯバス８には記憶装置９が接続される。
【００１３】
メモリバス５に接続されたメモリ４には、サーバ１の各種処理を実行するためのプログラムが格納されている。ＣＰＵ２は、メモリコントローラ３を介して、メモリ４からプログラムを読み出し、各種処理を実行する。ＣＰＵ２によって実行される各種処理の実行に伴い、メモリ４に対するデータの書き込み及び読み出しがメモリコントローラ３を介して実行される。
【００１４】
ＣＰＵ２は、ＩＯバスコントローラ６を介して、ＩＯバス８に接続されたＮＩＣ７にデータを転送し、また、ＮＩＣ７からデータやパケットを受け取る。ＣＰＵ２は、ＩＯバスコントローラ６を介して、ＩＯバス８に接続された記憶装置９からデータを読み出し、また記憶装置９にデータを書き込む。
【００１５】
ＣＰＵ２は、各種処理を実行するための１以上のＣＰＵコアを含んでいてもよい。また、各ＣＰＵコアは１以上のプロセッサを含んでいてもよい。なお、ＣＰＵ２が複数のＣＰＵコアを含む場合には、当該各種処理を、複数のＣＰＵコアに協業させて実行させてもよく、又はそのうちの１つのＣＰＵコアに実行させてもよい。また、各ＣＰＵコアが複数のプロセッサを含む場合には、当該各種処理を、複数のプロセッサに協業させて実行させてもよく、又はそのうちの１つのプロセッサに実行させてもよい。
【００１６】
メモリ４は、例えばＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などのＲＡＭである。記憶装置９は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリなどの不揮発性メモリ、又はＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等の磁気ディスク装置である。
【００１７】
なお、ＣＰＵ２、メモリコントローラ３、メモリ４、ＮＩＣ７、及び、記憶装置９が同じバスに接続された構成をサーバ１に適用してもよい。図１に示されるハードウェア構成によって、図２に示される機能ブロックが実現され、図３、４、７及び８に示される処理が実行される。
【００１８】
図２に、実施例の相関抽出装置の機能ブロックの例が示される。相関抽出装置の一例であるサーバ１は、ワーキングメモリとして使用されるメモリ４にロードされたプログラムがＣＰＵ２によって実行されることにより、計算部２００、選択部２０１、分類部２０２、抽出部２０３、判定部２０４、読み出し部２０５、登録部２０６、更新部２０７、設定部２０８、及び比較部２０９として機能する。なお、図２に示される各機能ブロックにより実行される処理が、図３、４、７及び８に示される処理と対応させて後述される。
【００１９】
図３に、実施例の相関抽出方法における処理の例が示される。図３に示される処理は、複数の属性を有する情報どうしの相関計算において、複数の属性から選ばれた一部の属性が等しい情報の組合せについて、他の属性の値を用いて相関を計算する場合の処理の例である。また、複数の属性の値がデジタル値によりあらわされ、それらのデジタル値が、ひとつのデータ列として扱われる場合には、図３に示される処理を、データ列からなる情報どうしの相関計算において、データ列の一部のビットで判定した相関が高いと予測された情報のペアについて、他のビットも使って相関を計算する場合の処理の例であるともいえる。なお、実施例はこれに限定されないが、ここでは、複数の属性を有する情報を、複数の属性毎の値が登録された複数のレコードとし、図３に示される処理によって、相関のあるレコードの組み合わせが抽出される場合を例示する。
【００２０】
各レコードについて、各属性の値を離散化する処理３０１が、計算部２００によって実行される。処理３０１により、各属性の値が離散化されて、１ビットないし数ビットで表わされることとなる。そして、処理３０１によって各属性の値が離散化された場合の具体例が、図５Ｂや図６Ｂに沿って後述される。なお、各レコードに記録されている属性値どうしが、後述されるレコードどうしの相関評価に照らして、すでに適当な概略関係にある場合には、処理３０１を省略してもよい。
【００２１】
所定のレコード組を登録しておくための集合ＨＣを初期化する処理３０２が、計算部２００によって実行される。処理３０２では、相関が高いと認められるとして抽出されたレコード組を登録しておくための集合ＨＣを空集合にする。なお、この集合ＨＣは、図１に示されるメモリ４や記憶装置９において実現されればよい。
【００２２】
ところで、処理３０２において、相関が低いと認められるレコード組を登録しておくための他の集合も準備しておき、この集合も空集合にしてもよい。実施例は何れの場合にも適用可能であるが、相関が高いと認められるとして抽出されたレコード組を登録しておくための集合ＨＣを例に説明を続ける。
【００２３】
所定のビット（値が離散化された属性）を選択する処理３０３が、選択部２０１によって実行される。ここで、ビットとは、処理３０２によって値が離散化された属性である。処理３０３では、各レコードを分類するためのインデックスを定めるため、各レコードにおいて、レコードに含まれるビットのうち、一部のビットを選択する。なお、処理３０２によって選択された一部のビットの具体例が、図５Ｂや図６Ｂに沿って後述される。
【００２４】
選択されたビットの値をインデックスとして各レコードをグループに分類する処理３０４が、分類部２０２によって実行される。処理３０４では、処理３０３によって選択された一部のビットの値に基づきインデックスを作成する。インデックスは、一部のビットの値の組み合わせにより互いに区別されることとなり、同じ値のインデックスとなったレコードどうしが同じグループに分類される。なお、インデックス毎のグループに分類されたレコードの具体例が、図５Ｃや図６Ｃに沿って後述される。
【００２５】
インデックス毎のグループに分類されたレコードどうしの相関計算に基づき、相関の認められるレコード組を抽出する処理３０５が、抽出部２０３によって実行される。処理３０５では、処理３０４によって同じグループに分類されたレコードどうしの相関を評価する。処理３０５の具体例が、図４の処理に沿って後述される。
【００２６】
相関の抽出処理を所定回数実行したかどうかを判定する処理３０６が、判定部２０４によって実行される。所定回数実行されていないと判定された場合には、抽出処理を継続するために処理３０３に移り、所定回数実行されたと判定された場合には、処理３０７に移り、図３に示された処理を終える。
【００２７】
図４に、実施例の相関抽出方法における処理の他の例が示される。この図４に示される処理によって、図３に示される処理３０５の処理、及び図７に示される処理７０６が、さらに具体的に示される。
【００２８】
図３に示される処理３０４、又は図７に示される処理７０５に次いで、集合ＨＣ、インデックス、及び分類されたレコードを読み出す処理４００が、読み出し部２０５によって実行される。
【００２９】
未選択のインデックスを選択する処理４０１が、選択部２０１によって実行される。処理４０１では、インデックス毎のグループに分類されたレコードどうしの相関を評価する場合に、全てのインデックスを網羅するために、まだ評価されていないインデックスを選択するための処理である。
【００３０】
選択されたインデックスが付されたグループに分類されたレコードのうち、相関が未評価のレコード組を選択する処理４０２が、選択部２０１によって実行される。処理４０２では、選択されたインデックスが付されたグループに分類されたレコードにおいて、それらのレコードの組み合わせの評価を網羅するために、まだ相関が評価されていないレコードの組み合わせを選択するための処理である。
【００３１】
選択されたレコード組が集合ＨＣに含まれるかどうかを判定する処理４０３が、判定部２０４によって実行される。集合ＨＣは、上述したように、相関が高いと認められるとして抽出されたレコード組を登録しておくための集合であるため、選択されたレコード組が、すでに集合ＨＣに記録されている場合には、冗長な相関計算を省略できる。そこで、処理４０３により、選択されたレコード組が集合ＨＣに含まれるかどうかを判定し、集合ＨＣに含まれると判定された場合には、処理４０７に移る。他方で、集合ＨＣに含まれないと判定された場合には、処理４０４に移る。なお、処理４０３の具体例が、図６Ｄに示される。
【００３２】
選択されたレコード組の相関を計算する処理４０４が、計算部２００によって実行される。処理４０４では、処理４０２により選択されたレコード組の相関を計算する。この相関の計算では、典型的な相関計算のアルゴリズムを適用すればよい。例えば、ビットの値の所定値からのずれを基準に、各レコードにおいてどの程度の差分があるか計算し、この差分に基づいて相関を評価してもよい。
【００３３】
なお、処理４０４の相関の計算において対象となるビットは、インデックスを作成するために選択された一部のビットだけでなく、それ以外のビットも対象となる。こうして、インデックスを作成する際に選択されたビットよりも多くのビットが、相関の計算の対象となる。
【００３４】
例えば、レコードに含まれる全てのビットに基づき相関の計算をしてもよく、処理４０４によって、インデックスに基づいて抽出された、相関が高いと予測されるレコード組について、さらに詳細な相関計算が実行されることとなる。なお、処理４０４の具体例が、図５Ｄや図６Ｄに例示される。
【００３５】
計算された相関が閾値よりも高いかどうかを判定する処理４０５が、判定部２０４によって実行される。処理４０５では、処理４０４により計算された相関の値と、相関が高いかどうかを判定するための閾値とを比較することで、レコード組に相関が認められるかどうかを判定する。そして、この処理４０５の具体例が、図５Ｄや図６Ｄに例示される。
【００３６】
なお、この閾値は、相関計算に適用されるアルゴリズムに応じて適宜設定してもよいし、相関計算をある程度実行して傾向をふまえてから設定してもよい。そして、閾値よりも高いと判定された場合には処理４０６に移り、閾値よりも低いと判定された場合には処理４０７に移る。
【００３７】
選択されたレコード組を集合ＨＣに登録する処理４０６が、登録部２０６によって実行される。処理４０６では、処理４０５によって判定された、相関が高いと認められるレコード組を集合ＨＣに登録する。なお、処理４０６の具体例が、図５Ｅや図６Ｅに例示される。
【００３８】
選択されたインデックスが付されたグループに分類されたレコードによる、全レコード組を評価したかどうかを判定する処理４０７が、判定部２０４によって実行される。全レコード組を評価していないと判定された場合には、他のレコード組についても評価をするために処理４０２に移る。全レコード組を評価したと判定された場合には、処理４０８に移る。
【００３９】
読み出されたインデックス全てを選択したかどうかを判定する処理４０８が、判定部２０４によって実行される。インデックス全てを選択していないと判定された場合には、他のインデックスについても評価をするために処理４０１に移る。インデックス全てを選択したと判定された場合には、処理４０９に移る。
【００４０】
処理４００及び処理４０６の結果に基づき、集合ＨＣを更新する処理４０９が、更新部２０７によって実行される。処理４０６が終了すると、図３に示される処理３０６、又は図７に示される処理７０７に移る。
【００４１】
図３や図４によって上述したように、実施例によれば、インデックスを使用することで、相関が高いと予測されるレコード組に相関の計算を絞ることで、相関が高いと認められるレコード組を抽出する際の計算量が減る。
【００４２】
図５に、実施例の相関抽出方法にかかるデータの例が示される。図５Ａ−Ｅには、図３や図７に示される処理において使用されるデータと処理結果等が例示され、これらにより、実施例の相関抽出方法により実現される相関抽出の具体例が例示される。
【００４３】
図５Ａには、データ列からなる情報の例として、複数の属性毎の値を有するレコードの例が示される。そして、図５Ａに例示されるレコードは、図１に示されるメモリ４や記憶装置９に格納されていたり、又は、ネットワーク経由でサーバ１が取得したりすることで、図３、４、７及び８に示される処理が実行される際に使用される。例えば、レコード１には、最上段の行に示される属性を識別するための番号“１”、“２”、“３”、・・・に対応して、属性の値“１．０”、“１．５”、“１．７”、・・・等が登録されている例が示されている。なお、説明のために、“１”番目の属性を属性１などと表す。
【００４４】
レコードの具体例を説明すると、レコードの番号によって地域が識別され、属性１、属性２、・・・などによって時刻が識別される場合、例えば、東京において時刻７：００に登録された気温が１．０℃であれば、レコード１の属性１に“１．０”の値が登録され、東京において時刻７：１０に登録された気温が１．５℃であれば、レコード１の属性２に“１．５”の値が登録されるといったように、１０分毎の各地域の気温がレコード毎に登録されていく。また、大阪において時刻７：００に登録された気温が０．０℃であれば、レコード２の属性１に“０．０”の値が登録され、大阪において時刻７：１０に登録された気温が０．１℃であれば、レコード２の属性２に“０．１”の値が登録される。
【００４５】
なお、各地に設置された気象センサにより得られてレコードに登録される情報は、気温だけでなく、風速や降雨量等、種々の観測量であってもよいし、また、それらが同時に登録されてもよい。そして、レコードどうし相関が評価されることで、例えば、似た天候の地域の抽出や、短期局所的な天候予測を行うことが期待される。
【００４６】
さらに、レコードの他の具体例を説明すると、レコードの番号によって人が識別され、属性１、属性２、・・・などによって時刻が識別される場合、例えば、ある人物Ａが時刻７：００に渋谷駅を通過すると、レコード１の属性１に、渋谷駅を識別するための値“１．０”が登録され、この人物Ａが時刻７：３０に新宿駅を通過すると、レコード１の属性４に、新宿駅を識別するための値“４．０”が登録される。この例の場合、レコード１の属性２及び３に値が登録されないが、レコードの種類によっては、全ての属性に値が登録されていない場合もありえる。
【００４７】
このようなレコードによって、人々の移動履歴が解析され、同じ時間帯に同じ場所に移動する人の傾向など、例えば、マーケティングに役立つ可能性のある知識が抽出されることが期待される。
【００４８】
なお、実施例は上記の具体例に限定されず、また、実施例のレコードに登録される情報の登録間隔は、対象となる情報の特性や相関の解析内容等に合わせて、適宜設定すればよい。
【００４９】
図５Ｂには、属性の値が離散化された場合のレコードが例示される。離散化された値に関して、図５Ａのレコードの含まれる値自体との直接的な関係はないが、図５Ａのレコードのように登録された属性の値が、所定の規則に従って、図５Ｂのように離散化される。なお、この離散化の処理は、図３の処理３０１又は図７の処理７０１に従い実行される。
【００５０】
なお、図５Ａでは、各属性の値が二値化されて、１ビットで表現される場合が例示されているが、実施例はこれに限定されず、各属性の値が数ビットで表現されるような所定の規則で離散化してもよい。なお、実施例では、説明を簡略化するために、各属性の値が二値化された場合を例に説明する。なお、説明のために、属性１、属性２、属性３、・・・をビット１、ビット２、ビット３、・・・のように表すことがある。例えば、レコード１であれば、ビット１の値が“０”、ビット２の値が“０”というように表すことがある。
【００５１】
ところで、図５Ｂでは、各レコードの属性の値が罫線によって区切られているが、この区切りに依存せずに、各レコードを属性の値が連続するデータ列としてみなして、各レコードの相関を計算してもよい。例えば、レコード１であれば、“０００１１０１１１１・・・”というデータ列として扱ってもよい。つまり、レコード間の相関を抽出する際に、属性毎の値を比較するとみなすだけでなく、データ列を比較するとみなしてもよい。
【００５２】
図５Ｃには、図５Ｂに示される各レコードを基にして、複数の属性のうちの一部の属性の値を使用したインデックス毎のグループに、各レコードが分類された例が示される。なお、上述のように、複数の属性の値が離散化され、離散化された値によってレコードがひとつのデータ列として扱われる場合には、このインデックスは、データ列の中から選択された一部のビットの組み合わせともいえる。そして、一部のビットの組み合わせによるビット列の値が同じになるレコードが、同じグループに分類される。
【００５３】
なお、どのビットが選択されるは、図３の処理３０３、又は図７の処理７０４によって決められ、選択されたビットの値をインデックスとするグループの何れにレコードを分類するかは、図３の処理３０４、又は図７の処理７０５によって決められる。
【００５４】
ところで、図５Ｃに示されるインデックスの例は、図５Ｂの符号５００で示されるように、各レコードの１ビット目、５ビット目、７ビット目、及び９ビット目の値に基づくインデックスである。なお、４つのビットに基づくインデックスはあくまでも例示であり、レコード間の相関を抽出する際に、より相関の高いレコードの組み合わせを抽出することが期待される場合には、より多くのビットに基づくインデックスによりレコードを分類してもよいし、逆に、相関がそれほど高くないレコードの集合から相関の認められるレコードの組み合わせを抽出する場合には、少ないビット数に基づくインデックスによりレコードを分類してもよい。
【００５５】
例えば、レコード１の１ビット目の値は“０”であり、５ビット目の値は“１”であり、７ビット目の値は“１”であり、９ビット目の値は“１”であるため、レコード１のインデックスは“０１１１”となる。こうして、図５Ｃに例示されるように、レコード１はインデックス“０１１１”のグループに分類される。なお、説明のために、“０１１１”のインデックスを、インデックス０１１１と表すことがある。
【００５６】
さらに例示すれば、レコード３の１ビット目の値は“０”であり、５ビット目の値は“１”であり、７ビット目の値は“１”であり、９ビット目の値は“１”であるため、レコード３のインデックスは“０１１１”となり、図３の処理３０４、又は図７の処理７０５により、レコード１と同じグループに分類されている。
【００５７】
図５Ｄには、同じグループに分類されたレコードどうしの相関を評価する場合の具体例が示される。はじめに、表記の説明をする。例えば、図５Ｄにおいて（１、３）と表された数の組み合わせは、レコード１及びレコード３が同じインデックスのグループに属していることを表している。なお、レコード１及びレコード３は、図５Ｃに示したように、共に、インデックス０１１１のグループに属している。
【００５８】
図５Ｄに示されるように、例えば、（１、３）のレコード組について相関が評価される。レコード組（１、３）が集合ＨＣにまだ登録されていない場合、図４に示される処理４０４により、インデックスに使用されたビット以外のビットも使用してレコード組（１、３）の相関が計算される。
【００５９】
このように、実施例では、データ列の一部のビット、つまり、一部の属性に基づくインデックを使用して、相関が高いと予測されるレコード組を絞る。そして、相関計算を実行するレコードの組み合わせを、同じインデックスのグループに属するレコード組に絞ることで、相関の高いレコードの組み合わせを抽出するための相関計算にかかる計算量を減らしている。
【００６０】
なお、後述するが、同じインデックスのグループに属するレコード組であっても、例えば、相関が高いと判定されたレコード組を登録しておくための集合ＨＣに既に登録されている場合には、図４に示される処理４０３の判定に従って、相関の計算が省略される。これによって、相関計算にかかる計算量がさらに減る。
【００６１】
次いで、図４に示される処理４０５により、（１、３）のレコード組の相関を、相関の閾値と比較した結果、相関が閾値よりも高いと判定される。その判定の結果、図４に示される処理４０６により、（１、３）のレコード組が集合ＨＣに登録される。
【００６２】
さらに例示すると、図５Ｄには、インデックス１１１１のグループに分類された（７、８）のレコード組の相関の計算が実行され、計算された相関と閾値との比較の結果、相関が低いと判定されて、集合ＨＣには登録されないことが示されている。さらに例示すると、図５Ｄには、インデックス１１１１のグループに分類された（７、９）のレコード組について、集合ＨＣに登録されていないため、インデックスに使用されたビット以外のビットも使用して相関の計算が実行される。そして、計算された相関と閾値との比較の結果、相関が高いと判定されて、集合ＨＣに登録されることが示されている。
【００６３】
図５Ｅには、相関が高いレコードの組み合わせとして抽出された、レコード組が示される。図５Ｄに沿って説明したように、相関が高いと判定されたレコード組である（１、３）及び（７、９）が、集合ＨＣに登録されている例が示されている。
【００６４】
図６に、実施例の相関抽出方法にかかるデータの他の例が示される。図６Ａ−Ｅには、図３の処理３０６や図７の処理７１１において、他のビットの組み合わせに基づく相関抽出を継続すると判定されて、図３及び４、又は図７及び８に示される処理が継続される場合に使用されるデータと処理結果等が例示される。なお、図６Ａ−Ｅに示される例は、図５Ａ−Ｅに沿って例示された処理結果が、さらに、図３及び４、又は図７及び８に示される処理によって処理されとして説明される。
【００６５】
図６Ａに、相関が高いと判定されたレコード組が、集合ＨＣに登録されている例が示される。図６に示される例は、上述したように、図５Ａ−Ｅに沿って例示された処理結果がさらに処理される例であり、この図６Ａには、図５Ｅに示される集合ＨＣが、図４に示される処理４００又は図８に示される処理８００によってあらためて読み込まれた後の、集合ＨＣが示されている。
【００６６】
なお、詳細は後述するが、図６Ａに示される集合ＨＣに、相関が高いと判定されたレコード組である（１、３）及び（７、９）が登録されていることによって、インデックスに含まれるビット以外も使用した相関計算において、レコード組（１、３）及び（７、９）の相関計算が省略されることになる。
【００６７】
図６Ｂに、属性の値が離散化された場合のレコードが例示され、このレコードの例は、図５Ｂに示される例と同じである。ただし、図６Ｂでは、インデックスが作成される際に選択されるビットの位置が、符号６００で示されるように、各レコードの２ビット目、４ビット目、７ビット目、及び８ビット目になっている。これらのビットの位置は、図３に示される３０３又は図７に示される７０４により、図５Ｂの位置とは別にあらためて選択される位置である。
【００６８】
図６Ｃに、図６Ｂに示される各レコードを基にして、複数の属性のうちの一部の属性の値を使用したインデックス毎のグループに、各レコードが分類された他の例が示される。上述したように、図６Ｂの符号６００で示されるビットに基づいてインデックス毎に、レコードが分類されている。なお、選択されたビットの値をインデックスとするグループの何れにレコードを分類するかは、図３の処理３０４、又は図７の処理７０５によって決められる。
【００６９】
例えば、レコード１の２ビット目の値は“０”であり、４ビット目の値は“１”であり、７ビット目の値は“１”であり、８ビット目の値は“１”であるため、レコード１のインデックスは“０１１１”となる。こうして、図６Ｃに例示されるように、レコード１はインデックス０１１１のグループに分類される。
【００７０】
さらに例示すれば、レコード３の２ビット目の値は“０”であり、４ビット目の値は“１”であり、７ビット目の値は“１”であり、８ビット目の値は“１”であるため、レコード３のインデックスは“０１１１”となり、図３の処理３０４、又は図７の処理７０５により、レコード１と同じグループに分類されている。
【００７１】
図６Ｄに、同じグループに分類されたレコードどうしの相関を評価する場合の他の具体例が示される。例えば、インデックス０１１１のグループに分類された（１、３）のレコード組について相関が評価される。レコード組（１、３）については、図４に示される処理４０３の判定により、レコード組（１、３）が集合ＨＣに含まれているため、相関の計算が省略される。つまり、集合ＨＣに登録されているレコード組であれば、相関の計算が既に実行済みであって、相関が高いと評価されているため、相関の計算を省略して計算量を省いている。
【００７２】
なお、相関が高いと評価されたレコード組ではなく、相関が低いと評価されたレコード組を別の集合に登録しておき、もしこの集合に既に登録されている場合には、重複する相関計算を避けるために、相関計算を省略してもよい。また、相関が高いと評価されたレコード組、及び相関が低いと評価されたレコード組の両方を登録して、相関計算の省略に利用してもよい。
【００７３】
ところで、多数のレコードの相関を評価する場合、ほとんどのレコード組の相関が低いと評価される場合がある。この場合、相関が低いと評価されるレコード組の数が膨大になるため、これらを登録しておくメモリ容量が多く必要になる。そのため、メモリ容量の使用率を低くすることを優先にする場合には、相関の高いレコード組のみを登録しておき、相関の低いレコード組の登録を省いてもよい。また、相関が低いと評価されるレコード組の数が膨大であれば、これらの重複計算を省けると計算量が著しく少なくなる可能性がある。すなわち、計算量を少なくすることを優先する場合には、少なくとも、相関の低いレコード組を登録しておいて、相関計算の省略判定に利用すればよい。
【００７４】
さらに例示すると、インデックス０１１１のグループに分類された（１、４）のレコード組の相関が評価される。レコード組（１、４）は、図６Ａに示される集合ＨＣに含まれないため、インデックスに使用されたビット以外のビットも使用して相関が計算される。そして、計算された相関と閾値との比較の結果、相関が高いと判定され、レコード組（１、４）は、集合ＨＣに登録されることとなる。
【００７５】
さらに例示すると、インデックス０１１１のグループに分類された（３、４）のレコード組の相関が評価される。レコード組（３、４）は、図６Ａに示される集合ＨＣに含まれないため、インデックスに使用されたビット以外のビットも使用して相関が計算される。そして、計算された相関と閾値との比較の結果、相関が低いと判定され、レコード組（３、４）は、集合ＨＣに登録されないこととなる。
【００７６】
さらに例示すると、インデックス１０１０のグループに分類された（６、７）のレコード組の相関が評価される。レコード組（６、７）は、図６Ａに示される集合ＨＣに含まれないため、インデックスに使用されたビット以外のビットも使用して相関が計算される。そして、計算された相関と閾値との比較の結果、相関が高いと判定され、レコード組（６、７）は、集合ＨＣに登録されることとなる。
【００７７】
さらに例示すると、インデックス１０１０のグループに分類された（７、８）のレコード組の相関が評価される。レコード組（７、８）は、図６Ａに示される集合ＨＣに含まれないため、インデックスに使用されたビット以外のビットも使用して相関が計算される。そして、計算された相関と閾値との比較の結果、相関が低いと判定され、レコード組（７、８）は、集合ＨＣに登録されないこととなる。
【００７８】
図６Ｅに、相関が高いレコードの組み合わせとして抽出された、レコード組が示される。図６Ｄに沿って説明したように、相関が高いと判定されたレコード組である（１、４）及び（６、７）等が集合ＨＣにさらに登録され、相関が高いと判定されたレコード組である（１、３）、（１、４）、（３、４）、（６、７）及び（７、８）等が含まれるように集合ＨＣが更新される。
【００７９】
図７に、実施例の相関抽出方法における処理の他の例が示される。図７に示される処理は、図３に示される処理に加えて、例えば、レコードの属性又は属性の一部の組み合わせがレコードどうしの相関に与える影響の度合いを考慮しながら、属性の一部を選択する際の確率を更新する処理等が実行される。図７に示される処理は、処理７００により開始される。
【００８０】
各レコードについて、各属性の値を離散化する処理７０１が、計算部２００によって実行される。なお、処理７０１は、処理３０１と同様の処理である。
【００８１】
所定のレコード組を登録しておくための集合ＨＣを初期化する処理７０２が、計算部２００によって実行される。なお、処理７０２は、処理３０２と同様の処理である。
【００８２】
ビット（値が離散化された属性）の選択確率を初期化する処理７０３が、計算部２００によって実行される。詳細は後述するが、実施例では、各レコードを分類するためのインデックスを定める際に、レコードに含まれるビットのうち、選択されやすいビット及び選択されにくいビットが設定されるようにしている。この処理７０３では、まずは、レコードに含まれるビットが互いに等確率で選択されるように、ビットの選択確率を初期化する。なお、ビットの選択確率に差をつける具体例は、図９Ｂや図１０Ｂに沿って後述される。
【００８３】
ビットの選択確率に従い所定のビットを選択する処理７０４が、選択部２０１によって実行される。処理７０４では、各レコードを分類するためのインデックスを定めるため、各レコードにおいて、レコードに含まれるビットのうち、設定された選択確率に従って、一部のビットを選択する。
【００８４】
選択されたビットの値をインデックスとして各レコードをグループに分類する処理７０５が、分類部２０２によって実行される。なお、処理７０５は、処理３０４と同様の処理である。
【００８５】
同じインデックスが付されたグループに分類されたレコードどうしの相関計算に基づき、相関の認められるレコード組を抽出する処理７０６が、抽出部２０３によって実行される。なお、処理７０６は、処理３０５と同様の処理である。
【００８６】
インデックス毎に、グループに属するレコード数及び抽出率を登録する処理７０７が、登録部２０６によって実行される。処理７０７では、上述の処理の結果に従い、同じインデックスが付されたグループに分類されたレコード数や、相関が高いと認められるレコード組の抽出率が登録される。なお、登録されるレコード数や抽出率の具体例が、図９Ａや図１０Ａに沿って後述される。
【００８７】
相関の抽出処理のための閾値を決定するために、定められた回数の処理を実行したかどうかを判定する処理７０８が、判定部２０４によって実行される。ここで決定される閾値は、上述したように、相関計算をある程度実行して傾向をふまえてから決定される閾値である。処理７０８では、この傾向を把握するために適宜定められる回数だけ処理が実行されたかどうかが判定される。定められた回数の処理を実行したと判定される場合には処理７０９に移り、定められた回数の処理を実行していないと判定される場合には処理７１１に移る。
【００８８】
レコード数の閾値及び抽出率の閾値を設定する処理７０９が、設定部２０８によって実行される。処理７０９において設定される閾値は、相関計算に適用されるアルゴリズムに応じて適宜設定されてもよいし、上述のように、相関計算をある程度実行して傾向をふまえてから設定されてもよい。例えば、相関計算を実行した結果、相関が認められる情報の組み合わせの数が少ない場合には、抽出される情報の組み合わせの数が多くなるように閾値を設定してもよい。また、相関計算を実行した結果、相関が認められる情報の組み合わせの数が多い場合には、抽出される情報の組み合わせが絞られるように閾値を設定してもよい。
【００８９】
ビットの選択確率を更新する処理７１０が、更新部２０７によって実行される。処理２０７の具体例は、図８の処理に沿って後述される。
【００９０】
相関の抽出処理を所定回数実行したかどうかを判定する処理７１１が、判定部２０４によって実行される。なお、処理７１１は、処理３０６と同様の処理であり、所定回数実行されていないと判定された場合には、抽出処理を継続するために処理７０４に移り、所定回数実行されたと判定された場合には、処理７１２に移って図７に示された処理を終える。
【００９１】
図８に、実施例の相関抽出方法における処理の他の例が示される。図８に示される処理によって、図７に示される処理７１０が、さらに具体的に示される。
【００９２】
図７に示される処理７０９に次いで、レコード数の閾値、抽出率の閾値、各ビットの選択確率、及び、各インデックスのレコード数と抽出率を読み出す処理８００が、読み出し部２０５によって実行される。なお、これらの閾値、選択確率、レコード数や抽出率は、上述の処理の結果、図１のメモリ４や記憶装置９に適宜格納されており、処理８００によって、メモリ４や記憶装置９から読み出される。
【００９３】
読み出された各インデックスで使用されているビットのうち、選択確率が未評価のビットを選択する処理８０１が、選択部２０１によって実行される。処理８０１では、読み出された各インデックスで使用されているビットにおいて、ビットの選択確率の評価を網羅するために、まだ選択確率が評価されていないビットを選択するための処理である。なお、処理８０１の具体例が、図９Ｂに沿って後述される。
【００９４】
読み出されたインデックスから、選択されたビットだけが異なるインデックスの組を抽出する処理８０２が、抽出部２０３によって実行される。このように、選択されたビットだけが異なるインデックスの組に注目することで、その選択されたビットが、レコード組の相関に影響を与える度合いが推定できる。なお、処理８０２の具体例が、図９Ｂに沿って後述される。
【００９５】
抽出率の閾値と、抽出されたインデックスの抽出率とを比較する処理８０３が、比較部２０９によって実行される。処理８０３では、処理８０２により抽出されたインデックスの抽出率と、処理８００により読み出された抽出率の閾値とを比較する。なお、図９Ｂに沿って後述されるように、処理８０２では、大きい閾値と小さい閾値との２つの閾値の各々と、抽出されたインデックスの抽出率とが比較される。
【００９６】
インデックスの抽出率の各々の差が第１の差以上になるかどうかを判定する処理８０４が、判定部２０４によって実行される。処理８０４では、処理８０２により抽出されたインデックスの組において、処理８０３の結果に基づき、インデックスの抽出率の各々の差が第１の差以上になるかどうかを判定する。
【００９７】
なお、この第１の差は、抽出率における大きい閾値と小さい閾値との差分で定まる差であり、例えば、インデックスの組のうち、第１のインデックスの抽出率が大きい閾値以上であり、第２のインデックスが小さい閾値よりも小さいと判定された場合には、第１のインデックスと第２のインデックスとの差が、第１の差以上であると判定される。
【００９８】
処理８０４において、第１の差以上になると判定されると処理８０５に移り、第１の差以上にならないと判定されると処理８０６に移る。
【００９９】
選択されたビットの選択確率を増加させる処理８０５が、設定部２０８によって実行される。処理８０５では、処理８０４により、インデックスの抽出率の各々の差が第１の差以上になると判定されているため、選択されたビットがレコード組の相関に与える影響が大きく、選択されていない他のビットの分布を表している可能性があるとして、相関計算されるレコード組を絞る際に使用されるインデックスの一部として選択されやすくするように、選択確率を増加させる。なお、処理８０５の具体例が、図９Ｂに沿って後述される。
【０１００】
インデックスの抽出率の各々が、共に大きい又は共に小さいかどうかを判定する処理８０６が、判定部２０４によって実行される。処理８０６では、処理８０２により抽出されたインデックスの組において、インデックスの抽出率の各々が、両方とも上述の大きい閾値以上になるか、又は、両方とも上述の小さい閾値よりも小さくなるかを判定する。共に大きい又は共に小さいと判定された場合には処理８０７に移り、共に大きくない又は共に小さくないと判定された場合には処理８０８に移る。
【０１０１】
選択されたビットの選択確率を減少させる処理８０７が、設定部２０８によって実行される。インデックスの抽出率の各々が、両方とも上述の大きい閾値以上、又は、両方とも上述の小さい閾値よりも小さい場合、つまり、インデックスの抽出率の各々の差が所定以下の場合、選択されたビットがレコード組の相関に与える影響が小さい又は選択されたビットがレコード組に与える影響が判定不能であるといえる。そのため、このビットを採用しても、相関の高いレコード組を抽出できる可能性が高くないとして、相関計算されるレコード組を絞る際に使用されるインデックスの一部として選択されにくくするように、選択確率を減少させる。なお、処理８０５の具体例が、図９Ｂに沿って後述される。
【０１０２】
読み出された各インデックスで使用された全てのビットの選択確率を評価したかどうかを判定する処理８０８が、判定部２０４によって実行される。全てのビットの選択確率を評価したと判定される場合には処理８０９に移り、全てのビットの選択確率を評価していないと判定される場合には、他のビットについても選択確率を評価するために、処理８０１に移る。
【０１０３】
読み出された各インデックスのうち、部分組み合わせの評価に関して未選択のインデックスを選択する処理８０９が、選択部２０１によって実行される。後述の処理によってインデックスを作成する際に、同時に選択されるビットの組み合わせの選択確率が設定されるが、このビットの部分組み合わせの評価のために、処理８０９によって、未評価のインデックスを選択することとなる。
【０１０４】
選択されたインデックスが付されたグループに分類されたレコードの数が、レコード数の閾値以上かどうかを判定する処理８１０が、判定部２０４によって実行される。レコードの数が閾値以上であると判定される場合には処理８１１に移り、レコードの数が閾値よりも小さいと判定される場合には処理８１３に移る。
【０１０５】
選択されたインデックスの抽出率が、抽出率の閾値以下かどうかを判定する処理８１１が、判定部２０４によって実行される。抽出率が閾値以下であると判定される場合には処理８１２に移り、抽出率が閾値よりも大きいと判定される場合には処理８１３に移る。
【０１０６】
選択されたインデックスで使用されるビットの部分組み合わせが選択される確率を減少させる処理８１２が、設定部２０８によって実行される。処理８１２は、処理８１０において、レコードの数が閾値以上であると判定され、処理８１１において、抽出率が閾値以下であると判定された場合に実行される処理である。具体例が図１０Ｂに沿って後述されるが、インデックスに分類されるレコード数が多くても、抽出率が低いということは、これらのビットの組み合わせをインデックスに使用して相関計算のレコード組を絞ったとしても、相関の高いレコード組を抽出できる可能性が低く、抽出効率が低いということであるため、処理８１２では、インデックスを作成する際にこのようなビットの部分組み合わせが選択される確率を減少させる。
【０１０７】
さらに例示すれば、処理８１２では、処理３０３や処理７０４において複数のビットを選択する場合に、あるビットが選ばれた場合には選択確率が小さく変更されるような、条件が付されたビットの選択確率を設定することとなる。
【０１０８】
全てのインデックスを選択したかどうかを判定する処理８１３が、判定部２０４によって実行される。全てのインデックスを選択したと判定される場合には処理８１４に移り、全てのインデックスを選択していないと判定される場合には、他のインデックスを選択するために処理８０９に移る。
【０１０９】
ビットの選択確率を更新する処理８１４が、更新部２０７によって実行される。処理８１４では、処理８０５、処理８０７、処理８１２による設定に従って、ビットの選択確率を更新する。処理８１４が終了すると、図７に示される処理７１１に移る。
【０１１０】
図９に、実施例の相関抽出方法にかかるデータの他の例が示される。図９に沿って、あるビットの組み合わせに従ってインデックス毎のグループにレコードが分類された後、グループに属するレコードによって可能な組み合わせ数と、その組み合わせのうち相関が高いと判定されたレコード組の数との比により定められる抽出率を使用して、ビットの選択確率が設定されるまでの具体例が説明される。なお、実施例は、図９Ａ及びＢに示される値に限定されない。
【０１１１】
図９Ａに、各レコードにおけるビット｛１、５、７、９｝が選択された場合の、各インデックスの抽出率が示される。例えば、ビット｛１、５、７、９｝に基づくインデックスが００００となるレコードの数が、図３に示される処理３０４や図７に示される処理７０５の結果、“１０００”であったとする。この場合、“１０００”のレコードによる組み合わせの数は、“（レコード数）×（レコード数−１）／２”の式により計算すると、“４９９５００”となる。なお、この計算は、図７に示される処理７０７において実行される。
【０１１２】
このレコードの組み合わせのうち、図３の処理３０５や図７の処理７０６により、ビット｛１、５、７、９｝以外のビットも使用して相関が計算された結果、相関が高いレコード組の数が“３９９６００”であったとする。この時の抽出率は、“（相関が高いレコード組数）／（レコードの組み合わせ数）”の式により、“０．８０”となる。これらの結果は、図７の処理７０７により、図９Ａに示されるように登録される。
【０１１３】
同様の計算により、インデックス０００１の抽出率が“０．７０”、インデックス００１０の抽出率が“０．００”、インデックス００１１の抽出率が“０．４０”、インデックス０１００の抽出率が“０．２０”、及びインデックス１０００の抽出率が“０．３０”等であることが、他のインデックスを代表して、図９Ａに例示されている。
【０１１４】
図９Ｂに、抽出率に基づきビットの選択確率を設定する場合の具体例が示される。ここで、ビットの選択確率を設定する際に、抽出率と比較される閾値が２つ、適宜設定される。ひとつは、大きい閾値であり、仮に“０．７０”であるとする。他方は、小さい閾値であり、仮に“０．１０”であるとする。なお、これらの閾値は、図８の処理８００で読み出される、抽出率の閾値である。
【０１１５】
まず、図９Ｂに示されるように、インデックス００００の抽出率が“０．８０”であり、この抽出率は、大きい閾値である“０．７０”以上である。他方で、インデックス０００１の抽出率は“０．７０”であり、この抽出率も、大きい閾値である“０．７０”以上である。つまり、インデックス００００及びインデックス００１０において、互いの抽出率が所定の差以下となっている。
【０１１６】
ここで、インデックス００００及びインデックス０００１において、ビット９の値だけが変更されていることに注目すると、ビット９の値が変わったとしても、レコードどうしの相関の度合いを表す抽出率の変化が小さいため、ビット９がレコードどうしの相関に与える影響は小さいといえる。つまり、実施例のように、相関の高いレコード組を抽出するために一部のビットによるインデックスを用いて相関計算をするレコードの組み合わせを絞る場合に、ビット９を含むインデックスを用いても、この時点で、相関の高いレコード組をグループ化できている可能性が低いと推定される。そこで、抽出処理を繰り返し実行する場合に、ビット９が、一部のビットのうちの１つとして選択される選択確率を減らすように設定される。なお、選択確率を減少させる設定は、図８の処理８０７により実行される。
【０１１７】
ところで、図９Ｂに示されるように、インデックス００００の抽出率“０．８０”が大きい閾値である“０．７０”以上である一方で、インデックス００１０の抽出率“０．００”が小さい閾値である“０．１０”よりも小さい。つまり、インデックス００００及びインデックス００１０において、互いの抽出率が所定の差以上となっている。
【０１１８】
このように、ビット７の値が変わると、レコードどうしの相関の度合いを表す抽出率が大きく変化するということは、ビット７の値が、レコードどうしの相関に影響を大きく与えているということが推定される。これは、ビット７が、インデックスに含まれない他のビットの分布を反映しているともいえ、例えば、レコードどうしにおいて、ビット７の値に相関が認められた場合に、他のビットにおいても相関が認められる可能性が高く、他のビットにおいても同じような挙動を示すことが推定される。そこで、抽出処理を繰り返し実行する場合に、ビット７が、一部のビットのうちの１つとして選択される選択確率を増加するように設定することで、相関の高いレコード組の抽出もれがないようにできる可能性がある。なお、選択確率を増加させる設定は、図８の処理８０５により実行される。
【０１１９】
さらに例示すると、図９Ｂに示されるように、インデックス００００の抽出率“０．８０”が大きい閾値である“０．７０”以上である一方で、インデックス０１００の抽出率“０．００”は、小さい閾値である“０．１０”よりも大きく大きい閾値“０．７０”よりも小さい。このような場合には、ビット５の値が、レコードどうしの相関に与える影響が大きいか小さいかをまだ特定しきれないとして、図８の処理８０４や処理８０６の判定に従い、ビット５が選択される選択確率が変更されない。これは、ビット１についても同様である。
【０１２０】
図１０に、実施例の相関抽出方法にかかるデータの他の例が示される。図１０に沿って、あるビットの組み合わせに従ってインデックス毎のグループにレコードが分類された後、グループに属するレコードの数及び抽出率を使用して、ビットの部分組み合わせの選択確率が設定されるまでの具体例が説明される。なお、実施例は、図１０Ａ及びＢに示される値に限定されない。
【０１２１】
図１０Ａに、各レコードにおけるビット｛２、４、７、８｝が選択された場合の、各インデックスの抽出率が示される。これらのビットの組み合わせは、図９Ｂに示される選択確率の設定の結果、ビット７の選択確率が増加したことにより、あらためて４つのビットを選択した場合に、ビット７を含む｛２、４、７、８｝が選択された例である。
【０１２２】
ビット｛２、４、７、８｝に基づくインデックスが００００となるレコードの数が、図３に示される処理３０４や図７に示される処理７０５の結果、“１００００”であったとする。この場合、レコードによる組み合わせの数は、“４９９９５０００”となる。なお、この計算は、図７に示される処理７０７において実行される。
【０１２３】
このレコードの組み合わせのうち、図３の処理３０５や図７の処理７０６により、ビット｛２、４、７、８｝以外のビットも使用して相関が計算された結果、相関が高いレコード組の数が“０”であったとする。従って、この時の抽出率は“０．００”となる。これらの結果は、図７の処理７０７により、図１０Ａに示されるように登録される。
【０１２４】
同様の計算により、インデックス０００１に分類されたレコード数が“１００００”であって、抽出率が“０．８０”であること、インデックス１１１１に分類されたレコード数が“６００００”であって、抽出率が“０．００”等であることが、他のインデックスを代表して、図１０Ａに例示されている。
【０１２５】
図１０Ｂに、レコード数及び抽出率に基づきビットの部分組み合わせの選択確率を設定する場合の具体例が示される。例えば、インデックス１１１１のグループに分類されたレコード数は、図１０Ａにも示されるように、“６００００”であるにも関わらず、それらのレコードの組み合わせにおいて、相関が高いと認められたレコード組は高々“４”組であり、その結果、抽出率が“０．００”となっている。つまり、｛２、４、７、８｝に基づくインデックスを使用して相関計算を絞っても、相関の高いレコード組を通出できる可能性が低く、抽出効率が悪いといえる。
【０１２６】
このような判定は、分類されたレコード数がレコード数の閾値よりも大きいかどうかが処理８１０により判定され、計算された抽出率が閾値よりも小さいかどうかが処理８１１によって判定されることにより実行される。そして、この判定の結果としてビットの部分組み合わせである、｛２、４｝、｛２、７｝、｛２、８｝、｛４、７｝、｛４、８｝、及び｛７、８｝が選択される選択確率が減少される。なお、選択確率を減らす処理は、処理８１２により実行される。この処理では、処理３０３や処理７０４において複数のビットを選択する場合に、例えばビット２が選ばれたのであれば、残りのビットを選択する際に、ビット４、ビット７、及びビット８が選択される選択確率を小さくしておくことで実現できる。
【０１２７】
以上に説明したように、上述の実施例に一側面によれば、データ列からなる情報どうしの相関計算で、データ列の一部のビットを使って判定された相関が高い情報のペアに限り、他のビットも使って相関を詳細に計算することで、相関が高い情報のペアを抽出する際の計算量が減る。
【０１２８】
これは、複数の情報どうしの相関を抽出する場合、情報の数が増えることで、相関計算の対象となる情報の組み合わせ数が多くなり、相関の計算量が膨大になってしまうからである。
【０１２９】
また、上述の実施例の他の側面によれば、複数の属性を有する情報どうしの相関計算において、複数の属性から選ばれた一部の属性が等しい情報の組合せだけ、属性の値全てを用いて相関を計算することで、相関計算を、相関が高いと予測される情報の組合せに絞り、計算量を減らしている。
【０１３０】
ところで、相関計算の計算量を少なくするために、例えば、情報に定められた複数の属性において特定の属性を除き、残りの属性を使用して情報どうしの相関を計算すると、相関が高い情報の組み合わせの抽出もれが発生する可能性がある。
【０１３１】
そこで、上述の実施例の他の側面によれば、複数の属性から一部の属性を選ぶ場合に、その属性の値が異なると、情報どうしの相関の差が所定以上になる場合には、その属性が含まれる確率が高くなるように、他の一部の属性を選択して情報どうしの相関を評価することで、情報どうしの相関を高める可能性の高い属性に絞り込んで、相関の評価を継続し、相関が高い情報の組み合わせの抽出もれが少なくなるようにしている。
【０１３２】
また、インデックスにより定められるグループに分類されたレコードの数が多くても、それらのレコード組の相関が低い場合、インデックスを定めている属性の組み合わせは、レコードどうしの相関に対する影響の度合いが低いといえる。
【０１３３】
そこで、上述の実施例の他の側面によれば、インデックスにより定められるグループに分類されたレコードの数が多くても、それらのレコード組の相関が低い場合、インデックスを定めている属性の一部による組み合わせが選ばれる確率が小さくなるように、他の一部の属性を選択して情報どうしの相関を評価することで、情報どうしの相関に寄与していない属性の組み合わせが選ばれないように相関の評価を継続し、相関が高い情報の組み合わせの抽出される確率が高まるようにしている。
【０１３４】
以上の実施例に関し、さらに以下の付記を開示する。
（付記１）  データ列を含む複数の情報どうしの相関を抽出する方法であって、コンピュータが、前記データ列から、一部のビットを選択し、選択された前記一部のビットに基づいて、前記複数の情報の相関を判定し、判定の結果に応じて、前記データ列における前記一部のビット以外のビットに基づいて、前記複数の情報の相関を抽出する
ことを特徴とする相関抽出方法。
（付記２）  前記コンピュータは、前記判定の結果に応じて、前記複数の情報の相関を抽出するための相関計算の対象となる情報のペアを、前記複数の情報における組み合わせから除外することを特徴とする付記１に記載の相関抽出方法。
（付記３）  前記コンピュータは、前記判定の結果に応じて相関が高いと予測される情報について、前記データ列における前記一部のビット以外のビットに基づいて、前記相関が高いと予測される情報の相関を計算することを特徴とする付記１に記載の相関抽出方法。
（付記４）  前記コンピュータが、前記相関の計算の結果に基づいて、特定の情報の組み合わせを登録し、前記データ列から、他の一部のビットを選択し、前記他の一部のビットに基づいて前記複数の情報の相関を抽出する場合に、登録されている前記特定の情報の組み合わせであれば相関の計算をしないことを特徴とする付記３に記載の相関抽出方法。
（付記５）  前記特定の情報の組み合わせは、前記相関の計算の結果、相関が所定以上となる情報の組み合わせであることを特徴とする付記４に記載の相関抽出方法。
（付記６）  前記ビットは前記複数の情報において定められた属性であり、前記データ列は複数の前記属性の値により構成され、前記コンピュータは、前記複数の属性から、一部の属性を選択することで、前記データ列から前記一部のビットを選択し、選択された前記一部の属性に基づいて前記複数の情報をグループに分類することで、前記選択された前記一部のビットに基づいて前記複数の情報の相関を判定し、同じグループに分類された情報の相関の計算に基づいて、前記複数の情報の相関を抽出することを特徴とする付記１〜５の何れか１つに記載の相関抽出方法。
（付記７）  前記コンピュータが、前記複数の情報を、前記選択された前記一部の属性についての値の組み合わせに従って、前記グループに分類し、前記組み合わせに含まれる値において、特定の属性についての値が異なると、情報の相関の差が所定以上になる場合には、前記特定の属性が含まれる確率が高くなるように、前記複数の情報の各々について、前記複数の属性から、他の一部の属性を選択して、選択された前記他の一部の属性に基づいて、前記複数の情報の相関を抽出することを特徴とする付記６に記載の相関抽出方法。
（付記８）  前記コンピュータが、前記同じグループに分類された情報の数が所定数以上になるグループであって、当該グループに分類された情報の相関の差が所定以下になる場合には、当該グループを特定するための値の組み合わせの一部が含まれる確率が小さくなり、かつ、前記特定の属性が含まれる確率が高くなるように、前記複数の情報の各々について、前記複数の属性から、前記他の一部の属性を選択することを特徴とする付記７に記載の相関抽出方法。
（付記９）  前記コンピュータが、前記複数の情報を、前記選択された前記一部の属性についての値の組み合わせに従って、前記グループに分類し、前記同じグループに分類された情報の数が所定数以上になるグループであって、当該グループに分類された情報の相関の差が所定以下になる場合には、当該グループを特定するための値の組み合わせの一部が含まれる確率が小さくなるように、前記複数の属性から、他の一部の属性を選択し、選択された前記他の一部の属性に基づいて、前記複数の情報の相関を抽出することを特徴とする付記６に記載の相関抽出方法。
（付記１０）  前記コンピュータが、前記複数の属性についての値を離散化することを特徴とする付記６〜９の何れか１つに記載の相関抽出方法。
（付記１１）  前記複数の情報の各々は、前記複数の属性毎に値が登録されたレコードであり、前記コンピュータは、前記選択された前記一部の属性についての値の組み合わせをインデックスにし、同じインデックスになるレコードどうしを、前記同じグループに分類することを特徴とする付記６〜１０の何れか１つに記載の相関抽出方法。
（付記１２）  前記複数の情報の相関を抽出することは、相関が認められる情報の組み合わせを抽出することであることを特徴とする付記１〜１１の何れか１つに記載の相関抽出方法。
（付記１３）  データ列を含む複数の情報の相関を抽出する装置であって、前記データ列から、一部のビットを選択する選択部と、選択された前記一部のビットに基づいて、前記複数の情報の相関を判定する判定部と、判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出する抽出部とを有することを特徴とする相関抽出装置。
（付記１４）  データ列を含む複数の情報の相関を抽出するためのプログラムであって、コンピュータに、前記データ列から、一部のビットを選択させ、選択された前記一部のビットに基づいて、前記複数の情報の相関を判定させ、判定の結果に応じて、前記データ列における前記一部のビット以外のビットにも基づいて、前記複数の情報の相関を抽出させることを特徴とするプログラム。
【符号の説明】
【０１３５】
１  サーバ
２  ＣＰＵ
３  メモリコントローラ
４  メモリ
５  メモリバス
６  ＩＯバスコントローラ
７  ＮＩＣ
８  ＩＯバス
９  記憶装置
２００  計算部
２０１  選択部
２０２  分類部
２０３  抽出部
２０４  判定部
２０５  読み出し部
２０６  登録部
２０７  更新部
２０８  設定部
２０９  比較部
【図１】
2015022613.tif 000003
【図２】
2015022613.tif 000004
【図３】
2015022613.tif 000005
【図４】
2015022613.tif 000006
【図５】
2015022613.tif 000007
【図６】
2015022613.tif 000008
【図７】
2015022613.tif 000009
【図８】
2015022613.tif 000010
【図９】
2015022613.tif 000011
【図１０】
2015022613.tif 000012