(57)【特許請求の範囲】
【請求項１】
プロセッサと記憶装置とを有するコンピュータで実現される方法であって、前記記憶装置に格納される、複数の特徴量を特徴とする複数のデータと関連付けられるデシジョンツリーのノードを洗練するための方法であって、
Ａ）前記プロセッサが、特徴量の各々に沿って複数のファジークラスタ解析を行なって、それぞれの前記ファジークラスタ解析における１つまたはそれ以上のクラスタについてのデータのメンバーシップ関数に基づいて複数のそれぞれの分割係数を計算して、前記計算された複数のそれぞれの分割係数を前記記憶装置に格納するステップを備え、前記メンバーシップ関数は、前記ファジークラスタ解析によって規定されるものであり、
Ｂ）前記プロセッサが、前記記憶装置に格納されている複数の分割係数のうちの最大分割係数に対応する特徴量のうち１つを選択するステップと、
Ｃ）前記プロセッサが、前記選択された特徴量に対応するファジークラスタ解析に基づいて、前記選択された特徴量に沿って、前記データを１つまたはそれ以上のグループに細分するステップと、
Ｄ）前記プロセッサが、１つまたはそれ以上のグループの各々ごとにデシジョンツリーの１つまたはそれ以上のアークをノードにそれぞれ作成し、前記１つまたはそれ以上のグループに基づくデシジョンツリーを構築するステップと、
Ｅ）前記プロセッサが、前記グループの各々のデータを前記複数の特徴量のうち前記選択された特徴量を除く残りの特徴量に射影し、射影されたデータが前記残りの特徴量で特徴付けられるようにするステップと、
Ｆ）前記プロセッサが、ｉ）各前記グループにおいて前記射影されたデータにファジークラスタ解析を行うことによって前記ステップＡおよびＢにより残りの特徴量から１つの特徴量を選択するステップと、ｉｉ）選択された特徴量についてステップＣないしＥにより葉ノードに到達するまでさらにデシジョンツリーを構築するステップを再帰的に行なうステップを含む、方法。
【請求項２】
前記ステップＡおよびＦにおける、ファジークラスタ解析を行なうステップは、複数のファジーｃ平均解析を行なうステップを含む、請求項１に記載の方法。
【請求項３】
ファジークラスタ解析を行うステップは、
前記１つまたはそれ以上のグループの各々ごとに、前記１つまたはそれ以上のグループのすべてを統合したデータの領域境界の差に対する前記各グループにおけるデータの領域境界の差の領域比を計算するステップと、
領域比が予め定められたしきい値と予め定められた関係を有するか否かを判断するステップと、
領域比が予め定められたしきい値と予め定められた関係を有する場合、データを単一のクラスタにグループ化するステップとを含む、請求項１に記載の方法。
【請求項４】
領域比が予め定められたしきい値と予め定められた関係を有するか否かを判断するステップは、領域比が予め定められたしきい値よりも小さいか否かを判断するステップを含む、請求項３に記載の方法。
【請求項５】
１つまたはそれ以上のプロセッサと記憶装置とを有するコンピュータに、前記記憶装置に格納される、複数の特徴量を特徴とする複数のデータと関連付けられるデシジョンツリーのノードを洗練するための処理を実行させるコンピュータプログラムを記録した不揮発性記録媒体であって、前記コンピュータプログラムは、
Ａ）前記プロセッサが、特徴量の各々に沿って複数のファジークラスタ解析を行なって、それぞれの前記ファジークラスタ解析における１つまたはそれ以上のクラスタについてのデータのメンバーシップ関数に基づいて複数のそれぞれの分割係数を計算して、前記計算された複数のそれぞれの分割係数を前記記憶装置に格納するステップを備え、前記メンバーシップ関数は、前記ファジークラスタ解析によって規定されるものであり、
Ｂ）前記プロセッサが、前記記憶装置に格納されている複数の分割係数のうちの最大分割係数に対応する特徴量のうち１つを選択するステップと、
Ｃ）前記プロセッサが、前記選択された特徴量に対応するファジークラスタ解析に基づいて、前記選択された特徴量に沿って、前記データを１つまたはそれ以上のグループに細分するステップと、
Ｄ）前記プロセッサが、１つまたはそれ以上のグループの各々ごとにデシジョンツリーの１つまたはそれ以上のアークをノードにそれぞれ作成し、前記１つまたはそれ以上のグループに基づくデシジョンツリーを構築するステップと、
Ｅ）前記プロセッサが、前記グループの各々のデータを前記複数の特徴量のうち前記選択された特徴量を除く残りの特徴量に射影し、射影されたデータが前記残りの特徴量で特徴付けられるようにするステップと、
Ｆ）前記プロセッサが、ｉ）各前記グループにおいて前記射影されたデータにファジークラスタ解析を行うことによって前記ステップＡおよびＢにより残りの特徴量から１つの特徴量を選択するステップと、ｉｉ）選択された特徴量についてステップＣないしＥにより葉ノードに到達するまでさらにデシジョンツリーを構築するステップを再帰的に行なうステップとをコンピュータに実行させる、コンピュータプログラムを記録した不揮発性記録媒体。
【請求項６】
前記ステップＡおよびＦにおける、ファジークラスタ解析を行なうステップは、複数のファジーｃ平均解析を行なうステップを含む、請求項５に記載のコンピュータプログラムを記録した不揮発性記録媒体。
【請求項７】
ファジークラスタ解析を行うステップは、
前記１つまたはそれ以上のグループの各々ごとに、前記１つまたはそれ以上のグループのすべてを統合したデータの領域境界の差に対する前記各グループにおけるデータの領域境界の差の領域比を計算するステップと、
領域比が予め定められたしきい値と予め定められた関係を有するか否かを判断するステップと、
領域比が予め定められたしきい値と予め定められた関係を有する場合、データを単一のクラスタにグループ化するステップとを含む、請求項５に記載のコンピュータプログラムを記録した不揮発性記録媒体。
【請求項８】
領域比が予め定められたしきい値と予め定められた関係を有するか否かを判断するステップは、領域比が予め定められたしきい値よりも小さいか否かを判断するステップを含む、請求項７に記載のコンピュータプログラムを記録した不揮発性記録媒体。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、データ解析に関し、より特定的にはデシジョンツリーを生成することに関する。
【０００２】
【発明の背景】
データマイニング、知識獲得およびデータ解析の他の形は、膨大な量の蓄積されたデータからの有用な情報の抽出を伴う。たとえば、製薬会社は、どの病気がどの薬品化合物によって有効に治療されるか、および薬品化合物の副作用は何であるかなどの、薬品化合物およびそれらの特徴を列挙する大きなデータベースを生成する。種々の薬品化合物が多数であることを考慮すると、手動でこのデータを分析して、薬品のどのグループが病気のグループの各々を治療するのにより有効であるとか、より有効でないとかいうことを決定するなどの、有用なパターンを確定することは困難であり、薬品および病気の所望のグルーピングが前もって特定されていないときにはとりわけそうである。
【０００３】
従来のデータマイニング技術は、パターン認識および確率論的解析を用いてデシジョンツリーを生成する。デシジョンツリーは、オブジェクトを複数個のクラスにいかにして分類するかをうまく示す規則の階層的配置を含むデータ構造である。より具体的には、各オブジェクトは、多数の属性によって特徴付けられ、デシジョンツリーにおける各規則は、属性の１つの値をテストする。デシジョンツリーは、目標変数に対して異なった影響を有する可能性の高い規則の組にデータを分ける。たとえば、薬品化合物およびその投与の方法の特性であって特定の病気を治療するのに有効である可能性の高いものを見付けたいことがあるかもしれない。これらの特性は、１組の規則に変換可能である。
【０００４】
図５は、患者のための仮定的医療条件をいかにして処理するかを表わす例示のデシジョンツリー５００を表わす。例示のデシジョンツリー５００は、２つの分岐ノード５１０および５３０と、３つの葉ノード５２０、５４０および５５０と、アーク５１２、５１４、５３２および５３４とを含む。
【０００５】
分岐ノード５１０および５３０の各々は、患者の特定の属性に対する多数の可能性ある値の中からいかにして選択するかを示す「規則」または条件を表わす。属性が取り得る可能な値は、アーク５１２、５１４、５３２および５３４によって示される。可能な値の中から選択がなされると、対応するアークが取られ、葉ノードまたは別の分岐ノードに到達する。分岐ノード５１０の１つは、デシジョンツリーの開始点である「ルート」ノードとして指定される。
【０００６】
たとえば、ルート分岐ノード５１０は、「ＡＧＥ？」とラベル付けされ、患者の年齢がテストされることを示す。分岐ノード５１０を葉ノード５２０に接続するアーク５１２は、「＜＝１２？」とラベル付けされ、患者の年齢が１２歳以下であるならば葉ノード５２０に到達すべきであることを示す。他方で、アーク５１４は分岐ノード５１０を分岐ノード５３０に接続し、患者の年齢が１２歳より大きければ分岐ノード５３０に到達すべきことを示す、「＞１２？」とラベル付けされる。分岐ノード５３０は、「ＴＥＭＰ？」とラベル付けされ、患者の体温がテストされることを示す。患者の体温が１０２°以下であれば（アーク５３２によって示される）、葉ノード５４０に到達する。さもなくば、患者の体温が１０２°より大きければ（アーク５３４によって示される）、葉ノード５５０に到達する。
【０００７】
葉ノード５２０、５４０および５５０は、オブジェクトの「判断」または分類を表わす。たとえば、判断は、患者に対して投与されるべき治療薬である。葉ノード５２０においては、判断は２０ｍｇの薬品Ｘを使用することであり、葉ノード５４０においては、判断は４０ｍｇの薬品Ｘを使用することであり、葉ノード５５０においては、判断は１０ｍｇの薬品Ｙを使用することである。
【０００８】
例示のデシジョンツリー５００は、「ルート」ノードで始まって、患者の属性をテストして、アークを選択し、葉ノードに到達するまでアークを辿ることにより、どの治療薬が患者に投与されるべきかを決定するために使用され得る。たとえば、９８．６°の体温の１０歳の子供が治療されるべきであるとする。ルート分岐ノード５１０で始まり、患者の年齢がテストされる。１０歳は１２歳未満であるので、アーク５１２を辿って葉ノード５２０に到達する。したがって、２０ｍｇの薬品Ｘがその１０歳児に処方される。別の例として、患者が１０５°の熱を有する３２歳であったとする。ルート分岐ノード５１０で始まり、患者の年齢がテストされる。３２歳という年齢は１２歳より大きいので、分岐ノード５３０までアーク５１４を辿り、ここで患者の体温がテストされる。患者は１０５°の熱を有するので、アーク５３４を辿って、１０ｍｇの薬品Ｙが投与されるべきであることを示す葉ノード５５０に到達する。
【０００９】
デシジョンツリー誘導とは、トレーニングデータのセットからデシジョンツリーをいかにして構築するかを決定するプロセスのことをいう。特に、デシジョンツリーは、あるとすれば、どの属性を最初にテストしどの特性を後にテストすべきかをうまく特定することにより構築される。デシジョンツリーを構築するためのよくある従来の方策は、「デシジョンツリーの誘導」またはＩＤ３として知られている。ＩＤ３は、１組の予め定義されたクラスに属する１組のトレーニングオブジェクトで始まる再帰的アルゴリズムである。すべてのオブジェクトが単一のクラスに属するのであれば、判断はなされず、葉ノードが生成され、そのクラスでラベル付けされる。さもなくば、分岐ノードが生成され、分岐ノードでオブジェクトを区別するためにその属性が使用されたならば最高の「情報利得」を与えるような属性が選択される。情報利得は、各属性の平均エントロピーを求めることにより計算される。
【００１０】
ＩＤ３によって発生されるものなどの従来のデシジョンツリーでの問題は、そのようなデシジョンツリーが固定的で柔軟性がなく脆弱であるということである。薬品の有効性の例において、従来のデシジョンツリーは、異なった薬品が様々な度合いの有効性を有しているときにも、データへの「二者択一的な」または２値的な方法を強いる。たとえば、デシジョンツリーにおけるクリスプな範囲の境界の近くのデータ値は、実世界データの不正確さのために誤って分類されがちである。したがって、デシジョンツリーに「ファジー論理」という概念を適用する多くの試みがなされてきた。
【００１１】
ファジー論理は、実世界の不確かさをモデル化するための手段として１９６０年代に導入された。オブジェクトを、あるクラスのフルメンバーまたは全くメンバーでないのいずれかとして分類する代わりに、ファジー論理は、オブジェクトがクラスに属する度合いを表わすために０．０と１．０との間の「メンバーシップ関数」を採用する。たとえば、患者の年齢を「１２歳以下」および「１２歳より上」として類別するのではなく、OldとYoungという２つのファジー集合を採用して、２歳児が、Oldファジー集合におけるメンバーシップ関数μOld（２）＝０．０１以外に、Youngファジー集合におけるメンバーシップ関数μYoung（２）＝０．９９を有してもよいようにすることができる。反対に、６５歳の退職者は、μYoung（６５）＝０．１３のYoungメンバーシップ関数と、μOld（６５）＝０．８７のOldメンバーシップ関数を有してもよい。しかしながら、ティーンエイジャーについては、メンバーシップ関数はそれほど極端ではない。たとえば、１３歳の者は、μYoung（１３）＝０．４５およびμOld（１３）＝０．５５というメンバーシップ関数を有してもよい。
【００１２】
古典的なクリスプなデシジョンツリーとファジー論理とを組合せるためのある試みは、ＦＩＤ３として知られており、ユーザが、トレーニングデータのすべてについて予め定義されたクラスの各々においてメンバーシップ関数を定義する。各メンバーシップ関数は、ファジーな判断のアークラベルとしての役割を果たすことができる。ＩＤ３においてのように、ＦＩＤ３は、情報利得を最大にすることによりそのデシジョンツリーを生成する。ファジーなデシジョンツリーの判断はファジー変数でもあり、可能な分類の各々においてテストされたオブジェクトのメンバーシップを示すものである。図５の例において、分岐ノード５１０から発するアーク５１２および５１４は、それぞれ、Youngファジー集合およびOldファジー集合上のメンバーシップ関数によってファジー化することが可能である。たとえば、アーク５１２は、μYoung（Ｘi）＜０．５または情報利得を最大にするような他の値というテストであり得る。アーク５３２および５３４については、それぞれのファジー集合は、それぞれ、Normal（正常）およびFeverish（熱っぽい）であり得る。たとえば、葉ノード５２０でのクラスの０．２０メンバーシップおよび葉ノード５４０でのクラスの０．８０メンバーシップによる結果は、３６ｍｇの薬品Ｘを使用することを示唆するかもしれない。
【００１３】
ＦＩＤ３での不利益の１つは、トレーニングデータのすべてについての属性の各々においてメンバーシップ関数が、ユーザによって前もって指定されなければならないということである。しかしながら、多数の属性または大きさを備えるデータに対して、メンバーシップ関数を決定することは典型的には困難な作業であり、専門家が集中的に関わる必要がある。さらに、ファジー集合自体は前もって知られてさえおらず、さらなる調査を必要とするかもしれない。
【００１４】
したがって、柔軟な態様で実世界のまたは「ファジーな」データを扱うことのできるデータ解析技術が必要とされる。また、データのグループ化またはファジーメンバーシップ関数などの他のアプリオリな情報が、前もって供給される必要のない技術も必要とされる。
【００１５】
【発明の概要】
これらのおよび他の必要性は、デシジョンツリーが生成される間データが動的にクラスタ化される、この発明によって解決される。ある実施例では、データは、ユーザが集合を予め定義したりまたは前もってメンバーシップ関数を計算することを必要とせずに、メンバーシップ関数をオンザフライで生成するファジークラスタリング解析を用いてクラスタ化される。
【００１６】
したがって、この発明のある局面は、いくつかの特徴量によって特徴付けられるデータのためのデシジョンツリーを生成するための方法およびソフトウェアに関し、いくつかのファジークラスタ解析を特徴量の各々に沿って行なって、１つ以上のファジーなクラスタの対応する集合および最大分割係数（partition coefficient）を計算する。最大分割係数に対応する特徴量が選択され、デシジョンツリーが、１つ以上のファジーなクラスタの対応する集合に基づいて構築される。ファジークラスタ解析を行なうことにより、実世界のデータがよりよく説明される。
【００１７】
この発明の別の局面は、いくつかの特徴量によって特徴付けられるデータのためのデシジョンツリーを生成するための方法およびソフトウェアに関し、いくつかのクラスタ解析を特徴量の各々に沿って行なって、最大クラスタ有効性測度を計算する。最大クラスタ有効性測度に対応する特徴量の１つが選択され、データは、選択された特徴量に基づいて１つ以上のグループに細分される。そして、デシジョンツリーが、１つ以上のグループに基づいて構築される。クラスタ解析を行なって最大クラスタ有効性を計算することにより、デシジョンツリーは、最適なクラスタ可分性に対応することができる。
【００１８】
この発明のさらに別の局面は、いくつかの特徴量（たとえば大きさまたは属性）によって特徴付けられるデータであってそのうちの１つが選択されるデータのためのデシジョンツリーを生成するための方法およびソフトウェアに属する。選択された特徴量に沿ったクラスタ解析を行なってデータを１つ以上のクラスタにグループ化し、デシジョンツリーが１つ以上のクラスタに基づいて構築される。クラスタ解析を行なうことにより、データがグループ化され得るさまざまな可能な集合を決定するために、データは予め分析される必要がない。
【００１９】
この発明のさらに他の目的および利点は、この発明を実施することが企図された最良の態様の例示のためにのみ、以下の詳細な説明から容易に明らかとなるであろう。理解されるであろうように、この発明は、他のおよび異なった実施例を可能とし、そのいくつかの詳細が、この発明から全く逸脱することなしに、さまざまな明白な点において変形を可能とする。したがって、図面および説明は、制限的でなく本質的に例示的なものと見なされるべきである。
【００２０】
この発明は、添付の図面の図において制限的なものでなく例として示され、同様の参照番号が同様の要素を参照する。
【００２１】
【好ましい実施例の説明】
デシジョンツリーを生成するための方法および装置が記載される。以下の記載において、説明の目的のために、この発明を完全に理解するために多くの具体的な詳細が述べられる。しかしながら、当業者には、この発明がこれらの具体的な詳細なしに実施され得ることが明らかとなるであろう。他の場合には、この発明を不必要にわかりにくくすることを回避するために、周知の構造および装置がブロック図で示される。
【００２２】
ハードウェア概要
図１は、この発明の実施例が実現され得るコンピュータシステム１００を示すブロック図である。コンピュータシステム１００は、情報をやり取りするためのバス１０２または他の通信メカニズムと、バス１０２に結合され情報を処理するためのプロセッサ１０４とを含む。コンピュータシステム１００は、バス１０２に結合され、プロセッサ１０４によって実行されるべき命令および情報を記憶するための、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置などの主メモリ１０６も含む。主メモリ１０６は、プロセッサ１０４によって実行されるべき命令の実行中、一時変数または他の中間情報を記憶するために使用されてもよい。コンピュータシステム１００は、バス１０２に結合され、プロセッサ１０４のための命令および静的情報を記憶するための、リードオンリメモリ（ＲＯＭ）１０８または他の静的記憶装置をさらに含む。磁気ディスクまたは光ディスクなどの記憶装置１１０が設けられ、バス１０２に結合され、情報および命令を記憶する。
【００２３】
コンピュータシステム１００は、情報をコンピュータユーザに表示するための陰極線管（ＣＲＴ）などのディスプレイ１１２にバス１０２を介して結合されてもよい。アルファベット数字および他のキーを含む入力装置１１４がバス１０２に結合され、プロセッサ１０４に情報およびコマンド選択を交信する。ユーザ入力装置の別のタイプは、プロセッサ１０４に方向情報およびコマンド選択を交信しかつディスプレイ１１２上のカーソルの動きを制御するための、マウス、トラックボール、カーソル方向キーなどのカーソル制御１１６である。この入力装置は、典型的には、装置が平面における位置を指定することを可能にする、第１の軸（たとえばｘ）および第２の軸（たとえばｙ）の２つの軸における２自由度を有する。
【００２４】
この発明は、デシジョンツリーを生成するためのコンピュータシステム１００の使用に関する。この発明のある実施例に従えば、プロセッサ１０４が主メモリ１０６に含まれる１つ以上の命令の１つ以上のシーケンスを実行することに応答して、デシジョンツリーの生成がコンピュータシステム１００によって与えられる。そのような命令は、記憶装置１１０などの別のコンピュータ読出可能媒体から主メモリ１０６に読出されてもよい。主メモリ１０６に含まれる命令のシーケンスの実行により、プロセッサ１０４は、ここに記載されるプロセスステップを行なうようになる。マルチプロセッシング構成における１つ以上のプロセッサを採用して、主メモリ１０６に含まれる命令のシーケンスを実行してもよい。代替の実施例では、この発明を実現するためにソフトウェア命令と組合されまたはその代わりにハードワイヤード回路構成が使用されてもよい。したがって、この発明の実施例は、ハードウェア回路構成およびソフトウェアのいかなる特定の組合せにも限られるものでない。
【００２５】
ここに使用される「コンピュータ読出可能媒体」という言葉は、命令をプロセッサ１０４に与えて実行させることに関与する任意の媒体のことをいう。そのような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むがこれに限られるものでない多くの形をとり得る。不揮発性媒体は、たとえば、記憶装置１１０などの光ディスクまたは磁気ディスクを含む。揮発性媒体は、主メモリ１０６などのダイナミックメモリを含む。伝送媒体は、バス１０２を含むワイヤを含む、同軸ケーブル、導線および光ファイバを含む。伝送媒体は、無線周波数（ＲＦ）および赤外（ＩＲ）データ通信の際に生成されるものなどの、音波または光波の形をとってもよい。コンピュータ読出可能媒体のよくある形は、たとえば、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、または任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤ、任意の他の光学媒体、パンチカード、紙テープ、穴のパターンを備える任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭおよびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップもしくはカートリッジ、以下に記載されるような搬送波、またはコンピュータが読出すことのできる任意の他の媒体を含む。
【００２６】
コンピュータ読出可能媒体の種々の形式のものが、１つ以上の命令の１つ以上のシーケンスをプロセッサ１０４に運び実行させるのに必要とされてもよい。たとえば、命令は最初に遠隔コンピュータの磁気ディスク上に担持されていてもよい。遠隔コンピュータは、命令をそのダイナミックメモリにロードし、モデムを用いて電話線を介して命令を送信することができる。コンピュータシステム１００にローカルなモデムは、電話線によりデータを受信し、赤外トランスミッタを用いてデータを赤外信号に変換することができる。バス１０２に結合される赤外検出器が、赤外信号で運ばれるデータを受信し、データをバス１０２に与えることができる。バス１０２はデータを主メモリ１０６に運び、プロセッサ１０４はそこから命令を取出して実行する。主メモリ１０６によって受取られた命令は、場合により、プロセッサ１０４による実行の前または後のいずれかで記憶装置１１０に記憶されてもよい。
【００２７】
コンピュータシステム１００は、バス１０２に結合される通信インターフェイス１１８も含む。通信インターフェイス１１８は、ローカルネットワーク１２２に接続されるネットワークリンク１２０に結合する双方向データ通信を与える。たとえば、通信インターフェイス１１８は、統合サービスデジタル網（ＩＳＤＮ）カードまたはモデムであって、データ通信接続を電話線の対応する型に与えてもよい。別の例として、通信インターフェイス１１８は、ローカルエリアネットワーク（ＬＡＮ）カードであって、データ通信接続を互換性のあるＬＡＮに与えてもよい。ワイヤレスリンクが実現されてもよい。いずれのそのような実現化例でも、通信インターフェイス１１８は、さまざまなタイプの情報を表わすデジタルデータストリームを運ぶ電気信号、電磁信号または光信号を送受信する。
【００２８】
ネットワークリンク１２０は、典型的には、１つ以上のネットワークを介して他のデータ装置にデータ通信を与える。たとえば、ネットワークリンク１２０は、ローカルネットワーク１２２を介してホストコンピュータ１２４に、またはインターネットサービスプロバイダ（ＩＳＰ）１２６によって作動されるデータ機器に接続を与えてもよい。ＩＳＰ１２６は、現在普通「インターネット」１２８と呼ばれているワールドワイドなパケットデータ通信ネットワークを介してデータ通信サービスを提供する。ローカルネットワーク１２２およびインターネット１２８はどちらも、デジタルデータストリームを運ぶ電気信号、電磁信号または光信号を用いる。コンピュータシステム１００におよびそれからデジタルデータを運ぶ、さまざまなネットワークを介する信号ならびにネットワークリンク１２０上のおよび通信インターフェイス１１８を介する信号は、情報を転送する搬送波の例示の形である。
【００２９】
コンピュータシステム１００は、ネットワーク、ネットワークリンク１２０および通信インターフェイス１１８を介してプログラムコードを含むデータを受取りメッセージを送ることができる。インターネットの例では、サーバ１３０が、インターネット１２８、ＩＳＰ１２６、ローカルネットワーク１２２および通信インターフェイス１１８を介してアプリケーションプログラムのための要求されたコードを伝送し得る。この発明に従えば、あるそのようなダウンロードされたアプリケーションは、ここに記載されるデシジョンツリーの生成に供する。受信されたコードは、受信されたときにプロセッサ１０４によって実行されてもよく、および／または記憶装置１１０もしくは他の不揮発性記憶装置に記憶されて後に実行されてもよい。このように、コンピュータシステム１００は搬送波の形でアプリケーションコードを獲得し得る。
【００３０】
ファジークラスタリング
この発明のある局面は、データセット自体が、合理的なメンバーシップ関数を得るために使用可能である情報を含むという認識から派生する。したがって、デシジョンツリーおよびメンバーシップ関数の両方が、データセットから自動的に抽出可能である。この発明のある実施例では、ファジーｃ−平均（ＦＣＭ）クラスタリング法を用いて、データからメンバーシップ関数を抽出するが、ファジークラスタリングの他の形がこの発明のさまざまな実施例において採用され得る。
【００３１】
ＦＣＭモデルは、所与のデータセットＸ＝｛ｘi｝、大きさｌ∈１．．ｐでｉ∈１．．ｎ、およびファジネスパラメータｍ∈（１，∞）に対する目的関数ＪFCMの最小化として定義され得る。
【００３２】
【数１】
0004817502.tif 000002
【００３３】
式中、Ｕ＝｛ｕik｝、Ｖ＝｛ｖi｝、ｕik∈［０，１］は、ｃ個のクラスタのｌ番目クラスタにおけるｘkのメンバーシップであり、ｉ∈１．．ｃ、ｋ∈１．．ｎ、すべてのｋ∈１．．ｎに対してΣｕik＝１であって、ｖiはｌ番目のクラスタの中心、ただし、ｉ∈１．．ｃであり、ｍは典型的には２である。ある実現化例では、ＦＣＭモデルは、ＪFCMの必要な極値による交互最適化（alternating optimization、ＡＯ）により最適化されるが、他の最適化技術を採用してもよい。
【００３４】
ＦＣＭのためのＡＯ技術では、クラスタ中心のその後の推定値ＶおよびＶ*が
【００３５】
【数２】
0004817502.tif 000003
【００３６】
ただしｖthはしきい値パラメータである、を満たすまで、メンバシップ関数ｕikおよびクラスタ中心ｖiは、以下のように交互に更新される：
【００３７】
【数３】
0004817502.tif 000004
【００３８】
および
【００３９】
【数４】
0004817502.tif 000005
【００４０】
連続なメンバーシップ関数μi(l)：ＩＲ→［０，１］，ｉ∈１．．ｃ，ｌ∈１．．ｐは、ｕikメンバーシップの射影およびその後の内挿または近似により、または単にクラスタ中心ｖiの射影ｖi(l)を式（４）に挿入することにより、求めることができる。
【００４１】
【数５】
0004817502.tif 000006
【００４２】
デシジョンツリーの生成
この発明のある実施例に従えば、メンバーシップ関数の抽出は、デシジョンツリーを誘導により生成しながらクラスタ化することにより得られる。動作の開始において、デシジョンツリーは、データセットと関連付けられるルートノードで始まる。データと関連付けられる各ノードＮについて（たとえばルートノードから始まる）、図２に示されるステップが行なわれる。説明の目的のために、この発明のこの実施例の動作は、以下により詳細に説明するように、パラメータ、ｍ＝２、ｃ＝４、ｖth＝１０-10および領域境界しきい値ｒth＝０．３を用いて図３に示す例示のデータセット３００に対して例示される。さらに、作業例の結果は、図４のデシジョンツリー４００として表わされる。
【００４３】
ステップ２００において、残りの大きさｐの数が調べられる。ゼロ個の大きさが残っていれば、さらに細分化すべきものはなく、現在のノードが葉ノードとされる。作業例における点データは連続であるので、「大きさ」という言葉がこの議論において用いられるが、この発明はそのように制限されるものでなく、記載される方策は、名目的な属性データおよび連続な大きさデータであり得るデータの特徴により一般的に適用可能である。大きさデータは、典型的には、長さ、時間、電荷、温度、質量、エネルギなどの連続なまたは量子化された測度のことをいう。名目的属性データは、典型的には、たとえば、男性／女性などの有限集合から選択された１つの要素のことをいう。
【００４４】
図３を参照し、データセット３００は、４つの明らかに目に見えるクラスタ、すなわち、左上角の６つの点からなるクラスタ３１０と、左下角の９個の点からなるクラスタ３２０と、中央の６個の点からなるクラスタ３３０と、右上角の４つの点からなるクラスタ３４０とを形成する２９個の２大きさの点を含む。目視検査により、クラスタは、垂直線ｘ＝２５およびｘ＝４５で、それぞれ、左側のクラスタ対と、中央および右の２個の単一クラスタとに分けることができる。クラスタ３１０および３２０を含む左側のクラスタ対は、水平線ｙ＝３０によってさらに分けることができる。作業例では、２つの残りの大きさｘおよびｙがあり、したがって実行はステップ２０２に進む。
【００４５】
ステップ２０２において、各大きさ（たとえばｘおよびｙ）におけるデータはクラスタ化され、クラスタリングの妥当性を量子化する分割係数が、クラスタ有効性、またはどれほどよくクラスタが分けられるかについての測度として、各大きさごとに計算される。ある実現化例では、ファジーｃ−平均クラスタリングが採用可能であるが、ファジーｋ平均などのファジークラスタリングの他の形が採用されてもよい。ファジーｃ−平均クラスタリング法においては、目的関数ＪFCMが、所与の数のクラスタｃに対して、最小化される。したがって、ファジークラスタリングが、分割Ｕc(l)を導くいくつかの異なったクラスタリング数（たとえば、最大ｃ＝４クラスタまで）について行なわれ、分割係数ＰＣ（Ｕc(l)）が計算される。
【００４６】
ある実施例において、ＰＣ（Ｕc(l)）が以下のようにｃ＞１に対して計算される。
【００４７】
【数６】
0004817502.tif 000007
【００４８】
ある状況下では、データ要素が、いかなるクラスタ構造も所有しないかもしれない。したがって、最適のクラスタリングが単一のクラスタリングであるかどうかを決定するためにデータをテストする必要がある。ある実施例では、データの領域境界がテストされ、大きさ（ξmax−ξmin）でのクラスタにおけるデータの領域が、全体のデータセットの領域（ｘmax−ｘmin）の予め定められた一部内にあるならば、データは、単一クラスタを構成するものと見なされる。より具体的には、以下のテストを行なうことができる。
【００４９】
【数７】
0004817502.tif 000008
【００５０】
式中、ｒthは、設定可能なしきい値パラメータ（たとえば０．３）である。データが単一クラスタ内にあるものと見なされるべきならば、分割係数は、複数のクラスタの分割係数よりも大きいものとなる１．０に設定される。
【００５１】
作業例では、最大分割係数０．９４である大きさｘのクラスタリングは３つのクラスタを有し、最大分割係数０．９３である大きさｙのクラスタリングも３つのクラスタを有する。
【００５２】
ステップ２０４で、最良の分割係数となる大きさｌ*が選択される。最大ＰＣ（Ｕc*(l*)）＝ｍａｘc,l｛ＰＣ（Ｕc(l)）｝に対して最良の分割が得られる。作業例では、大きさｘの分割係数（０．９４）が大きさｙの分割係数（０．９３）よりも大きいために大きさｘが選ばれる。
【００５３】
ステップ２０６で、次にデータは選択された大きさｌ*に沿ってｃ*個のクラスタに分割される。これらのサブセットは、現時のノードＮにラベルｘ(l*)＜ｂ1(l*)，ｂ1(l*)＜ｘ(l*)＜ｂ2(l*)，．．．，ｂc*-2(l*)＜ｘ(l*)＜ｂc*-1(l*)，ｂc*-1(l*)＜ｘ(l*)を持つｃ*個のアークを作成することにより、デシジョンツリーに挿入される（ステップ２０８）。境界ｂi(l*)，ｉ∈１．．ｃ*−１は、（４）で定義された隣接するメンバーシップ関数が等しくなるように決定されるかまたは、一般性を失うことなくクラスタ中心がソートされると仮定すると、以下のとおりである。
【００５４】
【数８】
0004817502.tif 000009
【００５５】
図４を参照する作業例では、大きさｘが選択された。したがってデシジョンツリーのルートの分岐ノード４１０は、ノード４１０で大きさｘがテストされることを示すようにラベル付けされる。ノード４１０からそれぞれのノード４２０、４３０および４４０への各アーク４１２、４１３および４１４は、それぞれ境界（８．００，２２．３１）、（２２．３１，４１．１９）および（４１．１９，５３．００）でラベル付けされる。
【００５６】
図２に戻って、ステップ２１０で、データは選択された大きさｌ*を除いて各クラスタに射影される。言い換えると、各データｘiは、ｂ0(l*)＝−∞かつｂc*(l*)＝＋∞としてｂi-1(l*)＜ｘ(l*)＜ｂi(l*) の条件ラベルを満たすデータセットＸのｐ−１の大きさの射影のサブセットを含む。大きさｘはステップ２０４で選択された大きさであるため、作業例ではｘ座標はデータから除去され、ｙ座標のみを残す。
【００５７】
ステップ２１２で、大きさまたはデータが残らなくなるまで、各クラスタごとにステップ２００−２１０のプロセスが再帰的に繰返される。図４を参照する作業例では、このプロセスの再帰的適用例は、それぞれクラスタ３２０および３１０に対応する２つの付加的な葉ノード４５０および４６０を生じる。分岐ノード４２０からそれぞれの葉ノード４５０および４６０へのアーク４２５および４２６は、それぞれ（８．００，３１．３２）および（３１．３２，５８．００）とラベル付けされる。しかしながら、分岐ノード４３０および４４０に対応する他のサブセットに対する再帰呼出しは、不等式（６）のテストが当てはまったため、クラスタへのさらなる分割は生じない。むしろ、単一のアーク４３７が分岐ノード４３０から葉ノード４７０に出たり、単一のアーク４４８が分岐ノード４４０から葉ノード４８０に出たりする。
【００５８】
したがって、例示的なデータセット３００についてのこの実施例の結果は、４つの葉ノード４５０、４６０、４７０および４８０を備えるデジジョンツリーであり、その各々が、目視検査で明らかであったデータセット３００中の４つのクラスタ３２０、３１０、３３０および３４０にそれぞれ対応する。このように、対応するクリスプ分割はさらに、視覚的に得られた分割と全く同じである。すなわち、点ｘk∈Ｘは同じ（クリスプな）クラスに属する。しかしながら、境界線はクラスタリングの結果から自動的に決定されたため、境界線ｘ＝２２．３１、ｘ＝４１．１９およびｙ＝３１．３２は、目視検査によって生じたものとはわずかに異なっている。さらに、自動的に生成された境界線は最適なクラスタ分離性を生じるように設定される。
【００５９】
したがって、デシジョンツリーと（クリスプなまたはファジーな）クラスタとの両者を抽出する統一された方策を用いるデシジョンツリークラスタリング手順が説明された。デシジョンツリーは単一の大きさまたは特徴のその後のクラスタリングによって構築され、好ましい分離の選択はクラスタ有効性に基づいている。１つの実施例では，クラスタリングはファジーｃ平均（ＦＣＭ）モデルおよび分割係数（ＰＣ）を用いて選択された分離を決定する。クラスタ有効性測度として分割係数を用いることにより、クラスタ分離性に対して優れたまたは最適な結果をもたらす。しかしながら、他の有効性測度を選択することによって他の最適性条件を組入れることができ、ＦＣＭ以外のクラスタリングモデルを用いてデシジョンツリーを生成することができる。たとえば、ＦＣＭの代わりにハードｃ平均（ＨＣＭ）モデルを用いることにより、クリスプデシジョンツリーがもたらされる。
【００６０】
この発明は現在最も実践的かつ好ましい実施例と考えられるものと関連して説明されたが、この発明が開示された実施例に限定されるものではなく、これに対して、添付の請求項の精神および範囲内に含まれるさまざまな修正および同等の構成を含むことを意図することを理解されたい。
【図面の簡単な説明】
【図１】  この発明の実施例が実現可能であるコンピュータシステムの図である。
【図２】  この発明のある実施例の動作を例示する流れ図である。
【図３】  この発明のある実施例の動作を例示するために使用される例示のデータセットのグラフの図である。
【図４】  この発明のある実施例によって発生される例示のデシジョンツリーの概略図である。
【図５】  デシジョンツリーの概略図である。
【図１】
0004817502.tif 000010
【図２】
0004817502.tif 000011
【図３】
0004817502.tif 000012
【図４】
0004817502.tif 000013
【図５】
0004817502.tif 000014