(57)【要約】【課題】近傍事例を探索する手法において、空間インデクス手法では基準事例ごとに探索処理が行われるため、類似した基準事例が存在した場合にも重複した探索処理が行われ、処理量が増大する。【解決手段】類似した基準事例に対して近傍事例探索が行われるように、基準事例をソートして探索の順番を決める。最初の基準事例に対する近傍事例探索時に、基準事例周辺に存在していた探索事例をキャッシュとして記憶しておき、以後の探索は記憶した探索事例から開始する。探索を実施する基準事例がキャッシュから外れた場合には、その基準事例を中心に新たなキャッシュを作成する。【選択図】  図１
2004326636.tif 000002
【特許請求の範囲】
【請求項１】
ユーザが指定した事象の観測事例に対し、事例間の距離を用いて近傍に存在する他の事例を探索する近傍事例探索方法において、探索を実施する事例を読み出して探索の順番を決定するステップと、近傍の範囲及びキャッシュの範囲をユーザが規定するステップと、探索を実施する事例を１つ読み出すステップと、読み出した事例がキャッシュに含まれるか判定するステップと、読み出した事例と距離の短いものをキャッシュに存在する事例から抽出するステップと、探索する範囲がキャッシュだけで良いかどうか判定するステップと、探索結果を保存するステップと、読み出す事例が残っているか判定するステップと、読み出した事例と距離の短いものをキャッシュに存在する事例を除く全事例の中から抽出するステップと、全事例を探索してキャッシュを作成するステップとを有することを特徴とする近傍事例探索方法。
【請求項２】
請求項１の近傍事例探索方法において、近傍の範囲及びキャッシュの範囲をユーザが規定するステップが、最近傍事例までの距離に対する係数、事例数のいずれかで規定するステップを含むことを特徴とする近傍事例探索方法。
【請求項３】
請求項１の近傍事例探索方法において、探索を実施する事例を読み出して探索の順番を決定するステップが、最も近い距離に存在する事例を逐次読み出すステップを含むことを特徴とする近傍事例探索方法。
【請求項４】
請求項３の近傍事例探索方法において、最も近い距離に存在する事例を逐次読み出すステップが、分散が最大となる変数を選択し、その変数値に基づいて事例を並べ替えるステップを含むことを特徴とする近傍事例探索方法。
【請求項５】
顧客に勧める商品を、その顧客に類似した他の顧客が購入した商品を元に決定する商品推薦方法において、請求項１の近傍事例探索方法を用いて類似した顧客を抽出することを特徴とする近傍事例探索方法。
【請求項６】
ユーザが指定した事象の観測事例に対し、事例間の距離を用いて近傍に存在する他の事例を探索する近傍事例探索装置において、探索を実施する事例を読み出して探索の順番を決定する手段と、近傍の範囲及びキャッシュの範囲をユーザが規定する手段と、探索を実施する事例を１つ読み出す手段と、読み出した事例がキャッシュに含まれるか判定する手段と、読み出した事例と距離の短いものをキャッシュに存在する事例から抽出する手段と、探索する範囲がキャッシュだけで良いかどうか判定する手段と、探索結果を保存する手段と、読み出す事例が残っているか判定する手段と、読み出した事例と距離の短いものをキャッシュに存在する事例を除く全事例の中から抽出する手段と、全事例を探索してキャッシュを作成する手段とを有することを特徴とする近傍事例探索装置。
【請求項７】
請求項６の近傍事例探索装置において、近傍の範囲及びキャッシュの範囲をユーザが規定する手段が、最近傍事例までの距離に対する係数、事例数のいずれかで規定する手段を含むことを特徴とする近傍事例探索装置。
【請求項８】
請求項６の近傍事例探索装置において、探索を実施する事例を読み出して探索の順番を決定する手段が、最も近い距離に存在する事例を逐次読み出す手段を含むことを特徴とする近傍事例探索装置。
【請求項９】
請求項８の近傍事例探索装置において、最も近い距離に存在する事例を逐次読み出す手段が、分散が最大となる変数を選択し、その変数値に基づいて事例を並べ替える手段を含むことを特徴とする近傍事例探索装置。
【請求項１０】
顧客に勧める商品を、その顧客に類似した他の顧客が購入した商品を元に決定する商品推薦装置において、請求項６の近傍事例探索装置を用いて類似した顧客を抽出することを特徴とする近傍事例探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、数値及び記号値によって特徴量表現された事例が存在する多次元空間において、ユーザが指定した事例の近傍に存在する他の事例を探索するシステムに関し、特にユーザが複数の事例を指定する場合に適用して探索を高速化する技術及び顧客に推薦する商品の決定を高速化する技術に関するものである。
【０００２】
【従来の技術】
近傍事例の探索を高速に行う方法に空間インデクスがある。この方法は、事例の分布に応じて多次元空間を部分空間に分割し、そのインデクスとして代表値と所属する事例を求めておくものである。探索時には代表値を利用して探索すべき事例を絞り込み、事例同士の距離計算回数を削減させる。
【０００３】
部分空間を２点により定義される矩形領域でインデクスを管理する方法にＲ−Ｔｒｅｅ（非特許文献１参照）、中心からの距離で定義される球形領域でインデクスを管理する方法にＳＳ−Ｔｒｅｅ（非特許文献２参照）、矩形と球形の両方を用いてインデクスを管理する方法にＳＲ−Ｔｒｅｅ（非特許文献３参照）がある。以後、これらを従来技術１と呼ぶ。
【０００４】
また、多次元空間を１次元軸に射影して近傍事例を探索する方法がある（非特許文献４参照）。この方法は、ベクトルのノルムが各成分の値よりも小さくならないことを利用したもので、射影軸上において近傍事例のノルムよりも遠い位置に存在する事例は探索しなくて良いため、計算量を削減できる。以後、これを従来技術２と呼ぶ。
【０００５】
【非特許文献１】
Ａ．  Ｇｕｔｔｍａｎ、Ｒ−ｔｒｅｅｓ：  ａ  ｄｙｎａｍｉｃ  ｉｎｄｅｘ  ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  ｓｐａｔｉａｌ  ｓｅａｒｃｈｉｎｇ、ＡＣＭ  ＳＩＧＭＯＤ  Ｐｒｏｃｅｅｄｉｎｇｓ、１９８４年、ｐ．４７−５７
【非特許文献２】
Ｄ．  Ａ．  Ｗｈｉｔｅ，  Ｒ．  Ｊａｉｎ、Ｓｉｍｉｌａｒｉｔｙ  Ｉｎｄｅｘｉｎｇ  ｗｉｔｈ  ｔｈｅ  ＳＳ−ｔｒｅｅ、ＩＣＤＥ  Ｐｒｏｃｅｅｄｉｎｇｓ、１９９６年、ｐ．５１６−５２３
【非特許文献３】
Ｎｏｒｉｏ  Ｋａｔａｙａｍａ，  Ｓｈｉｎ’ｉｃｈｉ  Ｓａｔｏｈ、Ｔｈｅ  ＳＲ−ｔｒｅｅ：  Ａｎ  Ｉｎｄｅｘ  Ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｈｉｇｈ−Ｄｉｍｅｎｓｉｏｎａｌ  Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒ  Ｑｕｅｒｉｅｓ、ＡＣＭ  ＳＩＧＭＯＤ  Ｐｒｏｃｅｅｄｉｎｇｓ、１９９７年、ｐ．３６９−３８０
【非特許文献４】
Ｆｒｉｅｄｍａｎ，  Ｊ．Ｈ．，  Ｂａｓｋｅｔｔ，  Ｆ．，  Ｓｈｕｓｔｅｋ，  Ｌ．Ｊ．、Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｆｉｎｄｉｎｇ  Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒｓ、  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｐｕｔｅｒｓ、１９７５年、ｐ．１０００−１００６
【０００６】
【発明が解決しようとする課題】
上記従来技術１は、多次元空間を部分空間に分割してインデクスを作成する処理を行うため、探索の前処理において処理量が増大する問題があり、インデクスを格納するデータ領域が必要となるため、探索に必要とするデータ領域が増大するという問題があった。以後、これらを課題１と呼ぶ。
【０００７】
上記従来技術２は、比較する事例の順番が常に固定であり、同じ事例を近傍探索する際にも処理を最初からやり直すという問題があった。以後、これを課題２と呼ぶ。
【０００８】
【課題を解決するための手段】
本発明は多次元空間にベクトルで表現される事例が多数存在する環境において、ユーザに指定された任意の事例に対して近傍に存在する事例を探索するシステムに関し、近傍を探索する事例が複数存在するときに、近傍を探索する順番を決定し、近傍事例探索を行う際にキャッシュとして事例を記憶しておき、それ以後の近傍事例探索時に記憶した事例を利用可能か判断し、利用可能であれば利用し、利用可能でなければ探索を行って、新たにキャッシュとして事例を覚えるもので、複数の事例に対して探索処理の共有手段を提供するものである。
【０００９】
本発明は多次元空間の分割処理を行わないため、課題１で問題とした処理量の増加を防ぐことが可能であり、インデクスを作成しないため、課題１で問題としたデータ領域の増大を防ぐことが可能である。また、キャッシュに事例を覚えることで、課題２で問題とした同じ事例に対する探索処理のやり直しを防ぐことが可能である。
【００１０】
【発明の実施の形態】
図１は本発明の第１の実施形態である近傍事例探索装置の概略構成を表している。ＣＰＵ１０１、ユーザ入力装置１０２、メモリ１１０、ディスク１２０がバス１０３によって接続された計算機において、メモリ１１０には基準事例管理部１１１、キャッシュ管理部１１２、探索処理部１１３の各プログラムが配置されて動作しており、またキャッシュ１１４、キャッシュ範囲１１５の各データが格納されている。ディスク１２０には基準事例群１２１、探索事例群１２２、探索結果１２３の各データが格納されている。
【００１１】
基準事例管理部１１１は、近傍事例探索を行う順番を決定するプログラムである。基準事例管理部１１１は、基準事例群１２１から基準事例を読み出し、近傍事例探索の実施順に並べ替える。
【００１２】
キャッシュ管理部１１２は、基準事例群１２１から読み出した基準事例がキャッシュ範囲１１５によって指定された範囲内に含まれるかどうか判定するプログラムである。キャッシュ管理部１１２は、基準事例群１２１から基準事例を読み出し、キャッシュ範囲１１５からキャッシュの範囲を読み出し、両者を比較して基準事例がキャッシュの範囲内に含まれるかどうか判定し、含まれる場合にはキャッシュ１１４に含まれる探索事例を探索して探索結果１２３を作成し、含まれない場合には全探索事例を探索して新しいキャッシュ１１４、キャッシュ範囲１１５、探索結果１２３を作成する。
【００１３】
探索処理部１１３は、基準事例から一定距離内に存在する探索事例を抽出するプログラムである。探索処理部１１３は、キャッシュ管理部１１２から探索対象とする探索事例群の情報を受け取り、基準事例とキャッシュに格納された探索事例もしくは基準事例と全探索事例の距離計算を行い、基準事例から一定距離内に存在する探索事例を抽出する。
【００１４】
キャッシュ１１４は、ある基準事例から一定距離内に存在する探索事例とその距離を格納したデータである。キャッシュ管理部１１２によってキャッシュ１１４が作成される時には、基準事例を中心にキャッシュ範囲内に存在する探索事例がキャッシュ１１４に格納される。探索処理部１１３によって探索処理が行われる時には、基準事例を中心に近傍距離内に存在する探索事例がキャッシュ１１４に格納される。キャッシュの範囲及び近傍距離の定義はユーザがユーザ入力装置１０２を使用して与える。
【００１５】
キャッシュ範囲１１５は、キャッシュの中心となる基準事例と、キャッシュがカバーする距離が格納されたデータである。キャッシュ範囲１１５は、キャッシュ管理部１１２によって作成され、その内容はキャッシュ１１４がキャッシュ管理部１１２によって新しく作成されるまで更新されない。
【００１６】
図２は、ディスク１２０およびメモリ１００に格納されている各データの例を示す図である。
【００１７】
基準事例２００は基準事例群１２１のデータ構造をテーブル形式で表したものである。基準事例群１２１は多次元ベクトルデータであり、基準事例２００は基準事例を識別する変数項目として基準事例番号２０１、基準事例の特徴を表す変数項目として変数Ａ２０２と変数Ｂ２０３を持つ。
【００１８】
探索事例２１０は探索事例群１２２のデータ構造をテーブル形式で表したものである。探索事例群１２２は多次元ベクトルデータであり、探索事例２１０は探索事例を識別する変数項目として探索事例番号２１１、探索事例の特徴を表す変数項目として変数Ａ２１２と変数Ｂ２１３を持つ。変数Ａ２１２は変数Ｂ２０２と同じ変数項目を表し、変数Ｂ２１３は変数Ａ２０３と同じ変数項目を表す。
【００１９】
探索結果データ２２０は探索結果１２３のデータ構造をテーブル形式で表したものである。探索結果１２３は多次元ベクトルデータであり、探索結果データ２２０は近傍事例探索を行った基準事例を識別する変数項目である基準事例番号２２１、近傍事例として見つかった探索事例の番号を表す変数項目である探索事例番号２２２で構成される。基準事例番号２２１は基準事例番号２０１と同じ変数項目を表し、探索事例番号２２２は探索事例番号２１１と同じ変数項目を表す。
【００２０】
キャッシュデータ２３０はキャッシュ１１４のデータ構造をテーブル形式で表したものである。キャッシュ１１４は多次元ベクトルデータであり、キャッシュデータ２３０はキャッシュに存在する探索事例を識別する変数項目である探索事例番号２３１、基準事例と探索事例間の距離を表す変数項目として距離２３２を持つ。探索事例番号２３１は、探索事例番号２１１および探索事例番号２２２と同じ変数項目を表す。キャッシュ管理部１１２によってキャッシュ１１４が作成される時には、基準事例からキャッシュ範囲１１５で定義された距離内に存在する探索事例の番号が探索事例番号２３１に格納され、基準事例と探索事例の距離が距離２３２に格納される。探索処理部１１３によってキャッシュ１１４に格納された探索事例に対して探索処理が行われる時には、基準事例とキャッシュ１１４に格納されていた探索事例との距離が距離２３２に格納される。探索処理部１１３によって全探索事例に対して探索処理が行われる時には、キャッシュ１１４作成時に格納した探索事例及び基準事例から近傍距離内に存在する探索事例の番号が探索事例番号２３１に格納され、基準事例と探索事例の距離が距離２３２に格納される。キャッシュの範囲及び近傍距離の定義はユーザがユーザ入力装置１０２を使用して与える。
【００２１】
キャッシュ範囲データ２４０はキャッシュ範囲１１５のデータ構造をテーブル形式で表したものである。キャッシュ範囲１１５は多次元ベクトルデータであり、キャッシュデータ２４０はキャッシュの中心となった基準事例の識別項目として基準事例番号２４１、キャッシュがカバーする中心からの距離を表す変数項目として距離２４２を持つ。基準事例番号２４１は、基準事例番号２０１及び基準事例番号２２１と同じ変数項目を表す。
【００２２】
図３は本実施形態の近傍事例探索装置の処理手順を示すフローチャ―トであり、図６は本実施形態の近傍事例探索装置における基準事例とキャッシュの関係を２次元で表した例である。図６における変数Ａは図２における変数Ａ２０２及び変数Ａ２１２と同じ変数項目を表し、図６における変数Ｂは図２における変数Ｂ２０３及び変数Ｂ２１３と同じ変数項目を表す。
【００２３】
以後、図１、図２、図３、図６を用いて本実施形態の近傍事例探索装置の処理手順３００を説明する。
【００２４】
ステップ３０１では、ユーザがユーザ入力装置１０２を操作し、基準事例に対する近傍を定義する値及びキャッシュの範囲を定義する値を設定して、近傍事例探索を開始する。近傍を定義する値は、基準事例からｋ番目に遠い探索事例までの距離、基準事例から最も近い探索事例までの距離のα倍のいずれかのうち少なくとも１つを与える。図６はαを与えた場合の例である。前述のｋならびにαはユーザが与える任意の定数である。また、キャッシュの範囲を定義する値は、基準事例からｍ番目に遠い探索事例までの距離、近傍距離のβ倍のいずれかのうち少なくとも１つを与える。図６はβを与えた場合の例である。前述のｍならびにβはユーザが与える任意の定数であり、ｍ≧ｋ、β≧αである。
【００２５】
ステップ３０２では、基準事例管理部１１１が基準事例群１２１へアクセスし、分散が最大となる変数を求め、その変数値に基づいて基準事例を並べ替える。これにより、近い距離にある基準事例を逐次選択して近傍事例探索を実施することが可能になる。図６の例では、基準事例群１２１に格納された基準事例１、基準事例２、基準事例３に対して、分散が最大となる変数に変数Ａが選択され、基準事例１、基準事例２、基準事例３の順番に並べ替えられたとする。
【００２６】
ステップ３０３では、キャッシュ管理部１１２が基準事例群１２１から基準事例を一つ読み出す。図６の例では基準事例１、基準事例２、基準事例３の順に読み出される。
【００２７】
ステップ３０４では、キャッシュ管理部１１２がキャッシュ１１４に基準事例が含まれるかどうか判定する。判定は、キャッシュ範囲１１５に格納された基準事例番号２４１を中心とした距離２４２の範囲に、ステップ３０３で読み出した基準事例が含まれるかどうかで行う。含まれる場合はステップ３０５へ進み、含まれない場合はステップ１１０へ進む。図６の例では、基準事例１が読み込まれた時点でキャッシュ１１４が存在しないため、ステップ３１０へ進んでキャッシュ１１４の作成を行う。基準事例２および基準事例３の場合は、基準事例１によってキャッシュがすでに作成されており、基準事例２の中心Ｏ２及び基準事例３の中心Ｏ３が、基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に含まれているため、ステップ３０５へ進む。
【００２８】
ステップ３０５では、探索処理部１１３がキャッシュ１１４に格納された探索事例に対して近傍事例探索を行う。探索処理部１１３はキャッシュ１１４の探索事例番号２３１に指定された探索事例に対して、基準事例との距離を計算し、距離２３２を更新してステップ３０６へ進む。ただし、距離を計算するのはキャッシュ１１４の作成時に探索事例番号２３１へ格納された探索事例のみである。図６の例では、基準事例２の場合は基準事例２の中心Ｏ２と探索事例番号２３１で指定された探索事例との距離を計算し、距離２３２を更新する。基準事例３の場合も同様に、基準事例３の中心Ｏ３と探索事例番号２３１で指定された探索事例との距離を計算し、距離２３２を更新する。
【００２９】
ステップ３０６では、キャッシュ管理部１１２がキャッシュ１１４とキャッシュ範囲１１５を参照し、ステップ３０５で行った近傍事例探索の結果を全探索事例に対する探索結果として良いか判定する。ステップ３０５で求めた基準事例の近傍がキャッシュの範囲内にあれば探索結果として良いと判定してステップ３０７へ進み、良いと判定しなければステップ３０９へ進む。図６の例では、基準事例２の場合は基準事例１の中心Ｏ１と基準事例２の中心Ｏ２の距離にα・Ｄ２を加えたものがβ・Ｄ１より小さくないため、近傍がキャッシュの範囲内におさまらず、探索結果として良いと判定できないためステップ３０９へ進む。基準事例３の場合は基準事例１の中心Ｏ１と基準事例３の中心Ｏ３の距離にα・Ｄ３を加えたものがβ・Ｄ１より小さいため、近傍がキャッシュの範囲内におさまり、探索結果として良いと判定できるためステップ３０７へ進む。
【００３０】
ステップ３０７では、キャッシュ管理部１１２がキャッシュ１１４を基準事例に対する近傍事例探索の結果として、探索結果１２３に格納し、ステップ３０８へ進む。図６の例では、基準事例１の場合は、キャッシュ１１４に基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に存在する探索事例が格納されているため、基準事例１の中心Ｏ１から半径α・Ｄ１の範囲に存在する事例を絞り込んで探索結果１２３に格納する。基準事例２の場合は、キャッシュ１１４に基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に存在する探索事例と基準事例２の中心Ｏ２から半径α・Ｄ２の範囲の存在する探索事例の両方が格納されているため、基準事例２の中心Ｏ２から半径α・Ｄ２の範囲に存在する事例を絞り込んで探索結果１２３に格納する。基準事例３の場合は、キャッシュ１１４に基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に存在する探索事例が格納されているため、基準事例３の中心Ｏ３から半径α・Ｄ３の範囲に存在する事例を絞り込んで探索結果１２３に格納する。
【００３１】
ステップ３０８では、キャッシュ管理部１１２は基準事例群１２１へアクセスし、近傍事例探索を行っていない基準事例がないか確認する。基準事例が残っていた場合には、ステップ３０３へと戻って、次の基準事例に対して近傍事例探索を行う。残っていなかった場合には、処理を終了する。図６の例では、基準事例１および基準事例２の場合には近傍事例探索を行う基準事例が残っているためステップ３０３へと戻り、基準事例３の場合は近傍事例探索を行う最後の基準事例であるため処理を終了する。
【００３２】
ステップ３０９では、探索処理部１１３は探索事例群１２２に含まれる全ての探索事例に対して基準事例との距離を計算し、ステップ３０１で与えられた近傍の定義を満たす探索事例をキャッシュ１１４に格納し、ステップ３０７へ進む。ただし、キャッシュ１１４に含まれる探索事例についてはステップ３０５で既に近傍事例探索済みであるため、対象から除く。図６の例では、基準事例２の場合は、基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に存在する探索事例を除く全探索事例に対して、基準事例２の中心Ｏ２から半径α・Ｄ２の範囲に存在する探索事例を抽出してキャッシュ１１４へ格納し、ステップ３０７へと進む。
【００３３】
ステップ３１０では、探索処理部１１３は探索事例群１２２に含まれる全ての探索事例に対して基準事例との距離を計算し、ステップ３０１においてユーザから与えられたキャッシュ範囲の定義を満たす探索事例を抽出し、キャッシュ１１４を作成する。図６の例では、基準事例１の場合は、基準事例１の中心Ｏ１から半径β・Ｄ１の範囲に存在する探索事例とその事例までの距離を求めキャッシュ１１４を作成する。
【００３４】
ステップ３０１において近い距離にある基準事例が逐次選択されるように並べ替え、ステップ３０４においてキャッシュが適用可能か判定し、ステップ３０６においてキャッシュに入らなかった場合にも探索の初期値を基準事例から近いところに設定し、ステップ３１０において近傍事例探索時にキャッシュを作成することで、複数の事例に対して近傍事例探索を行う際、類似した基準事例に対して同じ処理の実施を防止するところに、本実施例の特徴がある。これにより、類似した基準事例に対する探索処理量を削減することが可能になる。
【００３５】
図４は、本発明の第２の実施形態である商品推薦装置の概略構成を表している。図４の商品推薦装置は、図１の近傍事例探索装置を商品推薦に適用した場合の実施形態を示す図である。推論部４１７は、メモリ１１０に配置されて動作しているプログラムである。推論対象顧客４２１、既存顧客４２２、類似顧客４２３、推論結果４２４はディスク１２０に格納されるデータである。
【００３６】
ここで、推論対象顧客４２１は図１の基準事例群１２１、既存顧客４２２は図１の探索事例群１２２、類似顧客４２３は図１の探索結果１２３とそれぞれ対応し、推論結果４２３は推論部４１７による推論結果が格納されたデータである。
【００３７】
推論部４１７は、類似した顧客のデータを元に推薦する商品を計算するプログラムであり、推論対象顧客４２１、既存顧客４２２、類似顧客４２３を読み込み、推薦する商品を計算し、推論結果４２４へ出力する。
【００３８】
図５は、本実施形態の商品推薦装置におけるディスク１２０およびメモリ１１０に格納されている各データの例を示す図である。
【００３９】
推論実施顧客データ５００は推論実施顧客４２１のデータ構造をテーブル形式で表したものである。推論実施顧客４２１は多次元ベクトルデータであり、推論実施顧客データ５００顧客同士を識別する変数項目として探索顧客番号５０１、顧客の特徴を表す変数項目として顧客属性５０２を持つ。
【００４０】
既存顧客データ５１０は既存顧客４２２のデータ構造をテーブル形式で表したものである。既存顧客４２２は多次元ベクトルデータであり、既存顧客データ５１０は顧客同士を識別する変数項目として既存顧客番号５１１、顧客の特徴を表す変数項目として顧客属性５１２、購入した商品の識別子として商品番号５１３を持つ。顧客属性５１２は顧客属性５０２と同じ変数項目を表す。
【００４１】
類似顧客データ５２０は類似事例４２３のデータ構造をテーブル形式で表したものである。類似事例４２３は多次元ベクトルデータであり、類似顧客データ５２０は近傍事例探索を行った推論実施顧客を識別する変数項目である推論顧客番号５２１、近傍事例として見つかった既存顧客の番号を表す変数項目である類似顧客番号５２２で構成される。
【００４２】
推論結果データ５３０は推論結果４２４のデータ構造をテーブル形式で表したものである。推論結果４２４は多次元ベクトルデータであり、推論結果データ５５０は推論を実施した顧客を識別する番号として推論顧客番号５３１、推薦する商品を識別する番号として推薦商品番号５３２を持つ。商品番号５３２は商品番号５１３と同じ変数項目を表す。
【００４３】
以下、図３、図４、図５を用いて本実施形態の商品推薦装置の処理手順を説明する。
【００４４】
図４に示すように、ユーザにより顧客データがディスクに用意され、図３に示した処理手順により類似顧客データが図５に示した類似顧客４２３に格納される。次に、推論部は類似顧客４２３に格納された類似顧客番号５２２を元に、既存顧客４２２から商品番号５１３を取得し、多数決によって推定値を計算する。この推定値を推薦する商品として決定し、商品番号５３２に格納する。
【００４５】
このように、複数の顧客に対して商品を推薦する際、類似した顧客を探索する処理においてキャッシュを使用するところに本実施例の特徴がある。これにより、類似した顧客に対する商品の推薦時に、類似顧客の探索処理量を削減することが可能になる。
【００４６】
【発明の効果】
本発明によれば、近傍事例探索を実施する基準事例が複数存在した際に、類似した基準事例に対してキャッシュに含まれる探索事例の探索で済ませることが出来るため、探索処理に必要な処理量を削減することが可能である。
【図面の簡単な説明】
【図１】本実施形態の近傍事例探索装置の概略構成を示す図である。
【図２】本実施形態の近傍事例探索装置の内部データ例を示す図である。
【図３】本実施形態の近傍事例探索装置の処理手順を示すフローチャートである。
【図４】本実施形態の商品推薦装置を示す図である。
【図５】本実施形態の商品推薦装置の内部データ例を示す図である。
【図６】本実施形態の近傍事例探索装置で用いるパラメータの関係図である。
【符号の説明】
１０１…ＣＰＵ、１０２…入力装置、１０３…バス、１１０…メモリ、１２０…ディスク、１１１…基準事例管理部、１１２…キャッシュ管理部、１１３…探索処理部、１２１…基準事例群、１２２…探索事例群、１２３…探索結果。
【図１】
2004326636.tif 000003
【図２】
2004326636.tif 000004
【図３】
2004326636.tif 000005
【図４】
2004326636.tif 000006
【図５】
2004326636.tif 000007
【図６】
2004326636.tif 000008