(57)【要約】  本発明は、特徴のプール由来の少なくとも１つの特徴の順位を計算する方法に関し、当該方法は：複数の特徴サブセットを得るステップであり、各特徴サブセットが前記特徴のプール由来の特徴を含むステップ；及び、前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するステップ；を含む。例えば、前記少なくとも１つの特徴の順位は、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生頻度に基づく場合がある。このように、特徴のプール由来の特徴の順位付けに当該方法を有利に適用することができる。前記特徴のプール由来の特徴のサブセットよりも潜在的により有用である、最高位の特徴を含んだ新たな特徴のサブセットを、計算された特徴の順位の値から生じることができる。そのような前記特徴のプール由来の順位付けされた特徴のリストに対して、他の有利な用途が多くあり得る。
2010514001.tif 000002
【特許請求の範囲】
【請求項１】
特徴のプール由来の少なくとも１つの特徴の順位を計算する方法であって：
複数の特徴サブセットを得るステップであり、各特徴サブセットが前記特徴のプール由来の特徴を含むステップ；及び、
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生から計算するステップ；
を含む方法。
【請求項２】
前記複数の特徴サブセットが進化的計算アルゴリズムにより得られる、請求項１に記載の方法。
【請求項３】
前記複数の特徴サブセットを得るステップが、選択基準に基づき、複数の候補の特徴サブセットから前記複数の特徴サブセットを選択するステップを含む、請求項１に記載の方法。
【請求項４】
前記複数の候補の特徴サブセット由来の各候補の特徴サブセットが、それぞれの候補の特徴サブセットの特性と付随し、前記選択基準が、前記それぞれの候補の特徴サブセットの特性における評価に基づく、請求項３に記載の方法。
【請求項５】
前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップが、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生頻度にさらに基づく、請求項１に記載の方法。
【請求項６】
前記複数の特徴サブセット由来の各特徴のサブセットが、前記特徴のサブセットの特性と付随する、請求項１に記載の方法。
【請求項７】
前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップが、前記複数の特徴サブセット由来の前記それぞれの特徴サブセットと付随した特性にさらに基づく、請求項６に記載の方法。
【請求項８】
前記特徴のプール由来の前記少なくとも１つの特徴の順位が、前記複数の特徴サブセット由来の特徴サブセットにおける前記特徴のプール由来の２つ以上の特徴の共起に基づき計算される、請求項１に記載の方法。
【請求項９】
前記少なくとも１つの特徴の計算された順位に基づき、順位付けされた特徴のリストを作成するステップをさらに含む、請求項１に記載の方法。
【請求項１０】
特徴のプール由来の少なくとも１つの特徴の順位を計算するためのモジュールであって：
複数の特徴サブセットを得るための獲得装置であり、各特徴サブセットが前記特徴のプール由来の特徴を含む装置；及び
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するための計算装置；
を含むモジュール。
【請求項１１】
コンピュータプログラムプロダクトであって、該コンピュータプログラムプロダクトがコンピュータ上で実行される場合に請求項１に記載の方法を実行するよう処理装置に指示するためのコンピュータプログラムプロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパターンの発見に関し、特に、前記パターンに含まれる測定の順位付けに関する。本発明は、生物情報学に対する分類指標の評価において特に応用されている。
【背景技術】
【０００２】
近年、ヒトゲノムの詳細に対する、並びに、どのようにして遺伝子が健康な及び病気の対象において発現するかに対する利用可能な情報の量が非常に急増してきている。実験技術は、現在、生物学的対象におけるＤＮＡ、ＲＮＡ、蛋白質、及び他の有機高分子の濃度を特徴づける多くの測定値を迅速に得るために利用することができる。
【０００３】
例えばマイクロアレイは、ｃ−ＤＮＡ又は別のバインダーにおける少量の試料の「ドット」のアレイが配置されるガラススライド又はプレートを含む。各ドットは、関心のある特定の高分子と結合する特異的なｃ−ＤＮＡ又は他のバインダーを含み、１つのマイクロアレイが、そのような、何百、何千、又はそれ以上のドットを含むことができる。組織試料は患者から抽出され、関心のある分子種（例えば、ＤＮＡ、ＲＮＡ等）が抽出され、発光信号剤又は他のマーカーで処理されて、マイクロアレイの上を流される。組織内の特定の種類の高分子が、ハイブリダイゼーションと呼ばれるプロセスにおいて、それらの特定の高分子に対して調整されたバインダーを有するドットに集まる。一般的に、異なるマーカー（例えば、異なって着色された発光剤）で処理された比較又は参照試料も、そのマイクロアレイに適用される。種々のドットと付随した高分子の濃度を特徴づけるよう、１又は複数のマーカーが、例えばレーザービームを用いて励起されて光ルミネセンスを生じ、反応強度が測定される。このように、生物学的試料に含有された（例えば、何百、何千、又はそれ以上の）多数の有機高分子のアッセイが、迅速且つ量的に行われる。
【０００４】
質量スペクトル分析は、患者から取り出された試料内の多数の高分子の濃度を迅速にアッセイするための別の方法である。この方法において、試料はレーザー又は他の機構によって真空環境で電離され、電離された分子の断片における分子質量／電荷比の分布が、イオン計によって測定される。種々の高分子の濃度が、種々の高分子における既知のクラッキングパターンに基づき、質量スペクトルから引きだすことができる。あるいは、質量スペクトルパターンを特異的な高分子に相関させることなく、質量スペクトルのピークを生物情報学測定データとして使用することができる。
【０００５】
生物情報学は、マイクロアレイ測定、質量スペクトル、又は、他のゲノム若しくは有機高分子アッセイから有用な生物学的情報を抽出するために数値的方法を使用する。例えば、マイクロアレイ又は質量スペクトルにおける特定のパターンを特定の種類の癌と強く相関させることができる場合、従ってそのパターンは、その癌をスクリーニングするための分類指標として使用することができる。これは、血液若しくは脳脊髄液を引き出すか、唾液、尿、排泄物等の試料を採取するか、さもなければ、流体若しくは組織試料を得る等、比較的非侵襲性の技術によって、関心のある癌及び他の病態の早期発見を可能にする。
【０００６】
しかし、そのような医療診断検査を開発するために利用することができる多量な情報により問題が生じる。例えば、２５００個の測定から成るセット（５０ｘ５０のアレイのドットを有するマイクロアレイ等）から５つの測定（マイクロアレイのドット、質量スペクトルのピーク等）を使用する癌のスクリーニング検査を開発することが所望される場合、従って、診断検査に使用することができる、あり得る５つの試料の測定のサブセットにおける探索空間は、
【０００７】
【数１】
2010514001.tif 000003
であり、これは、徹底的に検討された技術により探索するにははるかに大きすぎる。さらに、見積は、開発中の癌のスクリーニング検査にとって５つの測定のサブセットが最適であると想定し、これは不適当である場合もある。最適な測定のサブセットは、４つの測定、６つの測定等でありえ、通常未知である。
【０００８】
ゲノム医療診断検査の開発における別の問題は、測定の総数は多いが、これらの測定が選出される患者の数が、一般的にはるかに少ないことである。例えば、典型的な調査は、５０ｘ５０のマイクロアレイ及び４０の検査対象から成る検査グループを使用し、そのうち２０の対象が関心のある癌を有し、２０の対象が癌を有していない対照である場合がある。しかし、小さな検査対象グループサイズと組み合わせて生じる１００，０００の測定から成る大きなセットは、一般の集団において関心のある癌に関連しない測定データにおける偽の相関性が多くあり得るという問題を提起する。
【０００９】
多数の測定が選出される少数の対象は、各測定の評価に基づき有用な測定の順位付けを得ることができない理由である。各測定に利用することができる順位数は、対象の数により制限され、従って、各測定を評価するにははるかに少なすぎる。
【００１０】
従って、各測定を順位付ける代わりに、遺伝的アルゴリズムが、対象を分類するのに有用な測定のサブセットを計算するために使用されてきた。遺伝的アルゴリズムでは、測定のセットのサブセットを示す遺伝子のセットを各染色体が有する最初の世代の染色体集団が作製される。例えば、５０ｘ５０のマイクロアレイにより生じる測定のセットを使用すると、各遺伝子は１から２５００の値を有し、それは、２５００ドットのマイクロアレイにより提供された２５００の測定の指標に一致する。１つの染色体における５つのそのような遺伝子は、２５００の測定のうち特定の５つの測定のサブセットを適切に特定する。分類指標は、２つ以上の分類（例えば、癌の分類及び非癌の分類）に対象を分類するため、染色体により特定された遺伝子を使用する。性能指数は、どの位正確にその分類指標が患者のグループにおいて癌を同定するか、及び、将来の世代への伝播のために染色体プールから最良適合の染色体を選択するために使用されるかを測定する。子孫の染色体は、その後、生物学的変異工程に類似した遺伝子の値における無作為な、又は、擬似乱数の変化によって変異される。多数のそのような変異及び擬似乱数の変化の後、染色体は、例えば、癌の種類及び非癌の種類等、２つ以上の種類にその対象を分類する能力に関して最適化される。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
遺伝的アルゴリズム、又は、いかなる他の適したアルゴリズムも、各染色体が遺伝子を含んだ、最適化された染色体のセットを生じる。以下で、遺伝子は特徴と呼ばれ、染色体は特徴サブセットと呼ばれる。測定値のセットを表す遺伝子のセットは、以下で、特徴のプールと呼ばれる。特徴のプール由来の特徴のサブセットは、例えば患者又は組織試料等、以下で検査対象と呼ばれる測定が行われる対象を２つ以上の種類に分類することにおける分類指標として有用である。特に、遺伝的アルゴリズムによって生じた、最適化された特徴のサブセットは、検査対象を２つ以上の種類に分類することにおけるその有用性に関して類似の質のものである。しかし、遺伝的アルゴリズムは、検査対象を分類することにおけるその有用性によって特徴のプール由来の特徴を順位付けしない。
【課題を解決するための手段】
【００１２】
特徴のプール由来の特徴を順位付ける方法を有することは有利であり、前記方法は、特徴のプールにおける特徴の数が、特徴を評価するのに利用可能な検査対象の数よりも、例えば１０倍以上の分だけはるかに多い場合に生じる、データとの特徴の偽の相関性に関する問題を解決することができる。
【００１３】
この問題に取り組むため、本発明の態様において、特徴のプール由来の少なくとも１つの特徴の順位を計算する方法が提供され、当該方法は：
複数の特徴サブセットを得るステップであり、各特徴サブセットが前記特徴のプール由来の特徴を含むステップ；及び、
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生から計算するステップ；
を含む。
【００１４】
前記特徴のプール由来の特徴における前記複数の特徴サブセットは、例えば遺伝的アルゴリズムに基づいた方法等、いかなる適した方法によっても得ることができる。得られた複数の特徴サブセットは、検査対象を分類するのに適した特徴サブセットを含む。一般的に、前記複数の特徴サブセット由来の前記特徴サブセットは、検査対象を分類することにおけるその有用性に関して主に高い質のものである。このように、得られた特徴のサブセットに含まれる特徴は、検査対象を分類することにおいて有用であるとみなすことができる。任意選択で、例えば、各分類指標が前記複数の特徴サブセット由来の特徴サブセットに基づき規定され、検査対象のセットの分類指標のうち少なくとも半分が５０％を超える検査対象のセットに基づき評価する性能を有するよう、複数の特徴サブセットを得ることができる。前記特徴のプール由来の特徴の順位は、前記特徴が生じる特徴サブセットの数に依存し得る。本発明の核心に、前記複数の特徴サブセット由来の多くの特徴サブセットに生じる特徴は、一般的に、検査対象を分類することにおいて、前記複数の特徴サブセット由来の少ない特徴サブセットに生じる特徴よりも有用であると推測される。この推測は、数多くの実験において検証されてきた。このように、特徴のプール由来の特徴の順位付けに当該方法を有利に適用することができる。計算された特徴の順位に基づき、最高位の特徴を含んだ新たな特徴のサブセットを生じることができ、前記新たな特徴のサブセットは、検査対象を分類することにおいて、前記特徴のプール由来の特徴のサブセットよりも潜在的により有用である。そのような前記特徴のプール由来の順位付けされた特徴のリストに対して、他の有利な用途が多くあり得る。
【００１５】
さらに、前記特徴のプール由来の各特徴が、他の特徴と組み合わせたその分類力を本質的に考慮に入れることが本発明の利点である。各特徴サブセットに対して、前記特徴サブセットに含まれた個々の特徴は、検査対象の分類におけるその性能に関して、本質的に補足的である。
【００１６】
複数の特徴サブセットを得るための選択基準を設定する、及び、特徴の順位を計算する方法を設定するプロセスは、有用な特徴の発見に向けて強力な道をあける。任意選択で、誤っているようではない新たな特徴サブセットに最高位の特徴を組み合わせることができる。従って、本発明は、検査対象の分類において種類と事実のとおりに付随した重要な特徴及び特徴サブセットを発見する方法、例えば、患者の臨床的状態を分類するのに有用なバイオマーカーを説明する重要な特徴及び特徴サブセットを提供する。
【００１７】
当該方法の実行において、前記複数の特徴サブセットは進化的計算アルゴリズムから得られる。大きな特徴のプールに対して、全特徴サブセットの数は非常に大きい。従って、特徴のプールにおける各特徴サブセットを評価することは実行可能ではない。進化的計算アルゴリズムは、検査対象のセットを分類するための能力に基づき最適化される特徴サブセットを生じる能力がある。好都合に、進化的計算アルゴリズムは、検査対象の有用な分類を得るために、特徴サブセットに含まれた多数の特徴の組み合わされた能力を考慮に入れる。
【００１８】
当該方法の実行において、前記複数の特徴サブセットを得るステップは、選択基準に基づき、複数の候補の特徴サブセットから前記複数の特徴サブセットを選択するステップを含む。これは、例えば進化的アルゴリズムによって、生じた前記複数の候補の特徴サブセットから最適な複数の特徴サブセットを選択することを可能にさせる。
【００１９】
当該方法の実行において、前記複数の候補の特徴サブセット由来の各候補の特徴サブセットは、それぞれの候補の特徴サブセットの特性と付随し、前記選択基準は、前記それぞれの候補の特徴サブセットの特性における評価に基づく。候補の特徴サブセットにおける特性を使用することは、前記複数の候補の特徴サブセットから最適化された複数の特徴サブセットを選択することに寄与する。
【００２０】
当該方法の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップは、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生頻度にさらに基づく。比較的より高い発生頻度を有する、すなわち、多くの特徴サブセットに生じる特徴は、比較的より低い発生頻度を有する、すなわち、より少ない特徴サブセットにおいて生じる特徴よりも高い順位を受ける。
【００２１】
当該方法の実行において、前記複数の特徴サブセット由来の各特徴のサブセットは、前記それぞれの特徴のサブセットの特性と付随する。前記特徴サブセットの特性は、前記特徴サブセットに含まれる特徴の順位を計算するステップにおけるその有用性に従い前記特徴サブセットを評価するために好都合に使用することができる。例えば、特徴の特性に基づいた重みは、前記複数の特徴サブセット由来の各特徴サブセットに割り当てることができる。
【００２２】
当該方法の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップは、前記複数の特徴サブセット由来の前記それぞれの特徴サブセットと付随した特性にさらに基づく。前記少なくとも１つの特徴の順位への特徴サブセットの寄与には、前記特徴サブセットに付随する特性に基づく重みを与えることができる。
【００２３】
当該方法の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位は、前記複数の特徴サブセット由来の特徴サブセットにおける前記特徴のプール由来の２つ以上の特徴の共起から計算される。例えば、特徴サブセットにおいて常に共に生じる２つの特徴は、より高い順位を受け、従って、検査対象を分類することにおいて組み合わされた力を考慮に入れることができる。
【００２４】
当該方法の実行において、当該方法は、前記少なくとも１つの特徴の計算された順位に基づき、順位付けされた特徴のリストを作成するステップをさらに含む。前記順位付けされた特徴のリストは、検査対象を分類するための最適化された特徴サブセットを作成するステップにおいて非常に有用であり得る。
【００２５】
本発明のさらなる態様において、特徴のプール由来の少なくとも１つの特徴の順位を計算するためのモジュールが提供され、当該モジュールは：
複数の特徴サブセットを得るための獲得装置であって、各特徴サブセットが前記特徴のプール由来の特徴を含む装置；及び
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するための計算装置；
を含む。
【００２６】
本発明のさらなる態様では、コンピュータプログラムプロダクトが、該コンピュータプログラムプロダクトがコンピュータ上で実行される場合に請求項１に記載の方法を実行するよう処理装置に指示するために、提供される。
【００２７】
一般に、本発明における種々の実行、実施形態、並びに態様を、本発明の範囲内で、いかなる考えられる様式でも組み合わせる、及び、結びつけることができる。これらの及び他の本発明の態様、特徴、及び／又は、利点は、以下に記述された実施形態から明らかになり、以下に記述された実施形態を参考にして説明される。
【００２８】
記述された当該方法の修正及びその変更に対応する、モジュール並びに／又はコンピュータプログラムプロダクトの修正及びその変更を、本発明の説明に基づき当業者によって行うことができる。
【００２９】
本発明の実施形態及び実行は、例えば以下の図面を参考にしてのみ記述される。
【図面の簡単な説明】
【００３０】
【図１】特徴のプール由来の少なくとも１つの特徴の順位を計算する方法を実行するための流れ図である。
【図２】特徴のプール由来の少なくとも１つの特徴の順位を計算するためのモジュールの実施形態を概略的に例示している。
【発明を実施するための形態】
【００３１】
図１は、特徴のプール由来の少なくとも１つの特徴の順位を計算する方法１０の例証的な実行の流れ図である。方法１０は、複数の特徴サブセットを得るステップ１で始まり、各特徴サブセットは前記特徴のプール由来の特徴を含む。複数の特徴サブセットを得るステップ１の後、当該方法は、前記特徴のプール由来の特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するステップ２に続く。前記特徴のプール由来の特徴が、前記複数の特徴サブセット由来の多くの特徴サブセットにおいて生じる場合、該特徴サブセットの数は予め決めることができるか、又は、ユーザー入力に基づくことができ、前記特徴は関連性があると順位付けされ、例えば、順位１を受けることができる。前記特徴のプール由来の特徴が、前記複数の特徴サブセット由来のいかなる特徴サブセットにおいても生じない場合、前記特徴は関連性がないと順位付けされ、順位０を受けることができる。特徴の順位を計算するステップ２の後、方法１０は、前記特徴のプール由来の別の特徴の順位を、特徴サブセットにおける前記別の特徴の発生に基づき計算するステップ２を続けることができる。当該方法は、例えば、前記特徴のプール由来の全特徴が順位付けされた場合等、前記特徴の順位を計算するステップ２を終結するための状態になるまで、特徴の順位を計算するステップ２を続ける。特徴の順位を計算するステップ２を終結するための状態になった場合、方法１０は終結する。
【００３２】
方法１０の実行において、当該方法は、前記少なくとも１つの特徴の計算された順位に基づき、順位付けされた特徴のリストを作成するステップ３をさらに含む。前記順位付けされた特徴のリストを使用して、例えば、検査対象を分類するため等、有用な特徴のサブセットを決定することができる。
【００３３】
方法１０の実行において、特徴における前記複数の特徴サブセットが、進化的計算アルゴリズムから得られる。前記進化的計算アルゴリズムの例は、遺伝的アルゴリズムである。本発明の方法１０の実行は遺伝的アルゴリズムを参考にして記述されているけれども、本発明の範囲はこの種のアルゴリズムに限定されない。一般に、複数の特徴サブセットを生じるいかなるアルゴリズムも、方法１０によって使用することができる。そのようなアルゴリズムは、それだけに限らないが、進化的アルゴリズム、進化的プログラミング、進化戦略、遺伝的プログラミング、反復局所探索法、及び、学習分類子システムを含む。
【００３４】
遺伝的アルゴリズムの実行は、一般的に、いくつかの実験を含む。各実験は、種々の特徴サブセットの初期アンサンブルから始まる。この特徴サブセットのアンサンブルは、第一の世代の特徴サブセットと呼ばれる。前記特徴サブセットの初期アンサンブル由来の各特徴サブセットは、前記特徴のプールから無作為に選択された特徴を含むことができる。特徴サブセットのアンサンブル由来の各特徴サブセットは、学習セットの検査対象から検査対象を分類することにおけるその有用性に関して評価される。この評価に基づく達成度査定を、前記特徴サブセットに割り当てることができる。各評価の後、前記特徴サブセットのアンサンブルに含まれた各特徴サブセットは、変異操作、交叉操作、及び／又は、他の操作により修正することができ、それによって、各特徴サブセットにおける潜在的に有用な特徴が保持され、潜在的に有用ではない特徴が各特徴サブセットから除去される。最新の特徴サブセットのアンサンブルは、例えば第二の世代、第三の世代等、次の世代の特徴サブセットと呼ばれる。前記最新の特徴サブセットのアンサンブルに含まれる各修正された特徴サブセットは再度評価される。修正−評価サイクルの反復は、終結状態が当てはまるまで続く。終結状態は、最新化前後の前記特徴サブセットのアンサンブルの比較に基づき得る。遺伝的アルゴリズムにおいて、修正−評価サイクルの反復は、修正前後の前記特徴サブセットのアンサンブルに含まれた特徴サブセットが類似する場合に終結される。各実験は、多数のいわゆるソフトのリスタートを含むことができる。ソフトのリスタートは、修正−評価の反復サイクルの反復を終結するための終結状態が生じた場合に実行することができる。各ソフトのリスタートで、前記特徴サブセットのアンサンブルに含まれた各特徴サブセットは、再度無作為に初期化され、すなわち、いくつかの特徴が特徴サブセットから取り除かれ、特徴のプール由来のいくつかの特徴が特徴サブセットに追加されるが、少なくとも１つの特徴サブセット、一般的には最高の達成度査定を有した特徴サブセットがそのまま残る。所定数のソフトのリスタートが実行された後に、実験を終結することができる。遺伝的アルゴリズムは、参照により本明細書において援用する“Ｇｅｎｅｔｉｃ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  ｇｅｎｏｍｉｃｓ−ｂａｓｅｄ  ｍｅｄｉｃａｌ  ｄｉａｇｎｏｓｔｉｃ  ｔｅｓｔ”と題された公開特許出願ＷＯ２００５／０７８６２９号に記載されている。遺伝的アルゴリズム及びその用途のさらなる態様は、同様に参照により本明細書において援用する、Ｔｈｅ  Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ｔｈｅ  ２００５  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  ｉｎ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｂｉｏｌｏｇｙ，ＣＩＢＣＥ  ２００５，Ｌａ  Ｊｏｌｌａ，ＣＡ，ＵＳＡ  ２００５において公開されたＤ．Ｓｃｈａｆｆｅｒ、Ａ．Ｊａｎｅｖｓｋｉ、及び、Ｍ．Ｓｉｍｐｓｏｎによる刊行物“Ａ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ  Ａｐｐｒｏａｃｈ  ｆｏｒ  Ｄｉｓｃｏｖｅｒｉｎｇ  Ｄｉａｇｎｏｓｔｉｃ  Ｐａｔｔｅｒｎｓ  ｉｎ  ���ｏｌｅｃｕｌａｒ  Ｍｅａｓｕｒｅｍｅｎｔ  Ｄａｔａ”に記載されている。
【００３５】
方法１０の実行において、前記複数の特徴サブセットを得るステップ１は、遺伝的アルゴリズムを実行することによって特徴サブセットを作製するステップを含む。前記複数の特徴サブセットは、遺伝的アルゴリズムの１又は複数の実行から得ることができる。実行中に生じる前記複数の特徴サブセットは、本発明の方法１０によって探索することができるようメモリ装置に記憶することができる。
【００３６】
方法１０の実行において、得られた複数の特徴サブセットは、遺伝的アルゴリズムの実行により生じた全てのサブセットを含む。従って、前記複数の特徴サブセットは、特徴サブセットの初期アンサンブル、遺伝的アルゴリズムの各ソフトのリスタートでの特徴サブセットにおける最新のアンサンブル、及び、遺伝的アルゴリズムの実行に含まれる各実験に含まれた全特徴サブセットを含む。
【００３７】
方法１０の実行において、前記複数の特徴サブセットを得るステップ１は、選択基準に基づき複数の候補の特徴サブセットから前記複数の特徴サブセットを選択するステップを含む。前記複数の候補の特徴サブセットは、遺伝的アルゴリズムの実行により生じる全てのサブセットを含むことができるが、前記複数の特徴サブセットは、例えば、各ソフトのリスタート後の所定数の修正−評価サイクルの反復において生じた特徴サブセットを含むことができる。例えば、終結基準に達する前の修正−評価サイクルの最後の１００回の反復に含まれた特徴サブセットは、前記複数の特徴サブセットに含むことができる。
【００３８】
方法１０の実行において、前記複数の候補の特徴サブセット由来の各候補の特徴サブセットは、それぞれの候補の特徴サブセットの特性と付随しており、選択基準は、前記それぞれの候補の特徴サブセットの特性における評価に基づいている。例えば、前記候補の特徴サブセットの特性は、遺伝的アルゴリズムにより計算することができる。遺伝的アルゴリズムにより計算される特性の例には、評価中の特徴サブセットの達成度査定、特徴サブセットのサイズ、及び、特徴サブセットの最長の世代、すなわち、前記特徴サブセットを含んだ、連続して最新化された特徴サブセットのアンサンブルの最大数が含まれる。例えば、各候補の特徴サブセットは、その達成度査定及び／又はその最長世代に基づき評価することができる。達成度査定が査定閾値を超える特徴サブセット、及び／又は、最長世代が世代閾値を超える特徴サブセットは、前記複数の特徴サブセットに含むことができる。
【００３９】
方法１０の実行において、前記複数の特徴サブセットを得るステップ１は、前記複数の候補の特徴サブセットから特徴サブセットを共に一団にするステップを含む。例えば、前記特徴のプール由来の同じ特徴を含む、遺伝的アルゴリズムの実行により生じた候補の特徴サブセット全てを、１つの特徴サブセットとみなすことができ、この１つの特徴サブセットのみを前記複数の特徴サブセットに含むことができる。任意選択で、前記１つの特徴サブセットの特性を、同じ特徴を含んだ前記候補の特徴サブセットのそれぞれの特性から計算することができる。任意選択で、前記１つの特徴サブセットの特性は、遺伝的アルゴリズムの実行により生じた同じ特徴を含んだ特徴サブセットの数を含むことができる。
【００４０】
記述された前記複数の特徴サブセットを得る方法は、本発明を例示するよう役立ち、請求項の範囲を限定しないことを当業者は理解するであろう。
【００４１】
方法１０の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップ２は、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生頻度にさらに基づいている。特徴ａの順位ｒａは、前記特徴が含まれる、前記複数の特徴サブセット由来のサブセットの数と同じでありえ：
【００４２】
【数２】
2010514001.tif 000004
合計は、前記複数の特徴サブセット由来の全特徴サブセットＡにわたり、ａ∈Ａの場合、χＡ（ａ）は１であり、それ以外の場合は０である。
【００４３】
方法１０の実行において、特徴における前記複数の特徴サブセット由来の各特徴サブセットは、前記それぞれの特徴サブセットの特性と付随している。例えば、各特徴サブセットの特性は、遺伝的アルゴリズムにより計算することができる。遺伝的アルゴリズムにより計算される特性の例には、評価中の特徴サブセットの達成度査定、特徴サブセットのサイズ、及び、特徴サブセットの最長の世代、すなわち、前記特徴サブセットを含んだ、連続して最新化された特徴サブセットのアンサンブルの最大数が含まれる。
【００４４】
方法１０の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップ２は、前記複数の特徴サブセット由来の各特徴サブセットに付随する特性にさらに基づいている。例えば、各特徴サブセットＡに付随する特性は、特徴サブセットＡの達成度査定ｐ（Ａ）であり得る。達成度査定ｐ（Ａ）は、特徴サブセットＡにより正確に分類されたバリデーションセットの検査対象由来の少しの検査対象と規定することができる。前記特徴のプール由来の特徴ａの順位ｒａは、
【００４５】
【数３】
2010514001.tif 000005
と規定することができ、合計は、前記複数の特徴サブセット由来の全特徴サブセットＡにわたる。各特徴サブセットＡに付随する特性は、前記特徴サブセットのサイズｓ（Ａ）であり得る。例えば、特徴ａの各発生は、前記特徴サブセットのサイズｓ（Ａ）に従い加重値を与えることができる。
【００４６】
【数４】
2010514001.tif 000006
方法１０の実行において、前記特徴のプール由来の前記少なくとも１つの特徴の順位は、前記複数の特徴サブセット由来の特徴サブセットにおける前記特徴のプール由来の２つ以上の特徴の共起から計算される。この場合、前記特徴の共起、すなわち、一組、三つ組等の発生を数えることができる。
【００４７】
方法１０の実行において、前記複数の特徴サブセット由来の特徴サブセットにおける前記特徴のプール由来の２つ以上の特徴の共起は、前記特徴のプールと前記複数の特徴サブセットによって規定されたアフィニティーネットワーク（ａｆｆｉｎｉｔｙ  ｎｅｔｗｏｒｋ）に基づき評価される。前記特徴のプールと前記複数の特徴サブセットに基づき規定されたアフィニティーネットワークはノードを含む。アフィニティーネットワークの各ノードは、前記特徴のプール由来の特徴に対応する。特徴サブセットが前記複数の特徴サブセットに存在する場合、アフィニティーネットワークの２つのノードはエッジにより接続されるため、２つのノードに対応する特徴は前記特徴サブセットに含まれる。前記特徴のプール由来の特徴は、アフィニティーネットワークの状況においてノードとも呼ぶことができる。アフィニティーネットワーク及びそのパラメータは、例えば、ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／ＰＳ＿ｃａｃｈｅ／ｃｏｎｄ−ｍａｔ／ｐｄｆ／０６０８／０６０８６７０．ｐｄｆで入手可能な“Ｇｅｎｅｒａｌｉｚａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ｃｌｕｓｔｅｒｉｎｇ  ｃｏｅｆｆｉｃｉｅｎｔ  ｔｏ  ｗｅｉｇｈｔｅｄ  ｃｏｍｐｌｅｘ  ｎｅｔｗｏｒｋｓ”と題されたＪａｒｉ  Ｓａｒａｍａｋ等による研究論文に記載されている。
【００４８】
アフィニティーネットワークは、隣接行列によって説明することができる。アフィニティーネットワークの隣接行列は要素Ｍａｂを含んだマトリックスであり、指数ａ、ｂはアフィニティーネットワークのノードである。２つのノードａ及びｂがエッジにより接続される場合、隣接行列の要素Ｍａｂは１に等しく、接続されない場合は０に等しい。
【００４９】
アフィニティーネットワーク、特に、ａという加重値が与えられたアフィニティーネットワークを説明する別のマトリックスは、加重マトリックスである。加重マトリックスは、要素Ｗａｂを含み、指数ａ、ｂはアフィニティーネットワークのノードである。加重マトリックスの要素Ｗａｂは、前記複数の特徴サブセットにおける特徴ａ及びｂの対の発生頻度に等しい。加重マトリックスの要素Ｗａｂは、ノードａ及びｂを接続するエッジの重みを規定する。
【００５０】
アフィニティーネットワーク及び加重値が与えられたアフィニティーネットワークのノードを説明するためのいくつかのパラメータが提案されてきた。例えば、ノードａの次数ｋａは、
【００５１】
【数５】
2010514001.tif 000007
と規定され；ノードａの強度ｓａは、
【００５２】
【数６】
2010514001.tif 000008
と規定され；ノードａのクラスター化係数は、
【００５３】
【数７】
2010514001.tif 000009
と規定され；ｔａは三角形の頂点として、及び、
【００５４】
【数８】
2010514001.tif 000010
としてノードａを有する三角形の数である。上記パラメータの規定における合計は、アフィニティーネットワークの全ノードｂ又はｂ及びｃにわたる。アフィニティーネットワーク及び加重値が与えられたアフィニティーネットワークのパラメータは、アフィニティーネットワークにおけるノードの、すなわち、前記特徴のプール由来の特徴の順位を計算するために使用することができる。例えば、ノードａの次数又は強度を発生頻度の重みとして使用することができる。
【００５５】
【数９】
2010514001.tif 000011
又は
【００５６】
【数１０】
2010514001.tif 000012
あるいは、アフィニティーネットワーク又は加重値が与えられたアフィニティーネットワークのパラメータを使用して、特徴の順位を規定することができる。
【００５７】
【数１１】
2010514001.tif 000013
方法１０の実行において、特徴のプール由来の特徴における複数の順位を計算することができる。別の順位を計算するように、種々の順位を組み合わせることができる。任意選択で、順位付けされた特徴の種々のリストを作成するステップに、種々の順位を使用することができる。特定の用途に使用するための順位付けされた特徴のリストの作成及び選択は、順位付けされた特徴のリスト由来の特徴により分類されることになる検査対象を得た外部の条件（例えば、温度、圧力、湿度、汚染）等の種々の要因、又は、検査対象を得た検査対象の母集団（例えば、農家、女性、男性等）に基づき得る。
【００５８】
実行において、方法１０は、２つ以上の複数の特徴サブセットを得るステップ１を含む。各複数の特徴サブセットは、特徴のプール由来の特徴を含む。例えば、各複数の特徴サブセットは、２つ以上の遺伝的アルゴリズムの実行から得ることができる。各複数の特徴サブセットに対して、前記特徴のプール由来の特徴の順位が計算される。この実行は、前記順位の２つ以上の値に基づき特徴を３つのグループに分類することを可能にさせ、各複数の特徴サブセットに対して高い順位を絶えず有する特徴は、マストハブ（ｍｕｓｔ  ｈａｖｅ）のグループである。例えば、順位が、複数の特徴サブセットにおける特徴の発生頻度によって規定される場合、マストハブは、各複数の特徴サブセットのうち大部分のサブセットに絶えず存在する特徴である。２つ以上の複数の特徴サブセット由来のいくつかの複数の特徴サブセットに対して高い順位、及び、他の複数の特徴サブセットに対して比較的低い順位を有する特徴は、スワップ（ｓｗａｐ）のグループである。例えば、順位が、複数の特徴サブセットにおける特徴の発生頻度によって規定される場合、スワップは、いくつかの複数の特徴サブセット由来の大部分の特徴サブセットに絶えず存在する、及び、他の複数の特徴サブセット由来の特徴サブセットにおいて比較的多く欠如している特徴である。前記２つ以上の複数の特徴サブセット由来の各複数の特徴サブセットに対して低い順位を絶えず有する特徴は、パッダ（ｐａｄｄｅｒ）のグループである。
【００５９】
特徴を３つのグループ、マストハブ、スワップ、パッダに分類することは、特徴の順位の値における統計的分布のパラメータの計算に基づき実行することもできる。例えば、前記パラメータは、順位値の平均偏差及び標準偏差であり得る。大きな平均偏差及び比較的小さな標準偏差を示す特徴はマストハブである。類似の平均偏差、例えば、マストハブと同じ大きさの程度の平均偏差を示すが、比較的大きい標準偏差を示す特徴はスワップである。最後に、小さい平均偏差及び小さい標準偏差を示す特徴は、検査対象を分類することにおいて有用ではなく、パッダである。
【００６０】
図２は、特徴のプール由来の少なくとも１つの特徴の順位を計算するためのモジュール２０における概略的な実施形態を例示している。当該モジュールの例証的な実施形態は：
複数の特徴サブセットを得るための獲得装置２１であって、各特徴サブセットが前記特徴のプール由来の特徴を含む装置；及び
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するための計算装置２２；
を含む。モジュール２０の例証的な実施形態は：
前記少なくとも１つの特徴の計算された順位に基づき、順位付けされた特徴のリストを作成するためのリスト装置２３；
入力データを受けるための入力コネクター２７；
出力データを送達するための出力コネクター２８；
入力コネクター２７を介して外部の装置から受けた前記入力データ、及び、モジュール２０の装置によって計算されたデータを記憶するためのメモリ装置２５；並びに
モジュール２０の装置を接続するためのメモリバス２６；
をさらに含む。
【００６１】
モジュールは、例えば、選択基準に基づき複数の候補の特徴サブセットから前記複数の特徴サブセットを選択するための選択装置等、さらなる装置を含むことができる。
【００６２】
本発明は、ハードウェア、ソフトウェア、若しくはファームウェアの実行、又は、それらのいかなる組合せも含めたいかなる適した形態においても実行することができる。本発明若しくは本発明のいくつかの特徴を、１又は複数のデータプロセッサ及び／又はデジタル信号プロセッサ上で実行されることになるコンピュータプログラムプロダクトとして実行することができる。本発明の実施形態における要素及び構成要素は、いかなる適した方法においても物理的に、機能的に、及び論理的に実行することができる。モジュール２０の機能性は、単一の装置において、又は、複数の装置において満たすことができる。
【００６３】
本発明は指定された実施形態に関して記述されてきたけれども、本明細書に明記された特定の形態に限定されるよう意図していない。正しくは、本発明の範囲は、付随の特許請求の範囲によってのみ限定される。特許請求の範囲において、「含む」という用語は、他の要素又はステップの存在を除外しない。さらに、個々の特徴を異なる請求項に含むことができるけれども、これらは、おそらく、好都合に組み合わせることができ、異なる請求項への包含は、特徴の組合せが実現可能及び／又は有利ではないということを意味しない。さらに、単数の言及は、複数形を除外しない。従って、「不定冠詞」、「定冠詞」、「第一」、「第二」等への言及は、その複数形を排除しない。さらに、特許請求の範囲における参照番号は、特許請求の範囲を限定するとして解釈されるべきではない。
【図１】
2010514001.tif 000014
【図２】
2010514001.tif 000015
【手続補正書】
【提出日】平成21年6月16日(2009.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
特徴のプール由来の少なくとも１つの特徴の順位を計算する方法であって：
複数の特徴サブセットを得るステップであり、各特徴サブセットが前記特徴のプール由来の特徴を含み、前記複数の特徴サブセットが進化的計算アルゴリズムにより得られるステップ；及び、
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生から計算するステップ；
を含む方法。
【請求項２】
前記複数の特徴サブセットを得るステップが、選択基準に基づき、複数の候補の特徴サブセットから前記複数の特徴サブセットを選択するステップを含む、請求項１に記載の方法。
【請求項３】
前記複数の候補の特徴サブセット由来の各候補の特徴サブセットが、それぞれの候補の特徴サブセットの特性と付随し、前記選択基準が、前記それぞれの候補の特徴サブセットの特性における評価に基づく、請求項２に記載の方法。
【請求項４】
前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップが、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生頻度にさらに基づく、請求項１に記載の方法。
【請求項５】
前記複数の特徴サブセット由来の各特徴のサブセットが、前記特徴のサブセットの特性と付随する、請求項１に記載の方法。
【請求項６】
前記特徴のプール由来の前記少なくとも１つの特徴の順位を計算するステップが、前記複数の特徴サブセット由来の前記それぞれの特徴サブセットと付随した特性にさらに基づく、請求項５に記載の方法。
【請求項７】
前記特徴のプール由来の前記少なくとも１つの特徴の順位が、前記複数の特徴サブセット由来の特徴サブセットにおける前記特徴のプール由来の２つ以上の特徴の共起に基づき計算される、請求項１に記載の方法。
【請求項８】
前記少なくとも１つの特徴の計算された順位に基づき、順位付けされた特徴のリストを作成するステップをさらに含む、請求項１に記載の方法。
【請求項９】
特徴のプール由来の少なくとも１つの特徴の順位を計算するためのモジュールであって：
複数の特徴サブセットを得るための獲得装置であり、各特徴サブセットが前記特徴のプール由来の特徴を含み、前記複数の特徴サブセットが進化的計算アルゴリズムにより得られる装置；及び
前記特徴のプール由来の前記少なくとも１つの特徴の順位を、前記複数の特徴サブセットにおける前記少なくとも１つの特徴の発生に基づき計算するための計算装置；
を含むモジュール。
【請求項１０】
コンピュータプログラムプロダクトであって、該コンピュータプログラムプロダクトがコンピュータ上で実行される場合に請求項１に記載の方法を実行するよう処理装置に指示するためのコンピュータプログラムプロダクト。
【国際調査報告】
2010514001.tif 000016
2010514001.tif 000017
2010514001.tif 000018