(57)【要約】【課題】  データの分類条件として適切な条件の組を検出する。【解決手段】  複数のオブジェクトを分類した分類結果について、分類の因子となるオブジェクトの構成要素の組を検出する分類因子検出装置であって、複数の構成要素のうち、構成要素の組である第１パターンを選択する第１選択手段と、第１パターンに他の構成要素を加えた第２パターンを選択する第２選択手段と、第１グループに分類されたオブジェクトのうち第１パターンを含みかつ第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち分類条件を満たすオブジェクトの数に基づいて、分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、評価値の示す確度が基準確度を超える場合に、第１パターン及び第２パターンを分類の因子として出力する分類因子出力手段とを備える分類因子検出装置を提供する。【選択図】図１
2005044163.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出する分類因子検出装置であって、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択手段と、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択手段と、
第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、
前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力手段と
を備える分類因子検出装置。
【請求項２】
前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、
前記分類因子検出装置は、
前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、
前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段と
を更に備え、
前記評価値生成手段は、更に、前記構成要素追加手段により追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する
請求項１記載の分類因子検出装置。
【請求項３】
前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記分類結果との相関が所定の値以下である分類条件を満たすオブジェクトの確率分布に対する、前記第１パターン及び前記第２パターンに基づく前記分類条件を満たすオブジェクトの確率分布の乖離度を示すカイ２乗検定値を生成する
請求項２記載の分類因子検出装置。
【請求項４】
前記第１グループに分類された複数のオブジェクトのうち前記第１パターンを含むオブジェクトの数をａとし、前記第２パターンを含むオブジェクトの数をｂとし、
前記第２グループに分類された複数のオブジェクトのうち前記第１パターンを含むオブジェクトの数をｃとし、前記第２パターンを含むオブジェクトの数をｄとする場合において、
前記評価値生成手段は、前記第１充足数である（ａ−ｃ）及び前記第２充足数である（ｂ−ｄ）に基づいて前記カイ２乗検定値を生成する前記評価関数であるｆ（ａ−ｃ，ｂ−ｄ）により定まる値を、前記評価値として生成し、
前記上限値見積手段は、前記第１パターン及び前記第２パターンのそれぞれ又は前記第２パターンに対して構成要素が追加される場合の前記カイ２乗検定値の上限値として、前記第２グループのうち第２パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ−ｃ，ｂ）及び前記第２グループのうち第１パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ，ｂ−ｄ）の最大値を生成する
請求項３記載の分類因子検出装置。
【請求項５】
前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記第１充足数及び前記第２充足数の一様性を示すエントロピー値に基づく値を生成する
請求項２記載の分類因子検出装置。
【請求項６】
前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記第１充足数及び前記第２充足数の差分の大きさを示すジニ係数値を生成する
請求項２記載の分類因子検出装置。
【請求項７】
前記上限値見積手段は、前記評価値生成手段により前記評価値が生成される毎に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加した場合及び前記第１パターンの内容を保持したまま前記第２パターンに構成要素を追加した場合の前記評価値の上限値を生成し、
前記上限値が示す確度が前記基準確度より大きい場合において、前記構成要素追加手段は、前記複数のオブジェクトの何れかが有する複数の構成要素のうち前記第２パターンに含まれていない構成要素である未評価要素のそれぞれを前記第２パターンに追加した第２追加済パターンのそれぞれを生成する第１の追加処理を行い、更に、前記第１パターン及び前記第２パターンが同一の場合に、前記未評価要素のそれぞれを前記第１パターン及び前記第２パターンに追加した第１追加済パターン及び第２追加済パターンのそれぞれを生成する第２の追加処理を行い、
前記評価値生成手段は、第１又は第２の前記追加処理が行われた前記第１追加済パターン及び前記第２追加済パターンについて前記評価値を生成する
請求項２記載の分類因子検出装置。
【請求項８】
前記基準確度を格納する基準確度格納手段と、
前記評価値生成手段により生成された前記評価値の示す確度が前記基準確度を超える場合に、当該評価値が示す確度を当該評価値が生成された場合の前記第１パターン及び前記第２パターンに対応付けて前記基準確度として前記基準確度格納手段に格納する基準確度更新手段と
を更に備え、
前記分類因子出力手段は、前記基準確度格納手段に格納された前記第１パターン及び前記第２パターンを、分類の因子として出力する
請求項２記載の分類因子検出装置。
【請求項９】
前記分類因子出力手段は、前記評価値生成手段により生成され確度が前記基準確度を超える複数の評価値のうち、確度の高い順に予め定められた数の評価値のそれぞれに対応する分類条件を、前記分類の因子として出力する
請求項２記載の分類因子検出装置。
【請求項１０】
前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して値を定める関数であって、前記第１充足数及び前記第２充足数がとりうる値の範囲内における端点の何れかが当該関数の最大値となる評価関数について、当該評価関数により定まる値を前記評価値として生成し、
前記分類因子検出装置は、
前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、
前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段と
を更に備え、
前記評価値生成手段は、更に、前記構成要素追加手段により追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する
請求項１記載の分類因子検出装置。
【請求項１１】
前記オブジェクトは、複数の構成要素として複数の元素が化学的に結合した化学物質であり、
複数の前記化学物質は、各化学物質が薬品として所定の効用を有するか否かを実験により判定した結果に基づいて２つのグループに分類されており、
前記第１選択手段は、前記複数の化学物質の何れかが有する元素又は元素間の結合のうち、少なくとも一の元素及び元素間の結合の組を前記第１パターンとして選択し、
前記第２選択手段は、前記第１パターンに少なくとも一の元素又は元素間の結合を加えた元素又は元素間の結合の組を前記第２パターンとして選択し、
前記評価値生成手段は、前記第１グループに分類された複数の化学物質のうち前記分類条件を満たす化学物質の数及び前記第２グループに分類された化学物質のうち前記分類条件を満たす化学物質の数に応じて、前記評価値を生成し、
前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける化学物質の組を、前記所定の効用を有する化学物質を分類する因子として出力する
請求項１記載の分類因子検出装置。
【請求項１２】
前記オブジェクトは、複数の語句により構成される文章であり、
複数の前記文章は、各文章を当該文章の内容を示すジャンルにより２つのグループに分類されており、
前記第１選択手段は、前記複数の文章の何れかが有する語句のうち、少なくとも一の語句の組を前記第１パターンとして選択し、
前記第２選択手段は、前記第１パターンに少なくとも一の語句を加えた語句の組を前記第２パターンとして選択し、
前記評価値生成手段は、前記第１グループに分類された複数の語句のうち前記分類条件を満たす文章の数及び前記第２グループに分類された文章のうち前記分類条件を満たす文章の数に応じて、前記評価値を生成し、
前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける語句の組を、複数の文章を所定のジャンルに分類する因子として出力する
請求項１記載の分類因子検出装置。
【請求項１３】
前記オブジェクトは、ワールド・ワイド・ウェブサイトの閲覧履歴であり、
前記構成要素は、閲覧されたウェブページ及び閲覧順序を示す順序情報であり、
複数の前記閲覧履歴は、閲覧の結果行われた処理により２つのグループに分類されており、
前記第１選択手段は、前記閲覧履歴の何れかが有する前記ウェブページ及び前記順序情報のうち、少なくとも一を前記第１パターンとして選択し、
前記第２選択手段は、前記第１パターンに少なくとも一の前記ウェブページ又は前記順序情報を加えた前記第２パターンを選択し、
前記評価値生成手段は、前記第１グループに分類された閲覧履歴のうち前記分類条件を満たす閲覧履歴の数及び前記第２グループに分類された閲覧履歴のうち前記分類条件を満たす閲覧履歴の数に応じて、前記評価値を生成し、
前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける前記ウェブページ及び前記閲覧順序の組を、閲覧の結果行う処理に応じた分類の因子として出力する
請求項１記載の分類因子検出装置。
【請求項１４】
前記複数の閲覧履歴は、閲覧の過程又は閲覧の結果、ウェブページにおいて商品の売買を行ったか否かにより２つのグループに分類されており、
前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおけるウェブページ及び閲覧順序を、閲覧の過程又は閲覧の結果商品の売買を行うか否かに応じた分類の因子として出力する
請求項１３記載の分類因子検出装置。
【請求項１５】
それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組をコンピュータにより検出する分類因子検出方法であって、
前記コンピュータにより、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択段階と、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択段階と、
第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成段階と、
前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力段階と
を備える分類因子検出方法。
【請求項１６】
前記評価値生成段階において、前記コンピュータは、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、
当該分類因子検出方法は、
前記コンピュータにより、
前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積段階と、
前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加段階と
を更に備え、
前記評価値生成段階として、前記コンピュータは、更に、前記構成要素追加段階において追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する
請求項１５記載の分類因子検出方法。
【請求項１７】
それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出する分類因子検出装置としてコンピュータを機能させるプログラムであって、
前記コンピュータを、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択手段と、
前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択手段と、
第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、
前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力手段と
して機能させるプログラム。
【請求項１８】
前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、
前記コンピュータを、
前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、
前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段と
して更に機能させ、
前記評価値生成手段は、前記構成要素追加手段において追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する
請求項１７記載のプログラム。
【請求項１９】
請求項１７又は請求項１８記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分類因子検出装置、分類因子検出方法、プログラム、及び記録媒体に関する。特に本発明は、分類の因子となる構造を検出する分類因子検出装置、分類因子検出方法、プログラム、及び記録媒体に関する。
【背景技術】
【０００２】
近年、様々な分野でit（Information Technology）が導入されるのに伴い、自然界の物質、社会の現象、及び人間の行動等のデータが電子化されつつある。このような背景の中で、大量に蓄積されたデータの中から頻繁に出現するパターンを検出して、検出された当該パターンをビジネス及び科学に有効利用するデータマイニング技術が注目されている。従来、リレーショナルテーブルに格納された関連性（リレーション）又はＰＯＳトランザクション等の定型的なログの中から、頻繁に出現するパターンを検出する方法が提案されている（非特許文献１８参照。）。
【０００３】
また、定型的なログのみならず、グラフ又は木構造のデータの中から、頻出するパターンを検出する方法が提案されている（グラフ構造のデータに対するデータマイニング技術については、非特許文献４、５、７、８、９、及び１２参照、木構造のデータに対するデータマイニング技術については、非特許文献２、１６、及び２４参照。）。
【０００４】
木構造又はグラフ構造のデータから頻出パターンを検出するデータマイニング技術は、化学物質の分子構造、自然言語における構文解析結果、又は自然言語における語の係り受け構造等、様々な分野に応用可能である。
その他、関連する非特許文献１、３、６、１０、１１、１３、１４、１５、１７、１８、１９、２０、２１、２２、及び２３参照。
【０００５】
【非特許文献１】Alberts,B.,Bray,D.,Johnson,A.,Lewis,J.,Raff,M.,Roberts,K.,& Walter,P.,中村  桂子、藤山  秋左夫、松原  謙一  監訳。Essential  細胞生物学。南光堂。
【非特許文献２】浅井  達哉、安部  賢治、川副  真治、有村  博紀、有川  節夫。半構造データマイニングのための部分構造パターンの効率的探索。電子情報通信学会技術研究報告、Vol.101,No.342,1-8,データエンジニアリング研究会。
【非特許文献３】Cook,D.J.,& Holder,L.B.(1994).Substructure Discovery Using Minimum Description Length and Background Knowledge.Journal of Artificial Intelligence Research,Vol.1,(pp.231-255).
【０００６】
【非特許文献４】Dehaspe,L.,Toivonen,H.,& King,R.D.(1998).Finding frequent substructures in chemical compounds. Proc.of the 4th KDD,(pp.30-36).
【非特許文献５】De Raedt,L.,& Kramer,S.(2001) .The Levelwise Version Space Algorithm and its Application to Molecular Fragment Finding. Proc.of the 17th IJCAI,(pp.853-859).
【非特許文献６】AIDS Antiviral Screen, http://dtp.nci.nih.gov/docs/aids/aids_data.html
【非特許文献７】Inokuchi,I.,Washio,T.,& Motoda,H.(2000).An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. Proc.of the 4th PKDD,(pp.12-23).
【０００７】
【非特許文献８】Inokuchi,A.,Washio,T.,Nishimura,Y.,& Motoda,H.A Fast Algorithm for Mining Frequent Connected Subgraphs.IBM Research Report,RT0448(February,2002).
【非特許文献９】猪口  明博、鷲尾  隆、西村  芳男、元田  浩。グラフ構造データからの連結多頻度グラフ抽出手法。第１６回人工知能学会全国大会、１  Ａ３−０３、（２００２）。
【非特許文献１０】猪口  明博、鷲尾  隆、西村  芳男、元田  浩。ＨＩＶデータに対するデータマイニング。第５８回人工知能学会知識ベースシステム研究会、（２００２）。
【非特許文献１１】Kramer,S.,De Raedt,L.,& Helma,C.(2001).Molecular Feature Mining in HIV Data. Proc.of the 17th International Conference on Knowledge Discovery and Data Mining,(pp.136-143).
【０００８】
【非特許文献１２】Kuramochi,M.,& Karypis,G.(2001)Frequent Subgraph Discovery. Proc.of the 1st ICDM.
【非特許文献１３】Kuramochi,M.,& Karypis,G.Discovering Frequent Geometric Subgraphs.Technical Report 02-024,2002.
【非特許文献１４】Matsuda,T.,Horiuchi,T.,Motoda,H.,& Washio,T.(2000).Extension of Graph-Based Induction for General Graph Structured Data. Proc.of the 4th PAKDD,(pp.420-431).
【非特許文献１５】松本  高利、田辺  和俊。ニューラルネットワークによる有機塩素化合物の発ガン性物質予測。JCPE Journal,Vol.11,No.1,29-34(1999)
【０００９】
【非特許文献１６】Matsuzawa,H.,&Fukuda,T.Mining Structured Association Patterns from Databases. Proc.of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining.
【非特許文献１７】T.Miyahara,T.Uchida,T.Shoudai,T.Kuboyama,K.Takahashi and H.Ueda: Discovery of Frequent Tree Structured Patterns in Semistructured Data.Proc.of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining,pp.1-10,2001.
【非特許文献１８】森本  康彦。空間データベースからの頻出集合数え上げアルゴリズム。第２回データマイニングワークショップ、ｐｐ．１−１０。
【００１０】
【非特許文献１９】Morishita,S.and Sese,J.(2000),Traversing Lattice Itemset with Statistical Metric Pruning.Proc.of POS 2000.
【非特許文献２０】Motoda,H.,& Yoshida,K.(1997).Machine Learning Techniques to Make Computers Easier to Use. Proc.of the 15th IJCAI,Vol.2,(pp.1622-1631).
【非特許文献２１】Wang,X.,Wang,J.,Shasha,D.,Shapiro,B.,Dikshitulu,S.,Rigoutsos,I.,& Zhang,K.Automated Discovery of Active Motifs in Three Dimensional Molecules. Proc.of the 3rd International Conference on KDD.pp.89-95.(1997)
【００１１】
【非特許文献２２】Wang,X.,Wang,J.,Shasha,D.,Shapiro,B.,Rigoutsos,I.,& Zhang,K.Finding Patterns in Three-Dimensional Graphs: Algorithms and Applications to Scientific Data Mining.IEEE Transactions on Knowledge and Data Engineering,Vol.14 No.4 pp.731-749.(2002)
【非特許文献２３】Yoshida,K.,& Motoda,H.(1995).CLIP:Concept Learning from Inference Patterns.AI,Vol.75,No.1 pp.63-92
【非特許文献２４】Zaki,M.Efficiently Mining Frequent Trees in a Forest. Proc.of the 8th International Conference on KDD.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来の手法は、所定の条件を満たすデータのグループにおいて、頻出する単一のパターンを検出していた。これにより、例えば、頻出するパターンを含むデータは、所定の条件を満たし易いという知見を得ることができた。しかしながら、対象とするデータの種類等によっては、より適切な知見が必要な場合がある。
【００１３】
例えば、化学の分野においては、新規な化学物質が続々と合成され、薬品等として人々の生活及び健康に役立っている。一方、これらの化学物質のもつ副作用が問題になっている。そのため、化学物質の有害性、例えば、生物に対する毒性、大気・水・土壌などの自然環境条件における分解性や蓄積性、及び生物体内における蓄積性や濃縮性等を評価する必要がある。しかしながら、化学物質の有害性を実験により評価するには、長い年月と巨額の費用が必要となる。
【００１４】
従って、実験によらず化学物質の有効性及び有害性を評価できれば、時間及び費用を大幅に削減することができる（非特許文献１５参照。）。従来のデータマイニング技術は、化学物質の有効性の要因となるパターン及び化学物質の有害性の要因となるパターンのそれぞれを別個に検出することができる。しかしながら、有効性を持ちながら有害性の少ない化学物質等を検出する等、所定の条件の組合せを適切に検出することは困難であった。
【００１５】
そこで本発明は、上記の課題を解決することのできる分類因子検出装置、分類因子検出方法、プログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１６】
即ち、本発明の第１の形態によると、それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出する分類因子検出装置であって、複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択手段と、複数のオブジェクトの何れかが有する複数の構成要素のうち、第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択手段と、第１グループに分類された複数のオブジェクトのうち第１パターンを含みかつ第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち分類条件を満たすオブジェクトの数に基づいて、分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、評価値の示す確度が予め定められた基準確度を超える場合に、第１パターン及び第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力手段とを備える分類因子検出装置、コンピュータを当該装置として機能させる分類因子検出方法、コンピュータを当該装置として機能させるプログラム、及び当該プログラムを記録した記録媒体を提供する。
【００１７】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１８】
本発明によればデータの分類条件として適切な条件の組を検出することができる。
【発明を実施するための最良の形態】
【００１９】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００２０】
図１は、分類因子検出装置１０の機能ブロック図である。分類因子検出装置１０は、それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出することを目的とする装置である。より詳細には、分類因子検出装置１０は、オブジェクトの構成要素に基づく複数の分類条件を生成し、当該複数の分類条件の中からオブジェクトを分類できる確度の評価値（例えば、カイ２乗検定値）が所定値以上の分類条件を探索する。この際、分類因子検出装置１０は、分類条件を変更し評価値を生成する過程でその後生成する評価値の上限値を見積り、当該上限値が所定値以下の場合には探索を中止することにより、探索時間を節約することができる。
【００２１】
分類因子検出装置１０は、オブジェクトデータベース１００と、第１選択手段１１０と、第２選択手段１２０と、評価値生成手段１３０と、上限値見積手段１４０と、構成要素追加手段１５０と、基準確度格納手段１６０と、基準確度更新手段１７０と、分類因子出力手段１８０とを備える。
【００２２】
オブジェクトデータベース１００は、２つのグループに分類された複数のオブジェクトを格納する。第１選択手段１１０は、構成要素追加手段１５０からの指示に基づいて、複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンをオブジェクトデータベース１００から選択し、評価値生成手段１３０に送る。また、第１選択手段１１０は、オブジェクトデータベース１００における選択可能な全ての構成要素を既に選択した場合に、その旨を構成要素追加手段１５０に送る。
【００２３】
第２選択手段１２０は、構成要素追加手段１５０からの指示に基づいて、当該第１パターンに少なくとも一の構成要素を加えた第２のパターンをオブジェクトデータベース１００から選択し、評価値生成手段１３０に送る。また、第２選択手段１２０は、オブジェクトデータベース１００における選択可能な全ての構成要素を既に選択した場合に、その旨を構成要素追加手段１５０に通知する。
【００２４】
評価値生成手段１３０は、第１グループに分類された複数のオブジェクトのうち第１パターンを含みかつ第２パターンを含まない分類条件を満たすオブジェクトの数である第１充足数と、第２グループに分類された複数のオブジェクトのうち当該分類条件を満たすオブジェクトの数である第２充足数とをオブジェクトデータベース１００の内容に基づいて生成する。そして、評価値生成手段１３０は、当該第１充足数および当該第２充足数に基づいて、分類条件により複数のオブジェクトを分類できる確度の評価値、例えば、カイ２乗検定値を生成し、当該評価値を生成した場合の第１パターン及び第２パターンに対応付けて基準確度更新手段１７０に送る。また、評価値生成手段１３０は、分類条件を上限値見積手段１４０に送る。
【００２５】
上限値見積手段１４０は、第１パターン及び第２パターンに構成要素を追加することにより第１充足数及び第２充足数がとりうる値の範囲内における評価値の上限値を、オブジェクトデータベース１００の内容に基づいて生成し、構成要素追加手段１５０に送る。
【００２６】
構成要素追加手段１５０は、上限値見積手段１４０から受け取った上限値の示す確度が基準確度格納手段１６０から受け取った基準確度より大きい場合に、第２パターンに構成要素を追加する第１の追加処理と、第１パターン及び第２パターンのそれぞれに同一の構成要素を追加する第２の追加処理とのそれぞれを順次行うべく、第１選択手段１１０及び第２選択手段１２０に指示を送る。
【００２７】
より具体的には、構成要素追加手段１５０は、上限値見積手段１４０から受け取った上限値の示す確度が基準確度より大きい場合に、順次行うべき追加処理の内容を、スタック（Ｓｔａｃｋ）等のデータ構造によりメモリに格納する。そして、構成要素追加手段１５０は、上限値見積手段１４０から上限値を受け取る毎に、上限値の示す確度が基準確度より大きいか否かに関わらず、メモリに格納された追加処理を一ずつ行う。
【００２８】
また、構成要素追加手段１５０は、選択可能な全ての構成要素を既に選択した旨の通知を第１選択手段１１０及び第２選択手段１２０のそれぞれから受けた場合に、評価値の生成処理を終了して分類因子を出力する旨の終了指示を分類因子出力手段１８０に通知する。
【００２９】
基準確度格納手段１６０は、予め定められた基準確度を格納する。基準確度更新手段１７０は、評価値を当該評価値が生成された場合の第１パターン及び第２パターンに対応付けて評価値生成手段１３０から取得する。そして、基準確度更新手段１７０は、評価値の示す確度が基準確度格納手段１６０に格納された基準確度を超える場合に、当該評価値が生成された場合の第１パターン及び第２パターンに対応付けて当該評価値が示す確度を基準確度として基準確度格納手段１６０に格納する。
【００３０】
これにより、基準確度格納手段１６０は、既に生成された評価値の最大値を格納することができる。これに代えて、基準確度格納手段１６０は、変更前の基準確度を更に格納してもよい。この場合、基準確度格納手段１６０は、評価値の最大値のみならず基準確度を超える確度を有する複数の評価値のそれぞれを、当該評価値を生成した場合の第１パターン及び第２パターンに対応付けて格納することができる。
【００３１】
分類因子出力手段１８０は、終了指示を構成要素追加手段１５０から受け取ると、評価値の最大値等を当該評価値が生成された場合の第１パターン及び第２パターンに対応付けて取得する。そして、分類因子出力手段１８０は、第１パターン及び第２パターンのそれぞれにおける構成要素を分類の因子として出力する。
【００３２】
このように、分類因子検出装置１０は、所定のパターンを含むか否かの条件のみならず、所定の条件の組合せ、例えば、第１パターンを含みかつ第２パターンを含まない分類条件を、分類の因子として検出することができる。これにより、薬品として所定の効用を有しかつ副作用を有さない化学構造等、様々な応用分野において適切な分類因子を検出することができる。
【００３３】
図２は、オブジェクトデータベース１００の内容の一例を示す。オブジェクトデータベース１００は、２つのグループに分類された複数のオブジェクトを格納する。本図の例において、オブジェクトは、複数の構成要素として複数の元素が化学的に結合した化学物質である。また、複数の化学物質は、各化学物質が薬品として所定の効用を有するか否かを実験により判定した結果に基づいて、所定の効用が認められたグループＹ及び所定の効用が認められないグループＮに分類されている。
【００３４】
なお、本発明に係る所定の特性を有するか否かの分析とは、例えば本例で示すように、薬品として所定の効用を有するか否かの実験である。これに代えて、所定の特性を有するか否かの分析とは、文章の内容が所定のジャンルに属するか否かの分析であってもよいし、ウェブページが閲覧された結果閲覧者が所定の行為を行ったか否かの分析であってもよい。即ち、所定の特性を有するか否かの分析とは、分析対象のオブジェクトの種類に関わらず、予め実験、計測、又は観測に基づきある特性の有無を判定した結果であればよい。
【００３５】
オブジェクトデータベース１００は、グループＹとして、所定の分子構造であるａ、ａと２重結合している炭素、及びそれぞれが炭素と結合した２つの水素を含む化学物質２００と、化学物質２００と略同一の構造であり分子構造ａに代えて分子構造ｂを有する化学物質２１０と、化学物質２００と略同一の構造であり分子構造ａに代えて分子構造ｃを有する化学物質２２０とを格納している。
【００３６】
また、オブジェクトデータベース１００は、グループＮとして、所定の分子構造であるｄ、ｄと結合している炭素、それぞれが炭素と結合した３つの水素を含む化学物質２３０と、化学物質２３０と略同一の構造であり分子構造ｄに代えて分子構造ｅを有する化学物質２４０と、所定の分子構造であるｆ、ｆと２重結合している炭素、それぞれが炭素と結合した２つの水素とを含む化学物質２５０とを格納している。
【００３７】
ここで、炭素との２重結合、炭素、及びそれぞれが炭素と結合した２つの水素の組が、薬品として所定の効用を発揮する薬理活性に大きく寄与する場合を例とする。所定の効用を有するパターンを検出する他の手法によれば、炭素及びそれぞれが当該炭素と結合した２つの水素の組が、薬品として所定の効用を有するパターンの候補として検出される場合がある。
【００３８】
しかしながら、検出された当該パターンの候補は、グループＮに分類された化学物質２３０、化学物質２４０、及び化学物質２５０のそれぞれにも含まれているので、複数のオブジェクトをグループＹ及びグループＮに分類する因子として検出されにくい。
【００３９】
このように、他の方法によれば、本来の分類の因子を適切に検出できない場合がある。これに対し、分類因子検出装置１０は、炭素及びそれぞれが当該炭素と結合した２つの水素の組を第１パターンとして選択し、炭素及びそれぞれが当該炭素と結合した３つの水素の組を第２パターンとして選択することにより、当該第１パターン及び当該第２パターンに基づく分類条件を、グループＹ及びグループＮに分類する因子として検出することができる。
【００４０】
より具体的には、評価値生成手段１３０は、グループＹのうち当該第１パターンを含みかつ当該第２パターンを含まない分類条件を満たすオブジェクトの数である第１充足数として３を算出する。そして、評価値生成手段１３０は、グループＮのうち当該分類条件を満たすオブジェクトの数である第２充足数として１を算出する。評価値生成手段１３０は、これらの充足数に基づいてカイ２乗検定等により評価値を生成する。これにより、分類因子検出装置１０は、当該評価値の示す分類の確度が基準確度より大きい場合には、当該分類条件を適切な分類の因子として出力することができる。
【００４１】
また、オブジェクトデータベース１００は、化学物質の分子構造をグラフ構造のデータとして格納している。そして、構成要素追加手段１５０は、当該グラフ構造のデータのうち、頂点若しくは辺又はこれらの組合せである部分グラフ等を順次追加して評価値を生成させる。これにより、分類因子検出装置１０は、テーブルに格納されたデータ、ラティス構造のデータ、及び定型的なログ等の比較的分析が容易な形式のみならず、グラフ構造等の解析困難な形式のデータであっても、分類の因子を適切に特定することができる。
【００４２】
図３は、分類因子検出装置１０の動作フローを示す。第１選択手段１１０は、第１パターンとして空集合を選択する（Ｓ３００）。第２選択手段１２０は、第２パターンとして空集合を選択する（Ｓ３１０）。そして、評価値生成手段１３０は、評価値を生成する処理を行う（Ｓ３２０）。評価値を生成する処理において、構成要素追加手段１５０は、第１パターン及び／又は第２パターンに構成要素を順次追加し、評価値生成手段１３０は、追加処理が行われる毎に評価値を生成する。詳細については、図４から図６において説明する。
【００４３】
分類因子出力手段１８０は、Ｓ３２０において生成された評価値の示す確度が予め定められた基準確度を超える場合に、当該評価値を生成した第１パターン及び第２パターンを分類の因子として出力する処理を行う（Ｓ３３０）。これに代えて、分類因子出力手段１８０は、評価値生成手段１３０により生成された評価値の示す確度の最大値について、当該最大値に対応する評価値を生成した第１パターン及び第２パターンを、分類の因子として出力してもよい。この場合、評価値生成手段１３０により生成された評価値のうち最も確度が高い場合について、分類条件を出力することができる。
【００４４】
更に他の例として、分類因子出力手段１８０は、評価値生成手段１３０により生成され確度が基準確度を超える複数の評価値のうち、確度の高い順に予め定められた数の評価値のそれぞれに対応する分類条件を、分類の因子として出力してもよい。この場合、分類因子出力手段１８０は、基準確度を超える評価値が多数生成された場合であっても、当該多数の評価値の中から予め定められた数の評価値を選択して出力することができる。
【００４５】
図４は、図３のＳ３２０における動作フローの詳細を示す。図５は、図４に続く動作フローを示す。図６は、図５に続く動作フローを示す。評価値生成手段１３０は、第１パターン及び第２パターンにより定まる分類条件に基づいて、第１グループのうち分類条件を満たすオブジェクトの数である第１充足数及び第２グループのうち分類条件を満たすオブジェクトの数である第２充足数を算出する。そして、評価値生成手段１３０は、第１充足数及び第２充足数に基づいて、分類条件により複数のオブジェクトを分類できる確度の評価値を生成する（Ｓ４００）。
【００４６】
評価値の具体例として、評価値生成手段１３０は、分類結果との相関が所定の値以下である分類条件を満たすオブジェクトの確率分布に対する、第１パターン及び第２パターンに基づく分類条件を満たすオブジェクトの確率分布の乖離度を示すカイ２乗検定値を生成する。これに代えて、評価値生成手段１３０は、評価関数により定まる評価値として、第１充足数及び第２充足数の一様性を示すエントロピー値に基づく値を生成してもよいし、第１充足数及び第２充足数の差分の大きさを示すジニ係数値を生成してもよい。例えば、エントロピー値は第１充足数及び第２充足数の一様性を示す値であるので、評価値生成手段１３０は、エントロピー値の増加に応じて減少し、エントロピー値の減少に応じて増加する値を、評価値として生成してもよい。
【００４７】
基準確度更新手段１７０は、評価値生成手段１３０により生成された評価値の示す確度が基準確度格納手段１６０に格納された基準確度を超える場合に、当該評価値が生成された場合の第１パターン及び第２パターンに対応付けて当該評価値が示す確度を基準確度として基準確度格納手段１６０に格納することにより、基準確度を更新する（Ｓ４１０）。
【００４８】
続いて、上限値見積手段１４０は、第１パターン及び第２パターンに構成要素を追加することにより第１充足数及び第２充足数がとりうる値の範囲内における評価値の上限値を生成する（Ｓ４２０）。
【００４９】
上限値の示す確度が基準確度以下の場合（Ｓ４３０：ＮＯ）又は第１パターン又は第２パターンとして選択可能な全ての構成要素を既に選択した場合（Ｓ４４０：ＹＥＳ）に、分類因子検出装置１０は、Ｓ３２０に示す処理を終了する。
【００５０】
上限値の示す確度が基準確度より大きく（Ｓ４３０：ＹＥＳ）かつ第１パターン又は第２パターンとして選択可能な構成要素を未だ選択していない場合（Ｓ４４０：ＮＯ）に、分類因子検出装置１０は、複数のオブジェクトの何れかが有する複数の構成要素のうち第２パターンに含まれていない構成要素である未評価要素のそれぞれについて、以下の処理を繰り返す（Ｓ５００）。
【００５１】
まず、構成要素追加手段１５０は、当該未評価要素を第２パターンに追加する第１の追加処理を行うべく、第２選択手段１２０に指示を送る（Ｓ５１０）。これを受けて、第２選択手段１２０は、第２パターンに当該未評価要素を追加した第２追加済パターンを生成する（Ｓ５２０）。
【００５２】
評価値生成手段１３０は、第１パターン及び第２追加済パターンを新たな第１パターン及び第２パターンとして、評価値を生成する処理を再帰的に行う（Ｓ３２０）。当該再帰的な処理の具体的実現方法の一例として、Ｓ３２０の処理は、所定のプログラミング言語におけるプログラムの関数により実現される。この場合、分類因子検出装置１０は、第１パターン及び第２追加済パターンを示す情報を、引数として値渡しにより当該関数に入力することにより、Ｓ３２０中の処理において新たな第１パターン及び第２パターンとして用いさせる。
【００５３】
これにより、評価値生成手段１３０は、当該新たな第１パターン及び第２パターンについて評価値を生成すると共に、当該新たな第１パターン及び第２パターンに更に未評価要素を追加した場合について評価値を生成することができる。
【００５４】
分類因子検出装置１０は、上記処理を未評価要素のそれぞれについて繰り返す（Ｓ５３０）。これにより、構成要素追加手段１５０は、未評価要素のそれぞれを第２パターンに追加した第２追加済パターンのそれぞれを生成する第１の追加処理を行い、評価値生成手段１３０は、第２追加済パターンのそれぞれについて評価値を生成することができる。
【００５５】
続いて、構成要素追加手段１５０は、第１パターン及び第２パターンが同一か否かを判断する（Ｓ６００）。第１パターン及び第２パターンが同一でない場合に（Ｓ６００：ＮＯ）、分類因子検出装置１０は、Ｓ３２０として示す処理を終了する。
【００５６】
第１パターン及び第２パターンが同一の場合に（Ｓ６００：ＹＥＳ）、分類因子検出装置１０は、未評価要素のそれぞれについて更に以下の処理を繰り返す（Ｓ６１０）。まず、構成要素追加手段１５０は、当該未評価要素を第１パターン及び第２パターンのそれぞれに追加する第２の追加処理を行うべく、第１選択手段１１０及び第２選択手段１２０に指示を送る（Ｓ６２０）。
【００５７】
好ましくは、構成要素追加手段１５０は、同一の分類条件について重複して評価値を生成させることを防止すべく、未評価要素を追加する順序を予め定めておく。例えば、オブジェクトが、構成要素Ａ、構成要素Ｂ、若しくは構成要素Ｃ又はこれらの組である場合には、構成要素追加手段１５０は、構成要素Ａ、構成要素Ｂ、及び構成要素Ｃをこの順序で追加し、順序を遡る追加処理を行わない。これにより、構成要素Ａ及び構成要素Ｂをこの順で追加した場合と、構成要素Ｂ及び構成要素Ａをこの順で追加した場合との双方において重複して評価値を生成することを防ぐことができる。
【００５８】
構成要素追加手段１５０からの指示を受けて、第１選択手段１１０は、第１パターンに当該未評価要素を追加した第１追加済パターンを生成する（Ｓ６３０）。更に、第２選択手段１２０は、第２パターンに当該未評価要素を追加した第２追加済パターンを生成する（Ｓ６４０）。
【００５９】
そして、評価値生成手段１３０は、第１追加済パターン及び第２追加済パターンを新たな第１パターン及び第２パターンとして、評価値を生成する処理を再帰的に行う（Ｓ３２０）。
【００６０】
分類因子検出装置１０は、上記処理を未評価要素のそれぞれについて繰り返し（Ｓ６５０）、Ｓ３２０として示した処理を終了する。これにより、構成要素追加手段１５０は、第１パターン及び第２パターンが同一の場合に、未評価要素のそれぞれを第１パターン及び第２パターンに追加した第１追加済パターン及び第２追加済パターンのそれぞれを生成する第２の追加処理を行うことができる。
【００６１】
以上本図で示したように、第１選択手段１１０及び第２選択手段１２０は、第１パターン及び第２パターンとして空集合を選択する。そして、構成要素追加手段１５０は、第１パターン及び第２パターンに未評価要素を順次追加し、評価値生成手段１３０は、追加後の第１パターン及び第２パターンの組のそれぞれについて評価値を生成する。この際、上限値見積手段１４０は、パターンに構成要素を追加した場合の評価値の上限値を生成する。そして、上限値見積手段１４０は、当該上限値の示す確度が所望の基準確度以下の場合には、構成要素の追加処理を停止する。これにより、分類因子検出装置１０は、評価するべき分類条件の数を減らし、探索時間を削減することができる。
【００６２】
図７は、図２に示したデータの分類表を示す。本図は、オブジェクトデータベース１００に格納されているオブジェクトの数の詳細を示すものであり、本図の説明の前提として、第１グループに分類された複数のオブジェクトのうち第１パターンを含むオブジェクトの数をａとし、前記第２パターンを含むオブジェクトの数をｂとし、第２グループに分類された複数のオブジェクトのうち第１パターンを含むオブジェクトの数をｃとし、第２パターンを含むオブジェクトの数をｄとする。
【００６３】
第１グループであるクラスＹのうち、第１パターンであるＰ１を含み第２パターンであるＰ２を含まない分類条件を満たすオブジェクトの数である第１充足数は、（ａ−ｃ）である。また、第２グループであるクラスＮのうち、当該分類条件を満たすオブジェクトの数である第２充足数は、（ｂ−ｄ）である。
【００６４】
また、クラスＹに含まれるオブジェクトの総数は、ｙであり、クラスＮに含まれるオブジェクトの総数は、ｎである。従って、オブジェクトデータベース１００に格納されるオブジェクトの総数は（ｙ＋ｎ）である。
【００６５】
本図において、第１充足数を記号（１）として表す。また、第２充足数を記号（２）として表す。また、クラスＹのうち分類条件を満たさないオブジェクトの数を記号（３）として表す。また、クラスＮのうち分類条件を満たさないオブジェクトの数を記号（４）として表す。
【００６６】
また、オブジェクトデータベース１００に格納されている分類条件を満たすオブジェクトの総数を記号（５）として表す。また、オブジェクトデータベース１００に格納されている分類条件を満たさないオブジェクトの総数を記号（６）として表す。また、分類条件を満たす旨を記号（７）として表す。また、分類条件を満たさない旨を記号（８）として表す。また、クラスＹに含まれるオブジェクトの総数を記号（９）として表す。また、クラスＮに含まれるオブジェクトの総数を記号（１０）として表す。
【００６７】
【数１】
2005044163.tif 000003
【数２】
2005044163.tif 000004
【数３】
2005044163.tif 000005
【数４】
2005044163.tif 000006
【数５】
2005044163.tif 000007
【数６】
2005044163.tif 000008
【数７】
2005044163.tif 000009
【数８】
2005044163.tif 000010
【数９】
2005044163.tif 000011
【数１０】
2005044163.tif 000012
【００６８】
図８（ａ）は、評価値生成手段１３０により生成される評価値を示す。本図において横軸は第１充足数を、縦軸は第２充足数を示す。また、高さ方向の軸は、第１充足数及び第１充足数に応じて定まるカイ２乗検定値を示す。評価値生成手段１３０は、第１充足数が（ａ−ｃ）でありかつ第２充足数が（ｂ−ｄ）である場合に、カイ２乗検定値である評価値８００を生成する。
【００６９】
評価値生成手段１３０は、第１パターン及び／又は第２パターンに構成要素が追加された場合に、第１充足数及び第２充足数のそれぞれに対して下に凸の評価関数により定まる値を、カイ２乗検定値である評価値として生成する（本図の実線で示す曲面）。より詳細には、評価値生成手段１３０は、第１充足数及び第２充足数に応じて値を定める以下の関数（１１）により、評価値を生成する。
【００７０】
【数１１】
2005044163.tif 000013
【００７１】
ここで、関数（１１）の導出過程を説明する。分類結果との相関が無い場合のオブジェクトの確率分布は、式（１２）により定まるＥｉｊである。
【００７２】
【数１２】
2005044163.tif 000014
【００７３】
カイ２乗検定値の定義式に基づき、分類結果との相関が無い場合に対する第１パターン及び第２パターンに基づく分類条件を満たすオブジェクトの確率分布の乖離度は、式（１３）により定まる。
【００７４】
【数１３】
2005044163.tif 000015
【００７５】
式（１２）を式（１３）に代入することにより、関数（１１）が導出される。なお、本例において、評価値生成手段１３０は、分類結果との相関が無い場合のオブジェクトの確率分布に対する第１パターン及び第２パターンに基づく分類条件を満たすオブジェクトの確率分布の乖離度を示すカイ２乗検定値を、評価値として生成する。これに代えて、評価値生成手段１３０は、分類結果との相関が所定値以下の場合のオブジェクトの確率分布に対する、第１パターン及び第２パターンに基づく分類条件を満たすオブジェクトの確率分布の乖離度を示すカイ２乗検定値を、評価値として生成してもよい。即ち、評価値生成手段１３０により生成される評価値は、式（１１）により定まる値に限定されるものではなく、分類条件によりオブジェクトを分類できる確度を示す値であればよい。
【００７６】
例えば、評価値生成手段１３０により生成される評価値を定める関数は、第１充足数及び第２充足数に基づいて下に凸の関数に限定されない。例えば、評価値生成手段１３０は、第１充足数及び第２充足数のそれぞれに対して値を定める関数であって、第１充足数及び第２充足数がとりうる値の範囲内における端点の何れかが当該関数の最大値となる評価関数について、当該評価関数により定まる値を評価値として生成してもよい。
【００７７】
図８（ｂ）は、第１パターンに構成要素を追加した場合における上限値を説明する図である。Ｐ１を拡張した場合、即ち、構成要素追加手段１５０が第１パターンに構成要素を追加した場合、第１パターンに含まれる構成要素の組は大きくなるので、第１パターンを含むオブジェクトの数は減少する。従って、Ｐ１を拡張した場合、第１充足数は、第２パターンの内容に関わらず０以上ａ以下の値となる。同様に、第２充足数は、０以上ｂ以下の値となる。例えば、評価値生成手段１３０は、第１パターンに構成要素を追加した場合の評価値として評価値８３０を生成する。
【００７８】
従って、第１パターンに構成要素を追加した場合の評価値の上限値は、第１充足数が０以上ａ以下及び第２充足数が０以上ｂ以下の範囲内における複数の端点のそれぞれにおける評価関数の値の最大値となる。例えば、評価値がカイ２条検定値である場合には、第１充足数及び第２充足数のそれぞれが０となった場合に対応する端点の最大値が上限値となる（式（１４））。
【００７９】
【数１４】
2005044163.tif 000016
【００８０】
なお、第１充足数及び第２充足数がとりうる値の範囲内における端点とは、第１充足数及び第２充足数の何れかが増加又は減少した場合に当該範囲外となる点をいう。例えば、第１充足数及び第２充足数がとりうる値の範囲が四角形で表される場合には、当該四角形の頂点又は辺上の点が、端点となる。
【００８１】
図８（ｃ）は、第２パターンに構成要素を追加した場合における上限値を説明する図である。Ｐ１⊂Ｐ２は、第１パターンが第２パターンの部分集合、部分木、又は部分グラフである旨を示す。Ｐ１⊂Ｐ２の条件の下Ｐ２を拡張した場合、即ち、第２パターンに構成要素を追加した場合、第２パターンに含まれる構成要素の組は大きくなるので、第１パターンを含みかつ第２パターンを含まない分類条件を満たすオブジェクトの数は増加する。従って、Ｐ１⊂Ｐ２の条件の下Ｐ２を拡張した場合、第１充足数は、ａ−ｃ以上ａ以下の値となる。同様に、第２充足数は、ｂ−ｄ以上ｂ以下の値となる。例えば、評価値生成手段１３０は、第２パターンに構成要素を追加した場合の評価値として評価値８４０を生成する。
【００８２】
従って、第２パターンに構成要素を追加した場合の評価値の上限値は、第１充足数がａ−ｃ以上ａ以下及び第２充足数がｂ−ｄ以上ｂ以下の範囲内における複数の端点のそれぞれにおける評価関数の値の最大値となる。例えば、評価値がカイ２条検定値である場合には、第２グループのうち第２パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ−ｃ，ｂ）及び第２グループのうち第１パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ，ｂ−ｄ）の最大値が上限値となる（式（１５））。
【００８３】
【数１５】
2005044163.tif 000017
【００８４】
構成要素追加手段１５０は、分類条件として選択しうる第１パターン及び第２パターンの全ての組合せについて評価値を生成させるべく、第１及び第２の追加処理を繰り返す。より詳細には、構成要素追加手段１５０は、第１パターン及び第２パターンが同一の場合には、第１及び第２の追加処理を行い、第１パターン及び第２パターンが同一でない場合には、第２の追加処理を行う。
【００８５】
ここで、構成要素追加手段１５０が第２の追加処理を行う場合、評価値の上限値は、式（１４）に示すＵ１により定まる値である。一方、構成要素追加手段１５０が第１の追加処理を行う場合、評価値の上限値は、式（１５）に示すＵ２により定まる値である。しかし、構成要素追加手段１５０が第２の追加処理を行う場合、第１パターン及び第２パターンが同一であるので、第１グループのうち第１パターンを含むオブジェクトの数であるａ及び第１グループのうち第２パターンを含むオブジェクトの数であるｃは等しい。同様に、第２グループのうち第１パターンを含むオブジェクトの数であるｂ及び第２グループのうち第２パターンを含むオブジェクトの数であるｄは等しい。この場合、Ｕ１＝Ｕ２となる。
【００８６】
従って、構成要素追加手段１５０が第１の追加処理及び第２の追加処理の何れを行うかに関わらず、上限値見積手段１４０は、第１パターン及び第２パターンのそれぞれ又は第２パターンに対して構成要素が追加される場合のカイ２乗検定値の上限値として、ｆ（ａ−ｃ，ｂ）及びｆ（ａ，ｂ−ｄ）の最大値を生成する。本図の例によると、上限値見積手段１４０は、上限候補値８１０及び上限候補値８２０の最大値を上限値として生成する。
【００８７】
以上本図で説明したように、評価値生成手段１３０は、第１パターン及び第２パターンのそれぞれ又は第２パターンに構成要素が追加された場合に、評価値として、図８（ａ）において実線で示す下に凸の関数が定める値を生成する。また、構成要素追加手段１５０による追加処理により、第１充足数及び第２充足数のとりうる範囲は定まっている。これにより、上限値見積手段１４０は、第１パターン及び／又は第２パターンに構成要素を追加することによる評価値の上限値を生成することができる。
【００８８】
図９は、基準確度を満たす分類条件を探索する順序を示す探索木の一例である。具体的には、本図は、複数のオブジェクトのそれぞれが、構成要素Ａ、構成要素Ｂ、若しくは構成要素Ｃ又はこれらの組である場合における評価値の生成順序を示している。
【００８９】
まず、第１選択手段１１０は、第１パターンとして空集合を選択し、第２選択手段１２０は、第２パターンとして空集合を選択する（Ｓ９００）。そして、構成要素追加手段１５０は、第１パターン及び第２パターンとして選択しうる全ての組合せについて評価値を生成させるべく、第１パターン及び第２パターンに順次未評価要素を追加する。
【００９０】
より詳細には、評価値生成手段１３０は、第１パターン及び第２パターンのそれぞれが構成要素Ａを含む場合に（Ｓ９０５）、Ｓ９０５において第２パターンに構成要素Ｂが追加された場合（Ｓ９１０）、Ｓ９１０において第２パターンに構成要素Ｃが追加された場合（Ｓ９１５）、Ｓ９０５において第２パターンに構成要素Ｃが追加された場合（Ｓ９２０）、Ｓ９０５において第１パターン及び第２パターンに構成要素Ｂが追加された場合（Ｓ９２５）、Ｓ９２５において第２パターンに構成要素Ｃが追加された場合（Ｓ９３０）、及びＳ９２５において第１パターン及び第２パターンに構成要素Ｃが追加された場合（Ｓ９３５）のそれぞれについて評価値を生成する。同様に、評価値生成手段１３０は、第１の追加処理及び第２の追加処理により、Ｓ９４０からＳ９９５のそれぞれにおいて評価値を生成する。
【００９１】
上記各ステップにおいて評価値生成手段１３０が評価値を生成する毎に、上限値見積手段１４０は、第１パターン及び／又は第２パターンに構成要素を追加した場合における評価値の上限値を生成する。そして、当該上限値の示す確度が基準確度以下の場合に、構成要素追加手段１５０は、構成要素の追加を停止する。例えば、本図のＳ９０５において、上限値見積手段１４０が生成した上限値の示す確度が基準確度以下の場合、構成要素追加手段１５０は、構成要素の追加を停止する。即ち、評価値生成手段１３０は、Ｓ９１０からＳ９４５までの処理を行うことなくＳ９５０に処理を移す。
【００９２】
本図で示すように、評価値生成手段１３０が、第１パターン及び第２パターンとして選択しうる全ての組合せについて評価値を生成してしまうと、その組合せの多さにより非常に大きな計算時間が必要となる。これに対し、本実施形態において、上限値見積手段１４０は、第１パターン及び／又は第２パターンに構成要素が追加される毎に、更に構成要素が追加された場合の評価値の上限値を生成し、上限値の示す確度が基準確度以下である場合に追加処理を停止させる探索木の枝刈処理を行う。これにより、評価値の示す確度が基準確度より大きくなる可能性がある場合についてのみ評価値を生成することができるので、各評価値の生成に要する処理を削減することにより計算時間を低減することができる。
【００９３】
なお、本図の例によれば、分類因子検出装置１０は、未評価要素を順次追加して評価値を生成する処理を繰り返す優先探索を行う。これに代えて、分類因子検出装置１０は、未評価要素のそれぞれを追加する処理を繰り返す幅優先探索を行ってもよい。即ち、本図に示した評価値の生成順序は一例であり、構成要素追加手段１５０は、第１パターン及び第２パターンが含み得る構成要素の全ての組合せについて評価値生成手段１３０に評価値を生成させるべく、第１パターン及び／又は第２パターンに未評価要素を追加すればよい。
【００９４】
図１０（ａ）は、所定の分析により薬理活性が認められる化学物質の一例を示す。図１０（ｂ）は、図１０（ａ）に関連する化学物質の一例を示す。図１０（ｃ）は、本実施形態とは異なる他の方法が薬理活性を有するパターンとして検出した構造の一例を示す。図１０（ｂ）に示すチミンに類似した構造を持つ図１０（ａ）に示すアジドチミジンは、細胞生物学的解析により、抗ＨＩＶ(Humman Immunodeficiency Virus)薬として知られている。
【００９５】
ＨＩＶは、免疫システムの中心的役割を果たすＣＤ４細胞の内部に侵入し、増殖して破壊する。ＣＤ４細胞がＨＩＶに感染すると、ＨＩＶのＲＮＡは逆転写酵素により２本鎖ＤＮＡに変換され、宿主染色体に組み込まれる。この２本鎖ＤＮＡの働きを抑制できれば、ＨＩＶの作用を抑制することができる。
【００９６】
しかしながら、宿主染色体に組み込まれたＤＮＡの能力は、宿主細胞の能力に隠されるので、この方法によるＨＩＶの作用の抑制は困難である。そこで、健全な宿主細胞に対しては何ら作用しない逆転写酵素の働きを抑えることにより、ＨＩＶの作用を抑制する方法が知られている。例えば、図１０（ａ）に示すアジドチミジンは、逆転写酵素の働きを抑える逆転写阻害剤として知られている。より詳細には、アジドチミジンは、逆転写酵素のある部位に結合して伸張中のＤＮＡ鎖に付加される。そして、アジドチミジンは、３’の位置の末端にＯＨ基を有していないので、更なるＤＮＡ鎖の合成を阻害することができる（非特許文献１参照。）。
【００９７】
他のデータマイニング手法に係る装置は、図１０（ｃ）に示すパターンを、薬理活性を有するパターンとして検出する。例えば、非特許文献１０に開示された方法に係る装置は、図１０（ｃ）に示すパターンのカイ２乗検定値が基準値より高い４９７９．５であるので、図１０（ｃ）に示すパターンを薬理活性を有するパターンとして検出する。
【００９８】
図１０（ｃ）に示すパターンは、図１０（ａ）に示すアジドチミジンに含まれるパターンであるので、当該装置は、薬理活性を有するパターンを適切に検出できたことになる。しかしながら、図１０（ｃ）に示すパターンを含む化学物質は多数存在するので、当該装置は、薬理効果の小さい他の化学物質をも薬理活性を有するパターンとして検出してしまう場合がある。これに対し、本実施形態に係る分類因子検出装置１０は、図１１及び図１２において説明するように、所定の条件の組を検出することができる。
【００９９】
図１１（ａ）は、分類因子検出装置１０により分類の因子として出力される第１パターンの一例を示す。図１１（ｂ）は、分類因子検出装置１０により分類の因子として出力される第２パターンの一例を示す。当該分類の因子が出力される処理の具体例を以下に示す。本例においてオブジェクトとは化学物質であり、構成要素とは複数の元素又はこれらの元素の化学的結合である。そして、複数の化学物質は各化学物質が薬品として所定の効用を有するか否かを実験により判定した結果に基づいて２つのグループに分類されている。
【０１００】
より詳細には、本図の例に用いるＨＩＶデータ（非特許文献６参照）における４２６８７個の化学物質は、実験により、ＨＩＶに対して活性が認められたＣＡグループ及びＨＩＶに対して活性の認められないＣＩグループに分類されている。
【０１０１】
第１選択手段１１０は、複数の化学物質の何れかが有する元素又は元素間の結合のうち、少なくとも一の元素及び元素間の結合の組を第１パターンとして選択し、第２選択手段１２０は、第１パターンに少なくとも一の元素又は元素間の結合を加えた元素又は元素間の結合の組を第２パターンとして選択する。例えば、第１選択手段１１０及び第２選択手段１２０のそれぞれは、元素をグラフの頂点とし、元素間の結合をグラフの辺としたデータから、頂点、辺、又は頂点及び辺の組を第１パターン及び第２パターンのそれぞれとして選択する。
【０１０２】
より詳細には、頂点の種類は、炭素、窒素、又は酸素等６６種類である。同種の元素でも芳香族結合を持つ元素と芳香族結合を持たない元素とは区別し互いに異なる頂点とする。また、辺の種類は単結合、２重結合、３重結合、又は芳香族結合の４種類である。
【０１０３】
そして、評価値生成手段１３０は、ＣＡグループに分類された複数の化学物質のうち分類条件を満たす化学物質の数である第１充足数及びＣＩグループに分類された化学物質のうち分類条件を満たす化学物質の数である第２充足数に応じて、評価値を生成する。例えば、評価値生成手段１３０は、図１１（ａ）に示す第１グループ及び図１１（ｂ）に示す第２グループに基づくカイ２乗検定値として、５３９４を生成する。
【０１０４】
分類因子出力手段１８０は、評価値の示す確度が基準確度を超える場合に、第１パターン及び第２パターンのそれぞれにおける化学物質の組を、所定の効用を有する化学物質を分類する因子として出力する。例えば、分類因子出力手段１８０は、カイ２乗検定値である５３９４の示す確度が基準確度を超えるので、図１１（ａ）に示す第１グループ及び図１１（ｂ）に示す第２グループを分類の因子として出力する。
【０１０５】
このように、分類因子検出装置１０は、図１１（ａ）に示す構成要素を含みかつ図１１（ｂ）に示す構成要素を含まない化学物質を、薬理活性を有する化学物質として検出することができる。これにより、分類因子検出装置１０は、薬理効果を有するパターンを適切に検出するのみならず、薬理効果を減少させてしまうパターンをも適切に検出することができる。特に、第２パターンの支持度が０．０２％と非常に小さいのにも関わらず、分類因子検出装置１０は、薬理効果を減少させてしまうパターンを適切に検出することができる。
【０１０６】
図１２（ａ）は、分類因子検出装置１０により分類の因子として出力される第１パターンの他の例を示す。図１２（ｂ）は、分類因子検出装置１０により分類の因子として出力される第２パターンの他の例を示す。分類因子出力手段１８０は、基準確度を超える確度を有する評価値を複数出力してもよい。例えば、分類因子出力手段１８０は、確度が基準確度を超える複数の評価値のうち、確度の高い方から予め定められた数の評価値に対応する分類条件を、分類の因子として出力してもよい。
【０１０７】
分類因子出力手段１８０は、図１１（ａ）及び図１１（ｂ）に示した分類条件と同様確度が基準確度を超えた評価値に対応するパターンとして、図１２（ａ）に示す第１パターン及び図１２（ｂ）に示す第２パターンを出力する。このように、分類因子検出装置１０は、薬理効果を有するパターン及び薬理効果を減少させるパターンの組を、分類の因子として複数出力してもよい。
【０１０８】
図１３は、ニュース記事を分類する因子を出力する例を示す。本例においてオブジェクトとはニュース記事の内容を示す文章であり、構成要素とは文章中の語句である。語句とは、例えば、少なくとも一の文字であってもよいし、単語であってもよい。そして、本図に示すニュース記事は、ニュース作成者又はニュース編集者が各ニュース記事のジャンルを分析することにより、国内経済ニュースのグループＹ及び国際経済ニュースのグループＮに分類されている。
【０１０９】
第１選択手段１１０は、複数の文章の何れかが有する語句のうち、少なくとも一の語句の組を第１パターンとして選択し、第２選択手段１２０は、第１パターンに少なくとも一の語句を加えた語句の組を第２パターンとして選択する。
【０１１０】
そして、評価値生成手段１３０は、第１グループに分類された複数の語句のうち分類条件を満たす文章の数及び第２グループに分類された文章のうち分類条件を満たす文章の数に応じて、評価値を生成する。
【０１１１】
分類因子出力手段１８０は、評価値の示す確度が基準確度を超える場合に、第１パターン及び第２パターンのそれぞれにおける語句の組を、複数の文章を所定のジャンルに分類する因子として出力する。例えば、分類因子出力手段１８０は、第１パターンとして語句「価格」を検出し、第２パターンとして語句「価格」及び語句「国際」を検出し、これらのパターンの組を、国内経済ニュースを分類する因子として出力する。
【０１１２】
このように、本実施形態における分類因子検出装置１０が分類の因子を検出する対象は、化学物質に限定されるものではなく、分類因子検出装置１０は、ニュース記事を示す文章を分類する因子を検出してもよい。これにより、分類因子検出装置１０を用いることにより、新たに製作されたニュース記事であっても適切なジャンルに迅速に分類することができる。
【０１１３】
なお、本図の例において分類因子検出装置１０は、第１パターン又は第２パターンとして語句の組を検出する。これに加えて、分類因子検出装置１０は、語句の係り受け関係、語句が形成する節、及び文章の構造等の組合せである構文解析結果を、第１パターン又は第２パターンとして検出してもよい。例えば、分類因子検出装置１０は、構文解析結果をグラフ又は木構造で示したデータに基づき、分類の因子を検出してもよい。
【０１１４】
図１４は、ウェブページの閲覧履歴を分類する因子を出力する例を示す。本例においてオブジェクトとはワールド・ワイド・ウェブサイトの閲覧履歴であり、構成要素とは閲覧されたウェブページ及び閲覧順序を示す順序情報である。そして、複数の閲覧履歴は、閲覧の結果行われた処理により２つのグループに分類されている。例えば、複数の閲覧履歴は、閲覧の過程又は閲覧の結果、ウェブページにおいて商品の売買を行ったか否かにより、商品の売買を行ったグループＹ及び商品の売買を行わなかったグループＮに分類されている。
【０１１５】
第１選択手段１１０は、閲覧履歴の何れかが有するウェブページ及び順序情報のうち、少なくとも一を第１パターンとして選択し、第２選択手段１２０は、第１パターンに少なくとも一のウェブページ又は順序情報を加えた第２パターンを選択する。
【０１１６】
そして、評価値生成手段１３０は、第１グループに分類された閲覧履歴のうち分類条件を満たす閲覧履歴の数及び第２グループに分類された閲覧履歴のうち分類条件を満たす閲覧履歴の数に応じて、評価値を生成する。
【０１１７】
分類因子出力手段１８０は、評価値の示す確度が基準確度を超える場合に、第１パターン及び第２パターンのそれぞれにおけるウェブページ及び閲覧順序の組を、閲覧の過程又は閲覧の結果商品の売買を行うか否かに応じた分類の因子として出力する。例えば、分類因子出力手段１８０は、第１パターンとしてウェブページ「購入確認」を検出し、第２パターンとしてウェブページ「購入確認」及び「商品性能」を検出し、これらのパターンの組を、商品の売買を行った閲覧履歴を分類する因子として出力する。
【０１１８】
このように、本例によると、分類因子検出装置１０は、ウェブページの閲覧履歴を対象として、当該閲覧履歴の分類の因子を適切に検出して出力することができる。これにより、分類因子検出装置１０は、ワールド・ワイド・ウェブシステムを用いた商品取引におけるマーケティング等を支援することができる。
【０１１９】
図１５は、分類因子検出装置１０のハードウェア構成の一例を示す。分類因子検出装置１０は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、グラフィックコントローラ１０７５、及び表示装置１０８０を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【０１２０】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【０１２１】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ファイバチャネル等のネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、分類因子検出装置１０が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
【０１２２】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、分類因子検出装置１０の起動時にＣＰＵ１０００が実行するブートプログラムや、分類因子検出装置１０のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【０１２３】
分類因子検出装置１０に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び／又は入出力コントローラ１０８４を介して、記録媒体から読み出され分類因子検出装置１０にインストールされて実行される。
【０１２４】
分類因子検出装置１０にインストールされて実行されるプログラムは、第１選択モジュールと、第２選択モジュールと、評価値生成モジュールと、上限値見積モジュールと、構成要素追加モジュールと、基準確度格納モジュールと、基準確度更新モジュールと、分類因子出力モジュールとを含む。各モジュールが分類因子検出装置１０に働きかけて行わせる動作は、図１から図１４において説明した分類因子検出装置１０における、対応する部材の動作と同一であるから、説明を省略する。
【０１２５】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを分類因子検出装置１０に提供してもよい。
【０１２６】
以上、本実施形態で説明したように、分類因子検出装置１０は、それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出することができる。
【０１２７】
より詳細には、分類因子検出装置１０は、所定のパターンを含むか否かの条件のみならず、第１パターンを含みかつ第２パターンを含まない分類条件を、分類の因子として検出することができる。これにより、薬品として所定の効用を有しかつ副作用を有さない化学構造等、様々な応用分野において適切な分類因子を検出することができる。
【０１２８】
また、分類因子検出装置１０は、第１パターン及び／又は第２パターンに構成要素を順次追加して分類の確度を生成する。この際、分類因子検出装置１０は、第１パターン及び／又は第２パターンに更に構成要素を追加した場合の評価値の上限値を生成する。そして、分類因子検出装置１０は、当該上限値が所望の確度に満たない場合には、更なる追加処理を停止する。これにより、評価値が上限値を超える可能性のある分類条件についてのみ評価値を生成することができるので、計算処理時間を低減することができる。
【０１２９】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０１３０】
以上の実施形態によると、以下の各項目に示す分類因子検出装置、分類因子検出方法、プログラム、及び記録媒体が実現される。
【０１３１】
（項目１）  それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出する分類因子検出装置であって、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択手段と、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択手段と、第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力手段とを備える分類因子検出装置。
【０１３２】
（項目２）  前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、前記分類因子検出装置は、前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段とを更に備え、前記評価値生成手段は、更に、前記構成要素追加手段により追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する項目１記載の分類因子検出装置。
（項目３）  前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記分類結果との相関が所定の値以下である分類条件を満たすオブジェクトの確率分布に対する、前記第１パターン及び前記第２パターンに基づく前記分類条件を満たすオブジェクトの確率分布の乖離度を示すカイ２乗検定値を生成する項目２記載の分類因子検出装置。
【０１３３】
（項目４）  前記第１グループに分類された複数のオブジェクトのうち前記第１パターンを含むオブジェクトの数をａとし、前記第２パターンを含むオブジェクトの数をｂとし、前記第２グループに分類された複数のオブジェクトのうち前記第１パターンを含むオブジェクトの数をｃとし、前記第２パターンを含むオブジェクトの数をｄとする場合において、前記評価値生成手段は、前記第１充足数である（ａ−ｃ）及び前記第２充足数である（ｂ−ｄ）に基づいて前記カイ２乗検定値を生成する前記評価関数であるｆ（ａ−ｃ，ｂ−ｄ）により定まる値を、前記評価値として生成し、前記上限値見積手段は、前記第１パターン及び前記第２パターンのそれぞれ又は前記第２パターンに対して構成要素が追加される場合の前記カイ２乗検定値の上限値として、前記第２グループのうち第２パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ−ｃ，ｂ）及び前記第２グループのうち第１パターンを含むオブジェクトの数が０である場合のカイ２乗検定値であるｆ（ａ，ｂ−ｄ）の最大値を生成する項目３記載の分類因子検出装置。
【０１３４】
（項目５）  前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記第１充足数及び前記第２充足数の一様性を示すエントロピー値に基づく値を生成する項目２記載の分類因子検出装置。
（項目６）  前記評価値生成手段は、前記評価関数により定まる前記評価値として、前記第１充足数及び前記第２充足数の差分の大きさを示すジニ係数値を生成する項目２記載の分類因子検出装置。
（項目７）  前記上限値見積手段は、前記評価値生成手段により前記評価値が生成される毎に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加した場合及び前記第１パターンの内容を保持したまま前記第２パターンに構成要素を追加した場合の前記評価値の上限値を生成し、前記上限値が示す確度が前記基準確度より大きい場合において、前記構成要素追加手段は、前記複数のオブジェクトの何れかが有する複数の構成要素のうち前記第２パターンに含まれていない構成要素である未評価要素のそれぞれを前記第２パターンに追加した第２追加済パターンのそれぞれを生成する第１の追加処理を行い、更に、前記第１パターン及び前記第２パターンが同一の場合に、前記未評価要素のそれぞれを前記第１パターン及び前記第２パターンに追加した第１追加済パターン及び第２追加済パターンのそれぞれを生成する第２の追加処理を行い、前記評価値生成手段は、第１又は第２の前記追加処理が行われた前記第１追加済パターン及び前記第２追加済パターンについて前記評価値を生成する項目２記載の分類因子検出装置。
【０１３５】
（項目８）  前記基準確度を格納する基準確度格納手段と、前記評価値生成手段により生成された前記評価値の示す確度が前記基準確度を超える場合に、当該評価値が示す確度を当該評価値が生成された場合の前記第１パターン及び前記第２パターンに対応付けて前記基準確度として前記基準確度格納手段に格納する基準確度更新手段とを更に備え、前記分類因子出力手段は、前記基準確度格納手段に格納された前記第１パターン及び前記第２パターンを、分類の因子として出力する項目２記載の分類因子検出装置。
（項目９）  前記分類因子出力手段は、前記評価値生成手段により生成され確度が前記基準確度を超える複数の評価値のうち、確度の高い順に予め定められた数の評価値のそれぞれに対応する分類条件を、前記分類の因子として出力する項目２記載の分類因子検出装置。
【０１３６】
（項目１０）  前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して値を定める関数であって、前記第１充足数及び前記第２充足数がとりうる値の範囲内における端点の何れかが当該関数の最大値となる評価関数について、当該評価関数により定まる値を前記評価値として生成し、前記分類因子検出装置は、前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段とを更に備え、前記評価値生成手段は、更に、前記構成要素追加手段により追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する項目１記載の分類因子検出装置。
（項目１１）  前記オブジェクトは、複数の構成要素として複数の元素が化学的に結合した化学物質であり、複数の前記化学物質は、各化学物質が薬品として所定の効用を有するか否かを実験により判定した結果に基づいて２つのグループに分類されており、前記第１選択手段は、前記複数の化学物質の何れかが有する元素又は元素間の結合のうち、少なくとも一の元素及び元素間の結合の組を前記第１パターンとして選択し、前記第２選択手段は、前記第１パターンに少なくとも一の元素又は元素間の結合を加えた元素又は元素間の結合の組を前記第２パターンとして選択し、前記評価値生成手段は、前記第１グループに分類された複数の化学物質のうち前記分類条件を満たす化学物質の数及び前記第２グループに分類された化学物質のうち前記分類条件を満たす化学物質の数に応じて、前記評価値を生成し、前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける化学物質の組を、前記所定の効用を有する化学物質を分類する因子として出力する項目１記載の分類因子検出装置。
【０１３７】
（項目１２）  前記オブジェクトは、複数の語句により構成される文章であり、複数の前記文章は、各文章を当該文章の内容を示すジャンルにより２つのグループに分類されており、前記第１選択手段は、前記複数の文章の何れかが有する語句のうち、少なくとも一の語句の組を前記第１パターンとして選択し、前記第２選択手段は、前記第１パターンに少なくとも一の語句を加えた語句の組を前記第２パターンとして選択し、前記評価値生成手段は、前記第１グループに分類された複数の語句のうち前記分類条件を満たす文章の数及び前記第２グループに分類された文章のうち前記分類条件を満たす文章の数に応じて、前記評価値を生成し、前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける語句の組を、複数の文章を所定のジャンルに分類する因子として出力する項目１記載の分類因子検出装置。
（項目１３）  前記オブジェクトは、ワールド・ワイド・ウェブサイトの閲覧履歴であり、前記構成要素は、閲覧されたウェブページ及び閲覧順序を示す順序情報であり、複数の前記閲覧履歴は、閲覧の結果行われた処理により２つのグループに分類されており、前記第１選択手段は、前記閲覧履歴の何れかが有する前記ウェブページ及び前記順序情報のうち、少なくとも一を前記第１パターンとして選択し、前記第２選択手段は、前記第１パターンに少なくとも一の前記ウェブページ又は前記順序情報を加えた前記第２パターンを選択し、前記評価値生成手段は、前記第１グループに分類された閲覧履歴のうち前記分類条件を満たす閲覧履歴の数及び前記第２グループに分類された閲覧履歴のうち前記分類条件を満たす閲覧履歴の数に応じて、前記評価値を生成し、前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける前記ウェブページ及び前記閲覧順序の組を、閲覧の結果行う処理に応じた分類の因子として出力する項目１記載の分類因子検出装置。
（項目１４）  前記複数の閲覧履歴は、閲覧の過程又は閲覧の結果、ウェブページにおいて商品の売買を行ったか否かにより２つのグループに分類されており、前記分類因子出力手段は、前記評価値の示す確度が前記基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおけるウェブページ及び閲覧順序を、閲覧の過程又は閲覧の結果商品の売買を行うか否かに応じた分類の因子として出力する項目１３記載の分類因子検出装置。
【０１３８】
（項目１５）  それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組をコンピュータにより検出する分類因子検出方法であって、前記コンピュータにより、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択段階と、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択段階と、第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成段階と、前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力段階とを備える分類因子検出方法。
（項目１６）  前記評価値生成段階において、前記コンピュータは、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、当該分類因子検出方法は、前記コンピュータにより、前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積段階と、前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加段階とを更に備え、前記評価値生成段階として、前記コンピュータは、更に、前記構成要素追加段階において追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する項目１５記載の分類因子検出方法。
【０１３９】
（項目１７）  それぞれが複数の構成要素により構成される複数のオブジェクトを、各オブジェクトが所定の特性を有するか否かを分析して２つのグループに分類した分類結果について、当該分類の因子となる構成要素の組を検出する分類因子検出装置としてコンピュータを機能させるプログラムであって、前記コンピュータを、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、少なくとも一の構成要素の組である第１パターンを選択する第１選択手段と、前記複数のオブジェクトの何れかが有する複数の構成要素のうち、前記第１パターンに少なくとも一の他の構成要素を加えた第２パターンを選択する第２選択手段と、第１グループに分類された複数のオブジェクトのうち前記第１パターンを含みかつ前記第２パターンを含まない分類条件を満たすオブジェクトの数及び第２グループに分類されたオブジェクトのうち前記分類条件を満たすオブジェクトの数に基づいて、前記分類条件により複数のオブジェクトを分類できる確度の評価値を生成する評価値生成手段と、前記評価値の示す確度が予め定められた基準確度を超える場合に、前記第１パターン及び前記第２パターンのそれぞれにおける構成要素を分類の因子として出力する分類因子出力手段として機能させるプログラム。
（項目１８）  前記評価値生成手段は、前記第１グループのうち前記分類条件を満たすオブジェクトの数である第１充足数及び前記第２グループのうち前記分類条件を満たすオブジェクトの数である第２充足数のそれぞれに対して下に凸の評価関数により定まる値を前記評価値として生成し、前記コンピュータを、前記第１パターン及び／又は前記第２パターンに構成要素を追加することにより前記第１充足数及び前記第２充足数がとりうる値の範囲内における評価値の上限値として、当該範囲内における複数の端点のそれぞれにおける前記評価関数の値の最大値を生成する上限値見積手段と、前記上限値の示す確度が前記基準確度より大きい場合に、前記第１パターン及び前記第２パターンのそれぞれに同一の構成要素を追加する処理又は前記第２パターンに構成要素を追加する処理を行う構成要素追加手段として更に機能させ、前記評価値生成手段は、前記構成要素追加手段において追加された前記第１パターン及び／又は前記第２パターンについて前記評価値を生成する項目１７記載のプログラム。
（項目１９）  項目１７又は項目１８記載のプログラムを記録した記録媒体。
【図面の簡単な説明】
【０１４０】
【図１】図１は、分類因子検出装置１０の機能ブロック図である。
【図２】図２は、オブジェクトデータベース１００の内容の一例を示す。
【図３】図３は、分類因子検出装置１０の動作フローを示す。
【図４】図４は、図３のＳ３２０における動作フローの詳細を示す。
【図５】図５は、図４に続く動作フローを示す。
【図６】図６は、図５に続く動作フローを示す。
【図７】図７は、図２に示したデータの分類表を示す。
【図８】図８（ａ）は、評価値生成手段１３０により生成される評価値を示す。  図８（ｂ）は、第１パターンに構成要素を追加した場合における上限値を説明する図である。  図８（ｃ）は、第２パターンに構成要素を追加した場合における上限値を説明する図である。
【図９】図９は、基準確度を満たす分類条件を探索する順序を示す探索木の一例である。
【図１０】図１０（ａ）は、所定の分析により薬理活性が認められる化学物質の一例を示す。  図１０（ｂ）は、図１０（ａ）に関連する化学物質の一例を示す。  図１０（ｃ）は、本実施形態とは異なる他の方法が薬理活性を有するパターンとして検出した構造の一例を示す。
【図１１】図１１（ａ）は、分類因子検出装置１０により分類の因子として出力される第１パターンの一例を示す。  図１１（ｂ）は、分類因子検出装置１０により分類の因子として出力される第２パターンの一例を示す。
【図１２】図１２（ａ）は、分類因子検出装置１０により分類の因子として出力される第１パターンの他の例を示す。  図１２（ｂ）は、分類因子検出装置１０により分類の因子として出力される第２パターンの他の例を示す。
【図１３】図１３は、ニュース記事を分類する因子を出力する例を示す。
【図１４】図１４は、ウェブページの閲覧履歴を分類する因子を出力する例を示す。
【図１５】図１５は、分類因子検出装置１０のハードウェア構成の一例を示す。
【符号の説明】
【０１４１】
１０  分類因子検出装置
１００  オブジェクトデータベース
１１０  第１選択手段
１２０  第２選択手段
１３０  評価値生成手段
１４０  上限値見積手段
１５０  構成要素追加手段
１６０  基準確度格納手段
１７０  基準確度更新手段
１８０  分類因子出力手段
２００  化学物質
２１０  化学物質
２２０  化学物質
２３０  化学物質
２４０  化学物質
２５０  化学物質
８００  評価値
８１０  上限候補値
８２０  上限候補値
８３０  評価値
８４０  評価値
【図１】
2005044163.tif 000018
【図２】
2005044163.tif 000019
【図３】
2005044163.tif 000020
【図４】
2005044163.tif 000021
【図５】
2005044163.tif 000022
【図６】
2005044163.tif 000023
【図７】
2005044163.tif 000024
【図８】
2005044163.tif 000025
【図９】
2005044163.tif 000026
【図１０】
2005044163.tif 000027
【図１１】
2005044163.tif 000028
【図１２】
2005044163.tif 000029
【図１３】
2005044163.tif 000030
【図１４】
2005044163.tif 000031
【図１５】
2005044163.tif 000032