(57)【要約】【課題】従来よりも少ないメモリで短時間に分類器を生成する技術を提供する。【解決手段】f(x)をXを定義域とする関数、EをXの部分集合、g(x)を任意のx∈Eに対してg(x)=f(x)となるアルゴリズムとし、関数f(x)、部分集合E、アルゴリズムg(x)から、x∈Xに対してf(x)を計算する分類器C(x)を生成する分類器生成装置であって、x∈X-Eに対してf(x)を計算する分類器C~(x)を生成する第１分類器生成部と、x∈Xに対して、x∈Eである場合はアルゴリズムg(x)を、x∈X-Eである場合は分類器C~(x)を用いて、f(x)を計算する分類器C(x)を生成する第２分類器生成部と、を含む。【選択図】図１
2019212088.tif 000002
【特許請求の範囲】
【請求項１】
f(x)をXを定義域とする関数、EをXの部分集合、g(x)を任意のx∈Eに対してg(x)=f(x)となるアルゴリズムとし、
関数f(x)、部分集合E、アルゴリズムg(x)から、x∈Xに対してf(x)を計算する分類器C(x)を生成する分類器生成装置であって、
x∈X-Eに対してf(x)を計算する分類器C~(x)を生成する第１分類器生成部と、
x∈Xに対して、x∈Eである場合はアルゴリズムg(x)を、x∈X-Eである場合は分類器C~(x)を用いて、f(x)を計算する分類器C(x)を生成する第２分類器生成部と、
を含む分類器生成装置。
【請求項２】
請求項１に記載の分類器生成装置であって、
Sを仮説検定、αを仮説検定Sの有意水準を表す定数、前記関数f(x)の定義域Xを仮説検定Sの入力データの集合、PVal(x)を仮説検定Sの入力データx∈Xに対する仮説検定Sのp値とし、
前記関数f(x)は、
【数８】
2019212088.tif 000010
（ただし、y0は仮説検定Sの帰無仮説を棄却できたことを示す値、y1は仮説検定Sの帰無仮説を棄却できなかったことを示す値とする）である
ことを特徴とする分類器生成装置。
【請求項３】
請求項２に記載の分類器生成装置であって、
U(x)を任意のx∈Xに対してPVal(x)≦U(x)を満たす関数、L(x)を任意のx∈Xに対してL(x)≦PVal(x)を満たす関数とし、
前記部分集合Eは、E=Y0∪Y1（ただし、Y0={x∈X|U(x)<α}、Y1={x∈X|L(x)≧α}とする）であり、
前記アルゴリズムg(x)は、
【数９】
2019212088.tif 000011
である
ことを特徴とする分類器生成装置。
【請求項４】
請求項３に記載の分類器生成装置であって、
Nを1以上の整数とし、
前記仮説検定Sは、フィッシャーの正確確率検定であり、
前記仮説検定Sの入力データの集合Xは、X={x=(a,b,c,d)|a+b+c+d=N}である
ことを特徴とする分類器生成装置。
【請求項５】
請求項４に記載の分類器生成装置であって、
前記関数L(x)は、L(x)=FisherPr(a,b,c,d)である
ことを特徴とする分類器生成装置。
【請求項６】
請求項４に記載の分類器生成装置であって、
前記関数U(x)は、
【数１０】
2019212088.tif 000012
である
ことを特徴とする分類器生成装置。
【請求項７】
請求項４ないし６のいずれか１項に記載の分類器生成装置により生成した分類器C(x)を用いて、ゲノムワイド関連分析の仮説検定を行う仮説検定装置であって、
前記分類器C(x)を用いて、ゲノムデータの分割表xから、遺伝子変異と疾患との間の関連の有無を検定し、検定結果を生成する仮説検定部と、
を含む仮説検定装置。
【請求項８】
f(x)をXを定義域とする関数、EをXの部分集合、g(x)を任意のx∈Eに対してg(x)=f(x)となるアルゴリズムとし、
分類器生成装置が、関数f(x)、部分集合E、アルゴリズムg(x)から、x∈Xに対してf(x)を計算する分類器C(x)を生成する分類器生成方法であって、
x∈X-Eに対してf(x)を計算する分類器C~(x)を生成する第１分類器生成ステップと、
x∈Xに対して、x∈Eである場合はアルゴリズムg(x)を、x∈X-Eである場合は分類器C~(x)を用いて、f(x)を計算する分類器C(x)を生成する第２分類器生成ステップと、
を含む分類器生成方法。
【請求項９】
請求項８に記載の分類器生成方法であって、
Sを仮説検定、αを仮説検定Sの有意水準を表す定数、前記関数f(x)の定義域Xを仮説検定Sの入力データの集合、PVal(x)を仮説検定Sの入力データx∈Xに対する仮説検定Sのp値とし、
前記関数f(x)は、
【数１１】
2019212088.tif 000013
（ただし、y0は仮説検定Sの帰無仮説を棄却できたことを示す値、y1は仮説検定Sの帰無仮説を棄却できなかったことを示す値とする）である
ことを特徴とする分類器生成方法。
【請求項１０】
請求項９に記載の分類器生成方法であって、
U(x)を任意のx∈Xに対してPVal(x)≦U(x)を満たす関数、L(x)を任意のx∈Xに対してL(x)≦PVal(x)を満たす関数とし、
前記部分集合Eは、E=Y0∪Y1（ただし、Y0={x∈X|U(x)<α}、Y1={x∈X|L(x)≧α}とする）であり、
前記アルゴリズムg(x)は、
【数１２】
2019212088.tif 000014
である
ことを特徴とする分類器生成方法。
【請求項１１】
請求項１０に記載の分類器生成方法であって、
Nを1以上の整数とし、
前記仮説検定Sは、フィッシャーの正確確率検定であり、
前記仮説検定Sの入力データの集合Xは、X={x=(a,b,c,d)|a+b+c+d=N}である
ことを特徴とする分類器生成方法。
【請求項１２】
請求項１１に記載の分類器生成方法であって、
前記関数L(x)は、L(x)=FisherPr(a,b,c,d)である
ことを特徴とする分類器生成方法。
【請求項１３】
請求項１１に記載の分類器生成方法であって、
前記関数U(x)は、
【数１３】
2019212088.tif 000015
である
ことを特徴とする分類器生成方法。
【請求項１４】
仮説検定装置が、請求項１１ないし１３のいずれか１項に記載の分類器生成方法により生成した分類器C(x)を用いて、ゲノムワイド関連分析の仮説検定を行う仮説検定方法であって、
前記分類器C(x)を用いて、ゲノムデータの分割表xから、遺伝子変異と疾患との間の関連の有無を検定し、検定結果を生成する仮説検定ステップと、
を含む仮説検定方法。
【請求項１５】
請求項１ないし６のいずれか１項に記載の分類器生成装置としてコンピュータを機能させるためのプログラム。
【請求項１６】
請求項７に記載の仮説検定装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力データを一定の規則に従って分類する分類器を生成する技術に関する。
【背景技術】
【０００２】
入力データを一定の規則に従って分類する分類器は、仮説検定や機械学習など様々な分野で幅広く利用されている。分類器利用の一例として、ゲノム全体にわたり患者群と対象群との間の遺伝子頻度を統計的に解析することで疾患遺伝子を発見する手法であるゲノムワイド関連解析がある（参考非特許文献１）。この解析では、遺伝子変異の有無と疾患の有無を集計した数百万個の2×2分割表についてフィッシャーの正確確率検定を行い、遺伝子変異と疾患の間に統計的に関連性があるかどうかを調べる。フィッシャーの正確確率検定では、p値と有意水準αを大小比較して関連性の有無を判定するが、この判定に分類器が利用されている。
（参考非特許文献１：Konrad Karczewski, “How to do a GWAS”, Lecture note in GENE 210: Genomics and Personalized Medicine, 2015.）
【０００３】
一般に、Xを定義域とする関数fに対して、{(x,f(x))|x∈X}を分類器生成アルゴリズムの入力とすることでXの各要素xに対して関数fと同じ値f(x)を出力する分類器を生成することができることが知られている。非特許文献１には、分類器生成アルゴリズムの従来技術として、分類器の一種である決定木を生成するID3アルゴリズムが記載されている。このアルゴリズムでは、すべての入出力の組み合わせに対して独立変数の平均情報量の期待値を求め、期待値が最大となる独立変数を木のノードとする操作を再帰的に行うことで決定木を生成する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J. Ross Quinlan, “Induction of Decision Trees”, Machine Learning, Vol.1, No.1, pp.81-106, 1986.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の方法では、取りうるすべての入出力の組み合わせを入力として与える必要があるため、入力の数に比例して組み合わせの数も膨大になる。その結果、決定木の生成に、大量のメモリが必要になり、計算時間もかかってしまうという課題があった。
【０００６】
そこで本発明は、従来よりも少ないメモリで短時間に分類器を生成する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様は、f(x)をXを定義域とする関数、EをXの部分集合、g(x)を任意のx∈Eに対してg(x)=f(x)となるアルゴリズムとし、関数f(x)、部分集合E、アルゴリズムg(x)から、x∈Xに対してf(x)を計算する分類器C(x)を生成する分類器生成装置であって、x∈X-Eに対してf(x)を計算する分類器C~(x)を生成する第１分類器生成部と、x∈Xに対して、x∈Eである場合はアルゴリズムg(x)を、x∈X-Eである場合は分類器C~(x)を用いて、f(x)を計算する分類器C(x)を生成する第２分類器生成部と、を含む。
【発明の効果】
【０００８】
本発明によれば、分類器の生成に必要となるメモリサイズや計算時間を削減することができる。
【図面の簡単な説明】
【０００９】
【図１】分類器生成装置１００の構成を示すブロック図。
【図２】分類器生成装置１００の動作を示すフローチャート。
【図３】ゲノムデータの分割表の一例を示す図。
【図４】仮説検定装置２００の構成を示すブロック図。
【図５】仮説検定装置２００の動作を示すフローチャート。
【図６】仮説検定部２１０の構成を示すブロック図。
【図７】仮説検定部２１０の動作を示すフローチャート。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１１】
＜定義＞
f(x)をXを定義域とする関数とする。また、EをXの部分集合とし、g(x)を任意のx∈Eに対してg(x)=f(x)となる計算可能な関数（アルゴリズム）とする。
【００１２】
＜第１実施形態＞
分類器生成装置１００は、x∈Xに対してf(x)を計算する分類器C(x)を生成する。その際、分類器生成装置１００は、アルゴリズムg(x)を関数f(x)に関する事前の知識として利用する。
【００１３】
以下、図１〜図２を参照して分類器生成装置１００について説明する。図１は、分類器生成装置１００の構成を示すブロック図である。図２は、分類器生成装置１００の動作を示すフローチャートである。図１に示すように分類器生成装置１００は、第１分類器生成部１１０と、第２分類器生成部１２０と、記録部１９０を含む。記録部１９０は、分類器生成装置１００の処理に必要な情報を適宜記録する構成部である。
【００１４】
図２に従い分類器生成装置１００の動作について説明する。
【００１５】
Ｓ１１０において、第１分類器生成部１１０は、関数f(x)、部分集合Eを用いて、x∈X-Eに対してf(x)を計算する分類器C~(x)を生成し、出力する。分類器C~(x)は、{(x,f(x))|x∈X-E}を分類器生成アルゴリズム（例えば、ID3アルゴリズム）の入力とすることにより、生成することができる。
【００１６】
Ｓ１２０において、第２分類器生成部１２０は、部分集合E、アルゴリズムg(x)、Ｓ１１０で生成した分類器C~(x)を用いて、x∈Xに対して、x∈Eである場合はアルゴリズムg(x)を、それ以外（つまり、x∈X-E）である場合は分類器C~(x)を用いて、f(x)を計算する分類器C(x)を生成し、出力する。
【００１７】
［適用例］
分類器生成装置１００を仮説検定に適用した例について説明する。つまり、関数f(x)を、ある仮説検定の入力データxに対して、当該仮説検定の帰無仮説の検定結果（つまり、棄却できるか否か）を示す値f(x)を計算、出力する関数として定義し、関数f(x)を計算する分類器C(x)を生成することを考える。
【００１８】
以下、詳しく説明する。
【００１９】
Sを仮説検定とする。仮説検定Sはどのような検定方法であってもよい。例えば、Sをフィッシャーの正確確率検定とすることができる。
【００２０】
αを仮説検定Sの有意水準を表す定数とする。また、PVal(x)を仮説検定Sの入力データx∈Xに対する仮説検定Sのp値とする。したがって、集合Xは、仮説検定Sの入力データの集合となる。仮説検定Sがフィッシャーの正確確率検定である場合、Nを1以上の整数とし、X={x=(a,b,c,d)|a+b+c+d=N}と表すことができる。
【００２１】
このとき、Xを定義域とする関数f(x)を次のように定義する。
【００２２】
【数１】
2019212088.tif 000003
【００２３】
ただし、y0は仮説検定Sの帰無仮説を棄却できたことを示す値、y1は仮説検定Sの帰無仮説を棄却できなかったことを示す値とする。
【００２４】
ここで、以下の条件を満たす関数U(x)、L(x)を考える。
（条件1）関数U(x)は、任意のx∈Xに対してPVal(x)≦U(x)を満たす。また、関数L(x)は、任意のx∈Xに対してL(x)≦PVal(x)を満たす。
【００２５】
もし、当該条件を満たす関数U(x)及びL(x)を構成することができるならば、定義域Xの部分集合EをE=Y0∪Y1（ただし、Y0={x∈X|U(x)<α}、Y1={x∈X|L(x)≧α}とする）とし、関数g(x)を
【００２６】
【数２】
2019212088.tif 000004
【００２７】
とすることにより、任意のx∈Eに対してg(x)=f(x)となる関数g(x)を構成することができる。
【００２８】
仮説検定Sがフィッシャーの正確確率検定である場合、関数U(x)、L(x)(x=(a,b,c,d))を以下のように定義することにより、関数g(x)は計算可能な関数（つまり、アルゴリズム）となる。
【００２９】
【数３】
2019212088.tif 000005
【００３０】
ここで、関数FisherPr(a,b,c,d)は、次式で表される関数である。
【００３１】
【数４】
2019212088.tif 000006
【００３２】
なお、(a,b,c,d)は次の2×2分割表を表すものとする。
【００３３】
【数５】
2019212088.tif 000007
【００３４】
なお、一般に、関数f(x)に対して、任意のx∈Eに対してg(x)=f(x)となるアルゴリズムg(x)が存在する場合、分類器生成装置１００は、アルゴリズムg(x)を関数f(x)に関する事前の知識として利用して、分類器C(x)を生成することができる。
【００３５】
本実施形態の発明によれば、事前に持っている知識を利用して、分類器を生成する際に入力する入出力の組み合わせの数を削減することにより、分類器の生成に必要となるメモリサイズや計算時間を削減することができる。
【００３６】
＜第２実施形態＞
ここでは、仮説検定Sをフィッシャーの正確確率検定、仮説検定Sの入力データの集合XをX={x=(a,b,c,d)|a+b+c+d=N}、関数U(x)を式(1)で定義される関数、関数L(x)を式(2)で定義される関数として、分類器生成装置１００が生成した分類器C(x)を用いて、ゲノムワイド関連分析の仮説検定を行う仮説検定装置２００について説明する。なお、Nは患者群と対象群の合計を表す。また、仮説検定Sの入力データx=(a,b,c,d)は2×2分割表であり、この分割表のことをゲノムデータの分割表という。図３は、ゲノムデータの分割表の一例を示す図である。
【００３７】
以下、図４〜図５を参照して仮説検定装置２００について説明する。図４は、仮説検定装置２００の構成を示すブロック図である。図５は、仮説検定装置２００の動作を示すフローチャートである。図４に示すように仮説検定装置２００は、仮説検定部２１０と、記録部２９０を含む。記録部２９０は、仮説検定装置２００の処理に必要な情報を適宜記録する構成部である。例えば、分類器生成装置１００が生成した分類器C(x)を記録しておく。
【００３８】
図５に従い仮説検定装置２００の動作について説明する。
【００３９】
Ｓ２１０において、仮説検定部２１０は、記録部２９０に記録した分類器C(x)を用いて、ゲノムデータの分割表xから、遺伝子変異と疾患との間の関連の有無を検定し、検定結果を生成し、出力する。
【００４０】
以下、図６〜図７を参照して仮説検定部２１０について説明する。図６は、仮説検定部２１０の構成を示すブロック図である。図７は、仮説検定部２１０の動作を示すフローチャートである。図６に示すように仮説検定部２１０は、部分集合判定部２１１と、検定結果生成部２１２を含む。
【００４１】
図７に従い仮説検定部２１０の動作について説明する。
【００４２】
Ｓ２１１において、部分集合判定部２１１は、ゲノムデータの分割表xを入力とし、当該分割表xが部分集合Eに含まれるか否かを判定し、判定結果を生成し、出力する。部分集合Eは、
【００４３】
【数６】
2019212088.tif 000008
【００４４】
であり、具体的には、以下のように処理する。分割表x=(a,b,c,d)に対して、
【００４５】
【数７】
2019212088.tif 000009
【００４６】
のいずれかの不等式が成り立つ場合は、分割表xが部分集合Eに含まれるという判定結果を生成し、それ以外の場合は、分割表xが部分集合Eに含まれないという判定結果を生成する。
【００４７】
Ｓ２１２において、検定結果生成部２１２は、分類器C(x)を用いて、Ｓ２１１で生成した判定結果から、遺伝子変異と疾患との間の関連の有無を示す検定結果を生成し、出力する。具体的には、以下のように処理する。分割表xが部分集合Eに含まれるという判定結果である場合は、式(3)、(4)のいずれかが成り立つことになるが、式(3)が成り立つ場合は、アルゴリズムg(x)を用いて、関連があることを示す検定結果を生成し、式(4)が成り立つ場合は、アルゴリズムg(x)を用いて、関連があるとはいえないことを示す検定結果を生成する。また、分割表xが部分集合Eに含まれないという判定結果である場合は、分類器C~(x)の出力に応じて、関連があることを示す検定結果か関連があるとはいえないことを示す検定結果のいずれかを生成する。ここで、関連があることを示す検定結果とは、仮説検定Sの帰無仮説を棄却できたことを示す値y0、関連があるとはいえないことを示す検定結果とは、仮説検定Sの帰無仮説を棄却できなかったことを示す値y1のことである。
【００４８】
例えば、N=4000、α=10-8、分類器C~(x)の生成にはID3アルゴリズムを用いるものとし、仮説検定装置２００を構成することができる。
【００４９】
なお、以上の説明では、関数U(x)、関数L(x)をそれぞれ式(1)で定義される関数、式(2)で定義される関数としたが、第１実施形態で説明した（条件1）を満たす関数であれば、どのような関数を用いてもよい。
【００５０】
本実施形態の発明によれば、分類器を用いて、ゲノムワイド関連分析の仮説検定を行うことが可能となる。
【００５１】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００５２】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００５３】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【００５４】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００５５】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００５６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019212088.tif 000016
【図２】
2019212088.tif 000017
【図３】
2019212088.tif 000018
【図４】
2019212088.tif 000019
【図５】
2019212088.tif 000020
【図６】
2019212088.tif 000021
【図７】
2019212088.tif 000022