(57)【要約】  本発明は、多次元空間からのターゲットアイテムにより表されるオブジェクトにスコアを提供する方法であって、前記スコアは、前記オブジェクトが所与のバイナリな性質を充足する確率を表し、当該方法は、記憶手段に接続される処理手段を有するコンピュータ環境において実行され、当該方法は、（ａ）前記多次元空間からのサンプルアイテムセットを表すデータを提供し、前記記憶手段に格納するステップであって、各サンプルアイテムは、該サンプルアイテムにより表されるオブジェクトが前記所与のバイナリな性質を充足する確率を表す多値ラベルに関連付けされる、前記提供及び格納するステップと、（ｂ）前記ターゲットアイテムを表すデータを前記記憶手段に格納するステップと、（ｃ）前記処理手段によって、所与の高さを有する有向バイナリツリーを表すデータを生成し、前記記憶手段に格納するステップであって、前記バイナリツリーは、該バイナリツリーにおける自らのポジションに関するインデックス値を有する複数のンモードにより規定され、前記ノードはルートノード、中間ノード及び終端ノードを有し、各ノードは、該ノードがルートノードである場合には関連するサブ空間は前記多次元空間全体であり、該ノードが非終端ノードである場合には関連するサブ空間は、前記非終端ノードの第１チャイルドノード及び第２チャイルドノードにそれぞれ関連する２つの互いに素なサブ空間ε＋及びε−に分割され、前記分割は、前記サブ空間ε＋に属するよう所与の第１ラベル値に関連するサンプルアイテムの個数及び／又は前記サブ空間ε−に属するよう所与の第２ラベル値に関連するサンプルアイテムの個数を最小化する分類手段に従って前記処理手段により実行され、前記第２ラベル値は、前記サンプルアイテムにより表されるオブジェクトが前記所与の第１ラベル値より前記所与のバイナリな性質を充足する確率が高いことを表す、前記生成及び格納するステップと、（ｄ）前記処理手段によって、前記バイナリツリーの少なくとも各終端ノードとスコアとを前記バイナリツリーにおけるそれのインデックス値に依存して関連付け、前記スコアの値を前記記憶手段に格納するステップと、（ｅ）前記処理手段によって、ターゲットノードを特定するステップであって、前記ターゲットノードは、関連するサブ空間が前記ターゲットアイテムを有する終端ノードである、前記特定するステップと、（ｆ）前記ターゲットノードに関連するスコアの値を出力するステップとを有する方法に関する。
2013541085.tif 000002
【特許請求の範囲】
【請求項１】
多次元空間からのターゲットアイテムにより表されるオブジェクトにスコアを提供する方法であって、前記スコアは、前記オブジェクトが所与のバイナリな性質を充足する確率を表し、当該方法は、記憶手段に接続される処理手段を有するコンピュータ環境において実行され、
当該方法は、
（ａ）前記多次元空間からのサンプルアイテムセットを表すデータを提供し、前記記憶手段に格納するステップであって、各サンプルアイテムは、該サンプルアイテムにより表されるオブジェクトが前記所与のバイナリな性質を充足する確率を表す多値ラベルに関連付けされる、前記提供及び格納するステップと、
（ｂ）前記ターゲットアイテムを表すデータを前記記憶手段に格納するステップと、
（ｃ）前記処理手段によって、所与の高さを有する有向バイナリツリーを表すデータを生成し、前記記憶手段に格納するステップであって、前記バイナリツリーは、該バイナリツリーにおける自らのポジションに関するインデックス値を有する複数のンモードにより規定され、前記ノードはルートノード、中間ノード及び終端ノードを有し、各ノードは、該ノードがルートノードである場合には関連するサブ空間は前記多次元空間全体であり、該ノードが非終端ノードである場合には関連するサブ空間は、前記非終端ノードの第１チャイルドノード及び第２チャイルドノードにそれぞれ関連する２つの互いに素なサブ空間ε＋及びε−に分割され、前記分割は、前記サブ空間ε＋に属するよう所与の第１ラベル値に関連するサンプルアイテムの個数及び／又は前記サブ空間ε−に属するよう所与の第２ラベル値に関連するサンプルアイテムの個数を最小化する分類手段に従って前記処理手段により実行され、前記第２ラベル値は、前記サンプルアイテムにより表されるオブジェクトが前記所与の第１ラベル値より前記所与のバイナリな性質を充足する確率が高いことを表す、前記生成及び格納するステップと、
（ｄ）前記処理手段によって、前記バイナリツリーの少なくとも各終端ノードとスコアとを前記バイナリツリーにおけるそれのインデックス値に依存して関連付け、前記スコアの値を前記記憶手段に格納するステップと、
（ｅ）前記処理手段によって、ターゲットノードを特定するステップであって、前記ターゲットノードは、関連するサブ空間が前記ターゲットアイテムを有する終端ノードである、前記特定するステップと、
（ｆ）前記ターゲットノードに関連するスコアの値を出力するステップと、
を有する方法。
【請求項２】
各ノードのインデックス値は、値のペアを有し、
第１インデックス値は、前記バイナリツリーにおける前記ノードの深さを表し、第２インデックス値は、前記ツリーにおける所与の深さレベルにおける前記ノードのポジションを表す、請求項１記載の方法。
【請求項３】
前記ルートノードのインデックスは（０，０）であり、
インデックスが（ｄ，ｋ）である非終端ノードの第１及び第２チャイルドノードのインデックスはそれぞれ、（ｄ＋１，２ｋ）及び（ｄ＋１，２ｋ＋１）である、請求項２記載の方法。
【請求項４】
インデックスが（ｄ，ｋ）であるノードに関連するスコアは、２Ｄ（１−ｋ／２ｄ）であり、Ｄは前記バイナリツリーの高さである、請求項３記載の方法。
【請求項５】
前記分割は、前記処理手段によって、前記サブ空間ε＋に属するよう所与の第１ラベル値に関連するサンプルアイテムの個数と、前記サブ空間ε−に属するよう所与の第２ラベル値に関連するサンプルアイテムの個数との重み付けされた組み合わせを最小化することによって実行される、請求項１乃至４何れか一項記載の方法。
【請求項６】
前記重み付けされた組み合わせのウェートはそれぞれ、互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第２ラベル値に関連するサンプルアイテムのレートと、互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第１ラベル値に関連するサンプルアイテムのレートとである、請求項５記載の方法。
【請求項７】
前記分割は、前記処理手段によって、
【数７８】
2013541085.tif 000080
の値を最小化することによって実行され、（Ｘ１，Ｙ１）．．．（Ｘｎ，Ｙｎ）はそれらのバイナリラベルに関連するサンプルアイテムのセットであり、ωは互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第２ラベル値に関連するサンプルアイテムのレートであり、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である、請求項６記載の方法。
【請求項８】
前記分割中に考慮する関連するサブ空間の次元数及び／又はサンプルアイテム数は、減少される、請求項１乃至７何れか一項記載の方法。
【請求項９】
前記多次元空間は、無限次元空間であり、
前記分割は、有限次元アイテムへのサンプルアイテムの近似を有する、請求項１乃至８何れか一項記載の方法。
【請求項１０】
（ｃ１）前記処理手段によって、前記形成されたバイナリツリーのサブツリーを選択し、前記バイナリツリーを前記サブツリーにより置換するステップを有し、
前記ステップ（ｃ１）は、ステップ（ｃ）に続く、請求項１乃至９何れか一項記載の方法。
【請求項１１】
ＲＯＣ（Ｒｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ）曲線は、可能な各サブツリーについてステップ（ｃ１）において前記処理手段により構成され、前記記憶手段に格納され、
前記選択されたサブツリーは、前記処理手段によって、関連するＲＯＣ曲線の下方の最も大きな面積を有するものとして決定される、請求項１０記載の方法。
【請求項１２】
ＲＯＣ曲線は、可能な各サブツリーについてステップ（ｃ１）において前記処理手段により構成され、前記記憶手段に格納され、
前記選択されたサブツリーは、関連するＲＯＣ曲線の下方の最も大きなＣｏｍｐｌｅｘｉｔｙ−ｐｅｎａｌｉｚｅｄされた面積を有するものとして決定される、請求項１０記載の方法。
【請求項１３】
前記ステップ（ｃ１）は、前記処理手段により前記可能なサブツリーのセットに対して実行される交差検証テストを有する、請求項１２記載の方法。
【請求項１４】
前記多値ラベルは、前記サンプルアイテムにより表されるオブジェクトが前記所与のバイナリな性質を充足するか否かを示すバイナリラベルであり、前記第１ラベル値は、前記所与のバイナリな性質を充足しないサンプルアイテムに関連するラベル値であり、前記第２ラベル値は、前記所与のバイナリな性質を充足するサンプルアイテムに関連するラベル値である、請求項１乃至１３何れか一項記載の方法。
【請求項１５】
前記多値ラベルは、少なくとも３つの値（１≦ξ≦Ξ）を有し、
前記ラベル値は、前記所与のバイナリな性質を充足する確率によって上がり、ラベル値の
【数７９】
2013541085.tif 000081
個の可能なペアのそれぞれについて、ξ１＜ξ２となるように有向バイナリツリーが形成及び格納され、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である、請求項１乃至１３何れか一項記載の方法。
【請求項１６】
前記多値ラベルは、少なくとも３つの値（１≦ξ≦Ξ）を有し、
前記ラベル値は、前記処置のバイナリな性質を充足する確率によって上がり、
ラベル値ξ２＝ξ１＋１の（Ξ−１）個の可能なペア（ξ１，ξ２）のそれぞれについて、有向バイナリツリーが形成及び格納され、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である、請求項１乃至１３何れか一項記載の方法。
【請求項１７】
ステップ（ａ）において、複数のサンプルアイテムセットが生成及び格納され、
各サンプルアイテムセットについて、有向バイナリツリーが形成及び格納される、請求項１乃至１６何れか一項記載の方法。
【請求項１８】
各サンプルアイテムセットは、前記処理手段によって、メインサンプルアイテムセットをリサンプリングすることによって生成されるブーストラップ複製である、請求項１７記載の方法。
【請求項１９】
（ｄ１）前記複数の形成されたバイナリツリーを集約し、最良のスコアリングルールを決定するステップをさらに有し、
前記ステップ（ｄ１）は、ステップ（ｃ）に続く、請求項１５乃至１８何れか一項記載の方法。
【請求項２０】
ステップ（ｄ１）は、
形成された各バイナリツリーについて、前記終端ノードに関連するサブ空間により形成される多次元空間のパーティションを提供し、記憶手段に格納するサブステップと、
前記処理手段によって、共通のサブパーティションを形成するため、前記パーティションを集約するサブステップと、
形成された各バイナリツリーについて、前記共通のサブパーティションの各パーツをスコアリングすることによって、スコアリングルールを提供及び格納するサブステップと、
各スコアリングルールについて、前記スコアリングルールに従ってスコアリングされた前記パーツのランキングを提供及び格納するサブステップと、
前記処理手段によって、前記複数のランキングから中間のランキングを決定し、前記中間のランキングを前記記憶手段に格納するサブステップと、
前記処理手段によって、前記中間のランキングに関連するスコアリングルールを前記最良のスコアリングルールとして選択するサブステップと、
を有する、請求項１９記載の方法。
【請求項２１】
前記中間のランキングを決定するサブステップは、前記処理手段により、各ランキングペアの間の非類似レートを計算し、その他のランキングと最も低い非類似レートを示すランキングを前記中間のランキングとして選択することを含む、請求項２０記載の方法。
【請求項２２】
前記中間のランキングは、
【数８０】
2013541085.tif 000082
となるようなランキング
【数８１】
2013541085.tif 000083
であり、
【数８２】
2013541085.tif 000084
はランキングであり、
【数８３】
2013541085.tif 000085
はランキングペアの間の非類似レートである。
【請求項２３】
前記非類似レートは、
【数８４】
2013541085.tif 000086
として定義され、
【数８５】
2013541085.tif 000087
は前記共通のサブパーティションのパーツであり、
【数８６】
2013541085.tif 000088
はランキング
【数８７】
2013541085.tif 000089
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである、請求項２２記載の方法。
【請求項２４】
前記非類似レートは、
【数８８】
2013541085.tif 000090
として定義され、
【数８９】
2013541085.tif 000091
は前記共通のサブパーティションのパーツであり、
【数９０】
2013541085.tif 000092
はランキング
【数９１】
2013541085.tif 000093
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである、請求項２２記載の方法。
【請求項２５】
前記非類似レートは、
【数９２】
2013541085.tif 000094
として定義され、
【数９３】
2013541085.tif 000095
は前記共通のサブパーティションのパーツであり、
【数９４】
2013541085.tif 000096
はランキング
【数９５】
2013541085.tif 000097
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである、請求項２２記載の方法。
【請求項２６】
処理手段、入力手段、出力手段及び記憶手段を有する意思決定支援システムであって、
前記処理手段は、請求項１乃至２５何れか一項記載の方法を実現するよう構成される意思決定支援システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、意思決定活動を支援する知識ベースシステムのものである。
【０００２】
より詳細には、本発明は、オブジェクトにスコアを提供する方法に関する。
【背景技術】
【０００３】
金融から医療までの様々な分野における多くの活動は、リスクを評価し、意思決定を行うことを必要とする。それは、投資を行ったり、所与の病状について患者の処置を開始したり、文書が関連があるか決定したり、製品を不良品として拒絶したり、又は２以上の可能性の間で単に選択するための決定であってもよい。
【０００４】
“意思決定支援システム”と呼ばれるコンピュータツールのファミリは、大量のデータを解析することによって意思決定を行うことを支援する目的を有する。例えば、大量の金融データを知得すると、当該システムは、投資が行われるべきか決定することを試みる。
【０００５】
数学とコンピュータサイエンスとの間のインタフェースにある教師付き分類方法は、“良好な支払人”と“支払不能な支払人”、“関連する文書”と“無関係な文書”、“健康な患者”と“病気の患者”、又は“適合した製品”と“不適合な製品”など、各ケースをバイナリラベルと関連付けることによって、テスト対象のケースを分類することを提案している。しかしながら、このような方法は、あるケースについて最も可能性のあるラベルを予測することしか試みない。誤りを犯すリスクは僅かしか低下しない。
【０００６】
スコアリング／ランキング方法は、他のアプローチを提案する。このような方法の目的は、多数の“良好な支払者”又は“関連する文書”が最大尤度を有するリストの先頭となるように、各ケースを並び替え／順序付けする方法を学習することである。
【０００７】
多変量観察対象を順序づける最も自然な方法は、観察された各ケース（新規又は非新規）にリスク度又は関連度として解釈可能な“スコア”という数値を割り当てるスコアリング関数を利用することである。このスコアリング関数のクオリティは、通常は偽陽性率に関する真陽性率の視覚的表示を可能にする関数基準、すなわち、Ｒｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ（ＲＯＣ）曲線を用いて評価される。情報抽出に広く利用されるＲｅｃａｌｌ−Ｐｒｅｃｉｓｉｏｎ曲線は、陽性のラベルデータの率が極めて高い又は極めて低いとき、識別結果を可視化するための類似したアプローチである。
【０００８】
高次元データの教師付き分類の多数の強力なアルゴリズム（ＣＡＲＴ、ＳＶＭ、ブースティング、ランダムフォレスト）がすでに知られているが、“機械学習”タイプのアルゴリズムの何れもスコアリングの問題に専用のものでない。大部分のアプリケーションでは、アプローチは、観察結果の分布のモデル化、情報の切り詰めなどの手作業のデータ前処理に主に基づき、ロジスティック回帰（リニア）又は線形判別解析などの従来の統計方法を利用するものである。これらのアプローチはまた、追加的な次元の追加（“次元の呪い”）に関するデータ量の指数的増加により引き起こされる問題に直面する。また、バイナリ分類方法は、スコアとして“マージンへの距離”を誤って利用することがある。
【０００９】
このため、機械学習に基づき改良されたスコアリング方法が必要とされる。
【発明の概要】
【００１０】
これらの目的のため、本発明は、多次元空間からのターゲットアイテムにより表現されるオブジェクトにスコアを提供する方法であって、前記スコアは、前記オブジェクトが所与のバイナリな性質を充足する確率を表し、当該方法は、記憶手段に接続される処理手段を有するコンピュータ環境において実行され、
当該方法は、
（ａ）前記多次元空間からのサンプルアイテムセットを表すデータを提供し、前記記憶手段に格納するステップであって、各サンプルアイテムは、該サンプルアイテムにより表されるオブジェクトが前記所与のバイナリな性質を充足する確率を表す多値ラベルに関連付けされる、前記提供及び格納するステップと、
（ｂ）前記ターゲットアイテムを表すデータを前記記憶手段に格納するステップと、
（ｃ）前記処理手段によって、所与の高さを有する有向バイナリツリーを表すデータを生成し、前記記憶手段に格納するステップであって、前記バイナリツリーは、該バイナリツリーにおける自らのポジションに関するインデックス値を有する複数のンモードにより規定され、前記ノードはルートノード、中間ノード及び終端ノードを有し、各ノードは、該ノードがルートノードである場合には関連するサブ空間は前記多次元空間全体であり、該ノードが非終端ノードである場合には関連するサブ空間は、前記非終端ノードの第１チャイルドノード及び第２チャイルドノードにそれぞれ関連する２つの互いに素なサブ空間ε＋及びε−に分割され、前記分割は、前記サブ空間ε＋に属するよう所与の第１ラベル値に関連するサンプルアイテムの個数及び／又は前記サブ空間ε−に属するよう所与の第２ラベル値に関連するサンプルアイテムの個数を最小化する分類手段に従って前記処理手段により実行され、前記第２ラベル値は、前記サンプルアイテムにより表されるオブジェクトが前記所与の第１ラベル値より前記所与のバイナリな性質を充足する確率が高いことを表す、前記生成及び格納するステップと、
（ｄ）前記処理手段によって、前記バイナリツリーの少なくとも各終端ノードとスコアとを前記バイナリツリーにおけるそれのインデックス値に依存して関連付け、前記スコアの値を前記記憶手段に格納するステップと、
（ｅ）前記処理手段によって、ターゲットノードを特定するステップであって、前記ターゲットノードは、関連するサブ空間が前記ターゲットアイテムを有する終端ノードである、前記特定するステップと、
（ｆ）前記ターゲットノードに関連するスコアの値を出力するステップと、
を有する方法を提供する。
【００１１】
本方法は、広範なシミュレーションを介し明らかにされた優れたパフォーマンスを可能にする。これは、関数的な最適化問題を実際に解くという事実から生じ、最適なＲＯＣ曲線により近い適応的な近似に収束する再帰的なスコアリング関数を構成する。
【００１２】
さらに、提案されたリサンプリング（ブーストラップ）の技術は、大量のサンプルを容易に取得することを可能にし、大変信頼できるスコアリングルールをもたらす。さらに、アプローチの非パラメータ的な側面は、ガウス分布にしばしば良好に適合しないデータの処理を可能にする。
【００１３】
しかしながら、最も重要なポイントは、本方法が非統計学者により容易に解釈可能なスコアリングルールの生成を可能にすることである。ここで、スコアリングルールと呼ばれるものは、観察結果のベクトルの各属性又はコンポーネントに対するインパクトを定量化することが可能なシンプルなバイナリルールの組み合わせである。
【００１４】
例えば、医療診断のケースでは、観察ベクトルが血液パラメータの指標のセットから構成されるとき、生成されるスコアリングルールは、“健康な患者”と“病気の患者”の２つのカテゴリを規定する各パラメータに対する値の範囲の形式をもたらす。カテゴリの個数は、もちろん２より大きなものであってもよい。
【００１５】
最後に、これらのルールは、非統計学者のユーザにより直接理解可能になるため、ツリーの先頭のパーツに最も興味のあるパラメータが現れる有向バイナリツリーとして容易に可視化可能である。
【００１６】
本発明の好適であるが、非限定的な特徴は以下のとおりである。
・各ノードのインデックス値は、値のペアを有し、第１インデックス値は、前記バイナリツリーにおける前記ノードの深さを表し、第２インデックス値は、前記ツリーにおける所与の深さレベルにおける前記ノードのポジションを表す。
・前記ルートノードのインデックスは（０，０）であり、インデックスが（ｄ，ｋ）である非終端ノードの第１及び第２チャイルドノードのインデックスはそれぞれ、（ｄ＋１，２ｋ）及び（ｄ＋１，２ｋ＋１）である。
・インデックスが（ｄ，ｋ）であるノードに関連するスコアは、２Ｄ（１−ｋ／２ｄ）であり、Ｄは前記バイナリツリーの高さである。
・前記分割は、前記処理手段によって、前記サブ空間ε＋に属するよう所与の第１ラベル値に関連するサンプルアイテムの個数と、前記サブ空間ε−に属するよう所与の第２ラベル値に関連するサンプルアイテムの個数との重み付けされた組み合わせを最小化することによって実行される。
・前記重み付けされた組み合わせのウェートはそれぞれ、互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第２ラベル値に関連するサンプルアイテムのレートと、互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第１ラベル値に関連するサンプルアイテムのレートとである。
・前記分割は、前記処理手段によって、
【００１７】
【数１】
2013541085.tif 000003
の値を最小化することによって実行され、（Ｘ１，Ｙ１）．．．（Ｘｎ，Ｙｎ）はそれらのバイナリラベルに関連するサンプルアイテムのセットであり、ωは互いに素なサブ空間ε＋及びε−に分割されるサブ空間における所与の第２ラベル値に関連するサンプルアイテムのレートであり、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である。
・前記分割中に考慮する関連するサブ空間の次元数及び／又はサンプルアイテム数は、減少される。
・前記多次元空間は、無限次元空間であり、前記分割は、有限次元アイテムへのサンプルアイテムの近似を有する。
・本方法は、（ｃ１）前記処理手段によって、前記形成されたバイナリツリーのサブツリーを選択し、前記バイナリツリーを前記サブツリーにより置換するステップを有し、前記ステップ（ｃ１）は、ステップ（ｃ）に続く。
・ＲＯＣ（Ｒｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ）曲線は、可能な各サブツリーについてステップ（ｃ１）において前記処理手段により構成され、前記記憶手段に格納され、前記選択されたサブツリーは、前記処理手段によって、関連するＲＯＣ曲線の下方の最も大きな面積を有するものとして決定される。
・ＲＯＣ曲線は、可能な各サブツリーについてステップ（ｃ１）において前記処理手段により構成され、前記記憶手段に格納され、前記選択されたサブツリーは、関連するＲＯＣ曲線の下方の最も大きなＣｏｍｐｌｅｘｉｔｙ−ｐｅｎａｌｉｚｅｄされた面積を有するものとして決定される。
・前記ステップ（ｃ１）は、前記処理手段により前記可能なサブツリーのセットに対して実行される交差検証テストを有する。
・前記多値ラベルは、前記サンプルアイテムにより表されるオブジェクトが前記所与のバイナリな性質を充足するか否かを示すバイナリラベルであり、前記第１ラベル値は、前記所与のバイナリな性質を充足しないサンプルアイテムに関連するラベル値であり、前記第２ラベル値は、前記所与のバイナリな性質を充足するサンプルアイテムに関連するラベル値である。
・前記多値ラベルは、少なくとも３つの値（１≦ξ≦Ξ）を有し、前記ラベル値は、前記所与のバイナリな性質を充足する確率によって上がり、ラベル値の
【００１８】
【数２】
2013541085.tif 000004
個の可能なペアのそれぞれについて、ξ１＜ξ２となるように有向バイナリツリーが形成及び格納され、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である。
・前記多値ラベルは、少なくとも３つの値（１≦ξ≦Ξ）を有し、前記ラベル値は、前記処置のバイナリな性質を充足する確率によって上がり、ラベル値ξ２＝ξ１＋１の（Ξ−１）個の可能なペア（ξ１，ξ２）のそれぞれについて、有向バイナリツリーが形成及び格納され、ξ１は前記第１ラベル値であり、ξ２は前記第２ラベル値である。
・ステップ（ａ）において、複数のサンプルアイテムセットが生成及び格納され、各サンプルアイテムセットについて、有向バイナリツリーが形成及び格納される。
・各サンプルアイテムセットは、前記処理手段によって、メインサンプルアイテムセットをリサンプリングすることによって生成されるブーストラップ複製である。
・本方法は、（ｄ１）前記複数の形成されたバイナリツリーを集約し、最良のスコアリングルールを決定するステップをさらに有し、前記ステップ（ｄ１）は、ステップ（ｃ）に続く。
・ステップ（ｄ１）は、
形成された各バイナリツリーについて、前記終端ノードに関連するサブ空間により形成される多次元空間のパーティションを提供し、記憶手段に格納するサブステップと、
前記処理手段によって、共通のサブパーティションを形成するため、前記パーティションを集約するサブステップと、
形成された各バイナリツリーについて、前記共通のサブパーティションの各パーツをスコアリングすることによって、スコアリングルールを提供及び格納するサブステップと、
各スコアリングルールについて、前記スコアリングルールに従ってスコアリングされた前記パーツのランキングを提供及び格納するサブステップと、
前記処理手段によって、前記複数のランキングから中間のランキングを決定し、前記中間のランキングを前記記憶手段に格納するサブステップと、
前記処理手段によって、前記中間のランキングに関連するスコアリングルールを前記最良のスコアリングルールとして選択するサブステップと、
を有する。
・前記中間のランキングを決定するサブステップは、前記処理手段により、各ランキングペアの間の非類似レートを計算し、その他のランキングと最も低い非類似レートを示すランキングを前記中間のランキングとして選択することを含む。
・前記中間のランキングは、
【００１９】
【数３】
2013541085.tif 000005
となるようなランキング
【００２０】
【数４】
2013541085.tif 000006
であり、
【００２１】
【数５】
2013541085.tif 000007
はランキングであり、
【００２２】
【数６】
2013541085.tif 000008
はランキングペアの間の非類似レートである。
・前記非類似レートは、
【００２３】
【数７】
2013541085.tif 000009
として定義され、
【００２４】
【数８】
2013541085.tif 000010
は前記共通のサブパーティションのパーツであり、
【００２５】
【数９】
2013541085.tif 000011
はランキング
【００２６】
【数１０】
2013541085.tif 000012
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである。
・前記非類似レートは、
【００２７】
【数１１】
2013541085.tif 000013
として定義され、
【００２８】
【数１２】
2013541085.tif 000014
は前記共通のサブパーティションのパーツであり、
【００２９】
【数１３】
2013541085.tif 000015
はランキング
【００３０】
【数１４】
2013541085.tif 000016
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである。
・前記非類似レートは、
【００３１】
【数１５】
2013541085.tif 000017
として定義され、
【００３２】
【数１６】
2013541085.tif 000018
は前記共通のサブパーティションのパーツであり、
【００３３】
【数１７】
2013541085.tif 000019
はランキング
【００３４】
【数１８】
2013541085.tif 000020
に従う前記共通のサブパーティションのその他のパーツからのパーツＣｉのランクである。
【００３５】
第２の態様では、本発明は、処理手段、入力手段、出力手段及び記憶手段を有する意思決定支援システムであって、前記処理手段は、本発明の第１の態様の方法を実現するよう構成される意思決定支援システムを提供する。
【図面の簡単な説明】
【００３６】
本発明の上記及び他の課題、特徴及び効果は、添付した図面に関して参照されるべき例示的な実施例の以下の詳細な説明において明らかになるであろう。
【図１】図１は、本発明の第１態様による方法に利用されるバイナリツリーの一例を示す。
【図２】図２は、本発明の第１態様による方法の実施例に利用されるバイナリサブツリーの一例を示す。
【図３】図３は、本発明の第１態様による方法の一例となるテストＲｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ（ＲＯＣ）曲線の図である。
【図４】図４は、本発明の第１態様による方法の実施例のステップを示す図である。
【図５】図５は、本発明の第１態様による方法の実施例に利用されるツリー構造のパーティションにより導かれる最大共通サブパーティションを特徴付けるバイナリサブツリーの一例を示す。
【図６ａ】図６ａは、本発明の第１態様による方法を示すのに利用されるサンプルアイテムセットの一例を示す。
【図６ｂ】図６ｂは、図５ａの具体例に関する回帰関数のバイナリレベルセットを示す図である。
【図６ｃ】図６ｃは、本発明の第１態様による方法を利用して図５ａの具体例から学習されたスコアリング関数のバイナリレベルセットを示す図である。
【図６ｄ】図６ｄは、図５ｃのスコアリング関数の最適なＲＯＣ曲線とテストＲＯＣ曲線とを示す図である。
【発明を実施するための形態】
【００３７】
図面を参照して、本発明の好適な実施例による方法が説明される。
［準備］
確率のフレームワークは、標準的なバイナリ分類のものと全く同じである。例えば、ランダムな変数のペアは（Ｘ，Ｙ）により表される。ここで、
【００３８】
【数１９】
2013541085.tif 000021
はバイナリラベルであり、ＸはＹを予測し、高次元の特徴空間
【００３９】
【数２０】
2013541085.tif 000022
におけるそれの値をとるため、いくつかの観察をモデル化するアイテムである。従って、各ペア（Ｘ，Ｙ）はオブジェクトを表し、当該オブジェクトは所与のバイナリな性質を充足するか、又は充足しない。バイナリな性質が充足される場合、Ｙ＝＋１であり、そうでない場合、Ｙ＝−１である。例えば、説明されるように、医療診断に関して、オブジェクトは患者であり、バイナリな性質は、“患者が健康である”というものである。患者に関するアイテムは、患者の体温、年齢及び血液中の所与の抗体及び／又はリンパ球の濃度からなる組であってもよい。
【００４０】
Ｘは（おそらく多変量の）サンプリングされた曲線（例えば、時間に依存するデータ、すなわち、Ｘ＝Ｘ（ｔ）など）、無限次元アイテムであってもよいことに留意されたい。この“関数”バージョンでは、入力される曲線は有限次元のサブスペースに写像される。
【００４１】
３以上のカテゴリのケースでは、バイナリな性質の組み合わせが利用されてもよい。例えば、“患者は健康である”、“患者は病気Ａを有している”及び“病気Ｂの患者”という３つのカテゴリを管理するため、第１ラベルＹ１は、患者が健康であるか否かを示し、Ｙ１＝１の場合、第２ラベルＹ２は、病気がＡ又はＢであるかを示す。これら２つのバイナリな性質は、別々に処理可能である。従って、すべてのマルチ分類問題は、１以上のバイナリ分類問題に還元可能である。
【００４２】
あるいは、Ｙは、バイナリな性質に関する達成の順序付けされた信頼度を表す多値ラベル
【００４３】
【数２１】
2013541085.tif 000023
であってもよい。特に、Ξ＝３である場合、Ｙ＝２は、特定の２つの状態の間の不確実性の状態（おそらく）に対応してもよい（バイナリな性質が充足される場合、Ｙ＝３であり、当該性質が充足されない場合、Ｙ＝１である）。例えば、病気の医療ベンチマークは、０（病気でない）から４（重大な病気）までの５つの値をとる。本発明による方法の実施例は、後述されるように、このようなマルチクラスのケースに利用可能である。
【００４４】
簡単化のため、以下の説明は、単一のバイナリ分類問題に実質的に関連するが、本発明はこのケースに限定されず、当業者は、それが任意のマルチ分類問題に適応させる方法を知るであろう。
【００４５】
従って、オブジェクトのバイナリラベルＹの値は一般に未知であり、本発明の目的は、ターゲットアイテムと呼ばれるアイテムＸを知り、またサンプルアイテムのセット（Ｘ１．．．Ｘｋ）に対するＹの値を知ると、Ｙの値に依存して位置決定を行うことを支援することである。このため、本発明による方法は、ターゲットアイテムＸにより表されるオブジェクトにスコアｓを提供することを提案し、当該スコアｓは、オブジェクトが所与のバイナリな性質を充足する確率、すなわち、Ｙ＝＋１となる確率を表す。
【００４６】
本方法は、メモリ手段に接続される処理手段を有するコンピュータ環境において実行される。例えば、メモリ手段は、コンピュータのハードドライブであり、処理手段は、コンピュータのプロセッサである。
［スコアリング−データ入力］
まず、ターゲットアイテム及びサンプルアイテムセットを表すデータが、メモリ手段に格納される必要がある。実際、上述されたように、本発明による方法は、機械学習に基づく。従って、ターゲットアイテムにより表されるオブジェクトにスコアを提供するスコア関数は、サンプルアイテムのセットから学習される。
【００４７】
当該セットが提供される必要がある。医療の具体例では、当該セットは健康であると知られている様々な患者の健康パラメータ（Ｙ＝＋１）と、病気であると知られている様々な患者の健康パラメータ（Ｙ＝−１）とから構成されてもよい。
【００４８】
サンプルアイテムの個数は重要である。それらがより多数になると、スコアはより正確になる。さらに、それらは極めて網羅的である必要があり、多次元空間全体の可能な最大サブ空間をカバーする必要がある。例えば、健康パラメータがサンプルアイテムとして利用されるすべての患者が３７〜３８度の同じ体温を有する場合、３９度を超える体温の患者を確実にスコアリングすることは困難になるであろう。
［スコアリング−バイナリランキングツリー］
メモリ手段に格納されているサンプルアイテムセットから、処理手段は、有向バイナリツリーを生成した。実際、本発明による方法は、部分単位の一定のスコアリング関数の特定のファミリ、すなわち、バイナリランキングツリーにより定義されるものに着目している。
【００４９】
まず、有限の深さＤ≧１のルートのある完全で左右の向きのあるバイナリツリーＴＤを考える。ＴＤのすべての非終端ノードは、サブセット
【００５０】
【数２２】
2013541085.tif 000024
に関連付けされ、２つのチャイルドノード、すなわち、２つのサブセット
【００５１】
【数２３】
2013541085.tif 000025
にそれぞれ関連付けされる左右の兄弟を有し、χは慣例的にルートノードに関連付けされるサブセットである。このような（完全な）ランキングツリーは、マスタランキングツリーと呼ばれ、例えば、図１により表される。
【００５２】
このように、バイナリツリーの何れかのレベルにおいて、関連するサブ空間はχの一部を形成する。各ノードにバイナリツリーにおけるそれのポジションに関してインデックス値を与えることによって、バイナリツリーにおけるそれのインデックス値に応じて、バイナリツリーの少なくとも各終端ノードにスコアを関連付けることが可能である。例えば、スコアは、右から左にツリーを探索するときに増加するようにしてもよい。効果的には、各ノードのインデックス値は値のペアからなり、第１インデックス値はバイナリツリーにおけるノードの深さを表し、第２インデックス値はバイナリツリーにおけるノードのポジションを表し、例えば、（ｄ，ｋ）は、
【００５３】
【数２４】
2013541085.tif 000026
である。この場合、ルートノードのインデックスは（０，０）であり、インデックスが（ｄ，ｋ）の非終端ノードの第１及び第２チャイルドノードのインデックスはそれぞれ、（ｄ＋１，２ｋ）及び（ｄ＋１，２ｋ＋１）である。効果的には、このようなインデックス処理によって、スコアリング関数は、
【００５４】
【数２５】
2013541085.tif 000027
として選択されてもよい。すなわち、インデックスが（ｄ，ｋ）であるノードに関するスコアは、
【００５５】
【数２６】
2013541085.tif 000028
である。すなわち、終端ノードは１〜２Ｄまでにスコアリングされる。このようなスコアリング関数は、図１に示される。
【００５６】
バイナリツリーの終端ノードはχの一部を構成するため、ターゲットアイテムは、１つのみの終端ノードに関連するサブ空間に属し、当該終端ノードは規定されたスコアに対応する。
［スコアリング−関連するサブ空間の分割］
信頼できるスコアリング関数を有するためのキーは、ノードに関連付けされるサブ空間の構築である。ツリーはルートノードから構成され、その後、高さＤまでレベル毎に到達する。生成されるノードは、インデックス値とサブ空間とに関連付けされ、メモリ手段に格納される。
【００５７】
関連付けされたサブ空間の生成は、２つのルールに従う。まず、上述されたように、ルートノードに関連付けされるサブ空間は、多次元空間χ全体である。その後、ノードが非終端ノードである場合、それの関連付けされたサブ空間は、それぞれが当該非終端ノードの第１チャイルドノード及び第２チャイルドノードに関連付けされる２つの互いに素であるサブ空間ε＋とε−とに分割される。当該分割は、サブ空間ε＋に属するように所与の第１ラベル値
【００５８】
【数２７】
2013541085.tif 000029
に関連するサンプルアイテムの個数、及び／又はサブ空間ε−に属するように所与のラベル値
【００５９】
【数２８】
2013541085.tif 000030
（すなわち、第２ラベル値は、サンプルアイテムにより表されるオブジェクトが所与の第１ラベル値より所与のバイナリな性質を充足する確率が高いことを表す）に関連するサンプルアイテムの個数を最小化する分類手段に従って処理手段により実行される。
【００６０】
上述されるように、簡単化のため、ラベルはバイナリラベルであり、すなわち、Ξ＝２であると考えられる。この結果、ξ１＝−１（当該ラベル値に関するサンプルアイテムは、所与のバイナリな性質を充足しない）であり、ξ２＝＋１（当該ラベル値に関するサンプルアイテムは、所与のバイナリな性質を充足する）である。
【００６１】
すべてのケースにおいて、所与のバイナリな性質を充足する確率は、サブ空間ε−に属するアイテムに対してより、サブ空間ε＋に属するアイテムに対してより高くなる。第１チャイルドノードが左の兄弟であり、第１チャイルドノードが右の兄弟である場合、ノードが左方にあるほど、関連するそれのスコアはより高くなる。
【００６２】
最善のサブ空間ε＋及びε−を求める方法の問題は、既知のバイナリ分類問題と等価である。実際、効果的には、最小化の必要のある関数は、サブ空間ε＋に属するよう所与のバイナリな性質を充足しないサンプルアイテムの個数と、サブ空間ε−に属するよう所与のバイナリな性質を充足するサンプルアイテムの個数との重み付けされた組み合わせであり、当該重み付けされた組み合わせにおけるウェートはそれぞれ、例えば、サブ空間の所与のバイナリな性質を充足するサンプルアイテムが互いに素なサブ空間ε＋及びε−に分割されるレートと、サブ空間の所与のバイナリな性質を充足しないサンプルアイテムが互いに素なサブ空間ε＋及びε−に分割されるレートとであり、すなわち、サブ空間Ｃにおける否定的なサンプルアイテムのレートは、
【００６３】
【数２９】
2013541085.tif 000031
であり、サブ空間Ｃにおける肯定的なサンプルアイテムのレートは、
【００６４】
【数３０】
2013541085.tif 000032
である。ここで、
【００６５】
【数３１】
2013541085.tif 000033
である。
【００６６】
このようなケースでは、最小化するための関数表現は、
【００６７】
【数３２】
2013541085.tif 000034
であってもよい。
【００６８】
すなわち、
【００６９】
【数３３】
2013541085.tif 000035
である。例えば、ＣＡＲＴ、ＳＶＭ、ニューラルネットワークなどの教師付き分類方法は、当該表現を最小化するサブ空間ε＋（及びサブ空間ε−）を迅速かつ効率的に求めるため、処理手段により実行されてもよい。
【００７０】
当該分割は完全である必要はないが、効率的である必要はある。正確すぎる分割は、ＸとＹとの間の現実の関係の代わりに、ランダムなエラーやノイズを示し、データにおける軽微な変動を誇張しすぎることになる。このような問題は、オーバフィッティング（ｏｖｅｒｆｉｔｔｉｎｇ）と呼ばれる。これを回避するため、自由度は分割する際に限定され、サブ空間のよりシンプルな分割と学習速度の増大とを導く。
【００７１】
効果的には、考慮されるサンプルアイテムの個数及び／又は空間の次元数は、バイナリツリーを深化する間に自発的に減少する。例えば、あるレベルから次のレベルまで、サンプルアイテムの１０％のみが再利用されてもよい。データランダム化と呼ばれるこのような技術は、オーバフィッティングを防ぎ、大きな次元のケースにおける効率性を向上させるための他の方法である。
【００７２】
例えば、データマイニングの正確なスコアリングのケースにおいて、オブジェクトはウェブページである。次元数は１万を超える可能性があり、サンプルアイテムの個数は数十億を超える可能性がある。オーバフィッティングのリスクは、極めて高い。
［フィルタリング］
入力における“関数”データＸ（上述されるような無限次元アイテム）のケースでは、“フィルタリング”又は“正規化”方法が、射影を提供することを支援し、すなわち、無限次元アイテムを本発明による方法においてより容易に利用可能な有限次元アイテムに変換することを支援してもよい。このため、変換（例えば、フーリエ変換、ラプラス変換、又は特に好ましくなウェーブレット変換など）と呼ばれる数学演算が、関数データを関数の直交基底により表現することを支援するのに効果的である。
【００７３】
ウェーブレット変換は、信号処理の分野において周知である。フーリエ解析に関して、ウェーブレット変換は、Ｘ（ｔ）信号をよりシンプルな要素に分解する（それぞれ、シヌソイドの和とウェーブレットの和）。主たる違いは、ウェーブレットは時間と周波数との双方でローカライズされ、標準的なフーリエ変換は周波数のみにおいてローカライズされる。
【００７４】
ウェーブレットは、ゼロにおいて増加を開始し、その後にゼロに減少する振幅を有する波形の振動である。それは、典型的には、“短い振動”として可視化可能である。
【００７５】
和のウェーブレットは、最もしばしばマザーウェーブレットである１つの生成関数Ψのシフトにより生成される。周知な具体例は、Ｄａｕｂｅｃｈｉｅｓ、Ｍｏｒｌｅｔ及びＣｏｉｆｌｅｔ関数である。
【００７６】
従って、ウェーブレット係数は、
【００７７】
【数３４】
2013541085.tif 000036
であり、例えば、
【００７８】
【数３５】
2013541085.tif 000037
である。
【００７９】
Ｘ関数の有限次元のウェーブレットベースの近似は、“フィルタリング”により取得可能であり、すなわち、ｎ個のウェーブレット係数Ｗ（ａ，ｂ）を選択する。例えば、当該ｎ個の係数は、閾値より大きい解像度レベル（“ａ”パラメータ）のうち最も大きな分散を有する。
【００８０】
この場合、当該近似は、
【００８１】
【数３６】
2013541085.tif 000038
により与えられる。Ｄａｕｂｅｃｈｉｅｓ−２ウェーブレット、４の解像度閾値及び３７項の近似に基づく具体例が、良好な結果を導いた。
【００８２】
本発明は、ウェーブレットベースフィルタリングに限定されるものでなく、当業者は、本発明による方法を関数データを減少した次元のスパニングセットに投影するための何れかの方法に適応する方法を知っているであろう。
［曲線下の面積］
肯定的な集団と否定的な集団とを区別するための候補のスコアリング関数ｓの能力は、一般にそれのＲＯＣ（Ｒｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ）曲線により評価され、簡単化のため以下の広範に利用される関数パフォーマンスの指標である。
【００８３】
スコアリング関数ｓの真のＲＯＣ曲線は、
【００８４】
【数３７】
2013541085.tif 000039
により与えられる“確率−確率”プロットである。
【００８５】
慣例的に、ジャンプが発生すると、当該曲線の対応する極値は直線部分により接続され、ｓ（ｘ）のＲＯＣ曲線は、連続写像
【００８６】
【数３８】
2013541085.tif 000040
のグラフとしてみなすことができる。
【００８７】
それは、“偽陽性アイテムのレートの関数における真陽性アイテムのレート”として理解できる。
【００８８】
この曲線は、スコアリングパフォーマンスを評価するのに有用な視覚的ツールを提供し、単位正方形［０，１］２の左上隅にＲＯＣ曲線が近くなるほど、スコアリング関数ｓは良好になる。従って、それは、すべてのスコアリング関数のセット上の半順序を導く。すなわち、すべての（ｓ１，ｓ２）に対して、ｓ２は、
【００８９】
【数３９】
2013541085.tif 000041
であるとき、ｓ１より正確である。
【００９０】
候補ｓのパフォーマンスは、通常はスカラ量により概略され、ＲＯＣ曲線の下方の面積（略してＡＵＣ）は、
【００９１】
【数４０】
2013541085.tif 000042
となる。
【００９２】
本発明による方法は、最適なＲＯＣ曲線を近似する方法としてみなすことができる。実際、提供されるスコアリング関数は、最適なＲＯＣ曲線の部分毎の線形近似である。すなわち、各終端ノードは、当該近似の線形部分に対応する。
【００９３】
実際、各分割において、ε＋に属するサンプルアイテムは肯定的である必要がある。この場合、それらは“真陽性”である。他方、それらが否定的である場合、それは、それらがε−に属するべきであり、実際に“偽陽性”であることを意味する。従って、各分割は、ＲＯＣ曲線の点を座標として有することに対応する（ε＋における否定的なサンプルアイテムのレート、ε＋における肯定的なサンプルアイテムのレート）。それは、ｓを表す部分単位の線形近似の切断点を形成する。
【００９４】
バイナリツリーにおいてより多くのレベルを形成することによって、曲線の新たな切断点が出現し、最適なＲＯＣ曲線のより精密な近似を導く。関連するバイナリーツリーの異なる高さに対応するＲＯＣ曲線の連続的な部分単位の線形近似の具体例と、最適なＲＯＣ曲線とが図３に示される。
［ランキングツリーの剪定］
ＲＯＣ曲線の良好な近似を有するのに最小数の終端ノードが必要であるが、多数の終端ノードを有することはオーバフィッティングを導き、χを多数のサブ空間にパーティションすることは、ローカルなノイズを明らかにし、分割は不安定になる（使用されるサンプルアイテムセットの若干の修正は、まったく異なるスコアリング関数の学習を導き、この問題は次のパートにおいてさらに議論される）。さらに、各レベルにおいてノード数が２倍になると、形成されるバイナリツリーは、高さが増加すると操作が急激に困難になり、スコアリング方法の計算複雑さはノード数に依存するため、大きなバイナリツリーは処理手段を遅くする。
【００９５】
好適な実施例では、本発明は、形成されるバイナリツリーのサブツリーを処理手段により選択し、バイナリツリーをサブツリーにより置換するステップを有し、当該ステップは、バイナリツリーを形成するステップに続く。バイナリツリーの“サブツリー”という用語は、任意のノードが終端ノードとなりうるバイナリツリーを意味する。他方、ノードは２つのチャイルドを有する。すなわち、これは、少なくとも１つのノードのすべての子孫を削除することによって剪定される初期的には完全なバイナリツリーである。例えば、図２は、図１に示されるバイナリツリーの可能なサブツリーを示す。
【００９６】
この剪定ステップは、大きなツリーを形成し、その後にパフォーマンスを増加させない、又はそれを低下させるノードを削除することによって、バイナリツリーの高さを最適に選択することを意図する。効果的には、ＲＯＣ曲線は、可能性のある各サブツリーについて処理手段により構成され、記憶手段に格納される。これらの部分単位の線形ＲＯＣ曲線のそれぞれについて、ＡＵＣが処理手段により計算される。
【００９７】
その後、第１の可能性は、最高のＡＵＣを有するサブツリーを処理手段が選択することである。選択されたサブツリーは、最も効率的なものであるが、それは依然として大きなツリーであり、大きな計算複雑さを有する可能性がある。
【００９８】
あるいは、“Ｃｏｍｐｌｅｘｉｔｙ−ｐｅｎａｌｉｚｅｄ  ＡＵＣ（ＣＰＡＵＣ）”と呼ばれる他の基準が利用される。
【００９９】
【数４１】
2013541085.tif 000043
ただし、＃Ｐ（Ｔ）は終端ノードの個数であり、λはトレーニングパフォーマンスとモデル計算複雑さとの間のトレードオフを規定するチューニングパラメータである。選択されたサブツリーは、最高のＣＰＡＵＣを有するサブツリーの場合、
【０１００】
【数４２】
2013541085.tif 000044
である。
【０１０１】
λは、おそらく手動により設定される必要があるが、可能なサブツリーのセットＴλ（可能なサブツリーセット全体の有限なサブセットである）に対して処理手段により実行される交差検証テストにおり効果的に推定される重要なパラメータである。Ｎ−分割交差検証では、オリジナルのサンプルセットが、Ｎ個のサブセットにランダムに分割される。Ｎ個のサブセットのうち、１つのサブセットがモデルをテストするための検証データとして保持され（すなわち、関連する経験的なＲＯＣ曲線を構成し、ＡＵＣを計算する）、残りの（Ｎ−１）個のサブセットがトレーニングデータとして利用される。その後、交差検証処理が、Ｎ個のサブサンプルのそれぞれが検証データとしてちょうど１回利用されることによって、Ｎ回（分割）繰り返される。当該分割からのＮ個の結果は、１つの推定値を生成するため平均化（又は合成）可能である。繰り返しのランダムサンプリングに対する当該方法の効果は、すべての観察結果がトレーニングと検証との双方に利用され、各観察結果がちょうど１回検証に利用されることである。交差検証されたＡＵＣを最大化する
【０１０２】
【数４３】
2013541085.tif 000045
の値は、処理手段により決定され、関連するサブツリー
【０１０３】
【数４４】
2013541085.tif 000046
が選択され、記憶手段に格納される。１０−分割交差検証が通常利用される。
［ランキングフォレスト−原理］
上述されたスコアリング方法などの再帰的な分割に基づく機械学習方法の主要な問題は不安定性である。上述されるように、利用されるサンプルアイテムセットの若干の修正は、まったく異なるスコアリング関数の学習を導く。
【０１０４】
図４に示される好適な実施例では、一緒になってランキングフォレストと呼ばれる複数のバイナリランキングツリーが生成され、ＡＵＣ基準に関して単一のバイナリランキングツリーのパフォーマンスを向上させるように集約される。このため、複数のサンプルアイテムセットが生成及び格納される。これら異なるセットのそれぞれから、バイナリツリーが形成される。
【０１０５】
大きなサンプルアイテムセットは分割されてもよい。あるいは、各サンプルアイテムセットは、ブートストラップ複製であってもよい。ブートストラップ複製は、主要なサンプルアイテムセットを類似することによって生成されるセットである。
【０１０６】
従って、Ｋ個のサンプルアイテムの異なるＢ個のセットを取得するため、（Ｎ＞Ｋ）個のサンプルアイテムの１つのセットのみが必要とされる。これは、メインセットＤである。その後、Ｂ個のブートストラップ複製Ｄ＊１，．．．，Ｄ＊Ｂが、目インセットＤから置換サンプルアイテムによる描画により構成される。再帰的な分割の不安定さのため、このようなリサンプリングは、独立したバイナリツリーＴ＊１，．．．，Ｔ＊Ｂが形成可能であるサンプルアイテムセットと、関連する学習されたスコアリング関数とを生成するのに十分である。
【０１０７】
これらのツリーは、その後に合成される必要がある。
［ランキングフォレスト−集約］
異なるバイナリツリーが異なるサンプルセットから生成されるとき、終端ノードに関連するサブ空間により形成される多次元空間χのパーティションは両立しない。集約の第１の目的は、ランキングフォレストの任意のツリーの終端ノードに関連するサブ空間により形成されるχのパーティションに両立するχの新たなパーティションを構成することである。
【０１０８】
このため、形成された各バイナリツリーについて、終端ノードに関連するサブ空間により形成される多次元空間χのパーテイションが提供され、記憶手段に格納され、その後、これらのパーティションは、共通のサブパーティションを形成するのに処理手段により集約される。実際、
【０１０９】
【数４５】
2013541085.tif 000047
がそれぞれバイナリツリーＴ１及びＴ２に関するχの２つのパーティションである場合、共通のサブパーティションは、
【０１１０】
【数４６】
2013541085.tif 000048
の式のサブセットの集まりである。
【０１１１】
図式的には、それは、以下の方法でＴ１ツリー構造を拡大することによって取得可能である。すなわち、
【０１１２】
【数４７】
2013541085.tif 000049
の任意のｋに対して、サブ空間Ｃ（１）ｋに関連するＴ１の終端ノードにおいて、Ｃ（１）ｋを有するＴ２に対応するサブツリーをルートとして追加する。グローバルルートχから始まる結果として得られた合成されたサブツリーの終端ノードに関連するサブ空間は、図５により示されるように、共通のサブパーティションに対応する（当該サブパーティションのパーツのいくつかはエンプティとすることが可能であることに気付くかもしれない）。この方式は、Ｂ＞２個のツリー構造のパーティションにより導出されるサブパーティションのすべてのパーツを復元するため繰り返し可能である。計算上の理由のため、集約は、効果的には最も複雑なツリーから開始され、進捗するに従って徐々に複雑さが軽減されたツリーに結び付く。
［ランキングフォレスト−メディアンランキング］
共通のサブパーティションは、異なるツリーに関連するスコアリング関数を比較可能にする。このサブパーティションが形成され、記憶手段に格納されると、ランキングフォレストの形成された各バイナリツリーに対して、スコアリングルールが、共通のサブパーティションの各パーツをスコアリングすることによって提供され、記憶手段に格納される。
【０１１３】
次のステップは、各スコアリングルールに対して、当該スコアリングルールに従ってスコアリングされたパーツのランキングを提供及び格納することである。特に、多次元空間χ上の全順序を規定する最も自然な方法は、スコアリング関数により実数直線上に自然順序を移すことであり、すなわち、可測写像
【０１１４】
【数４８】
2013541085.tif 000050
である。χ上のランキング
【０１１５】
【数４９】
2013541085.tif 000051
は、
【０１１６】
【数５０】
2013541085.tif 000052
により定義される。
【０１１７】
共通のサブパーティションがシンプルなバイナリツリーに関連する何れかのパーティションより多くのパーツから構成されるとき、いくつかの異なるパーツは同一のスコアを有してもよく、それらのランクに関してそれらを“平等（ｅｘ−ａｅｑｕｏ）”にする。パーツのタンクの確実な比較を可能にするため、共通のサブパーティションＰ＊（χ）のパーツＣのすべてのアイテムが同一のスコアを有するとき、パーツＣのランクは、例えば、
【０１１８】
【数５１】
2013541085.tif 000053
により与えられてもよい。ここで、
【０１１９】
【数５２】
2013541085.tif 000054
は、関係
【０１２０】
【数５３】
2013541085.tif 000055
のみが証明されることを意味する（すなわち、ｚとｚ’とは異なるスコアを有する）。
【０１２１】
異なるランキングが異なるサンプルセットから生じるため、不安定性のケースでは、共通のサブパーティションの所与のパーツのランクは、ランキング
【０１２２】
【数５４】
2013541085.tif 000056
に従って変化してもよい。これらのランクの変形は、最も不安定なランキングを明らかにする。他方、選択されるべきランキングは、中間のランキング、すなわち、あまり不安定でないランキングと呼ばれる。
【０１２３】
このため、効果的には、各ランキングペアの間の非類似レートが処理手段により計算され、その他のランキングと最も低い非類似レートを示すランキングが、中間ランキングとして処理手段により選択される。非類似レートは、２つのランキングの間のランクの可変性を表す基準である。
【０１２４】
例えば、中間ランキングは、
【０１２５】
【数５５】
2013541085.tif 000057
となるようなランキング
【０１２６】
【数５６】
2013541085.tif 000058
である。ただし、
【０１２７】
【数５７】
2013541085.tif 000059
はランキングであり、
【０１２８】
【数５８】
2013541085.tif 000060
はランキングペア間の非類似レートである。
【０１２９】
異なる式が、共通のサブパーティションのパーツのランクに基づく関数において非類似レートを計算するため当業者に知られている。例えば、以下の３つのうちの１つが利用されてもよい。
−Ｓｐｅａｒｍａｎランクオーダ相関
【０１３０】
【数５９】
2013541085.tif 000061
ただし、
【０１３１】
【数６０】
2013541085.tif 000062
は、共通のサブパーティションのパーツであり、
【０１３２】
【数６１】
2013541085.tif 000063
は、ランキング
【０１３３】
【数６２】
2013541085.tif 000064
に従う共通のサブパーティションのその他のパーツのうちのパーツＣｉのランクである。
−Ｓｐｅａｒｍａｎフットルール
【０１３４】
【数６３】
2013541085.tif 000065
ただし、
【０１３５】
【数６４】
2013541085.tif 000066
は、共通のサブパーティションのパーツであり、
【０１３６】
【数６５】
2013541085.tif 000067
は、ランキング
【０１３７】
【数６６】
2013541085.tif 000068
に従う共通のサブパーティションのその他のパーツのうちのパーツＣｉのランクである。
−Ｋｅｎｄａｌｌ  ｔａｕ
【０１３８】
【数６７】
2013541085.tif 000069
ただし、
【０１３９】
【数６８】
2013541085.tif 000070
は、共通のサブパーティションのパーツであり、
【０１４０】
【数６９】
2013541085.tif 000071
は、ランキング
【０１４１】
【数７０】
2013541085.tif 000072
に従う共通のサブパーティションのその他のパーツのうちのパーツＣｉのランクである。
【０１４２】
中間のランキングが決定され、記憶手段に格納されると、処理手段は、最終的には中間のランキングに関連するスコアリングルールをベストなスコアリングルールとして選択可能である。
［多値ラベル］
上述されるように、本発明による方法は、マルチクラスデータと両立し、すなわち、多値ラベル
【０１４３】
【数７１】
2013541085.tif 000073
に関連するサンプルアイテムを処理可能である。
【０１４４】
このため、複数の二分ランキング問題が効果的に解かれる。
【０１４５】
第１実施例では、有向バイナリツリーが、ラベル値ξ２＝ξ１＋１の（Ξ−１）個の可能なペア（ξ１，ξ２）のそれぞれについて形成及び格納される。ここで、第１ラベル値はξ１であり、第２ラベル値はξ２である。例えば、ラベルが３値ラベル（ｎｏ／ｍａｙｂｅ／ｙｅｓ）である場合、第１の二分問題は、“ｎｏ”（Ｙ＝１）又は“ｍａｙｂｅ”（Ｙ＝２）によりラベル付けされたサンプルアイテムのみを考慮することによって解かれ、第２の二分問題は、“ｍａｙｂｅ”（Ｙ＝２）又は“ｙｅｓ”（Ｙ＝３）によりラベル付けされたサンプルアイテムのみを考慮することによって解かれる。
【０１４６】
好適な実施例では、
【０１４７】
【数７２】
2013541085.tif 000074
個のラベル値の可能なペア（ξ１，ξ２）のそれぞれについて、ξ１＜ξ２となるように有向バイナリツリーが形成及び格納される。ここで、第１ラベル値はξ１であり、第２ラベル値はξ２である。ここで、上記具体例に関して、第３の二分問題は、“ｎｏ”（Ｙ＝０）又は“ｙｅｓ”（Ｙ＝２）によりラベル付けされたサンプルアイテムを考慮することによって解かれる。
【０１４８】
双方のケースにおいて、複数の取得されたツリーが合成される必要がある。これは、効果的には、ランキングフォレストと同じ機構により実行され、すなわち、集約及び中間ランキングである。
【０１４９】
ランキングフォレストは、マルチクラスランキングと共に利用可能であることに留意されたい。すなわち、複数のサンプルアイテムセットがブートストラップ複製により生成され、各サンプルアイテムセットと各ラベル値ペアとに対して、ツリーが生成される。すなわち、各ラベル値ペアについて、セット数と同程度のツリーが生成される。
【０１５０】
これらのツリーはすべて、同時に合成可能であるが、効果的には、ランキングフォレストがまず実行され（ツリーがラベル値ペア毎に合成される）、その後、集約されたツリーが合成される。
［具体例］
本発明による方法の効率性を示すため、図６ａに示されるサンプルアイテムの人工的なデータセットが、以下のように生成される。
【０１５１】
単位正方形χ＝［０，１］２は、４つの１／４に分割される。
【０１５２】
【数７３】
2013541085.tif 000075
可測セット
【０１５３】
【数７４】
2013541085.tif 000076
上の一様分布をＵＣにより表すと、クラス分布は、
【０１５４】
【数７５】
2013541085.tif 000077
により与えられる。ここで、Ｈ（ｄｘ）及びＧ（ｄｘ）はそれぞれ、Ｙ＝＋１が与えられた条件付き分布Ｘ及びＹ＝−１が与えられた条件付き分布Ｘである。
【０１５５】
本例では、２０００個のサンプルアイテムが利用される。図６ａでは、“＋”は所与の性質（Ｙ＝＋１）を充足するアイテムを表し、“ｏ”は所与の性質（Ｙ＝−１）を充足しないアイテムを表す。このセットアップでは、最適なスコアリング関数は、回帰関数
【０１５６】
【数７６】
2013541085.tif 000078
と同様に、部分毎に一定である。
【０１５７】
回帰関数は、
【０１５８】
【数７７】
2013541085.tif 000079
となる確率を所与のＸに提供する関数である。回帰関数の２レベルセットが、図６ｂにより示される。正方形の４つの領域が明確に示される。
【０１５９】
本発明による方法の結果は、その後、図６ｃにより示され、図６ａのサンプルアイテムセットから学習されたスコアリング関数を表す。マスタランキングツリーは、開示された方法により拡大し、次にブートストラップ複製により上述されたＮ−分割交差検証手順を介して剪定される。４つのレベルのスコアが、正方形の４つのエリアにほぼ完全に対応して出現することが観察できる。
【０１６０】
図６ｄは、最適なＲＯＣ曲線と図６ｃのスコアリング関数のテストＲＯＣ曲線とを表すグラフである。これら２つの曲線はほとんど区別できないと仮定することができる。
［アプリケーション］
上述されるように、本発明による方法は、多数の産業上又は経済上の用途を可能にする。クレジットスコアリング、医療診断及びデータマイニングの精度スコアリングが説明された。
【０１６１】
さらに、本発明による方法は、例えば、クオリティ制御及び／又は故障検出などに効果的である。実際、工場の製造ラインでは、製品のクオリティはいくつかの基準に基づき評価される必要がある。この場合、所与のバイナリな性質は“規格（又は非規格）製品”である。サンプルアイテムセットは、製造ライン上の製品をランダムに抽出し、それらを手作業によりチェックすることによって容易に設定可能である。故障は、例えば、非規格製品の比率が閾値以上である場合、検出可能である。
【０１６２】
さらに、本発明による方法は、生物及び化学、特に分子、タンパク質、触媒、遺伝子などのテストに適用可能である。それは、分子（又はタンパク質、触媒）が所与の効果を有することが可能であるか、それの構造と他の既知の分子の構造とを比較することによって予測することを可能にする。
【０１６３】
様々な分野において他の多数の用途が想到可能である。
［意思決定支援システム］
第２の態様によると、本発明は、処理手段、入力手段、出力手段及び記憶手段を有する意思決定支援システムに関する。当該意思決定支援システムの処理手段は、上述されたようなスコアリング方法を実現するよう構成される。
【０１６４】
入力手段は、ターゲットアイテムを表す入力データとサンプルアイテムセットとを入力することを可能にする。それらは、例えば、ユーザがこれらのデータを手動により入力することを所望する場合、キーボードなどとすることが可能であり、あるいは、サンプルのデータベースを有する何れかのコンピュータよのインタフェースなどとすることが可能である。出力手段は、例えば、表示画面である。
【０１６５】
当業者は、本発明を何れか既知のタイプのコンピュータ言語や何れかのタイプのプロセッサに適応する方法を知っているであろう。
【図１】
2013541085.tif 000098
【図２】
2013541085.tif 000099
【図３】
2013541085.tif 000100
2013541085.tif 000101
【図４】
2013541085.tif 000102
2013541085.tif 000103
【図５】
2013541085.tif 000104
【図６ａ】
2013541085.tif 000105
【図６ｂ】
2013541085.tif 000106
【図６ｃ】
2013541085.tif 000107
【図６ｄ】
2013541085.tif 000108
【国際調査報告】
2013541085.tif 000109
2013541085.tif 000110