(57)【要約】 【課題】  複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を高速に生成する情報処理装置を提供する。【解決手段】  エントリーの各々を正負符号および取引数量からなる符号付きの値を成分とする数値ベクトルの形式で記憶する記憶手段と、前記記憶手段に記憶された複数のエントリーの組み合わせについて前記数値ベクトルの値に基づき評価コストを計算し、該評価コストを用いて最適な組み合わせを探索する探索手段と、前記探索手段により探索された最適な組み合わせの中の異なるエントリー間で前記取引項目を互いに対応付けるマッチング処理を行なうことにより前記取引情報を生成するマッチング処理手段と、を具備する。【選択図】    図１
2005108011.tif 000002
【特許請求の範囲】
【請求項１】
取引対象を提供する取引あるいは取引対象を入手する取引のどちらを希望するかを示す正負符号、取引項目名、および取引数量により一つの取引項目が表現され、各々が複数の前記取引項目を含む複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を生成する情報処理装置において、
前記複数のエントリーの各々を前記正負符号および前記取引数量からなる符号付きの値を成分とする数値ベクトルの形式で記憶する記憶手段と、
前記記憶手段に記憶された複数のエントリーの組み合わせについて前記数値ベクトルの値に基づき評価コストを計算し、該評価コストを用いて最適な組み合わせを探索する探索手段と、
前記探索手段により探索された最適な組み合わせの中の異なるエントリー間で前記取引項目を互いに対応付けるマッチング処理を行なうことにより前記取引情報を生成するマッチング処理手段と、
を具備する情報処理装置。
【請求項２】
前記マッチング処理手段により生成された取引情報の表示情報を生成する手段と、
前記表示情報を前記各エントリーを提供したユーザに送信する手段と、
を具備することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記数値ベクトルは、前記取引項目名に対応するインデックスを有することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記探索手段は、前記数値ベクトルの和を計算し、該数値ベクトルの和の各成分の絶対値和を前記評価コストとする請求項１に記載の情報処理装置。
【請求項５】
前記エントリーの各々は予め指定された期待効用値を含み、
前記探索手段は、前記複数のエントリーの各々の効用値を計算し、前記期待効用値と前記効用値との差分が小さくなるように該エントリーの組み合わせを逐次改善することを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記効用値は、一つのエントリーにおける取引の成立割合を含む請求項５に記載の情報処理装置。
【請求項７】
前記探索手段はシミュレーティッド・アニーリング法に従って前記最適な組み合わせを探索する請求項１に記載の情報処理装置。
【請求項８】
前記探索手段は前記ユーザから新たに提供された一つのエントリーを基点に前記最適な組み合わせを探索する請求項１に記載の情報処理装置。
【請求項９】
前記探索手段は前記記憶手段に記憶された全てのエントリーを分割し、該分割されたエントリー毎に前記最適な組み合わせを探索する請求項１に記載の情報処理装置。
【請求項１０】
前記取引項目名が異なる取引項目間を対応付けるテーブルと、
前記テーブルに従い対応付け可能な取引項目を含むエントリーの組み合わせを前記最適な組み合わせに追加する手段と、
を具備する請求項１に記載の情報処理装置。
【請求項１１】
取引対象を提供する取引あるいは取引対象を入手する取引のどちらを希望するかを示す正負符号、取引項目名、および取引数量により一つの取引項目が表現され、各々が複数の前記取引項目を含む複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を生成する取引情報生成方法において、
前記複数のエントリーの各々を前記正負符号および前記取引数量からなる符号付きの値を成分とする数値ベクトルの形式で記憶手段に記憶する記憶ステップと、
前記記憶手段に記憶された複数のエントリーの組み合わせについて前記数値ベクトルの値に基づき評価コストを計算し、該評価コストを用いて最適な組み合わせを探索する探索ステップと、
前記探索ステップにより探索された最適な組み合わせの中の異なるエントリー間で前記取引項目を互いに対応付けるマッチング処理を行なうことにより前記取引情報を生成するマッチング処理ステップと、
を含む取引情報生成方法。
【請求項１２】
取引対象を提供する取引あるいは取引対象を入手する取引のどちらを希望するかを示す正負符号、取引項目名、および取引数量により一つの取引項目が表現され、各々が複数の前記取引項目を含む複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を生成するプログラムにおいて、
前記複数のエントリーの各々を前記正負符号および前記取引数量からなる符号付きの値を成分とする数値ベクトルの形式で記憶手段に記憶する機能と、
前記記憶手段に記憶された複数のエントリーの組み合わせについて前記数値ベクトルの値に基づき評価コストを計算し、該評価コストを用いて最適な組み合わせを探索する探索機能と、
前記探索機能により探索された最適な組み合わせの中の異なるエントリー間で前記取引項目を互いに対応付けるマッチング処理を行なうことにより前記取引情報を生成するマッチング処理機能と、
をコンピュータにより実現するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザが希望する製品またはサービスの取引を表す複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を生成するための情報処理装置、取引情報生成方法、ならびにプログラムに関する。
【背景技術】
【０００２】
例えば複数の店舗間で在庫交換を行う場合、従来は登録された在庫の一覧の中から各ユーザ（各店舗）の検索条件に合ったものを見つけ出す、いわゆる検索システムがよく利用されている（例えば下記特許文献１参照）。また、旅行プラン作成システムにおいても、電車、飛行機、タクシー等の交通手段や、ホテル等の宿泊施設、観光場所等を組み合わせる場合に、ユーザごとに希望を取り入れて、基本的に個別の検索によってプランを作成している（例えば下記特許文献２参照）。
【０００３】
複数の業者や顧客が互いに関わることによって、初めて良好な取引（関係）が成立する場合が実問題として少なくない。例えば上記在庫交換において、業者の各店舗では入手したい在庫と提供したい在庫が複数存在する場合が多々ある。そのような場合、在庫１つずつについて取引先を見つけるのは大変であり、取引先がそれぞれ異なる場合には輸送費も余計にかかってしまう。また、在庫によっては一緒に入手したり、あるいはその逆に一緒に提供したい等の組合せもありうる。
【０００４】
このような多数の業者や顧客が希望する取引を集約すれば、１対１の場合あるいは１対多の場合よりも好ましい「多対多」の組合せが成立しうる。ここで、「多」というのは多数というよりもむしろ数個という意味である。なお、取引を伴うため、関係する業者や顧客は少ない方が好ましい。
【特許文献１】特開２００２−３６６８０７公報
【特許文献２】特開２００１−２８２８９３公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明はユーザが希望する製品またはサービスの取引を表すエントリーを集約し、そのマッチングを高速に求めて取引情報を生成し、ユーザに対し迅速に推奨することのできる情報処理装置および取引情報生成方法ならびにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一観点に係る情報処理装置は、取引対象を提供する取引あるいは取引対象を入手する取引のどちらを希望するかを示す正負符号、取引項目名、および取引数量により一つの取引項目が表現され、各々が複数の前記取引項目を含む複数のエントリーを組み合わせることにより、各エントリーを提供したユーザに推奨すべき取引情報を生成する情報処理装置において、前記複数のエントリーの各々を前記正負符号および前記取引数量からなる符号付きの値を成分とする数値ベクトルの形式で記憶する記憶手段と、前記記憶手段に記憶された複数のエントリーの組み合わせについて前記数値ベクトルの値に基づき評価コストを計算し、該評価コストを用いて最適な組み合わせを探索する探索手段と、前記探索手段により探索された最適な組み合わせの中の異なるエントリー間で前記取引項目を互いに対応付けるマッチング処理を行なうことにより前記取引情報を生成するマッチング処理手段と、を具備する。
【発明の効果】
【０００７】
本発明によれば、複数のエントリーの各々を正負符号および取引数量からなる符号付きの値を成分とする数値ベクトルの形式で表現し、この数値ベクトルの値に基づき評価コストを計算することから、処理を高速化できる。
【０００８】
したがって、ユーザが希望する製品またはサービスの取引を表すエントリーを集約し、そのマッチングを高速に求めて取引情報を生成し、ユーザに対し迅速に推奨することのできる情報処理装置および取引情報生成方法ならびにプログラムを提供できる。
【発明を実施するための最良の形態】
【０００９】
図１は本発明の実施形態に係り、取引情報を生成する情報処理装置が適用された電子取引システムの概略構成を示すブロック図である。本発明の実施形態に係る情報処理装置は、例えばグループ推奨サーバ２として実現される。グループ推奨サーバ２は汎用のコンピュータ、好ましくはサーバコンピュータからなり、ネットワーク１に接続されている。グループ推奨サーバ２には、ネットワーク１に接続されたパーソナルコンピュータ（ＰＣ）３や携帯端末４のユーザへの推奨のために、取引情報を生成しあるいは更新する機能を実現するためのプログラムがプログラム記憶装置２５に格納されている。このプログラムは例えばエントリー受付モジュール２０、推奨グループ探索モジュール２１、表示モジュール２２の３つのモジュールから構成される。プログラム記憶装置２５は例えば磁気ディスク装置や光ディスク装置等からなる。上記プログラムが図示しないＣＰＵからの制御でランダムアクセスメモリ（ＲＡＭ）に読み込まれ、同ＣＰＵにより実行されることにより、コンピュータをグループ推奨サーバ２として機能させることができる。なおグループ推奨サーバ２には、各種コンピュータ資源を管理し、ファイルシステムやネットワーク通信機能、ならびにグラフィカルユーザインタフェース（ＧＵＩ）等を提供するオペレーティングシステムも導入されている。また、上記磁気ディスク装置や光ディスク装置等を制御するファイルシステム上に、エントリー記憶装置２３および推奨グループ記憶装置２５が実現される。
【００１０】
グループ推奨サーバ２は、ユーザのＰＣ３や携帯端末４からネットワーク１を通じて送信される複数のエントリーを受信する。ここでのユーザは業者や顧客等が想定される。受信されたエントリーはエントリー受付モジュール２０により受付処理され、エントリー記憶装置２３に記憶される。
【００１１】
グループ推奨サーバ２は、それらのエントリーに対して、各エントリーの希望（期待効用）を満たすようなエントリーの組合せからなるグループとそのグループ内の要素間の取引関係（マッチング）を表す取引情報を高速に求め、これをグループ内の各エントリーの登録者に推奨する。ここで、「要素」とは製品やサービスなどの個々の取引項目のことをいう。要素には種類、型、色、日時などの属性が伴う場合があるが、以下の説明では異なる属性値を持つ要素は異なる要素として扱うものとする。各要素には、該要素を入手（購入）することの希望を示す場合には負の符号が付され、逆に、該要素を提供（販売）することの希望を示す場合には正の符号が付される。例えば要素Aが-Aという符号付きで表されている場合、その要素Aを入手する取引を希望する主体（業者等）が存在することを意味する。
【００１２】
エントリーは、１つまたは複数の符号付き要素からなる集合によって表現される。例えばe1={+A, -B, -B, +C}は１つのエントリーを表す。このエントリーe1は「要素Bを２つ入手して、かつ要素Aと要素Cを提供したい」という取引内容を表している。要素名が同じでかつ符号の異なる２つの符号付き要素は、互いに取引の条件を満たす。これをマッチング可能であるという。例えば、他のエントリーe2の中に-Cがあれば、e1の+Cとe2の-Cはマッチング可能である。マッチング可能な２つの符号付き要素の間に、実際に取引を定めること、あるいはその取引関係をマッチングという。
【００１３】
エントリーの「期待効用」とは、取引が成立して欲しい要素数の割合（値）のことをいいう。期待効用はエントリーごとに独立した値であってもよいし、また特に指定がない場合は期待効用のデフォルト値が用いられてもよい。また期待効用を全く指定しないことも可能である。その場合は期待効用を零と見なせばよい。また、後に詳述するグループの探索において取引の成立とみなせる要素数の割合をそのエントリーの「効用値」という。例えば前記エントリーe1の期待効用が0.7である場合、このエントリーe1の例えば{-B, -B, +C}に対する取引が成立するならば、e1の効用値は3/4=0.75であり、期待効用の値を上回るから、その取引はエントリーe1の期待効用を満たしていると解釈される。
【００１４】
エントリー内の符号付き要素の数をその「エントリーのサイズ」という。前記エントリーe1のサイズは４である。また、グループ内のエントリー数をその「グループのサイズ」という。グループ推奨サーバ２で得られたそれぞれのグループの情報は、その後、該グループ内の各エントリーの登録者に推奨（通知）されることになる。なお、グループのサイズは小さい方が好ましいことから、グループのサイズには例えば「１０以下でなければならない」というような制約条件が前もって与えられるものとする。このサイズに関する制約条件（以下、「サイズ制約条件」という）を満たし、かつ内包するエントリーの効用値が全て期待効用以上であるようなグループを「推奨グループ」という。推奨グループを求めることは、そのグループ内の取引関係（マッチング）をも求めることを意味する。
【００１５】
ここで、例えば次の４つのエントリーe1={+A, -B, -B, +C}, e2={+A, -C, -D}, e3={+B, -C, +E}, e4={-A, +D}が既にグループ推奨サーバ２に受け付けられており、そこに新たにエントリーe5={-A, +B, -E}が受け付けられたとする。
【００１６】
同じエントリー内には、+Aと-Aのように、要素名が同一で符号が異なる要素のペアは冗長であるから存在しないものと仮定してよい。このように仮定すると、エントリーは要素をインデックスに持つ数値ベクトルで表現できる。例えば、上記のエントリーe1,e2, …,e5はそれぞれ、  
e1=( 1,-2, 1, 0, 0),   
e2=( 1, 0,-1,-1, 0),   
e3=( 0, 1,-1, 0, 1),   
e4=(-1, 0, 0, 1, 0),   
e5=(-1, 1, 0, 0,-1)   
という数値ベクトルで表現できる。各エントリーのインデックスは要素名A, B, C, D, Eに相当する。この数値ベクトルを「要素ベクトル」と呼ぶことにする。
【００１７】
１つまたは複数のエントリーからなるグループに対して、それらのエントリーの要素ベクトルの和の各成分の絶対値の和を、そのグループの「コスト」という。例えば上記の例においてグループ{e1, e2, e3}の要素ベクトルの和は(2,-1,-1,-1, 1)となる。このグループのコストは2+1+1+1+1=6である。要素ベクトルの和を計算する過程では、同じインデックスの正の値と負の値により和が帳消しになる場合がある。これは、異なるエントリーで対応する要素間に取引（マッチング）が可能であることを意味する。
【００１８】
例えば、上記エントリーe1とe2の要素ベクトルの和を計算すると、３番目のインデックスにおける和の値が0となる。これは、エントリーe1の要素+Cとエントリーe2の要素-Cの間に取引が可能であることを意味する。
【００１９】
一般に、コストが小さいグループほど、それに含まれる各エントリーの効用値は大きくなる。特にコストが0であるようなグループの場合は、そのグループ内のどのエントリーの効用値も1となる。
【００２０】
以下、推奨グループを求める方法として、新たに受け付けられたエントリーを対象に推奨グループを求める第１の方法を第１の実施形態において説明し、常に全エントリーを対象に推奨グループへの分割を行う第２の方法を第２の実施形態において説明する。例えば次の４つのエントリーe1={+A, -B, -B, +C}, e2={+A, -C, -D}, e3={+B, -C, +E}, e4={-A, +D}が既に登録済みであり、そこに新たにエントリーe5={-A, +B, -E}が登録されたとする。このとき第１の方法では、図２に示すように、基点エントリーe5を含むグループとして例えばG1={e1, e3, e5}を求める。グループ推奨サーバ２は、このグループG1をe1, e3, e5のそれぞれの登録者に推奨する。ここで、グループG1内の各エントリーの効用値は全て1であることに注意する。もしe2とe5の期待効用がともに1/3以下ならば、グループ{e2, e5}も推奨可能である。一方、第２の方法では、図３に示すように、例えばG1={e1, e3, e5}, G2={e2, e4}を求めて、関係する各エントリーの登録者に推奨する。なお、第２の方法はエントリーが新たに登録されるたびに実行するのではなく、ある一定の時間おきに実行してもよい。
【００２１】
（第１実施形態）
上述したように、第１の方法は、既に幾つかのエントリーが受け付けられ、エントリー記憶装置２３に記憶（登録）されている状況において、新たに受け付けられたエントリーを対象に推奨グループを求めるというものである。この新たに受け付けられ、推奨グループを求める基準とするエントリーを「基点エントリー」と称する。第１の方法では、基点エントリーを含む推奨グループを１つまたは複数求める。具体的には、基点エントリーを含み、かつグループのサイズ制約条件を満たすグループのうちで、コストができるだけ小さなグループを１つまたは複数求める。
【００２２】
ただし、コスト最小のグループであっても、そのグループに含まれる各エントリーの効用値が期待効用以上になるとは限らない。また、期待効用はどのエントリーに対しても同じ値とは限らない。したがって、コストの最小化のみでは不十分な場合もありうる。しかし、後述するように、コストができるだけ小さなグループを１つまたは複数求め、それらの各グループに対して具体的なマッチングを決める際に、各エントリーの期待効用と実際の効用値との差を、大きいものから順に縮めることによって、推奨グループが求まりやすいように制御することができる。
【００２３】
なお、対象とする要素名の集合は予め指定されているものとし、要素ベクトルのインデックスも予めどの要素名に相当するのかが決まっているものとする。そして、既存の各エントリーについては、その受け付け時に要素ベクトルに変換済みであるとする。また、対象とする要素名の集合は必ずしも予め指定する必要はない。指定しない場合は、エントリーが新たに受け付けられるたびに、そのエントリーで新たに使われている要素名を前記要素名の集合に追加し、かつ要素ベクトルの桁数をその分だけ動的に増やすことによって対応可能である。
【００２４】
第１の方法では、基点エントリーのみからなるグループを初期解とする。この初期解に対して既存のエントリーを追加し、削除し、あるいは入れ替えながら、逐次改善を繰り返す。その逐次改善の１手法として、本実施形態では例えばシミュレーテッド・アニーリング法（SA法）を用いる。なお、本発明の実施形態はSA法の基本的な機能を用いて実現することができるが、SA法の他の機能を追加的に用いて性能を向上することが好ましい。
【００２５】
また、SA法の他にタブーサーチや遺伝的アルゴリズムを使うことも可能である。これらの探索手法はメタ解法と呼ばれる（例えば、柳浦、茨木著、「組合せ最適化」、朝倉書店、２００１年、参照）。  SA法の温度パラメータとして、初期温度、最終温度、同一温度での繰り返し回数、および温度を下げる際に掛ける係数を前もって与えておく。SA法において、現在の解候補に少しだけ局所的な変更を加える操作のことを「ムーヴ(move)」という。
【００２６】
図４は第１の実施形態に係り、第１の方法に従って推奨グループを求める具体的な処理手順を示したフローチャートである。この処理は、図４に示すように６つのステップからなる。各ステップの詳細は次の通りである。
【００２７】
先ずステップＳ１において、基点エントリーを読み込み、これを要素ベクトルで表現すしてエントリー記憶装置２３に格納する。次にステップＳ２において、基点エントリーのみからなるグループGを作成し、これを初期解とする。このグループGを最良解（最良グループ）として記憶装置２４に保存する。次にステップＳ３では、グループGをSA法により逐次改善する。
【００２８】
ここで、ステップＳ３の詳細な処理手順を図５のフローチャートを参照して詳細に説明する。
【００２９】
先ずＳ３０１において、SA法の温度変数tに初期温度をセットする。次に、Ｓ３０２において、同一温度での繰り返し回数のカウンタcntに0をセットする。次に、Ｓ３０３において、グループGに対するムーヴのタイプを決め、グループGに対してそのムーヴを実行した場合のコストの差分を計算する。ムーヴには次の３つのタイプがある。
【００３０】
タイプ１：Gの外部からランダムに１つのエントリーe1を選び、e1をGに追加する。  
タイプ２：Gの内部からランダムに１つのエントリーe2を選び、e2をGから削除する。  
タイプ３：Gの内部と外部からランダムに１つずつエントリーe1, e2を選び、それらを入れ替える。即ち、Gからe1を削除し代わりにe2をGに追加する。
【００３１】
ムーブのタイプを決定して実行する処理は具体的には次の手順に従う。
【００３２】
（イ）：グループGのサイズが1の場合はタイプ１を選ぶ。グループGのサイズが所定のサイズ制約条件に等しい場合は、タイプ２またはタイプ３のいずれかをランダムに選ぶ。グループGのサイズがこれら以外の場合は、タイプ１、２、３のいずれかをランダムに選ぶ。
【００３３】
（ロ）：グループGに対して（イ）で選んだタイプのムーヴを実行した場合のコストの差分を計算する。
【００３４】
（ハ）：（イ）でムーヴの対象となったエントリーの番号e1やe2、およびそのムーヴを実行した場合のコストの差分を保存する（これらは次のＳ３０４で使用される）。
【００３５】
次に、図５のＳ３０４においては、Ｓ３０３で求めたコストの差分が0以下ならば、次の（ｉ）を実行し、0より大ならば（ｉｉ）を実行する。そしてカウンタcntに１を加算する。
【００３６】
（ｉ）：グループGに対して、Ｓ３０３で選択されたムーヴを実行する。グループGのコストが最良グループのコストよりも小さい場合は、最良グループをグループGに置き換える。また、グループGのコストが0になった場合は、ステップＳ４に進む。
【００３７】
（ｉｉ）：グループGに対して、Ｓ３０３で選択されたムーヴを実行するか否かを、確率p=exp(-1*コストの差分/現在の温度)に基づいて決定する。具体的には、０以上かつ１以下の乱数を発生させ、その値がp以下ならば、Ｓ３０３で選択されたムーヴを実行し、pよりも大ならば何もしない。
【００３８】
次に、図５のＳ３０５においては、カウンタcntをチェックする。カウンタcntが所定の繰り返し回数(max_cnt)に満たない場合はＳ３０３に戻る。
【００３９】
次に、Ｓ３０６においては、温度変数tに所定の係数α(0<α<1)を掛けることによって温度を下げる。その温度が所与の最終温度に満たない場合はＳ３０２に戻る（Ｓ３０７）。最終温度に達したならば、Ｓ３０８において、この時点の最良グループを新たな推奨グループの候補として採用する。
【００４０】
図４に説明を戻す。ステップＳ３により求まった推奨グループの候補数が、所定のグループ数に満たない場合はステップＳ２に戻り、達した場合はステップＳ４に進む。なお、ステップＳ２に戻った際は、SA法で用いられる乱数表を入れ替える。
【００４１】
次にステップＳ４では、ステップＳ３で求めた推奨グループの各候補に対して具体的なマッチングを求める。そのマッチングの結果について、グループ内の各エントリーの効用値を求める。そして、各エントリーの効用値が期待効用以上であるようなグループを推奨グループとして確定する。この一連の処理をマッチング処理という。
【００４２】
ここで、図４のステップＳ４の詳細な処理手順を図６のフローチャートを参照して説明する。ここでは、推奨グループの候補の１つをグループGとし、このグループGに対する処理を詳しく説明する。
【００４３】
先ずＳ４０１では、グループG内のエントリーを要素ごとに、その要素を正の要素として持つか、あるいは負の要素として持つかで分類する。この分類によって得られる結果を、グループGの「要素ごとのエントリー情報」という。
【００４４】
例えば、グループGが次の９つのエントリーからなるとする。各エントリーは要素ベクトルで表現されており、そのインデックスは左から順に要素名A, B, C, D, Eに相当するものとする。基点エントリーはe1であるとする。
【００４５】
e18=( 1, 1, 0, 0, 1),   
e79=(-1, 0,-2,-2, 0),   
e80=( 1,-2, 0, 1, 1),   
e72=(-1, 1, 0, 1,-1),   
e76=( 0, 1,-1, 1, 0),   
e1=(-1,-1, 0, 0, 0),   
e96=( 0, 0, 1, 1, 0),   
e63=( 0, 0, 0,-2, 1),   
e88=( 0, 0,-1, 0,-1)
これらのエントリーを要素ごとに、その要素を正の要素として持つか、あるいは負の要素として持つかで分類すると、次のようになる。
【表１】
2005108011.tif 000003
【００４６】
要素ベクトルの成分の中に-2以下または2以上の値がある場合は、対応するエントリーの番号が複数回現れる。
【００４７】
次にＳ４０２では、Gの要素ごとのエントリー情報を参照して、マッチングが必然的に確定する部分をまず確定させる。例えば上記の例の場合、+Aの欄には２つのエントリー番号があり、-Aの欄には３つのエントリー番号があるため、e18およびe80の+Aには必ずマッチング相手が見つかることが分かる。確定する部分を明記すると次のようになる。
【表２】
2005108011.tif 000004
【００４８】
「#（数字）」が記入されている欄は未確定であり、括弧内のエントリーは、マッチング相手が未確定であることを表している。これら括弧内のリストを「未確定リスト」という。未確定リストについてはＳ４０４以降のステップにおいて、#の右側の数だけ選んで確定を行うことになる。具体的には、Ｓ４０４以降で並べ替えを行い、最終的には、同一カラムにあるエントリー同士が互いにマッチング相手であると見なす。なお、同一要素の正の欄または負の欄が空欄ならば、その要素の正および負の欄は共に確定したと見なす。また、要素Bのように正負のエントリー数が一致する場合は、この時点でマッチング相手も確定したものと見なす。
【００４９】
次にＳ４０３においてはグループG内の各エントリーに対して、Ｓ４０２で確定した部分だけを用いて効用値を求めるとともに、期待効用（値）から効用値を減じてこれを差分値（期待効用−効用値）とする。この時点で効用値が１のエントリーは、マッチングが確定済みのエントリーであると見なす。そして、未確定のエントリーをヒープに蓄える。このヒープは期待効用と効用値の差分値に関して降順の木構造である。「ヒープ」とは、根付き木のことであり、「根以外の各ノードｖに対して、親の要素の方がｖの要素よりも大きいか等しい」という条件を満すように、木の各ノードｖに順序集合Ｓの要素が割り当てられたものである。ヒープ自体については公知であり、例えば参考文献（「情報の構造（上）」、浅野孝夫著、日本評論社、ｐ．４５参照）に詳しい。なお、降順の木構造における「降順」とは、親の要素の方が子の要素よりも「大きいか等しい」という意味である。
【００５０】
上記の例の場合、どのエントリーの期待効用も0.5であるとすると、効用値と、期待効用と効用値の差分値は次のようになる。
【表３】
2005108011.tif 000005
ヒープが空でない限り、次のＳ４０４を繰り返し実行する。
【００５１】
Ｓ４０４では、ヒープの根からエントリーを削除する（このエントリーを記号entで表す）。そして、entと同じエントリーを未確定リストから探す。entと同じエントリーが見つかった場合は次のステップ（ｉ）を、見つからなかった場合は（ｉｉ）を実行する。
【００５２】
（ｉ）：entを同リストにおける最初の未確定のエントリーと交換し、entを未確定リストから外す。また、entの効用値と、期待効用と効用値の差分値を更新し、効用値が1未満の場合はentをヒープに戻す。効用値が1の場合はentを確定済みとし、ヒープには戻さない。
【００５３】
（ｉｉ）：entを確定済みとする（ヒープには戻さない）。
【００５４】
上記の例の場合、entは期待効用と効用値の差分値が最大のe79となる。未確定リストは、
【表４】
2005108011.tif 000006
【００５５】
である。e79は-Aの欄から見つかる。e79は-Aの欄における最初の未確定のエントリーであるから特に交換は不要であり、
【表５】
2005108011.tif 000007
に変更される。e79の効用値と期待効用と効用値の差分値については、
【００５６】
【表６】
2005108011.tif 000008
【００５７】
に変る。e79の効用値は１未満であるからヒープに戻す。なお、未確定リストの欄の#の右側の値が0になったら、その欄は確定したものとみなす（たとえ未確定のエントリーが残っていても、その欄は未確定リストとみなさない）。
【００５８】
次にＳ４０５においては、どのエントリーについても期待効用と効用値の差分値が0以下ならば、グループGを推奨グループとして確定する。そして、エントリー内の要素のマッチング関係についてはグループGの要素ごとのエントリー情報を参照し、同一要素の正負の欄において同一カラムにあるエントリー同士を互いのマッチング相手であると決定する。期待効用と効用値の差分値が正のエントリーがある場合は、グループGは無効とする（つまり推奨グループとして確定しない）。
【００５９】
上記の例の場合、各エントリーの効用値と、期待効用と効用値の差分値については次のようになる。
【表７】
2005108011.tif 000009
【００６０】
期待効用と効用値の差分値は全て0以下であるから、このグループGは推奨グループとして確定される。グループGの要素ごとのエントリー情報は次のようになる。
【表８】
2005108011.tif 000010
【００６１】
図４に説明を戻す。ステップＳ５においては、ステップＳ４で得られた各推奨グループに対して、それが更に小さな推奨グループに分割可能か否かを調べる。もし分割可能な推奨グループがあれば、それを分割して小さな推奨グループに置き換える。
【００６２】
一般に、エントリーe1とe2の要素間にマッチング関係が存在するとき、e1とe2はMに関して「隣接している」という。エントリーe1, enに対して、２つ以上のエントリーからなる系列e1, e2, ..., enが存在し、隣り合うどの２つのエントリーもMに関して隣接している場合、e1とenはMに関して「連結している」という。ステップＳ４で得られた推奨グループは、この連結性という同値関係によって複数の同値類に分割される場合がある。一般に、推奨グループのサイズは小さいほどよいので、このように分割可能な場合は分割を行う。
【００６３】
次のステップＳ６においては、推奨グループのデータを推奨グループ探索モジュール２１が出力する。即ち、推奨グループごとに、そのグループに含まれるエントリー番号の集合と、エントリー間の要素間のマッチング関係を出力する。
【００６４】
上記の例の場合、推奨グループの１つとして、  
e18={+A:e79, +B:e80, +E:e72},   
e79={-A:e18, -C:-, -C:-, -D:e80, -D:e72},   
e80={+A:e1, -B:e18, -B:e72, +D:e79, +E:-},   
e72={-A:-, +B:e80, +D:e79, -E:e18},   
e76={+B:e1, -C:-, +D:e63},   
e1={-A:e80, -B:e76},   
e96={+C:e88, +D:e63},   
e63={-D:e76, -D:e96, +E:e88},   
e88={-C:e96, -E:e63}  
が出力される。括弧内は、そのエントリーの符号付き要素名と、要素ごとのマッチング相手のエントリー番号を表す。マッチング相手がいない要素については記号"-"を付している。例えばe18の+A:e79は、e18の+Aとe79の-Aがマッチング関係にあることを示している。なお、このように出力された推奨グループの情報は推奨グループ記憶装置２４に格納される。また、表示モジュール２２は、上記のような推奨グループの表示情報を生成し、該当するユーザのＰＣ３や携帯端末４に送信する。
【００６５】
（第２実施形態）
次に、第２の方法について説明する。上述したように、第２の方法は全エントリーを対象に推奨グループへの分割を行う。全エントリーを対象とするのは、できるだけ多数のエントリーにグループを推奨する為である。尚、どの推奨グループにも属さないエントリーが存在し得るため、厳密な意味での「分割」ではないが、便宜上、分割という用語を用いる。第２の方法では、全エントリーを、グループのサイズ制約条件を満たすような複数のグループに分割し、それぞれのグループのコストの総和を最小化する。そのようにして得られるそれぞれのグループが全て推奨グループになるとは限らないが、第１の方法の場合と同様に、各グループ内でのマッチングを決める際になるべく推奨グループになるように制御するため、一般には、多数のエントリーに対してグループを推奨することができる。
【００６６】
第１の方法の場合と同様に、対象とする要素名の集合は予め指定されているものとし、要素ベクトルのインデックスも予めどの要素名に相当するのかが決まっているものとする。そして、各エントリーについては、その登録時に要素ベクトルによって表現されているものとする。
【００６７】
第２の方法では、まず全エントリーを１つのエントリーのみからなるグループに分割する。この分割により得られるグループ集合を初期解とする。そして、初期解のグループ間でエントリーを移動し、あるいは交換しながら、グループ集合を逐次改善する。その逐次改善の１手法として、第１の方法と同様にSA法を用いることができる。グループ集合のコストには、各グループのコストの総和を用いる。
【００６８】
図７は第２の実施形態に係り、第２の方法に従って推奨グループを求める具体的な処理手順を示したフローチャートである。この処理は、図７に示すように５つのステップからなる。各ステップの詳細は次の通りである。
【００６９】
まずステップＳ１において、全エントリーを１つのエントリーのみからなるグループに分割し、これにより得られたグループ集合Gを初期解とする。またこのグループ集合Gを最良解（最良グループ集合）として保存する。
【００７０】
次にステップＳ２では、グループ集合GをSA法で逐次改善する。ここで、図７のステップＳ２の詳細な処理手順を図８のフローチャートを参照して説明する。
【００７１】
先ずＳ２０１では、SA法の温度変数tに初期温度をセットする。次にＳ２０２では同一温度での繰り返し回数のカウンタcntに0をセットする。次にＳ２０３ではグループ集合Gの中から異なる２つのグループg1, g2をランダムに選び、サイズの大きい方をg1とする。サイズが同じ場合はグループ番号の小さい方をg1とする。そして、g1, g2に対するムーヴのタイプを決め、グループ集合Gに対してそのムーヴを実行した場合のコストの差分を計算する。ムーヴには次の４つのタイプがある。
【００７２】
タイプ１：g1, g2からそれぞれランダムに１つずつ選んだエントリーe1, e2をg1, g2間で交換する。  
タイプ２：g1からランダムに選んだエントリーe1をg2に移す。  
タイプ３：g2からランダムに選んだエントリーe2をg1に移す。  
タイプ４：g1のエントリー番号の列をランダムに選んだ境界で二分することによって、g1を２つのグループに分割する。  
ここで、ムーブのタイプを決定して実行する処理は具体的には次の手順に従う。
【００７３】
（イ）：g1のサイズが1（従ってg2のサイズも1）の場合は、タイプ３を選ぶ。g2のサイズが所定のサイズ制約条件に等しい（従ってg1のサイズも所定のサイズ制約条件に等しい）場合は、タイプ４を選ぶ。g1のサイズが所定のサイズ制約条件に等しく、かつg1のサイズが所定のサイズ制約条件に満たない場合はタイプ１または２のいずれかを一方をランダムに選ぶ。その他の場合はタイプ１、２、３のいずれか１つをランダムに選ぶ。
【００７４】
（ロ）：グループ集合Gに対して（イ）で選んだタイプのムーヴを実行した場合のコストの差分を計算する。
【００７５】
（ハ）：グループの番号g1, g2、エントリーの番号e1, e2、タイプ４における境界、およびムーヴを実行した場合のコストの差分を保存する（これらは次のＳ２０４で使用する）。
【００７６】
Ｓ２０４では、Ｓ２０３で求めたコストの差分が0以下ならば次の（ｉ）を、0より大ならば（ｉｉ）を実行する。そしてカウンタcntに１を加算する。
【００７７】
（ｉ）：グループ集合Gに対して、Ｓ２０３を選んだムーヴを実行する。グループ集合Gのコストが最良グループ集合のコストよりも小さい場合は、最良グループ集合をグループ集合Gに置き換える。また、グループ集合Gのコストが0になった場合は、ステップＳ３に進む。
【００７８】
（ｉｉ）：グループ集合Gに対して、Ｓ２０３で選んだムーヴを実行するか否かを、確率p=exp(-1*コストの差分/現在の温度)により決定する。即ち、0以上1以下の乱数を発生させ、その値がp以下ならばＳ２０３で選んだムーヴを実行し、pよりも大ならば何もしない。
【００７９】
次にＳ２０５ではカウンタcntをチェックする。このカウンタcntが所定の繰り返し回数(max_cnt)に満たない場合はＳ２０３に戻る。
【００８０】
次にＳ２０６では温度変数tに所定の係数α(0<α<1)を掛けることによって温度を下げる。その温度が所与の最終温度に満たない場合はＳ２０２に戻る（Ｓ２０７）。最終温度に達した場合は、この時点の最良グループ集合を推奨グループ集合の候補として採用する（Ｓ２０８）。もし推奨グループ集合の候補を複数求めたい場合は、ステップＳ１に戻り、SA法で使う乱数表を入れ替えてステップＳ１とＳ２を必要数繰り返せばよい。
【００８１】
図７に説明を戻す。次にステップＳ３では、ステップＳ２で求めた最良グループ集合Gの各グループに対してマッチングを決めて、かつグループ内の各エントリーの効用値を求める。そして、各エントリーの効用値が期待効用以上であるようなグループの全体を、推奨グループの全体として確定する。各グループに対する処理は、第１の方法のステップＳ４のＳ４０１〜Ｓ４０５（図６参照）と同様である。
【００８２】
次にステップＳ４では、ステップＳ３で得られた各推奨グループに対して、それが更に小さな推奨グループに分割可能か否かを調べる。もし分割可能な推奨グループがあれば、それを分割して小さな推奨グループに置き換える。
【００８３】
そしてステップＳ５においては、全ての推奨グループのデータを推奨グループ探索モジュール２１が出力する。即ち、推奨グループごとに、そのグループに含まれるエントリー番号の集合と、エントリー間の要素間のマッチング関係を出力する。
【００８４】
例えば、下記のような推奨グループのデータが出力される。g1, g2, g3は推奨グループに付した番号である。
【表９】
2005108011.tif 000011
【００８５】
（第３実施形態）
本発明の第３実施形態は上述した第１、第２実施形態のそれぞれと組み合わせることが可能である。第１、第２実施形態では、要素名が同じでかつ符号が異なる要素間のマッチングが想定されている。しかし、要素名が異なっていてもマッチングが可能な場合がある。例えば、「甲信越地方の野菜」の入手を望む人に「長野県の野菜」や「川上村のレタス」を提供する取引は現実に起こり得る。つまり、−（甲信越地方の野菜）と＋（長野県の野菜）、−（甲信越地方の野菜）と＋（川上村のレタス）はいずれも要素名が異なっているもののマッチングが可能である。また、レタスは野菜の一つの分類であるが、「川上村のレタス」の入手を望む人に「甲信越地方の野菜」を提供することが可能な場合もある。それは、＋（甲信越地方の野菜）という要素が、甲信越地方の野菜ならば何でも提供できるという意味を持つ場合もあるからである。
【００８６】
第３実施形態では、このように異なる要素間にもマッチング可能な組合せがある場合を予め想定し、そのような組合せを予めテーブル等に記憶しておく。そして、グループのコストを計算（第１の方法のステップＳ３、第２の方法のステップＳ２）する際、およびマッチングを決める（第１の方法のステップＳ４、第２の方法のステップＳ３）際に、そのテーブルを参照して、可能な限りマッチングを追加する。
【００８７】
本実施形態におけるグループのコストの計算方法について詳しく説明する。まず、同じ要素名の間のマッチングを考慮に入れ、これら要素ベクトルの全体の和をとる。そして、その和のベクトルＳの正の成分の要素に対して、それとマッチング可能な負の成分の要素が存在する場合は、その正の成分から１を減じ、負の成分に１を加算する。このような処理をベクトルＳの全ての正の成分に対して行う。最後にベクトルＳの各成分の絶対値の和を求め、それを前記グループのコストとする。
【００８８】
例えば、下記の９つのエントリーからなるグループGを例に説明する。これらのエントリーは要素ベクトルで表現されており、そのインデックスは左から順に要素名A, B, C, D, Eに相当するものとする。そして、異なる要素間には(-A,+C), (-C,+E), (-A,+E)という３つのマッチング可能な組合せがあるものとする。これらはテーブルM = {(-A,+C), (-C,+E), (-A,+E)}に格納されているものとする。  
e18=( 1, 1, 0, 0, 1),   
e79=(-1, 0,-2,-2, 0),   
e80=( 1,-2, 0, 1, 1),   
e72=(-1, 1, 0, 1,-1),   
e76=( 0, 1,-1, 1, 0),   
e1=(-1,-1, 0, 0, 0),   
e96=( 0, 0, 1, 1, 0),   
e63=( 0, 0, 0,-2, 1),   
e88=( 0, 0,-1, 0,-1)
このグループGのコストを計算する場合、まず、これら要素ベクトルの全体の和をとると、ベクトルS=(-1, 0,-3, 0, 1)が得られる。次に、ベクトルＳの５番目の成分１の要素Eに対して、それとマッチング可能な負の成分の要素があるか否かを、テーブルMで確かめる。この場合、(-C,+E)と(-A,+E)というマッチング可能な組合せが存在する。そこで例えば(-C,+E)を採用すると、ベクトルSはS=(-1, 0,-2, 0, 0)となる。このベクトルSにはもう正の成分がないので、この時点でグループGのコストは１＋２＝３と計算される。
【００８９】
次に、推奨グループの候補に対するマッチングの決め方について詳しく説明する。まず、前述した第１の方法のステップＳ４と同じ処理によって、同じ要素名の間のマッチングを決める。次に、効用値が１未満のエントリーを（期待効用−効用値）に関して降順のヒープに蓄える。そして、このヒープの根からエントリーを１つずつ取り出しては、未確定リストと、「異なる要素間でマッチング可能な組合せのテーブル」を参照してマッチング相手を探していく。その際、マッチング相手が見つからなかった場合は、再度ヒープの根からエントリーを取り出す。マッチング相手が見つかった場合は、その効用値が１に満たない場合に限りヒープに戻す。以下、ヒープが空になるまで同様の処理を繰り返す。途中で、もし正の要素の欄にしか未確定リストがない、あるいは負の要素の欄にしか未確定リストがない、という状態になった場合は、そこで処理を終了する。
【００９０】
例えば、上述のグループGが推奨グループの候補であるとして説明する。まず、前述した第１の方法のステップＳ４と同じ処理によって、同じ要素名の間のマッチングを決めると、グループGの要素ごとのエントリー情報として、
【表１０】
2005108011.tif 000012
【００９１】
が得られる。ここで括弧内はこの時点での未確定リストを表している。各エントリーの効用値と、期待効用と効用値の差分値については次のようになっている。
【表１１】
2005108011.tif 000013
【００９２】
次に、効用値が１未満のエントリーe79, e80, e72, e76を期待効用と効用値の差分値に関して降順のヒープに蓄える。このヒープの根はe79である。そこでe79を取り出し、未確定リストからe79を探すと、e79が-Cの欄に見つかる。次に、テーブルMの中から-Cを含む組合せ(-C,+E)を見つける（見つからない場合は、ヒープの根からエントリーを選び直すという処理に戻る）。そして、+Eの欄に未確定リストが存在するかを調べる。この場合、+Eの欄に未確定リストが存在し、e80があるので、e80の+Eとe79の-Cの間にマッチングを決定する（+Eの欄に未確定リストが存在しない場合は、ヒープの根からエントリーを選び直すという処理に戻る）。これによって、未確定リストは、
【表１２】
2005108011.tif 000014
となり、e79, e80の効用値と、期待効用と効用値の差分値は、
【００９３】
【表１３】
2005108011.tif 000015
【００９４】
となる。e79の効用値はまだ1に満たないのでe79はヒープに戻す。e80の効用値は１であるからe80はヒープから削除する。
【００９５】
以下、ヒープが空になるまで同様の処理を繰り返すが、この例の場合は-Aの欄と-Cの欄にしか未確定リストがないので、その時点で処理は終了となる。
【００９６】
以上説明した本発明の実施形態によれば、各エントリーを要素ベクトルで表現し、要素ベクトルの和から算出されるコストでグループを評価しながら逐次探索し、最後にグループの最良候補に対して要素間の取引関係（マッチング）を決めて効用値を算出する。したがって、グループの評価にはグループ内の具体的なマッチング情報が不要となることから、良好なグループの候補を高速に算出することができる。また、異なる要素間に取引（マッチング）可能な組合せがある場合にも、そのような組合せを予めテーブル等に記憶しておき、グループのコスト計算やマッチングを決める際に、前記テーブル等を参照して、可能な限りマッチングを追加することによって、良好なグループを高速に算出することができる。また、実施形態で説明した電子取引システムは、例えば社内の事業所間で必要物資と不要在庫の収受を決定するシステム等として実現してもよい。
【００９７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９８】
【図１】本発明の実施形態に係り、取引情報を生成する情報処理装置が適用された電子取引システムの概略構成を示すブロック図
【図２】第１の実施形態の概要を説明するための図
【図３】第２の実施形態の概要を説明するための図
【図４】第１の実施形態に係り、第１の方法に従って推奨グループを求める具体的な処理手順を示したフローチャート
【図５】図４のステップＳ３の詳細な処理手順を示すフローチャート
【図６】図４のステップＳ４の詳細な処理手順を示すフローチャート
【図７】第２の実施形態に係り、第２の方法に従って推奨グループを求める具体的な処理手順を示したフローチャート
【図８】図７のステップＳ２の詳細な処理手順を示すフローチャート
【符号の説明】
【００９９】
１…ネットワーク、２…グループ推奨サーバ、３…パーソナルコンピュータ（ＰＣ）、４…携帯端末、２０…エントリー受付モジュール、２１…推奨グループ探索モジュール、２２…表示モジュール、２３…エントリー記憶装置、２４…推奨グループ記憶装置、２５…プログラム記憶装置
【図１】
2005108011.tif 000016
【図２】
2005108011.tif 000017
【図３】
2005108011.tif 000018
【図４】
2005108011.tif 000019
【図５】
2005108011.tif 000020
【図６】
2005108011.tif 000021
【図７】
2005108011.tif 000022
【図８】
2005108011.tif 000023