(57)【特許請求の範囲】
【請求項１】
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得する取得部と、
前記取得部により取得された前記データに含まれる複数のレコードを、分類後のグループ間の変数値の共有の程度を示す共有値に基づき、複数のグループに分類する分類部とを有する
ことを特徴とするデータ分類装置。
【請求項２】
前記分類部は、前記複数のグループの１つである第１のグループに属する第１のレコードに含まれる変数値の前記第１のグループにおける同一変数値の数に基づき算出した、前記第１のレコードの前記第１のグループにおける出現確率が多くなり、かつ、前記共有値が少なくなるように、前記複数のレコードを前記複数のグループに分類する
ことを特徴とする請求項1に記載のデータ分類装置。
【請求項３】
前記分類部は、前記複数のレコードの分類において、前記第１のレコードの各々の出現確率の逆数の合計を算出し、さらに、前記第１のグループとは異なる第２のグループに属する同一変数値の数と前記第２のグループの各々に属する相互に異なる変数値の総数とに基づき算出した前記共有値を、前記第２のグループの各々に属する変数値の各々について算出し、前記複数のレコードの各々の出現確率の逆数の合計と前記変数値の各々の共有値の合計との総合計が少なくなるように、前記複数のレコードを前記複数のグループに分類する
ことを特徴とする請求項2に記載のデータ分類装置。
【請求項４】
前記分類部は、前記複数のレコードの分類において、前記複数のレコードの各々の出現確率の逆数の対数の第1の合計を算出し、さらに、前記変数値の各々の共有値の対数の第2の合計を算出し、前記第1の合計と前記第2の合計との総合計が少なくなるように、前記複数のレコードを前記複数のグループに分類する
ことを特徴とする請求項3に記載のデータ分類装置。
【請求項５】
前記分類部は、
前記複数のレコードの分類において、前記取得部により取得された前記データに含まれる複数のレコードの中から、相互に共有する変数値が少なくなるようにNa(Naは2以上の整数)個のレコードをランダムに選択してNa個のグループを生成し、前記生成したグループに属するレコードが当該グループに出現する出現確率が多くなるように、前記複数のレコードにおいて前記Na個のレコード以外のレコードを、前記Na個のグループに配置したグループを生成する生成部と、
前記複数のレコードの分類において、前記Na個のグループに属するレコードの中から、レコードを異なるグループに配置した場合に、前記第1の合計と前記第2の合計との総合計の減少量が最大になる1以上のレコードを選択し、選択した前記1以上のレコードを、選択した前記1以上のレコードが属する第３のグループから、前記第1の合計と前記第2の合計との総合計の減少量が最大になる第４のグループに配置する配置部とを有する
ことを特徴とする請求項4に記載のデータ分類装置。
【請求項６】
前記配置部は、
前記1以上のレコードの選択において、相互に変数値を共有しないレコードを、前記出
現確率の逆数の対数が高い順に選択し、選択した第３のレコードを前記Na個のグループ以
外の他のグループに追加する第1の追加処理を実行し、さらに、前記データに含まれるレ
コードの中から、前記第３のレコードに含まれる複数の変数値の何れか1つの変数値を含む第４のレコードを選択し、選択した前記第４のレコードを前記他のグループに追加する第2の追加処理を実行し、
前記他のグループにレコードを追加する度に、前記減少量を概算し、最大の減算値を概算した場合の前記他のグループを前記1以上のレコードとして選択する
ことを特徴とする請求項5に記載のデータ分類装置。
【請求項７】
前記共有値は、同一値の変数値を有するグループ数に基づき算出される
請求項１記載のデータ分類装置。
【請求項８】
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得し、
取得された前記データに含まれる複数のレコードを複数のグループに分類する処理において、分類後のグループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類する
処理を実行させることを特徴とするデータ分類プログラム。
【請求項９】
データ分類装置におけるデータ分類方法であって、
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得し、
取得された前記データに含まれる複数のレコードを複数のグループに分類する処理において、分類後のグループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類する
ことを特徴とするデータ分類方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分類装置、データ分類プログラム、および、データ分類方法に関する。
【背景技術】
【０００２】
いわゆる離散データを各集団（グループ）に分類(集団化やクラスタリングとも呼ばれる)する方法が様々提案されている。離散データは、例えば、識別子(ID)付きPOS(Point Of Sale system)のレコードや、WEB(World Wide Web)アクセスログのレコードなどを含む。
【０００３】
離散データの分析者は、人の意図や行動を推測する目的で、分類された離散データ(換言すれば、各集団のレコード)を分析する。例えば、かかる分析者は、共通の消費者ニーズに基づく購買行動を推測する目的や、共通の興味に基づくWEB閲覧行動を推測する目的で、分類された離散データを分析する。
【０００４】
離散データの分類の一方法として、集団内におけるレコードの発生確率(出現確率とも呼ばれる)と集団数の定数倍とに基づいて算出された集団の評価値を参照して、離散データを分類する方法がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｄａｎｉｅｌ  Ｂａｒｂａｒa、  Ｙｉ  Ｌｉ、  Ｊｕｌｉａ  Ｃｏｕｔｏ．  ＣＯＯＬＣＡＴ：  ａｎ  ｅｎｔｒｏｐｙ−ｂａｓｅｄ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃａｔｅｇｏｒｉｃａｌ  ｃｌｕｓｔｅｒｉｎｇ．  ＣＩＫＭ  ２００２：  ５８２−５８９
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、提案されている離散データの分類化方法では、前記したレコードの発生確率と集団数の定数倍と基づいて評価値を算出しているので、分析者の目的を容易に達成できる集団（グループ）に離散データを分類することが困難であった。
【０００７】
本実施の形態の一つの側面では、離散データを目的に応じたグループに分類することを目的とする。
【課題を解決するための手段】
【０００８】
一つの態様では、複数の種類の変数値を其々が含む複数のレコードを含むデータを取得する取得部と、前記取得部により取得された前記データに含まれる複数のレコードを複数のグループに分類する分類部とを有し、前記分類部は、グループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類することを特徴とするデータ分類装置である。
【発明の効果】
【０００９】
一つの側面によれば、離散データを目的に応じたグループに分類することができる。
【図面の簡単な説明】
【００１０】
【図１】図1は、離散データに含まれるレコードを説明する図である。
【図２】図2は、離散データの一例と、一方法により離散データを分類した場合の集団内のレコードなどを示す集団構成テーブルの一例である。
【図３】図3は、離散データの分類の一方法の処理の流れを説明するフロー図である。
【図４】図4は、初期集団を示す集団構成テーブルを示す図である。
【図５】図5は、再配置後の集団構成テーブルを示す第1の図である。
【図６】図6は、再配置後の集団構成テーブルを示す第2の図である。
【図７】図7は、一方法の課題を説明する第1の図である。
【図８】図8は、一方法の課題を説明する第2の図である。
【図９】図9は、本実施の形態のデータ分類装置DVのハードウェアブロック図である。
【図１０】図10は、図9のデータ分類装置DVのソフトウェアブロック図である。
【図１１】図11は、本実施の形態における離散データの分類処理の流れを説明するフロー図である。
【図１２】図12は、図11のステップS3の処理の流れを説明するフロー図である。
【図１３】図13は、実施の形態における具体例を説明する第1の図である。
【図１４】図14は、実施の形態における具体例を説明する第2の図である。
【図１５】図15は、実施の形態における具体例を説明する第3の図である。
【図１６】図16は、実施の形態における具体例を説明する第4の図である。
【図１７】図17は、実施の形態における具体例を説明する第5の図である。
【図１８】図18は、実施の形態における具体例を説明する第6の図である。
【図１９】図19は、実施の形態における具体例を説明する第7の図である。
【図２０】図20は、実施の形態における具体例を説明する第8の図である。
【図２１】図21は、実施の形態における具体例を説明する第9の図である。
【図２２】図22は、実施の形態における具体例を説明する第10の図である。
【図２３】図23は、実施の形態における具体例を説明する第11の図である。
【図２４】図24は、実施の形態における具体例を説明する第12の図である。
【図２５】図25は、実施の形態における具体例を説明する第13の図である。
【図２６】図26は、実施の形態における具体例を説明する第14の図である。
【図２７】図27は、実施の形態における具体例を説明する第15の図である。
【図２８】図28は、実施の形態における具体例を説明する第16の図である。
【図２９】図29は、実施の形態における具体例を説明する第17の図である。
【図３０】図30は、実施の形態における具体例を説明する第18の図である。
【発明を実施するための形態】
【００１１】
[離散データに含まれるレコード]
図1は、離散データに含まれるレコードを説明する図である。以下の図において、"…"は、省略を示す。
【００１２】
図1(A)は、ID付きPOSのレコードを含む離散データLSD1を示す図である。ID付きPOSのレコードは、2種類の変数値を含む。1種類目の変数値は、顧客を一意に識別する顧客IDである。2種類目の変数値は、商品を一意に識別する商品IDである。図1(A)では、"{顧客ID,商品ID}"で1個のレコードを示す。そして、大括弧間"{},{}"のカンマ(",")で各レコードを区切る。図1(A)では、例えば、{顧客1,商品1}のレコードは、顧客IDとして"顧客1"、商品IDとして"商品1"を含む。
【００１３】
図1(B)は、WEBアクセスログのレコードを含む離散データLSD2を示す図である。WEBアクセスログのレコードは、3種類の変数値を含む。1種類目の変数値は、アクセス先のサーバのIPアドレスである。2種類目の変数値は、このサーバにアクセスした利用者を一意に識別するユーザIDである。3種類目の変数値は、アクセスされたURL(Uniform Resource Locator)である。
【００１４】
図1(B)では、{IPアドレス,ユーザID,URL}で1個のレコードを示す。そして、大括弧間"{},{}"のカンマ(",")で各レコードを区切る。図1(B)では、例えば、{IP1, user1, URL1}のレコードは、IPアドレスとして"IP1"、ユーザIDとして"user1"、URLとして"URL1"を含む。
【００１５】
図1(C)は、ネットワークトラフィックログ(以下、トラフィックログと適宜記す)のレコードを含む離散データLSD3を示す図である。トラフィックログは、装置間でTCP(Transmission Control Protocol)/IP(Internet Protocol)プロトコルにより通信されている場合において、この装置間で送受信されている通信パケットに含まれる送信先IPアドレス、送信先ポート番号を含む。
【００１６】
トラフィックログのレコードは、2種類の変数値を含む。1種類目の変数値は、送信先IPアドレスである。2種類目の変数値は、送信先ポート番号である。
【００１７】
図1(C)では、{送信先IPアドレス,送信先ポート番号}で1個のレコードを示す。そして、大括弧間"{},{}"のカンマ(",")で各レコードを区切る。図1(C)では、例えば、{IP1, 80}のレコードは、IPアドレスとして"IP1"、ポート番号として"80"を含む。
【００１８】
離散データに含まれるレコードの数は、例えば、数十万〜数千万件である。レコードに含まれる変数値の種類(個数とも呼ぶ)は、例えば、2〜10種類(個)である。各変数の取り得る値の幅は、例えば、数千〜数万である。
【００１９】
[離散データの分類の一方法]
離散データの分類の一方法(以下、一方法と適宜記す)について説明する。一方法は、離散データに含まれる複数のレコードを分類する場合、集団内のレコードの変数値のばらつきが少なくなるように、離散データを分類する。なお、離散データに含まれる複数のレコードを分類することは、離散データを分類することと同義である。
【００２０】
換言すれば、一方法は、離散データを分類する場合、集団内の変数値の中で希な変数値が少なくなるように、離散データを分類する。図2〜図6を参照して、一方法について説明する。
【００２１】
(集団構成テーブル)
図2は、離散データの一例と、一方法により離散データを分類した場合の集団内のレコードなどを示す集団構成テーブルの一例である。
【００２２】
離散データLSD4は、図1(C)で説明したトラフィックログのレコードを含む離散データの一例である。以下の説明では、説明を簡略化するために、分類対象の離散データLSD4に含まれるレコードの個数を24個とする。
【００２３】
集団構成テーブルT110は、分類されたレコードの構成(換言すれば、レコードの集団構成)を示すテーブルである。集団構成テーブルT110は、集団欄と、集団構成欄と、集団内情報量欄とを有する。集団欄は、1個以上のレコードを含む集団を一意に識別する集団識別子を記憶する。集団識別子は、例えば"#k"(小文字kは1以上の整数)で示される。
【００２４】
集団構成欄は、集団識別子で識別される集団に属するレコードを記憶する欄である。なお、集団に属するレコードは、集団内のレコード、集団に含まれるレコードと同義である。集団内情報量欄は、集団構成欄に記憶されているレコードの集団内情報量を記憶する。
【００２５】
集団内情報量は、集団内の各レコードの出現確率(発生確率とも呼ぶ)の逆数の対数である。なお、対数は、例えば、10を底とする常用対数である。レコードの出現確率は、このレコードが属する集団に属するレコードに含まれる変数値の各々のこの集団における出現確率の積である。変数値の各々の出現確率は、ある集団(集団Xと記す)に属する1個以上のレコードに含まれる同一変数値の合計を、集団Xに属するレコードの合計で除算した値である。
【００２６】
図2において、第1の集団#1に属するレコード{IP1,80}の集団内情報量を算出する。第1の集団#1に属するレコード{IP1,80}の同一変数値IP1の合計は、2個である(レコード{IP1,80}、{IP1,8080}参照)。また、第1の集団#1に属するレコード{IP1,80}の同一変数値80の合計は、5個である(レコード{IP1,80},{IP2,80},{IP3,80},{IP4,80},{IP5,80}参照)。そして、第1の集団#1に属するレコードの合計は10個である。
【００２７】
従って、同一変数値IP1の出現確率は、(2/10)である。そして、同一変数値80の出現確率は、(5/10)である。従って、第1の集団#1におけるレコード{IP1,80}の集団内情報量は、-log{(2/10)*(5/10)}(図2の一点鎖線枠内参照)である。なお、集団内情報量における対数(log)内の"/"は除算を示し、"*"は乗算を示す。なお、レコードの出現確率は、値の同時確率とも呼ばれる。
【００２８】
図2において、あるレコード(レコードXと記す)の集団内情報量は、集団構成欄においてレコードXが記憶されている行(平行位置)と同じ行に記憶されている集団内情報量(集団内情報量Xと記す)である。例えば、レコードXが第1の集団#1におけるレコード{IP1,80}の場合(図2の点線枠内参照)、レコードXの集団内情報量Xは第1の集団#1における-log{(2/10)*(5/10)}(図2の一点鎖線枠内参照)である。
【００２９】
第k(小文字kは1以上の整数)の集団#kに属する各レコードの集団内情報量の合計を、この各レコードを記憶するセルの下側に示す。例えば、第1の集団#1に属する各レコードの集団内情報量の合計は、"10.0"である。なぜなら、第1の集団#1に属する各レコードの総数は、10個である。また、第1の集団#1に属する各レコードの集団内情報量は"-log{(2/10)*(5/10)}"、すなわち("1")である。従って、第1の集団#1に属する各レコードの集団内情報量の合計は、"10.0"である(図2の破線枠内参照)。
【００３０】
集団構成テーブルT110において、下から2番目の行と集団内情報量欄とが交わるセルは、各集団における各レコードの集団内情報量の総合計を記憶する。例えば、第1の集団#1〜第3の集団#3における各レコードの集団内情報量の合計は、それぞれ"10.0"、"4.7"、"7.2"である。従って、前記した総合計は、"21.9"である。
【００３１】
集団構成テーブルT110において、下から1番目の行と集団内情報量欄とが交わるセルは、集団構成の評価値を記憶する。一方法における集団構成の評価値は、集団内情報量の総合計と、集団数の定数倍との合計である。ここで、定数倍を1とする。集団構成テーブルT110の例では、3個の集団(第1の集団#1〜第3の集団#3)に分けられているので、集団数は3である。そのため、集団数の定数倍は3である。従って、集団構成の評価値は、24.9(21.9+3.0)である。
【００３２】
(離散データの分類の一方法のフロー図)
図3は、離散データの分類の一方法の処理の流れを説明するフロー図である。なお、フロー図において、"Ss"(小文字sは1以上の整数)は、ステップSsを示す。
【００３３】
ステップS101:一方法は、初期集団を生成する。具体的には、一方法は、分類処理の対象である離散データに含まれるレコードの中から、相互に変数値の共有が少ないk個(kは1以上の整数)のレコードを無規則(すなわち、ランダム)に選択して、選択したレコードを1個ずつ含むk個の集団を作成する。
【００３４】
この選択された各レコードが、集団の核(種とも呼ぶ)となるレコードである。以後、一方法は、この核となるレコードを含む集団に、この核となるレコードに類似するレコードを追加する。具体的には、一方法は、分類処理の対象である離散データに含まれるレコードからk個のレコードを除いたレコードについては、評価値が最も良くなるように、k個の集団に順次配置して、k個の初期集団を生成する。
【００３５】
ステップS102:一方法は、元の集団を記憶し、元の集団の評価値e_preを算出する。元の集団は、S101が1回目に実行される場合、初期集団(S101)である。元の集団は、S102が2回目以降に実行される場合、S105終了後の集団である。なお、一方法は、例えば、集団構成テーブルの形式で、集団を記憶する。
【００３６】
ステップS103:一方法は、集団内情報量の高いm個(mは1以上の整数)のデータを含むレコード集合Qを選択する。
【００３７】
ステップS104:一方法は、レコード集合Qの中で最も集団内情報量が高い1個のレコードrを取得する。
【００３８】
ステップS105:一方法は、評価値が最も良くなる集団に取得した1個のレコードrを再配置する。ここで、評価値が最も良いとは、評価値が最も低いことと同義である。
【００３９】
ステップS106:一方法は、レコード集合Qから1個のレコードrを除外する。
【００４０】
ステップS107:一方法は、レコード集合Qは空集合か判定する。レコード集合Qは空集合でない場合(S107/NO)、S104に移る。レコード集合Qは空集合の場合(S107/YES)、S108に移る。
【００４１】
ステップS108:一方法は、再配置後の評価値eを算出する。
【００４２】
ステップS109:一方法は、再配置後の評価値eは、元の評価値e_preを超えるか判定する。再配置後の評価値eは、元の評価値e_preを超えない場合(S109/NO)、S110に移る。再配置後の評価値eは、元の評価値e_preを超える場合(S109/YES)、S111に移る。
【００４３】
ステップS110:一方法は、S102〜S103のステップをR回繰り返したか判定する。一方法は、S2〜S3のステップをR回繰り返した場合(S110/YES)、処理を終了する。一方法は、この処理終了時の再配置後の集団を分類後の離散データの集団とする。一方法は、S2〜S3のステップをR回繰り返さない場合(S110/NO)、S102に移る。
【００４４】
ステップS111:一方法は、S105で再配置したレコードrを元の集団に戻し、再配置前の集団を分類後の離散データの集団とする。
【００４５】
(離散データの分類の一方法の具体例)
図2〜図6を参照して、離散データの分類の一方法の具体例を説明する。図4は、初期集団を示す集団構成テーブルを示す図である。図5、図6は、再配置後の集団構成テーブルを示す第1、第2の図である。なお、図4〜図6の集団構成テーブルは、図2の集団構成テーブルT110の構成と同様の構成である。ただし、図4〜図6の集団構成テーブルの集団内情報量は、説明を簡略にするため、式ではなく数値で示す。
【００４６】
一方法は、分類処理の対象である離散データに含まれるレコードの中から、相互に変数値の共有が少ないk個(kは例えば3個)のレコードをランダムに選択して、選択したレコードを1個ずつ含むk個の集団を作成する。一方法は、図2の離散データLSD4に含まれるレコードの中から3個のレコード(例えば、{IP1,80},{IP4,110},{IP6,143})を選択して3個の集団を作成する。そして、一方法は、分類処理の対象である離散データに含まれるレコードから3個のレコードを除いたレコードについては、評価値が最も良くなるように、3個の集団に順次配置して初期集団を生成する。
【００４７】
一方法は、元の集団である集団構成テーブルT101を記憶し、元の集団の評価値e_preを算出する(S102)。元の集団の評価値は、図4に示すように"30.1"である。
【００４８】
一方法は、集団内情報量の高いm個(このステップではmは3)のデータを含むレコード集合Qを選択する(S103)。なお、一方法は、"m"をステップ毎に適宜変化させてもよい。一方法は、図4の例では、集団内情報量が1.8のレコード{IP6,110},{IP7,110}と、集団内情報量が1.3のレコード{IP5,110}とを選択する(点線枠参照)。
【００４９】
一方法は、レコード集合Qの中で最も集団内情報量が高い1個のレコードr(例えば、{IP7,110}、図4の"最大"吹き出し参照)を取得する(S104)。一方法は、再配置の結果、評価値が最も良くなる(すなわち評価値が最も低くなる第2の集団#2にレコードrを再配置する(S105)(図4の" #2に再配置したら評価値が最良"参照)。
【００５０】
一方法は、レコード集合Qから1個のレコードr({IP7,110})を除外する(S106)。
【００５１】
図5にレコードr({IP7,110})を第2の集団#2に再配置した集団構成テーブルT102を示す。なお、一方法は、図5に示すように、再配置後(S105参照)の集団内情報量を更新する。
【００５２】
レコード集合Qは空集合でないので(S107/NO)、S104に移る。一方法は、レコード集合Q({IP5,110},{IP6,110})の中で最も集団内情報量が高い1個のレコードr(例えば、{IP6,110}、図5の"最大"吹き出し参照)を取得する(S104)。一方法は、再配置の結果、評価値が最も良くなる第2の集団#2にレコードrを再配置する(S105)(図5の" #2に再配置したら評価値が最良"参照)。
【００５３】
一方法は、レコード集合Qから1個のレコードr({IP6,110})を除外する(S106)。以後、一方法は、レコード集合Qについて、S107、S104〜S106の処理を行い、レコード集合Qに含まれるレコード{IP5,110}を第2の集団＃2に再配置し、レコード集合Qからレコード{IP5,110}を除外する。
【００５４】
図6にレコード集合Qの全レコード({IP5,110},{IP6,110},{IP7,110})を第2の集団#2に再配置した集団構成テーブルT103を示す。一方法は、レコード集合Qが空集合になると(S107/YES)、再配置後の評価値eを算出する(S108)。再配置後の評価値は、図6の集団構成テーブルT103に示すように、"25.8"である。
【００５５】
再配置後の評価値eは、元の評価値e_preを超えないので(S109)、一方法は、S102〜S103のステップをR回(例えば、2回)繰り返したか判定する(S110)。前記の例では、一方法は、S102〜S103のステップを1回繰り返しているので(S110/NO)、S102に移る。
【００５６】
一方法は、元の集団である集団構成テーブルT103を記憶し、元の集団の評価値e_preを算出する(S102)。元の集団の評価値は、図6に示すように"25.8"である。
【００５７】
一方法は、集団内情報量の高いm個(このステップではmは2)のレコードを含むレコード集合Qを選択する(S103)。一方法は、図6の例では、集団内情報量が1.2のレコード{IP8,110},{IP9,110}を選択する(図6の点線枠、"最大"吹き出し参照)。一方法は、以後、S104〜S107の処理を繰り返し行い、レコード{IP8,110},{IP9,110}を第2の集団#2に再配置する。この再配置後の集団構成テーブルは、図2の集団構成テーブルT110である。
【００５８】
そして、一方法は、レコード集合Qが空集合になると(S107/YES)、再配置後の評価値eを算出する(S108)。再配置後の評価値は、図2に示すように、"24.9"である。なお、図2では、集団内情報量については、数式で示し、数値の記載を省略している。
【００５９】
再配置後の評価値eは、元の評価値e_preを超えないので(S109/NO)、一方法は、S102〜S103のステップをR回(例えば、2回)繰り返したか判定する(S110)。前記の例では、一方法は、S102〜S103のステップを2回繰り返しているので(S110/NO)、処理を終了する。
【００６０】
一方法により、離散データLSD4を分類した結果、図2に示すように、離散データLSD4に含まれる複数のレコードが第1の集団#1〜第3の集団#3に分類される。離散データの分析者は、分類されたレコードを参照して、人の意図や行動を推測する。
【００６１】
(一方法の課題)
次に、一方法の課題について説明する。離散データに含まれるレコードの内容によっては、離散データの分析者の目的を達成できる最適な集団が異なる。この最適な集団は、分析者の目的に応じた集団である。すなわち、分析者の目的を達成するために、分類の方法を変更することが好ましい。例えば、図2で説明した離散データLSD4は、トラフィックログのレコードを含む。かかるレコードを含む離散データを分類する場合、単に、集団内情報量の総合計を考慮するだけでなく、他の要素(例えば、以下に説明する共有数)を考慮することが好ましい。
【００６２】
図7は、一方法の課題を説明する第1の図である。図7の集団構成テーブルT104は、図2の集団構成テーブルT110の右欄に変数値欄を追加したテーブルである。
【００６３】
変数値欄は、集団構成欄に記憶されているレコードの変数値を記憶する。例えば、第1の集団#1における集団構成欄に記憶されているレコードの変数値は、IP1,IP2,IP3,IP4,IP5,80,8080である。従って、第1の集団#1の集団識別子"#1"が記憶された行と、変数値欄とが交わるセルに、これらの変数値IP1,IP2,IP3,IP4,IP5,80,8080が記憶される。
【００６４】
集団構成テーブルT104において、下から2番目の行と変数値欄とが交わるセルは、共有数を記憶するセルである。共有数は、異なる集団が同一変数値を共有する場合、この同一変数値の総数を示す。例えば、異なる第1の集団#1、第2の集団#2は、同一変数値IP4,IP5を共有している。異なる集団が共有している同一変数値を点線枠で示す。図7の例の場合、点線枠内の変数値の総数が共有数であり、この共有数は12である。
【００６５】
図8は、一方法の課題を説明する第2の図である。図8の集団構成テーブルT105は、図7の集団構成テーブルT104の構成と同様の構成である。集団構成テーブルT105は、一方法とは異なる手法により、離散データLSD4を分類した集団構成テーブルを示す。
【００６６】
図8の集団構成テーブルT105では、図7の集団構成テーブルT104における第2の集団#2のレコード{IP6,110},{IP7,110},{IP8,110},{IP9,110}が、第3の集団#3に配置されている。図8でも、図7と同様に、異なる集団が共有している同一変数値を点線枠で示す。図8の例の場合、点線枠内の変数値の総数が共有数であり、この共有数は6である。図8の例では、異なる第1の集団#1、第2の集団#2は、同一変数値IP4,IP5を共有し、異なる第2の集団#2、第3の集団#3は、同一変数値110を共有する。
【００６７】
図8において、第1の集団#1に属するレコード{IP4,80},{IP4,8080},{IP5,80},{IP5,8080}、第2の集団#2に属するレコード{IP4,110},{IP5,110}に着目する。ここで、IPアドレスIP4が設定されている第1のサーバはWEBサーバであり、IPアドレスIP5が設定されている第2のサーバはWEBサーバであるとする。このように第1、第2のサーバは、WEBサーバであり、メールサーバではない。
【００６８】
ここで、例えば電子メールの配信を行うメールサーバは、特徴的なポート番号25,110,143を使用する。ポート番号25はSMTPのポート番号、ポート番号110はPOP3のポート番号、ポート番号143はIMAP4のポート番号である。なお、SMTPは" Simple Mail Transfer Protocol"の略語、POPは"Post Office Protocol"の略語、IMAPは" Internet Message Access Protocol "の略語である。
【００６９】
しかし、第2の集団#2に属するレコード{IP4,110},{IP5,110}によれば、WEBサーバである第1、第2のサーバのポート番号110を送信先ポート番号とするTCP/IPパケットが送信されていることがわかる。ポート番号110を使用(解放とも呼ぶ)して、通信を実行するサーバは、メールサーバである。しかし、IPアドレスIP4,IP5が設定されている第1、第2のサーバは、WEBサーバであり、メールサーバではない。かかるTCP/IPパケットによる通信は、ポートスキャンや特定のポートに対する攻撃を目的とした通信の可能性が高い。なお、かかるTCP/IPパケットによる通信は、いわゆる特異な通信群とも呼ばれる。
【００７０】
すなわち、かかるTCP/IPパケットのレコード({IP4,110},{IP5,110})は、不正行為を行おうとうする意図など特異な意図に基づく行動により発生したレコードの集団である可能性が高い。
【００７１】
離散データの分析者は、かかる特異な意図に基づく行動を見つける目的で、分類された離散データを分析する場合、かかる特異な意図に基づく行動により発生したレコードが分類(集団化)されていれば、かかる行動を見つけることが容易になる。分析者は、かかる行動を見つけると、不正行為を阻止する対策をネットワークの管理者などに指示する。
【００７２】
なお、識別子付きPOSの場合、実際に購買が行われていないのにもかかわらず、店員が、不正行為を行おうとする意図に基づき、あたかも購買が行われたように見せかけてレジ操作を行うことを想定する。この想定の場合、通常の購買行動により生成されたPOSのレコードの内容から逸脱した内容のレコードがPOSシステムにより生成される。かかる逸脱した内容のレコードも、特異な意図に基づく行動により発生したレコードである。
【００７３】
さて、一方法では、集団内情報量の総和が小さい集団構成として、ポート番号別に集団が生成される場合がある。一方法により生成された集団を示す図7の集団構成テーブルT104によれば、第1の集団#1は、ポート番号80,8080を含むレコードを含む集団である。なお、ポート番号80,8080は、WEBサーバのHTTP (Hypertext Transfer Protocol)用のポート番号である。
【００７４】
第2の集団#2は、ポート番号110を含むレコードを含む集団である。第3の集団#3は、ポート番号25,143を含むレコードを含む集団である。
【００７５】
しかし、例えば特異な通信群を発見する目的で離散データを分類する場合、以下のようにレコード集団を生成することが望ましい。すなわち、特徴的(典型的とも呼ぶ)なポート番号の組み合わせを使用するサーバに関するレコード集団を纏め、特徴的なポート番号の組み合わせから逸脱した通信群を示すレコード集団を別のレコード集団とする。なお、特異な通信群を発見する目的は、前記した不正行為を行おうとうする意図など特異な意図に基づく行動により発生したレコードを発見する目的に含まれる。
【００７６】
図8の例では、一点鎖線の枠で囲った、第3の集団#3に属する複数のレコード("典型的な通信"の吹き出し参照)が特徴的なポート番号の組み合わせを使用するサーバに関するレコード集団である。また、図8の例では、二点鎖線の枠で囲った、第2の集団#2に属する複数のレコード("特異な通信"の吹き出し参照)が逸脱した通信群を示すレコード集団である。このように、図7に示す第1の集団#1に属するレコード｛IP5,110｝は、図8に示すように第2の集団#2に属していたほうが、特異な通信群を発見するという分析者の目的を達成できる最適な集団になる。他にも、図7に示す第2の集団#2に属するレコード｛IP6,110｝,｛IP7,110｝, ｛IP8,110｝,｛IP9,110｝は、図8に示すように第3の集団#3に属していたほうが、特異な通信群を発見するという分析者の目的を達成できる最適な集団になる。
【００７７】
以上説明したように、分析者の目的が、例えば特異な通信群を発見する目的の場合、一方法とは異なる手法で離散データを分類した方が、分析者の目的を容易に達成できる最適な集団に離散データを分類できる。
【００７８】
ここで、図7と、図8とを比較すると、図8における集団内情報量の総合計(23.6)は、図7における集団内情報量の総合計（21.9）に比べて多くなる。なお、図7、図8では、集団数(3)は同じなので、図8における評価値(26.6)は、図7における評価値（24.9）に比べて多い。しかし、図8における共有数(6)は、図7の共有数(12)に比べて少ない。
【００７９】
他の方法で分類した場合の集団内情報量の合計は、一方法で分類した場合の集団内情報量の合計に比べて多い。しかし、他の方法で分類した場合の共有数は、一方法で分類した場合の共有数に比べて少なくなる(特徴点と記す)。
【００８０】
この特徴点によれば、分析者の目的が、不正行為を行おうとする意図など特異な意図に基づく行動を見つける場合、集団内情報量だけでなく、共有数を考慮すれば、分析者の目的を容易に達成できる最適な集団に離散データを分類できることがわかる。この分類では、共有数がなるべく少なくなるように分類を行えば、最適な集団に離散データを分類できる。
【００８１】
また、情報理論における最小記述長(MDL:minimum description length)原理では、モデルの複雑さと、モデルで表したときの実際のデータに対する誤差との和が小さい方がより良いデータの説明であることが知られている。離散データの分類においては、このモデルは、例えば、レコードの集団に該当し、モデルの複雑さは、例えば、集団内において互いに相違する変数値の数に該当する。また、誤差は、前記したレコードの出現確率や、集団内情報量に該当する。
【００８２】
最小記述長原理によれば、集団内において互いに相違する変数値が少なくなれば(換言すれば、モデルの複雑さが少なくなれば)、最適な集団を作成することができると考えられる。この集団に属する変数値を少なくすることは、異なる集団に属する同一変数値の数(共有数)がなるべく少なくなるように分類することによっても達成できる。
【００８３】
[本実施の形態]
そこで、本実施の形態のデータ分類装置は、集団間の変数値の共有の程度を示す共有値が少なくなるように複数のレコードを複数の集団(グループとも呼ぶ)に分類(分割とも呼ぶ)する。本実施の形態のデータ分類装置は、この分類において、さらに、集団に属するレコードに含まれるレコードのこの集団における出現確率が多くなように複数のレコードを複数の集団に分類する。この変数値の共有の程度を示す共有値が少なくなることは、異なる集団に属する同一変数値の数が少なくなることと同義である。
【００８４】
(ハードウェアブロック図)
図9は、本実施の形態のデータ分類装置DVのハードウェアブロック図である。データ分類装置DVは、バスBに接続された、CPU11と、RAM12と、ROM13と、通信装置14と、ストレージ装置15と、外部記憶媒体読み取り装置16とを有する。データ分類装置DVは、例えば、情報処理装置である。なお、CPUは"Central Processing Unit"の略語、RAMは"Random Access Memory"の略語、ROMは" Read Only Memory"の略語である。
【００８５】
CPU11は、データ分類装置DVの全体を制御する中央演算処理装置である。RAM12は、CPU11が実行する処理や、分類プログラムPGが実行する各ステップにおいて生成(算出)されたデータなどを一時的に記憶する。RAM12は、例えばDRAM(Dynamic Random Access Memory)などの半導体メモリである。
【００８６】
CPU11は、データ分類装置DVの起動時に、ストレージ装置15から分類プログラムPGの実行ファイルを読み出し、RAM12に展開し、分類プログラムPGを実行する。なお、この実行ファイルを外部記憶媒体MDに記憶してもよい。
【００８７】
ROM13は、各種設定情報を記憶する。通信装置14は、例えばNIC(Network Interface Card)を有し、ネットワークに接続し、他の装置と通信する処理を実行する。ストレージ装置15は、例えばハードディスクドライブ(HDD：Hard Disk Drive)や、ソリッドステートドライブ(SSD:Solid State Drive)などの大容量記憶装置である。
【００８８】
外部記憶媒体読み取り装置16は、外部記憶媒体MDに記憶されたデータを読み取る装置である。外部記憶媒体MDは、例えば、CD-ROM(Compact Disc Read Only Memory)、DVD(Digital Versatile Disc)などの可搬型記憶媒体や、USBメモリなどの可搬型の不揮発性メモリである。外部記憶媒体MDは、例えば、分類処理の対象である離散データを記憶する。
【００８９】
(ソフトウェアブロック図)
図10は、図9のデータ分類装置DVのソフトウェアブロック図である。分類プログラムPGは、入力部(取得部)101と、分類部102と、出力部103とを有する。以下、入力部(取得部)101を入力部101と記す。
【００９０】
入力部101は、離散データを他の装置や外部記憶媒体MDから取得し、分類部102に入力する。入力部101は、複数の種類の変数値を其々が含む複数のレコードを含むデータ(例えば、離散データ)を取得する取得部の一例である。なお、他の装置は、通信装置14が接続するネットワークと通信可能なストレージサーバなどである。
【００９１】
次に、分類部102の詳細について説明する。分類部102は、入力部101により取得された離散データに含まれる複数のレコードを複数の集団(グループとも呼ぶ)に分類する。分類部102は、この分類において、集団間の変数値の共有の程度を示す共有値に基づき、複数のレコードを複数の集団に分類する。具体的には、分類部102は、集団に属するレコードに含まれるレコードのこの集団における出現確率が多くなり、かつ、集団間の変数値の共有の程度を示す共有値が少なくなるように、前記した離散データに含まれる複数のレコードを複数の集団に分類する。
【００９２】
分類部102は、レコードの出現確率を、集団に属するレコードに含まれる変数値のこの集団における出現確率に基づき算出する。
【００９３】
分類部102は、レコードの出現確率の算出において、このレコードが属する集団に属するレコードに含まれる変数値の各々のこの集団における出現確率の積を算出し、積の算出値をこのレコードの出現確率とする。また、分類部102は、異なる集団に属する同一変数値の数と集団の各々に属する相互に異なる変数値の総数とに基づき共有値を算出する。この共有値は、異なる集団に属する同一変数値の数(共有数)に対応する。
【００９４】
分類部102が実行する前記した分類の方法により、図7、図8で説明したように、集団内情報量だけでなく、共有数をも考慮した離散データの分類が可能になり、その結果、分析者の目的を容易に達成できる最適な集団に離散データを分類できる。すなわち、分類部102が実行する前記した分類の方法により、離散データを分析者の目的に応じたグループに分類できる。さらに、前記した分類の方法によれば、異なる集団に属する同一変数値の数(共有数)がなるべく少なくなるように分類しているので、前記した最小記述長原理によっても、最適な集団を作成することができる。
【００９５】
具体的には、分類部102は、複数のレコードの分類において、レコードの各々の出現確率の逆数の合計を算出する。なお、出現確率の逆数は、図2、図7、図8などで説明した集団内情報量に対応する。
【００９６】
さらに、分類部102は、共有値を、集団の各々に属する変数値の各々について算出する。そして、分類部102は、レコードの各々の出現確率の逆数の合計と変数値の各々の共有値の合計との総合計が少なくなるように、複数のレコードを前記複数の集団に分類する。
【００９７】
レコードの各々の出現確率の逆数の合計が少なくなることは、レコードの各々の出現確率の合計が多くなることと同義である。従って、レコードの各々の出現確率の逆数の合計と変数値の各々の共有値の合計との総合計が少なくなるように、複数のレコードを前記複数の集団に分類すれば、集団内情報量だけでなく、共有数をも考慮した離散データの分類が可能になる。その結果、前記した最適な集団に離散データを分類できる。
【００９８】
ここで、分類部102は、複数のレコードの分類において、レコードの各々の出現確率の逆数の対数の第1の合計を算出する。分類部102、さらに、変数値の各々の共有値の対数の第2の合計を算出する。そして、分類部102は、第1の合計と第2の合計との総合計が少なくなるように、複数のレコードを前記複数の集団に分類する。
【００９９】
なお、出現確率の逆数の対数、共有値の対数を算出するのは、情報理論において、ある情報量(エントロピーとも呼ぶ)を算出する場合、確率の逆数の対数を利用することが一般に行われているからである。
【０１００】
分類部102は、前記した離散データの分類を実行するため、初期集団を生成する集団生成部102aと、レコードの再配置を実行する再配置部102bとを有する。
【０１０１】
集団生成部102aは、図3のS101で説明したように、初期集団を生成する。具体的には、集団生成部102aは、入力部101により取得された離散データに含まれる複数のレコードの中から、相互に共有する変数値が少なくなるようにk(kは2以上の整数)個のレコードをランダムに選択してk個の集団を生成する。集団生成部102aは、この集団に属するレコードがこの集団に出現する出現確率が高くなるように、複数のレコードにおいてk個のレコード以外のレコードを、k個の集団に配置した集団を生成する。なお、kをNaと示しても良い。この初期集団の生成により、最初に、集団に属するレコードに含まれるレコードのこの集団における出現確率が多くなるように離散データを分類する。
【０１０２】
再配置部102bは、集団生成部102aが生成した初期集団内の第1の集団に属するレコードを他の第2の集団に再配置する処理を実行する。出力部103は、再配置部102bの実行後に生成された集団を、例えば端末TAに出力する。
【０１０３】
(本実施の形態における離散データの分類のフロー図)
図11は、本実施の形態における離散データの分類処理の流れを説明するフロー図である。図11のS1の前に、入力部101は離散データを取得し、集団生成部102aに入力する。
【０１０４】
ステップS1: 集団生成部102aは、分類処理の対象である離散データに含まれる複数のレコードを分類して初期集団を生成する。S1は、図3のS101と同様であるので、詳細な説明を省略する。
【０１０５】
ステップS2: :集団生成部102aまたは再配置部102bは、元の集団をRAM12に記憶し、元の集団の評価値e_preを算出しRAM12に記憶する。評価値e_preは、元の集団における集団内情報量の合計と、集団間情報量の合計との総合計である。集団間情報量は、図14で詳細に説明する。元の集団は、S1が1回目に実行される場合、初期集団(S1)である。元の集団は、S2が2回目以降に実行される場合、S5終了後の集団である。
【０１０６】
S102が1回目に実行される場合、集団生成部102aが、S102を実行する。S102が2回目以降に実行される場合、再配置部102bが、S102を実行するが、この場合、元の評価値e_preを算出せず、S8で算出した評価値を元の評価値として記憶してもよい。なお、集団生成部102aまたは再配置部102bは、例えば、集団構成テーブルの形式で、集団を記憶する。
【０１０７】
ステップS3:再配置部102bは、評価値の改善量が大きいm(mは1以上の整数)個のレコードを含むレコード集合Qを選択する。この改善量は、集団内情報量の減少量から、変数値の異なり数の総合計の増加分(重み付けを含む)を減算した値である。評価値の改善量を、(式1)で示す。
【０１０８】
評価値の改善量＝(集団内情報量の減少)―α×(変数値の異なり数の増加)…(式1)
なお、αはいわゆる重み付け係数であり、分析者により適宜調整可能である。S3の詳細な説明は、図12のフロー図で説明する。
【０１０９】
ステップS4:再配置部102bは、レコード集合Qの中で、評価値の改善量が最も大きいレコード群rgを取得する。なお、レコード群rgは、1個のレコードを含んでいてもよい。
【０１１０】
ステップS5:再配置部102bは、評価値が最も良くなる集団にレコード群rgを再配置する。
【０１１１】
ステップS6:再配置部102bは、レコード集合Qからレコード群rgを除外する。
【０１１２】
ステップS7:再配置部102bは、レコード集合Qは空集合か判定する。レコード集合Qは空集合でない場合(S17/NO)、S4に移る。レコード集合Qは空集合の場合(S7/YES)、S8に移る。なお、S7〜S9は、図3のS107〜S109と同様であるので、詳細な説明を省略する。
【０１１３】
ステップS8:再配置部102bは、再配置後の評価値eを算出する。
【０１１４】
ステップS9:再配置部102bは、再配置後の評価値eは、元の評価値e_preを超えるか判定する。再配置後の評価値eは、元の評価値e_preを超えない場合(S9/NO)、S10に移る。再配置後の評価値eは、元の評価値e_preを超える場合(S9/YES)、S11に移る。
【０１１５】
ステップS10:再配置部102bは、S2〜S3のステップをR回繰り返したか判定する。再配置部102bは、S2〜S3のステップをR回繰り返した場合(S10/YES)、処理を終了する。再配置部102bは、この処理終了時の再配置後の集団を分類後の離散データの集団とする。そして、再配置部102bは、再配置後の集団を出力部103に入力する。出力部103は、再配置部102bから入力された再配置後の集団を、例えば端末装置TAに出力する。再配置部102bは、S2〜S3のステップをR回繰り返さない場合(S10/NO)、S2に移る。
【０１１６】
ステップS11:再配置部102bは、S5で再配置したレコード群rgを元の集団に戻し、再配置前の集団を分類後の離散データの集団とする。そして、再配置部102bは、再配置前の集団を出力部103に入力する。出力部103は、再配置部102bから入力された再配置前の集団を、例えば端末装置TAに出力する。
【０１１７】
図12は、図11のステップS3の処理の流れを説明するフロー図である。
【０１１８】
ステップS31:再配置部102bは、最新の集団構成テーブルに含まれるレコードの中から、集団内情報量が高い順に、相互に変数値を共有しないm個のレコードを含むレコード群Vを選択する。
【０１１９】
ステップS32:再配置部102bは、集団Uを空集合にリセットする。
【０１２０】
ステップS33:再配置部102bは、レコード群Vから順に1個のレコードr1を取得し、集団Uに追加する。
【０１２１】
ステップS34:再配置部102bは、集団U内の何れかの変数値を共有するレコードの中で、集団Uに追加したときの評価値の改善量が最も大きいレコードを、最新の集団構成テーブルに含まれるレコードの中から選択し、集団Uに追加する。
【０１２２】
ステップS35:再配置部102bは、g(gは1以上の整数)個のレコードを追加したか判定する。g個のレコードを追加していない場合(S35/NO)、S34に移る。g個のレコードを追加した場合(S35/YES)、S36に移る。
【０１２３】
ステップS36:再配置部102bは、評価値の改善量が最も大きくなるときの集団Uを、レコード集合Qに加える。
【０１２４】
ステップS37:再配置部102bは、レコード群Vから全てのレコードを取得したか判定する。レコード群Vから全てのレコードを取得していない場合(S37/NO)、S32に移る。レコード群Vから全てのレコードを取得した場合(S37/YES)、S3を終了し図11のS4に移る。
【０１２５】
[具体例]
次に、本実施の形態における離散データの分類の具体例について、図13〜図30を参照して説明する。図13〜図30は、本実施の形態における具体例を説明する第1の図〜第18の図である。
【０１２６】
図13を参照して、具体例の概略を説明する。図13の具体例の概略では、初期集団を示す集団構成テーブルT1を起点に、選択されたレコードが各集団に順次再配置される状態を模式的に示している。なお、ある集団に属するレコードを、同一の集団に配置した場合(換言すれば、移動させない場合)も再配置という言葉で説明している。
【０１２７】
この再配置により、集団構成テーブルT1は、集団構成テーブルT2、T3、T4、T5と変化する。集団構成テーブルT1、T2、T3、T4、T5においては、2行目以降のセルに、各集団に属するレコードを記憶している。集団構成テーブルT1、T2、T3、T4、T5において、"集団構成"が記憶された1行目のセルの次の2行目のセルに、第1の集団#1に属するレコードが記憶される。そして、3行目のセルに、第2の集団#2に属するレコードが記憶され、4行目のセルに、第3の集団#3に属するレコードが記憶される。
【０１２８】
集団生成部102aは、図2の離散データLSD4に対して、図11の初期集団の生成処理(S1)を実行し、集団構成テーブルT1に示すように複数のレコードを分類する。以後、再配置部102bは、図11のS2以下の処理を実行し、レコードを再配置する。
【０１２９】
図13において点線枠で囲ったレコードが、図11のS4、S5で説明したレコード群rgである。また、符号R1で示す破線枠で囲った集団構成テーブルT2、T3は、レコード集合Q1(S3参照)に属するレコード集団U1a、U1bの再配置(S5参照)が再配置部102bにより実行されたことにより生成される集団構成テーブルを示す。そして、符号R2で示す破線枠で囲った集団構成テーブルT4、T5は、レコード集合Q2(S3参照)に属するレコード集団U2a、U2bの再配置(S5参照)が再配置部102bにより実行されたことにより生成される集団構成テーブルを示す。なお、集団構成テーブルT1、T2、T3、T4、T5の詳細は、それぞれ、図14、図19、図20、図26、図28で説明する。
【０１３０】
(初期集団)
図14を参照して、初期集団を説明する。図14の集団構成テーブルT11は、図7、図8に示した集団構成テーブル(T104,T105)の変数値欄を集団間情報量欄に替えたテーブルである。集団間情報量欄は、集団間情報量を"変数値：変数値の集団間情報量"の形式で記憶する。この変数値は、集団間情報量が記憶されているセルが属する行と、集団欄とが交わるセルに記憶された集団識別子で識別される集団に属するレコードの変数値である。
【０１３１】
集団生成部102aは、図14で説明する初期集団を生成し(S1)。そして、集団生成部102aは、図14に示すように、全レコードの集団内情報量と集団間情報量とを算出する(S2)。さらに、集団生成部102aは、集団内情報量の総合計(27.2)と、集団間情報量の総合計(21.1)とを加算して元の評価値e_pre(48.3)算出する(S2)。以下、このS1、S2について説明する。なお、初期集団については図3のS101で説明し、集団内情報量については図2で説明したのでその説明を省略する。
【０１３２】
図14の例では、第1の集団#1に属するレコードの変数値は、以下の変数値である。すなわち、前記した変数値は、IP1,IP2,IP3,IP4,IP5,IP6,IP7,80,8080,110である。
【０１３３】
ある変数値(以下、変数値Xと記す)の集団間情報量は、変数値Xがある集団に出現する確率を示す変数値Xの出現確率の逆数の対数である。変数値Xの出現確率は、変数値Xを含む集団の数を、各集団に属している相互に異なる変数値の個数の合計で除算した値である。この集団間情報量は、図10で説明した、例えば、変数値の共有の程度の一例である。
【０１３４】
図14において、第1の集団#1内の変数値IP1(点線枠参照)の集団間情報量を算出する。第1の集団#1内の変数値IP1を含む集団は、第1の集団#1であるので、第1の集団#1内の変数値IP1を含む集団の数は、1個である。
【０１３５】
また、第1の集団#1に属している相互に異なる変数値は、以下の変数値である。すなわち、IP1,IP2,IP3,IP4,IP5,IP6,IP7,80,8080,110である。従って、第1の集団#1に属している相互に異なる変数値の個数は、10個である。また、第2の集団#2に属している相互に異なる変数値は、IP4,110である。従って、第2の集団#2に属している相互に異なる変数値の個数は、2個である。また、第3の集団#3に属している相互に異なる変数値は、IP6,IP7,IP8,IP9,110,143,25である。従って、第3の集団#3に属している相互に異なる変数値の個数は、7個である。以上より、各集団に属している相互に異なる変数値の個数の合計は、19個(10個+2個+7個)である。
【０１３６】
従って、第1の集団#1に含まれる変数値IP1が第1の集団に#1に出現する出現確率は、(1/19)である。そして、第1の集団#1に含まれる変数値IP1の集団間情報量は、-log(1/19)である(点線枠参照)。
【０１３７】
第3の集団#3に含まれる変数値110(一点鎖線枠参照)の集団間情報量を算出する。第3の集団#3内の変数値110を含む集団は、第1の集団#1、第2の集団#2、第3の集団#3であるので、第1の集団#1内の変数値110を含む集団の数は、3個である。そして、前記したように、各集団に属している相互に異なる変数値の個数の合計は、19個(10個+2個+7個)である。
【０１３８】
従って、第1の集団#1に含まれる変数値110が第1の集団#1に出現する出現確率は、(3/19)である。そして、従って、第1の集団#1内に含まれる変数値110の集団間情報量は、-log(3/19)である(一点鎖線枠参照)。
【０１３９】
第k(小文字kは1以上の整数)の集団#kに属するレコードの変数値の集団間情報量の合計を、この集団間情報量を記憶するセルの下側に示す。例えば、第1の集団#1に属するレコードの変数値の集団間情報量の合計は、"11.4"である。具体的には、この総合計は、(-log(1/19))+(-log(1/19))+(-log(1/19))+(-log(2/19))+(-log(1/19))+(-log(2/19))+(-log(2/19))+(-log(1/19))+(-log(1/19))+(-log(3/19))である。
【０１４０】
集団構成テーブルT11において、下から2番目の行と集団間情報量欄とが交わるセルは、全集団における各変数値の集団間情報量の総合計を記憶する。例えば、第1の集団#1〜第3の集団#3における各変数値の集団内情報量の合計は、それぞれ"11.4"、"1.8"、"7.9"である。従って、前記した総合計は、"21.1"(11.4+1.8+7.9)である。
【０１４１】
以後、再配置部102bは、k個の集団に属するレコードの中から、レコードを異なる集団に配置した場合に、第1の合計と第2の合計との総合計の減少量が最大になる1以上のレコードを選択する。第1の合計は、例えば集団内情報量の合計である。第2の合計は、例えば、集団間情報量の合計である。再配置部102bは、選択した1以上のレコードを、選択した1以上のレコードが属する集団(例えば、第1の集団)から、第1の合計と第2の合計との総合計の減少量が最大になる集団(例えば、第2の集団)に配置する。
【０１４２】
(再配置対象のレコード集合の選択)
次に、図14〜図16を参照して、レコード集合Qの選択(S3)について説明する。再配置部102bは、最新の集団構成テーブル（換言すれば、元の集団）に含まれるレコードの中から、集団内情報量が高い順に、相互に変数値を共有しないm個のレコードを含むレコード群Vを選択する。この最新の集団構成テーブルは、図14の集団構成テーブルT11である。再配置部102bは、図14の集団構成テーブルT11に含まれるレコードの中から、集団内情報量が高い順に、例えば、相互に変数値を共有しないm個のレコード{IP7,110},{IP1,80}を含むレコード群Vを選択する(S31)。このステップでは、mは2である。
【０１４３】
ここで、図14の集団構成テーブルT11において、最大の集団内情報量は、1.8(-log{(1/13)*(3/13)})である。なお、対数の算出においては、小数点以下第2位を四捨五入している。
【０１４４】
最大の集団内情報量(1.8)を有するレコードは、第1の集団#1に属する2個のレコード{IP7,110},{IP6,110}(図14の二点鎖線枠参照)である。レコード{IP7,110},{IP6,110}は、変数値110を共有する。従って、再配置部102bは、レコード{IP7,110},{IP6,110}の中から1個のレコード、例えばレコード{IP7,110}を選択する。
【０１４５】
第1の集団#1に属する、選択されたレコード{IP7,110}の変数値を共有しないレコードであって、かつ、このレコードの集団内情報量が、最大の集団内情報量(1.8)の次に大きい集団内情報量を有するレコードは、例えば、レコード{IP1,80}である。最大の集団内情報量(1.8)の次に大きい集団内情報量は、1.2(-log{(2/13)*(5/13)})である。従って、再配置部102bは、レコード{IP1,80}を選択する。
【０１４６】
以上の選択処理により、再配置部102bは、2個のレコード{IP7,110}、{IP1,80}を選択する(S31)。そして、再配置部102bは、集合Uを空集合にリセットする(S32)。以下、リセット後の集合Uを集合Uaと記す。図15を参照して、集合Uaの作成について説明する。
【０１４７】
再配置部102bは、2個のレコード{IP7,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1(例えば、{IP7,110})を取得し、集団Uaに追加する(S33)。図15において、レコード{IP7,110}を一点鎖線の枠で示し、この追加を一点鎖線の矢印で示す。なお、レコード{IP7,110}は、図14の集団構成テーブルT11における第1の集団#1に属するレコードである(図15のレコード群Vにおいて"#1"で示す点線矢印参照)。
【０１４８】
集団Uaにレコード{IP7,110}が追加されている状態を集団Uaのセル内に"集団構成：{IP7,110}"で示す。再配置部102bは、レコード{IP7,110}の集団Uaにおける集団内情報量0.0を算出する。なお、レコード{IP7,110}の集団Uaにおける集団内情報量は、0.0(-log{(1/1)*(1/1)})である。
【０１４９】
この算出を集団Uaのセル内に"集団内情報量：0.0"で示す。集団Uaに属するレコード{IP7,110}の変数値は、IP7,110である。この変数値を集団Uaのセル内に"変数値：IP7,110"で示す。
【０１５０】
集団Xに属するレコードを他の集団(集団Yと適宜記す)に再配置する場合、集団内情報量の総合計がなるべく減少することが好ましい。そこで、集団Xに属するレコードを集団Yに再配置したことにより集団内情報量がどれだけ減少するかを考える。
【０１５１】
例えば、第1の集団#1に属するレコード{IP7,110}を集団Uaに再配置することにより、レコード{IP7,110}の第1の集団#1における集団内情報量(1.8)が減少し、集団Uaの集団内情報量は0.0増加する。なお、集団内情報量が0.0増加するとは、集団内情報量が増加しないこととと同義である。
【０１５２】
従って、集団Uaにレコード{IP7,110}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図15の集団Uaにおける全集団内情報量は、1.8(1.8-0.0)減少する。この減少を集団Uaのセル内に"減少：1.8-0.0=1.8"で示す。
【０１５３】
集団Xに属するレコードを他の集団(集団Yと適宜記す)に再配置した場合、変数値の共有数が少なくなることが好ましい。そこで、集団Xに属するレコードを集団Yに再配置したことにより変数値がどれだけ減少するか考える。この変数値の減少では、レコードを集団Yに再配置したことにより、このレコードに含まれるn(nは1以上の整数)個の変数値と同じ変数値が、集団X内の変数値に含まれなくなると、このn個の変数値がn個減少したとする。
【０１５４】
図14において、第1の集団#1に属するレコード{IP7,110}を集団Uaに再配置すると、変数値IP7と同一変数値が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数110は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP7,110}を集団Uaに再配置すると、変数値は1個減少する。この減少を集団Uaのセル内に"#1の減少：1"で示す。
【０１５５】
ここで、レコード{IP7,110}が属する集団Uaの変数値は、2個である。この変数値の個数を集団Uaのセル内に"Uの変数値の数：2"で示す。
【０１５６】
ここで、集団Xに属するレコードを集団Yに再配置した場合における評価値の改善量を考える。この再配置により、(式1)で示した評価値の改善量が多くなることが好ましい。
【０１５７】
この改善量は、（集団内情報量の減少）-α×（変数値の異なり数の増加）で示される。ここで、変数値の異なり数の総合計の増加は、集団Uの変数値から、前記した変数値の減少を減算した値であるとする。
【０１５８】
第1の集団#1に属するレコード{IP7,110}を集団Uaに再配置した場合における評価値の改善量は、0.8(1.8-α×(2-1)、ただしαは1)である。この"1.8"は、集団内情報量の減少値である。この"(2-1)"の"2"は、レコード{IP7,110}が属する集団Uaの変数値の個数であり、この"1"は、変数値の減少である。このαの数値は調整可能である。分析者は、このαの数値を調整して、後記する評価値の算出において、集団間情報量がこの評価値に与える影響を変更する。このαの数値を調整すれば、各集団を構成するレコードの内容が変化する。分析者は、このαの数値を調整し、離散データの分類をデータ分類装置DVに実行させ、レコードの内容の変化を見る。そして、分析者は、この変化を見ながら、分析者の意図に沿うように離散データの分類処理をデータ分類装置DVに実行させ、分析者の意図に沿った離散データの分類結果を得る。
【０１５９】
再配置部102bは、集団Uaにおける集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０１６０】
次いで、再配置部102bは、集団Ua内の何れかの変数値を共有するレコードの中で、集団Uaに追加したときの評価値の改善量が最も大きいレコードを、集団Uaに追加する(S34)。例えば、集団Ua内の何れかの変数値(IP7または110)を共有するレコードを{IP6,110}とする。このレコードは、図14の集団構成テーブルT11における第1の集団#1に属するレコードである(図15の集団Up1において"#1"で示す点線矢印参照)。
【０１６１】
集団Uaに第1の集団#1に属するレコード{IP6,110}を追加すると想定する。集団Uaにレコード{IP6,110}が追加されている状態を集団Up1のセル内に"集団構成：{IP7,110},{IP6,110}"で示す。再配置部102bは、レコード{IP7,110},{IP6,110}の集団Up1における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。
【０１６２】
この算出を集団Up1のセル内に"集団内情報量：0.3,0.3"で示す。集団Up1に属するレコード{IP7,110},{IP6,110}の変数値は、IP7,IP6,110である。この変数値を集団Up1のセル内に"変数値：IP7,IP6,110"で示す。
【０１６３】
第1の集団#1に属するレコード{IP7,110},{IP6,110}を集団Up1に再配置することにより、レコード{IP7,110}の第1の集団#1における集団内情報量(1.8)とレコード{IP6,110}の第1の集団#1における集団内情報量(1.8)が減少する。そして、この再配置により、集団Up1の集団内情報量は0.6(0.3+0.3)増加する。従って、集団Up1にレコード{IP7,110},{IP6,110}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図15の集団Up1における全集団内情報量は、3.0((1.8+1.8)-(0.3+0.3))減少する。この減少を集団Up1のセル内に"減少：(1.8+1.8)-(0.3+0.3)=3.0"で示す。
【０１６４】
図14において、レコード{IP7,110},{IP6,110}を第1の集団#1から集団Up1に再配置すると、変数値IP7,IP6と同一変数値IP7,IP6が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数110は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP7,110},{IP6,110}を集団Up1に再配置すると、変数値は2個減少する。この減少を集団Up1のセル内に"#1の減少：2"で示す。
【０１６５】
ここで、レコード{IP7,110},{IP6,110}が属する集団Up1の変数値は、3個である。この変数値の個数を集団Up1のセル内に"Uの変数値の数：3"で示す。
【０１６６】
第1の集団#1に属するレコード{IP7,110},{IP6,110}を集団Up1に再配置した場合における評価値の改善量は、2.0(3.0-α×(3-2)、ただしαは1)である。
【０１６７】
再配置部102bは、集団Up1における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０１６８】
集団Uaに第3の集団#3に属するレコード{IP8,110}を追加すると想定する(図15の集団Up2において"#3"で示す点線矢印参照)。集団Uaにレコード{IP8,110}が追加されている状態を集団Up2のセル内に"集団構成：{IP7,110},{IP8,110}"で示す。再配置部102bは、レコード{IP7,110},{IP8,110}の集団Up2における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。
【０１６９】
この算出を集団Up2のセル内に"集団内情報量：0.3,0.3"で示す。集団Up2に属するレコード{IP7,110},{IP8,110}の変数値は、IP7,IP8,110である。この変数値を集団Up2のセル内に"変数値：IP7,IP8,110"で示す。
【０１７０】
レコード{IP7,110}を第1の集団#1から集団Up2に再配置し、レコード{IP8,110}を第3の集団#3から集団Up2に再配置する。この再配置により、レコード{IP7,110}の第1の集団#1における集団内情報量(1.8)とレコード{IP8,110}の第3の集団#3における集団内情報量(1.2)が減少し、集団Up2の集団内情報量は0.6(0.3+0.3)増加する。なお、レコード{IP8,110}の第3の集団#3における集団内情報量は、1.2(-log{(3/10)*(2/10)})である。
【０１７１】
従って、集団Up2にレコード{IP7,110},{IP8,110}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図15の集団Up2における全集団内情報量は、2.4((1.8+1.2)-(0.3+0.3))減少する。この減少を集団Up2のセル内に"減少：(1.8+1.2)-(0.3+0.3)=2.4"で示す。
【０１７２】
第1の集団#1に属するレコード{IP7,110}を集団Up2に再配置すると、変数値IP7と同一変数値IP7が、第1の集団#1内の変数値から含まれなくなる。従って、第1の集団#1に属するレコード{IP7,110}を集団Up2に再配置すると、変数値は1個減少する。この減少を集団Up2のセル内に"#1の減少：1"で示す。
【０１７３】
第3の集団#3に属するレコード{IP8,110}を集団Up2に再配置すると、変数値IP8,110と同一変数値IP8,110が、第3の集団#3内の変数値から含まれなくなることがない。従って、第3の集団#3に属するレコード{IP8,110}を集団Up2に再配置しても、変数値は減少しない。この減少しないことを集団Up2のセル内に"#3の減少：0"で示す。
【０１７４】
ここで、レコード{IP7,110},{IP8,110}が属する集団Up2の変数値は、3個である。この変数値の個数を集団Up2のセル内に"Uの変数値の数：3"で示す。
【０１７５】
第1の集団#1に属するレコード{IP7,110}、第3の集団#3に属するレコード{IP8,110}を集団Up2に再配置した場合における評価値の改善量は、0.4(2.4-α×(3-1-0)、ただしαは1)である。
【０１７６】
再配置部102bは、集団Up2における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０１７７】
以上説明したように、集団Uaにレコード{IP6,110}を追加した場合の評価値の改善量は2.0であり、この評価値の改善量が最大である(図15の吹き出し"最大"参照)。そこで、再配置部102bは、レコード{IP6,110}を、集団Uaに追加する(S34)。
【０１７８】
再配置部102bは、g(gは例えば1)個のレコードを追加したか判定する(S35)。既に、1個のレコードを集団Uaに追加したので(S35/YES)、再配置部102bは、評価値の改善量が最も大きくなるときの集団Up1をレコード集合Q1に加える(S36)。以下、評価値の改善量が最も大きくなるときの集団Up1に含まれる2個のレコードの集団を集団U1aで示す。
【０１７９】
再配置部102bは、2個のレコード{IP7,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1({IP7,110})を取得しているので、レコード群Vから全てのレコードを取得していない(S37/NO)。従って、再配置部102bは、集合Uを空集合にリセットする(S32)。以下、リセット後の集合Uを集合Ubと記す。図16を参照して、集合Ubの作成について説明する。
【０１８０】
再配置部102bは、2個のレコード{IP7,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1(例えば、{IP1,80})を取得し、集団Ubに追加する(S33)。図16において、レコード{IP1,80}を一点鎖線の枠で示し、この追加を一点鎖線の矢印で示す。なお、レコード{IP1,80}は、図14の集団構成テーブルT11における第1の集団#1に属するレコードである(図16のレコード群Vにおいて"#1"で示す点線矢印参照)。
【０１８１】
集団Ubにレコード{IP1,80}が追加されている状態を集団Ubのセル内に"集団構成：{IP1,80}"で示す。再配置部102bは、集団Ubにおけるレコード{IP1,80}の集団内情報量0.0を算出する。この算出を集団Ubのセル内に"集団内情報量：0.0"で示す。集団Ubに属するレコード{IP1,80}の変数値は、IP1,80である。この変数値を集団Ubのセル内に"変数値：IP1,80"で示す。
【０１８２】
例えば、第1の集団#1に属するレコード{IP1,80}を集団Ubに再配置することにより、レコード{IP1,80}の第1の集団#1における集団内情報量(1.2)が減少し、集団Ubの集団内情報量は0.0増加する。なお、レコード{IP1,80}の第1の集団#1における集団内情報量は、1.2(-log{(2/13)*(5/13)})である。
【０１８３】
従って、集団Ubにレコード{IP1,80}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図16の集団Ubにおける全集団内情報量は、1.2(1.2-0.0)減少する。この減少を集団Ubのセル内に"減少：1.2-0.0=1.2"で示す。
【０１８４】
第1の集団#1に属するレコード{IP1,80}を集団Ubに再配置しても、変数IP1,80は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP1,80}を集団Ubに再配置しても、変数値は減少しない。この減少しないことを集団Ubのセル内に"#1の減少：0"で示す。
【０１８５】
ここで、レコード{IP1,80}が属する集団Ubの変数値は、2個である。この変数値の個数を集団Ubのセル内に"Uの変数値の数：2"で示す。
【０１８６】
第1の集団#1に属するレコード{IP1,80}を集団Ubに再配置した場合における評価値の改善量は、-0.8(1.2-α×(2-0)、ただしαは1)である。この"1.2"は、集団内情報量の減少値である。この"(2-0)"の"2"は、レコード{IP1,80}が属する集団Ubの変数値の個数であり、この"0"は、変数値の減少である。
【０１８７】
再配置部102bは、集団Ubにおける集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０１８８】
次いで、再配置部102bは、集団Ub内の何れかの変数値を共有するレコードの中で、集団Ubに追加したときの評価値の改善量が最も大きいレコードを、集団Ubに追加する(S34)。例えば、集団Ub内の何れかの変数値(IP1または80)を共有するレコードを{IP1,8080}とする。このレコードは、図14の集団構成テーブルT11における第1の集団#1に属するレコードである。
【０１８９】
集団Ubにレコード{IP1,8080}を追加すると想定する(図16の集団Up11において"#1"で示す点線矢印参照)。集団Ubにレコード{IP1,8080}が追加されている状態を集団Up11のセル内に"集団構成：{IP1,80},{IP1,8080}"で示す。再配置部102bは、集団Up11におけるレコード{IP1,80},{IP1,8080}の集団Up1における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。
【０１９０】
この算出を集団Up11のセル内に"集団内情報量：0.3,0.3"で示す。集団Up11に属するレコード{IP1,80},{IP1,8080}の変数値は、IP1,80,8080である。この変数値を集団Up11のセル内に"変数値：IP1,80,8080"で示す。
【０１９１】
第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up11に再配置することにより、レコード{IP1,80}の第1の集団#1における集団内情報量(1.2)とレコード{IP1,8080}の第1の集団#1における集団内情報量(1.2)が減少する。そして、この再配置により、集団Up11の集団内情報量は0.6(0.3+0.3)増加する。
【０１９２】
従って、集団Up11にレコード{IP1,80},{IP1,8080}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図16の集団Up11における全集団内情報量は、1.8((1.2+1.2)-(0.3+0.3))減少する。この減少を集団Up11のセル内に"減少：(1.2+1.2)-(0.3+0.3)=1.8"で示す。
【０１９３】
図14において、第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up11に再配置すると、変数値IP1と同一変数値IP1が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数80,8080は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up11に再配置すると、変数値は1個減少する。この減少を集団Up11のセル内に"#1の減少：1"で示す。
【０１９４】
ここで、レコード{IP1,80},{IP1,8080}が属する集団Up11の変数値は、3個である。この変数値の個数を集団Up11のセル内に"Uの変数値の数：3"で示す。
【０１９５】
第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up11に再配置した場合における評価値の改善量は、-0.2(1.8-α×(3-1)、ただしαは1)である。
【０１９６】
再配置部102bは、集団Up11における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０１９７】
集団Ubに第1の集団#1に属するレコード{IP2,80}を追加すると想定する(図16の集団Up12において"#1"で示す点線矢印参照)。集団Ubにレコード{IP2,80}が追加されている状態を集団Up2のセル内に"集団構成：{IP1,80},{IP2,80}"で示す。再配置部102bは、レコード{IP1,80},{IP2,80}の集団Up12における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。
【０１９８】
この算出を集団Up12のセル内に"集団内情報量：0.3,0.3"で示す。集団Up12に属するレコード{IP1,80},{IP2,80}の変数値は、IP1,IP2,80である。この変数値を集団Up12のセル内に"変数値：IP1,IP2,80"で示す。
【０１９９】
第1の集団#1に属するレコード{IP1,80},{IP2,80}を集団Up12に再配置することにより、レコード{IP1,80}の第1の集団#1における集団内情報量(1.2)とレコード{IP2,80}の第1の集団#1における集団内情報量(1.2)が減少する。そして、この再配置により、集団Up12の集団内情報量は0.6(0.3+0.3)増加する。なお、レコード{IP2,80}の第1の集団#1における集団内情報量は、1.2(-log{(2/13)*(5/13)})である。
【０２００】
従って、集団Up12にレコード{IP1,80},{IP2,80}を再配置したことにより、図14の集団構成テーブルT11で示す第1の集団#1〜第3の集団#3および図16の集団Up12における全集団内情報量は、1.8((1.2+1.2)-(0.3+0.3))減少する。この減少を集団Up12のセル内に"減少：(1.2+1.2)-(0.3+0.3)=1.8"で示す。
【０２０１】
第1の集団#1に属するレコード{IP1,80},{IP2,80}を集団Up12に再配置しても、変数値IP1,IP2,80と同一変数値IP1,IP2,80が、第1の集団#1内の変数値から含まれなくなることがない。従って、第1の集団#1に属するレコード{IP1,80},{IP2,80}を集団Up12に再配置しても、変数値は減少しない。この減少しないことを集団Up12のセル内に"#1の減少：0"で示す。
【０２０２】
ここで、レコード{IP1,80},{IP2,80}が属する集団Up12の変数値は、3個である。この変数値の個数を集団Up12のセル内に"Uの変数値の数：3"で示す。
【０２０３】
第1の集団#1に属するレコード{IP1,80}、{IP2,80}を集団Up12に再配置した場合における評価値の改善量は、-1.2(1.8-α×(3-0)、ただしαは1)である。
【０２０４】
再配置部102bは、集団Up12における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２０５】
集団Ubにレコード{IP1,8080}を追加した場合の評価値の改善量は-0.2であり、この評価値の改善量が最大である(図16の吹き出し"最大"参照)。そこで、再配置部102bは、レコード{IP1,8080}を、集団Ubに追加する(S34)。
【０２０６】
再配置部102bは、g(gは例えば1)個のレコードを追加したか判定する(S35)。既に、1個のレコードを集団Uaに追加したので(S35/YES)、再配置部102bは、評価値の改善量が最も大きくなるときの集団Up11をレコード集合Q1に加える(S36)。以下、評価値の改善量が最も大きくなるときの集団Up11に含まれる2個のレコードの集団を集団U1bで示す。
【０２０７】
図12、図15、図16で説明したように、再配置部102bは、再配置する1以上のレコードの選択において、相互に変数値を共有しないレコードを、出現確率の逆数の対数(例えば、集団内情報量)が高い順に選択する(S31)。図15、図16の例では、再配置部102bは、レコード{IP7,110},{IP1,80}を含むレコード群Vを選択する(S31)。
【０２０８】
そして、再配置部102bは、選択した第1のレコード(例えば、図15のレコード{IP7,110})をk個の集団以外の他の集団(例えば、図15の集団Ua)に追加する第1の追加処理を実行する(S33)。そして、再配置部102bは、離散データLSD4に含まれるレコードの中から、第1のレコードに含まれる複数の変数値の何れか1つの変数値を含む第2のレコード(例えば、図15のレコード{IP6,110})を選択する(S33)。再配置部102bは、選択した第2のレコードを他の集団Uaに追加する第2の追加処理を実行する(S33)。
【０２０９】
再配置部102bは、他の集団にレコードを追加する度に、第1の合計と第2の合計との減少量を概算する。なお、第1の合計は、レコードの各々の出現確率の逆数の対数(例えば、集団内情報量)の合計である。また、第2の合計は、変数値の各々の共有値の対数の合計である。
【０２１０】
再配置部102bは、この概算においては、例えば、図15の評価値の改善量を算出している。再配置部102bは、最大の減算値を概算した場合の他の集団(例えば、図15のレコード集団U1a)を再配置する1以上のレコードとして選択する。
【０２１１】
最大の減算値を概算した場合の他の集団を再配置する1以上のレコードとして選択することで、評価値の減少量が極大になるレコードを選択することができる。
【０２１２】
再配置部102bは、減少量の概算において、他の集団にレコードを追加する度に、以下の算出処理を実行する。すなわち、再配置部102bは、他の集団に属する1以上の第3のレコードの各々のk個の集団における出現確率の逆数の対数(例えば、集団内情報量)の第1の和を算出する。そして、再配置部102bは、第3のレコードの各々の他の集団における出現確率の逆数の対数(例えば、集団内情報量)の第2の和を算出する。次いで、再配置部102bは、第1の和から第2の和を減算した第1の値を算出する。
【０２１３】
次いで、再配置部102bは、他の集団に含まれる相互に異なる変数値の総数から、第3のレコードの各々を第3のレコードが属する集団から除外した際に、第3のレコードに含まれる変数値が該集団に含まれなくなる場合における該変数値の個数を減算した第2の値を算出する。
【０２１４】
再配置部102bは、第1の値から第2の値を減算した減算値を算出し、この減算値を減少量の概算とする。この減少量の概算は、評価値の改善量である。再配置部102b、減算値の算出において、第1の値から、第2の値に重み付け係数を乗算した値を減算した値を減算値とする。この重み付け係数は、例えば、図15、図16で説明したα(例えば、1)であり、調整可能である。
【０２１５】
ここで、図15の例において、集団Uにレコード{IP7,110}を追加した場合(集団Ua参照)を第1の場合とする。そして、図15の例において、集団Uaにレコード{IP6,110}を追加した場合(集団Up1参照)を第2の場合とする。
【０２１６】
第1の場合、図14、図15の例で示すように、第1の和は集団内情報量(1.8)であり、第2の和は集団内情報量(0.0)であり、第1の値は"減少：1.8-0.0=1.8"である。第1の場合、第3のレコードは、図14の第1の集団#1に属するレコード{IP7,110}である。第1の場合、他の集団Uaに含まれる相互に異なる変数値は、変数値IP7,110であり、この変数値の総数は2("Uの変数値の数：2")である。第1の場合、第3のレコードに含まれる変数値が第1の集団#1に含まれなくなる場合におけるこの変数値の個数は、図15で説明したように、"#1の減少：1"で示す1個である。従って、第1の場合、第2の値は、1(2-1)である。第1の場合、第1の値から第2の値を減算した減算値(すなわち、評価値の改善量)は、"1.8-α(2-1)=0.8"である(αは例えば、1)。
【０２１７】
第2の場合、図14、図15の例で示すように、第1の和は集団内情報量(1.8+1.8)であり、第2の和は集団内情報量(0.3+0.3)であり、第1の値は"減少：(1.8+1.8)-(0.3+0.3)=3.0"である。第2の場合、第3のレコードは、図14の第1の集団#1に属するレコード{IP7,110},{IP6,110},である。第2の場合、他の集団Up1に含まれる相互に異なる変数値は、変数値IP7,IP6,110であり、この変数値の総数は3("Uの変数値の数：3")である。
【０２１８】
第2の場合、第3のレコードに含まれる変数値が第1の集団#1に含まれなくなる場合におけるこの変数値の個数は、図15で説明したように、"#1の減少：2"で示す2個である。従って、第2の場合、第2の値は、1(3-2)である。第2の場合、第1の値(3.0)から第2の値(1.0)を減算した減算値(すなわち、評価値の改善量)は、"3.0-α(3-2)=2.0"である(αは例えば1)。
【０２１９】
再配置部102bは、前記した第1の追加処理において、相互に変数値を共有しないレコードをm(1以上の整数)個選択する(S31)。なお、mをNbと記しても良い。そして、再配置部102bは、出現確率の逆数の対数(例えば、集団内情報量)が高い順に1個のレコードを他の集団に追加する(S32)。第1の追加処理は、前記した第1の場合で説明した。
【０２２０】
次いで、再配置部102bは、前記した第2の追加処理において、g(1以上の整数)個の第2のレコードを他の集団に順次追加して、評価値の改善量が最大になる再配置用の集団(例えば、図15のレコード集団U1a)を生成する(S34)。再配置部102bは、g個の第2のレコードの追加が終了すると(S35/YES)、この他の集団を配置用の集団として記憶部(例えば、RAM12)に記憶する(S36)。そして、再配置部102bは、相互に変数値を共有しない前記Nb個のレコードを全て他の集団に追加するまで、第1、第2の追加処理を繰り返し行う(S33〜S36)。すなわち、再配置部102bは、第1、第2の追加処理を繰り返し行い、相互に変数値を共有しないNb個のレコードを全て他の集団に追加すると、RAM12に記憶した配置用の集団を1以上のレコード(すなわち、再配置の対象となるレコード)として選択する。
【０２２１】
以後、再配置部102bは、選択した1以上のレコード(すなわち、再配置の対象となるレコード)を、集団内情報量の合計と集団間情報量の合計との総合計の減少量が最大になる集団に再配置する。なお、この集団は、第1の集団#1〜第3の集団#3の何れか1つの集団である。
【０２２２】
(再配置するレコード群の取得)
再配置部102bは、レコード群Vから全てのレコード({IP7,110},{IP1,80})を取得したので(S37/YES)、S4に移る。再配置部102bは、レコード集合Q1の中で、評価値の改善量が最も大きいレコード群rgを取得する(S4)。
【０２２３】
図15の例では、最も大きい評価値の改善量は2.0であり、最も大きい評価値の改善量になるときの集団Up1(集団U1a)に属するレコードは、レコード{IP7,110},{IP6,110}である。そして、図16の例では、最も大きい評価値の改善量は-0.2であり、最も大きい評価値の改善量になるときの集団Up11(集団U1b)に属するレコードは、レコード{IP1,80},{IP1,8080}である。
【０２２４】
従って、レコード集合Q1の中で、評価値の改善量が最も大きいレコード群rgは、図15の例において、最も大きい評価値の改善量(2.0)になるときの集団Up1(集団U1a)に属するレコードである。従って、再配置部102bは、レコード群rg(集団U1a)を取得する(S4)。
【０２２５】
(レコード群の再配置)
再配置部102bは、第1の集団#1〜第3の集団#3の中の何れか1個の集団にレコード群rg(集団U1a)を再配置したときに、評価値が最も良くなる集団にレコード群rgを再配置する(S5)。この再配置を、図17〜図19を参照して説明する。
【０２２６】
再配置部102bは、第1の集団#1〜第3の集団#3にレコード群rg(集団U1a)を再配置した場合における各値を算出する。この各値は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計および集団間情報量の総合計、評価値である。
【０２２７】
図17は、第1の集団#1にレコード群rg(集団U1a)を再配置したときの(点線枠参照)、集団構成テーブルT21を示す。なお、集団Xに属するレコード群rgを、同一の集団Xに配置した場合(換言すれば、移動させない場合)も再配置という言葉で説明する。
【０２２８】
集団構成テーブルT21は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(27.2)および集団間情報量の総合計(21.1)、評価値(48.3)を示す。
【０２２９】
図18は、第2の集団#2にレコード群rg(集団U1a)を再配置したときの(点線枠参照)、集団構成テーブルT22を示す。集団構成テーブルT22は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(24.0)および集団間情報量の総合計(21.1)、評価値(45.1)を示す。
【０２３０】
図19は、第3の集団#3にレコード群rg(集団U1a)を再配置したときの(点線枠参照)、集団構成テーブルT23を示す。集団構成テーブルT23は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(25.0)および集団間情報量の総合計(18.9)、評価値(43.9)を示す。
【０２３１】
再配置部102bは、図17〜図19に示したように、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計および集団間情報量の総合計、評価値を算出しRAM12に記憶する。
【０２３２】
図19に示したように、第3の集団#3にレコード群rg(集団U1a)を再配置したときの評価値が、最も良い(換言すれば、最小)。この最小の評価値を、図19の吹き出し"最小"で示す。従って、再配置部102bは、第3の集団#3にレコード群rg(集団U1a)を再配置する(S5)。図19の集団構成テーブルT23の集団構成欄が、図13の集団構成テーブルT2の集団構成欄に対応する。
【０２３３】
再配置部102bは、レコード集合Q1からレコード群rg(集団U1a)を除外する(S6)。レコード群rg(集団U1a)を除外したレコード集合Q1は、集団U1bを含むので、レコード集合Q1は、空集合ではない(S7/NO)。従って、再配置部102bは、S7でNOと判定し、S4に移る。
【０２３４】
再配置部102bは、除外後のレコード集合Q1の中で、評価値の改善量が最も大きいレコード群rgを取得する(S4)。
【０２３５】
図16の例では、最も大きい評価値の改善量は-0.2であり、最も大きい評価値の改善量になるときの集団Up11(集団U1b)に属するレコードは、レコード{IP1,80},{IP1,8080}である。
【０２３６】
従って、レコード集合Q1の中で、評価値の改善量が最も大きいレコード群rgは、最も大きい評価値の改善量(-0.2)になるときの集団Up11(集団U1b)に属するレコード(集団U1b)である。従って、再配置部102bは、レコード群rg(集団U1b)を取得する(S4)。
【０２３７】
再配置部102bは、第1の集団#1〜第3の集団#3の中の何れか1個の集団にレコード群rg(集団U1b)を再配置したときに、評価値が最も良くなる集団にレコード群rgを再配置する(S5)。この再配置を、図20〜図22を参照して説明する。前記したように、再配置部102bは、第1の集団#1〜第3の集団#3にレコード群rg(集団U1b)を再配置した場合における各値を算出する。
【０２３８】
図20は、第1の集団#1にレコード群rg(集団U1b)を再配置したときの(点線枠参照)、集団構成テーブルT31を示す。集団構成テーブルT31は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(25.0)および集団間情報量の総合計(18.9)、評価値(43.9)を示す。
【０２３９】
図21は、第2の集団#2にレコード群rg(集団U1b)を再配置したときの(点線枠参照)、集団構成テーブルT32を示す。集団構成テーブルT32は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(23.7)および集団間情報量の総合計(21.1)、評価値(44.8)を示す。
【０２４０】
図22は、第3の集団#3にレコード群rg(集団U1b)を再配置したときの(点線枠参照)、集団構成テーブルT33を示す。集団構成テーブルT33は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(27.1)および集団間情報量の総合計(21.1)、評価値(48.1)を示す。
【０２４１】
再配置部102bは、図20〜図22に示したように、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計および集団間情報量の総合計、評価値を算出しRAM12に記憶する。
【０２４２】
図20に示したように、第1の集団#1にレコード群rg(集団U1b)を再配置したときの評価値が、最も良い(換言すれば、最小)。この最小の評価値を、図20の吹き出し"最小"で示す。従って、再配置部102bは、第1の集団#1にレコード群rg(集団U1b)を再配置する(S5)。図20の集団構成テーブルT31の集団構成欄が、図13の集団構成テーブルT3の集団構成欄に対応する。
【０２４３】
再配置部102bは、レコード集合Q1からレコード群rg(集団U1b)を除外する(S6)。レコード群rg(集団U1b)を除外したレコード集合Q1は、空集合である(S7/YES)。従って、再配置部102bは、S7でYESと判定し、S8に移る。再配置部102bは、再配置後の評価値e(43.9)を算出する(S8)。
【０２４４】
再配置部102bは、再配置後の評価値e(43.9)は、元の評価値e_pre(図14の評価値48.3参照)未満なので(S9/NO)、S10に移る。
【０２４５】
再配置部102bは、S2〜S3のステップをR回(例えば2回)繰り返したか判定する。図14〜図22の例では、再配置部102bは、S2〜S3のステップを1回実行しているので、S10でNOと判定し、S2に移る。
【０２４６】
再配置部102bは、図20の集団構成テーブルT31を元の集団としてRAM12に記憶し、図20の集団構成テーブルT31の評価値(43.9)を元の評価値e_preとしてRAM12に記憶する(S2)。
【０２４７】
(再配置対象のレコード集合の選択)
次に、図20、図23〜図24を参照して、レコード集合Qの選択(S3)について説明する。再配置部102bは、最新の集団構成テーブルに含まれるレコードの中から、集団内情報量が高い順に、相互に変数値を共有しないm個のレコードを含むレコード群Vを選択する。この最新の集団構成テーブルは、図20の集団構成テーブルT31である。再配置部102bは、図20の集団構成テーブルT31に含まれるレコードの中から、集団内情報量が高い順に、例えば、相互に変数値を共有しないm個のレコード{IP5,110},{IP1,80}を含むレコード群Vを選択する(S31)。このステップでは、mは2である。
【０２４８】
ここで、図20の集団構成テーブルT31において、最大の集団内情報量は、1.6(-log{(3/11)*(1/11)})である。最大の集団内情報量(1.6)を有するレコードは、第1の集団#1に属する1個のレコード{IP5,110}である。従って、再配置部102bは、レコード{IP5,110}を選択する。
【０２４９】
選択されたレコード{IP5,110}の変数値を共有しないレコードであって、かつ、このレコードの集団内情報量が、最大の集団内情報量(1.6)の次に大きい集団内情報量を有するレコードは、例えば、レコード{IP1,80}である。最大の集団内情報量(1.6)の次に大きい集団内情報量は、1. 1(-log{(2/11)*(5/11)})である。従って、再配置部102bは、レコード{IP1,80}を選択する。
【０２５０】
以上の選択処理により、再配置部102bは、2個のレコード{IP5,110}、{IP1,80}を選択する(S31)。そして、再配置部102bは、集合Uを空集合にリセットする(S32)。以下、リセット後の集合Uを集合Ucと記す。図23を参照して、集合Ucの作成について説明する。
【０２５１】
再配置部102bは、2個のレコード{IP5,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1(例えば、{IP5,110})を取得し、集団Ucに追加する(S33)。図23において、レコード{IP5,110}を一点鎖線の枠で示し、この追加を一点鎖線の矢印で示す。なお、レコード{IP5,110}は、図20の集団構成テーブルT31における第1の集団#1に属するレコードである(図23のレコード群Vにおいて"#1"で示す点線矢印参照)。
【０２５２】
集団Ucにレコード{IP5,110}が追加されている状態を集団Ucのセル内に"集団構成：{IP5,110}"で示す。再配置部102bは、レコード{IP5,110}の集団Ucにおける集団内情報量0.0を算出する。なお、レコード{IP5,110}の集団Ucにおける集団内情報量は、0.0(-log{(1/1)*(1/1)})である。
【０２５３】
この算出を集団Ucのセル内に"集団内情報量：0.0"で示す。集団Ucに属するレコード{IP5,110}の変数値は、IP5,110である。この変数値を集団Ucのセル内に"変数値：IP5,110"で示す。
【０２５４】
例えば、第1の集団#1に属するレコード{IP5,110}を集団Ucに再配置することにより、レコード{IP5,110}の第1の集団#1における集団内情報量(1.8)が減少し、集団Ucの集団内情報量は0.0増加する。
【０２５５】
従って、集団Ucにレコード{IP5,110}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図23の集団Ucにおける全集団内情報量は、1.6(1.6-0.0)減少する。この減少を集団Ucのセル内に"減少：1.6-0.0=1.6"で示す。
【０２５６】
図20において、第1の集団#1に属するレコード{IP5,110}を集団Ucに再配置すると、変数値110と同一変数値が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数IP5は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP5,110}を集団Ucに再配置すると、変数値は1個減少する。この減少を集団Ucのセル内に"#1の減少：1"で示す。
【０２５７】
ここで、レコード{IP5,110}が属する集団Ucの変数値は、2個である。この変数値の個数を集団Ucのセル内に"Uの変数値の数：2"で示す。
【０２５８】
第1の集団#1に属するレコード{IP5,110}を集団Ucに再配置した場合における評価値の改善量は、0.6(1.6-α×(2-1)、ただしαは1)である。この"1.6"は、集団内情報量の減少値である。この"(2-1)"の"2"は、レコード{IP5,110}が属する集団Ucの変数値の個数であり、この"1"は、変数値の減少である。
【０２５９】
再配置部102bは、集団Ucにおける集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２６０】
次いで、再配置部102bは、集団Uc内の何れかの変数値を共有するレコードの中で、集団Ucに追加したときの評価値の改善量が最も大きいレコードを、集団Ucに追加する(S34)。再配置部102bは、評価値の改善量が大きくならない場合、このレコードの追加を実行しない。例えば、集団Uc内の何れかの変数値(IP5または110)を共有するレコードを{IP5,80}とする。このレコードは、図20の集団構成テーブルT31における第1の集団#1に属するレコードである(図23の集団Up21において"#1"で示す点線矢印参照)。
【０２６１】
集団Ucに第1の集団#1に属するレコード{IP5,80}を追加すると想定する。集団Ucにレコード{IP5,80}が追加されている状態を集団Up21のセル内に"集団構成：{IP5,110},{IP5,80}"で示す。再配置部102bは、レコード{IP5,110},{IP5,80}の集団Up21における集団内情報量0.3を算出する。この算出式は、-log{(2/2)*(1/2)}である。なお、-log{(2/2)*(1/2)}の値は0.3である。
【０２６２】
この算出を集団Up21のセル内に"集団内情報量：0.3,0.3"で示す。集団Up21に属するレコード{IP5,110},{IP5,80}の変数値は、IP5,80,110である。この変数値を集団Up21のセル内に"変数値：IP5,80,110"で示す。
【０２６３】
第1の集団#1に属するレコード{IP5,110},{IP5,80}を集団Up21に再配置することにより、レコード{IP5,110}の第1の集団#1における集団内情報量(1.6)とレコード{IP5,80}の第1の集団#1における集団内情報量(0.9)が減少する。そして、この再配置により、集団Up21の集団内情報量は0.6(0.3+0.3)増加する。
【０２６４】
従って、集団Up21にレコード{IP5,110},{IP5,80}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図23の集団Up21における全集団内情報量は、1.9((1.6+0.9)-(0.3+0.3))減少する。この減少を集団Up21のセル内に"減少：1.9((1.6+0.9)-(0.3+0.3)=1.9"で示す。
【０２６５】
図20において、レコード{IP5,110},{IP5,80}を第1の集団#1から集団Up21に再配置すると、変数値110と同一変数値110が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数IP5,80は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP5,110},{IP5,80}を集団Up21に再配置すると、変数値は1個減少する。この減少を集団Up21のセル内に"#1の減少：1"で示す。
【０２６６】
ここで、レコード{IP5,110},{IP5,80}が属する集団Up21の変数値は、3個である。この変数値の個数を集団Up21のセル内に"Uの変数値の数：3"で示す。
【０２６７】
第1の集団#1に属するレコード{IP5,110},{IP5,80}を集団Up21に再配置した場合における評価値の改善量は、-0.1(1.9-α×(3-1)、ただしαは1)である。
【０２６８】
再配置部102bは、集団Up21における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２６９】
集団Ucに第3の集団#3に属するレコード{IP6,110}を追加すると想定する(図23の集団Up22において"#3"で示す点線矢印参照)。集団Ucにレコード{IP6,110}が追加されている状態を集団Up22のセル内に"集団構成：{IP5,110},{IP6,110}"で示す。再配置部102bは、レコード{IP5,110},{IP6,110}の集団Up22における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。
【０２７０】
この算出を集団Up22のセル内に"集団内情報量：0.3,0.3"で示す。集団Up22に属するレコード{IP5,110},{IP6,110}の変数値は、IP5,IP6,110である。この変数値を集団Up22のセル内に"変数値：IP5,IP6,110"で示す。
【０２７１】
第1の集団#1に属するレコード{IP5,110}を集団Up22に再配置し、第3の集団#3に属するレコード{IP6,110}を集団Up22に再配置する。この再配置により、レコード{IP5,110}の第1の集団#1における集団内情報量(1.6)とレコード{IP6,110}の第3の集団#3における集団内情報量(1.1)が減少し、、集団Up22の集団内情報量は0.6(0.3+0.3)増加する。なお、レコード{IP6,110}の第3の集団#3における集団内情報量は、1.1(-log{(3/12)*(4/12)})である。
【０２７２】
従って、集団Up22にレコード{IP5,110},{IP6,110}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図23の集団Up22における全集団内情報量は、2.1((1.6+1.1)-(0.3+0.3))減少する。この減少を集団Up22のセル内に"減少：(1.6+1.1)-(0.3+0.3)=2.1"で示す。
【０２７３】
第1の集団#1に属するレコード{IP5,110}を集団Up22に再配置すると、変数値110と同一変数値110が、第1の集団#1内の変数値から含まれなくなる。従って、第1の集団#1に属するレコード{IP5,110}を集団Up22に再配置すると、変数値は1個減少する。この減少を集団Up22のセル内に"#1の減少：1"で示す。
【０２７４】
第3の集団#3に属するレコード{IP6,110}を集団Up22に再配置すると、変数値IP6,110と同一変数値IP6,110が、第3の集団#3内の変数値から含まれなくなることがない。従って、第3の集団#3に属するレコード{IP6,110}を集団Up22に再配置しても、変数値は減少しない。この減少しないことを集団Up22のセル内に"#3の減少：0"で示す。
【０２７５】
ここで、レコード{IP5,110},{IP6,110}が属する集団Up22の変数値は、3個である。この変数値の個数を集団Up22のセル内に"Uの変数値の数：3"で示す。
【０２７６】
第1の集団#1に属するレコード{IP5,110}、第3の集団#3に属するレコード{IP6,110}を集団Up22に再配置した場合における評価値の改善量は、0.1(2.1-α×(3-1-0)、ただしαは1)である。
【０２７７】
再配置部102bは、集団Up22における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２７８】
以上説明したように、レコード{IP5,80}、{IP6,110}を集団Ucに追加しても、レコード{IP5,80}、{IP6,110}を追加しない場合における集団Ucの評価値の改善量(0.6)よりも評価値の改善量が大きくなることがない。すなわち、集団Ucの評価値の改善量(0.6)が最大である(図23の吹き出し"最大"参照)。そこで、再配置部102bは、レコード{IP5,80}、{IP6,110}を、集団Ucに追加しない。
【０２７９】
再配置部102bは、g(gは例えば1)個のレコードを追加したか判定する(S35)。既に、1個のレコードをUaに追加したので(S35/YES)、再配置部102bは、評価値の改善量が最も大きくなるときの集団Ucをレコード集合Q2に加える(S36)。以下、評価値の改善量が最も大きくなるときの集団Ucに含まれる1個のレコードの集団を集団U2aで示す。
【０２８０】
再配置部102bは、2個のレコード{IP5,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1({IP5,110})を取得しているので、レコード群Vから全てのレコードを取得していない(S37/NO)。従って、再配置部102bは、集合Uを空集合にリセットする(S32)。以下、リセット後の集合Uを集合Udと記す。図24を参照して、集合Udの作成について説明する。
【０２８１】
再配置部102bは、2個のレコード{IP5,110}、{IP1,80}を含むレコード群Vから順に1個のレコードr1(例えば、{IP1,80})を取得し、集団Udに追加する(S33)。図24において、レコード{IP1,80}を一点鎖線の枠で示し、この追加を一点鎖線の矢印で示す。なお、レコード{IP1,80}は、図20の集団構成テーブルT31における第1の集団#1に属するレコードである(図24のレコード群Vにおいて"#1"で示す点線矢印参照)。
【０２８２】
集団Udにレコード{IP1,80}が追加されている状態を集団Udのセル内に"集団構成：{IP1,80}"で示す。再配置部102bは、集団Udにおけるレコード{IP1,80}の集団内情報量0.0を算出する。この算出を集団Udのセル内に"集団内情報量：0.0"で示す。集団Udに属するレコード{IP1,80}の変数値は、IP1,80である。この変数値を集団Udのセル内に"変数値：IP1,80"で示す。
【０２８３】
例えば、第1の集団#1に属するレコード{IP1,80}を集団Udに再配置することにより、レコード{IP1,80}の集団内情報量(1.1)が減少し、集団Udの集団内情報量は0.0増加する。なお、レコード{IP1,80}の第1の集団#1における集団内情報量は、1.1(-log{(2/11)*(5/11)})である。
【０２８４】
従って、集団Udにレコード{IP1,80}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図24の集団Udにおける全集団内情報量は、1.1(1.1-0.0)減少する。この減少を集団Udのセル内に"減少：1.1-0.0=1.1"で示す。
【０２８５】
第1の集団#1に属するレコード{IP1,80}を集団Udに再配置しても、変数IP1,80は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP1,80}を集団Udに再配置しても、変数値は減少しない。この減少しないことを集団Udのセル内に"#1の減少：0"で示す。
【０２８６】
ここで、レコード{IP1,80}が属する集団Udの変数値は、2個である。この変数値の個数を集団Udのセル内に"Uの変数値の数：2"で示す。
【０２８７】
第1の集団#1に属するレコード{IP1,80}を集団Udに再配置した場合における評価値の改善量は、-1.1(1.1-α×(2-0)、ただしαは1.1)である。再配置部102bは、このαを適宜調整可能である。この"1.1"は、集団内情報量の減少値である。この"(2-0)"の"2"は、レコード{IP1,80}が属する集団Udの変数値の個数であり、この"0"は、変数値の減少である。
【０２８８】
再配置部102bは、集団Udにおける集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２８９】
次いで、再配置部102bは、集団Ud内の何れかの変数値を共有するレコードの中で、集団Udに追加したときの評価値の改善量が最も大きいレコードを、集団Udに追加する(S34)。例えば、集団Ud内の何れかの変数値(IP1または80)を共有するレコードを{IP1,8080}とする。このレコードは、図20の集団構成テーブルT31における第1の集団#1に属するレコードである。
【０２９０】
集団Udにレコード{IP1,8080}を追加すると想定する(図24の集団Up31において"#1"で示す点線矢印参照)。集団Udにレコード{IP1,8080}が追加されている状態を集団Up31のセル内に"集団構成：{IP1,80},{IP1,8080}"で示す。再配置部102bは、集団Up31におけるレコード{IP1,80},{IP1,8080}の集団Up31における集団内情報量0.3を算出する。この算出式は、-log{(2/2)*(1/2)}である。なお、-log{(2/2)*(1/2)}の値は0.3である。
【０２９１】
この算出を集団Up31のセル内に"集団内情報量：0.3,0.3"で示す。集団Up31に属するレコード{IP1,80},{IP1,8080}の変数値は、IP1,80,8080である。この変数値を集団Up31のセル内に"変数値：IP1,80,8080"で示す。
【０２９２】
第1の集団#1に属するレコードをレコード{IP1,80},{IP1,8080}を集団Up31に再配置することにより、レコード{IP1,80}の第1の集団#1における集団内情報量(1.1)とレコード{IP1,8080}の第1の集団#1における集団内情報量(1.1)が減少する。そして、この再配置により、集団Up31の集団内情報量は0.6(0.3+0.3)増加する。従って、集団Up31にレコード{IP1,80},{IP1,8080}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図24の集団Up31における全集団内情報量は、1.6((1.1+1.1)-(0.3+0.3))減少する。この減少を集団Up31のセル内に"減少：(1.1+1.1)-(0.3+0.3)=1.6"で示す。
【０２９３】
図20において、第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up31に再配置すると、変数値IP1と同一変数値IP1が、第1の集団#1内の変数値から含まれなくなる。しかし、この再配置をしても、変数80,8080は、第1の集団#1内の変数値に含まれる。従って、第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up31に再配置すると、変数値は1個減少する。この減少を集団Up31のセル内に"#1の減少：1"で示す。
【０２９４】
ここで、レコード{IP1,80},{IP1,8080}が属する集団Up31の変数値は、3個である。この変数値の個数を集団Up31のセル内に"Uの変数値の数：3"で示す。
【０２９５】
第1の集団#1に属するレコード{IP1,80},{IP1,8080}を集団Up31に再配置した場合における評価値の改善量は、-0.6(1.6-α×(3-1)、ただしαは1.1)である。
【０２９６】
再配置部102bは、集団Up31における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０２９７】
集団Udに第1の集団#1に属するレコード{IP2,80}を追加すると想定する(図24の集団Up32において"#1"で示す点線矢印参照)。集団Udにレコード{IP2,80}が追加されている状態を集団Up32のセル内に"集団構成：{IP1,80},{IP2,80}"で示す。再配置部102bは、レコード{IP1,80},{IP2,80}の集団Up32における集団内情報量0.3を算出する。この算出式は、-log{(1/2)*(2/2)}である。なお、-log{(1/2)*(2/2)}の値は0.3である。この算出を集団Up32のセル内に"集団内情報量：0.3,0.3"で示す。集団Up32に属するレコード{IP1,80},{IP2,80}の変数値は、IP1,IP2,80である。この変数値を集団Up32のセル内に"変数値：IP1,IP2,80"で示す。
【０２９８】
レコード{IP1,80},{IP2,80}を第1の集団#1から集団Up32に再配置する。この再配置により、レコード{IP1,80}の第1の集団#1における集団内情報量(1.1)とレコード{IP2,80}の第1の集団#1における集団内情報量(1.1)が減少し、集団Up32の集団内情報量は0.6(0.3+0.3)増加する。なお、レコード{IP2,80}の第1の集団#1における集団内情報量は、1.1(-log{(2/11)*(5/11)})である。
【０２９９】
従って、集団Up32にレコード{IP1,80},{IP2,80}を再配置したことにより、図20の集団構成テーブルT31で示す第1の集団#1〜第3の集団#3および図24の集団Up32における全集団内情報量は、1.6((1.1+1.1)-(0.3+0.3))減少する。この減少を集団Up32のセル内に"減少：(1.1+1.1)-(0.3+0.3)=1.6"で示す。
【０３００】
第1の集団#1に属するレコード{IP1,80},{IP2,80}を集団Up32に再配置すると、変数値IP1,IP2,80と同一変数値IP1,IP2,80が、第1の集団#1内の変数値から含まれなくなることがない。従って、第1の集団#1に属するレコード{IP1,80},{IP2,80}を集団Up32に再配置しても、変数値は減少しない。この減少しないことを集団Up32のセル内に"#1の減少：0"で示す。
【０３０１】
ここで、レコード{IP1,80},{IP2,80}が属する集団Up32の変数値は、3個である。この変数値の個数を集団Up32のセル内に"Uの変数値の数：3"で示す。
【０３０２】
第1の集団#1に属するレコード{IP1,80}、{IP2,80}を集団Up32に再配置した場合における評価値の改善量は、-1.7(1.6-α×(3-0)、ただしαは1.1)である。
【０３０３】
再配置部102bは、集団Up32における集団内情報量の算出、評価値の改善量の算出を実行し、算出結果をRAM12に記憶する。
【０３０４】
以上説明したように、集団Udにレコード{IP1,8080}を追加した場合の評価値の改善量は-0.6であり、この評価値の改善量が最大である(図24の吹き出し"最大"参照)。そこで、再配置部102bは、レコード{IP1,8080}を、集団Udに追加する(S34)。
【０３０５】
再配置部102bは、g(gは例えば1)個のレコードを追加したか判定する(S35)。既に、1個のレコードを集団Udに追加したので(S35/YES)、再配置部102bは、評価値の改善量が最も大きくなるときの集団Up31をレコード集合Q2に加える(S36)。以下、評価値の改善量が最も大きくなるときの集団Up31に含まれる2個のレコードの集団を集団U2bで示す。
【０３０６】
(再配置するレコード群の取得)
再配置部102bは、レコード群Vから全てのレコード({IP5,110},{IP1,80})を取得したので(S37/YES)、S4に移る。再配置部102bは、レコード集合Q2の中で、評価値の改善量が最も大きいレコード群rgを取得する(S4)。
【０３０７】
図23の例では、最も大きい評価値の改善量は0.6であり、最も大きい評価値の改善量になるときの集団Uc(集団U2a)に属するレコードは、レコード{IP5,110}である。そして、図24の例では、最も大きい評価値の改善量は-0.6であり、最も大きい評価値の改善量になるときの集団Up31(集団U2b)に属するレコードは、レコード{IP1,80},{IP1,8080}である。
【０３０８】
従って、レコード集合Q2の中で、評価値の改善量が最も大きいレコード群rgは、図23の例において、最も大きい評価値の改善量(0.6)になるときの集団Uc(集団U2a)である。従って、再配置部102bは、レコード群rg(集団U2a)を取得する(S4)。
【０３０９】
(レコード群の再配置)
再配置部102bは、第1の集団#1〜第3の集団#3の中の何れか1個の集団にレコード群rg(集団U2a)を再配置したときに、評価値が最も良くなる集団にレコード群rgを再配置する(S5)。この再配置を、図25〜図27を参照して説明する。前記したように、再配置部102bは、第1の集団#1〜第3の集団#3にレコード群rg(集団U2a)を再配置した場合における各値を算出する。
【０３１０】
図25は、第1の集団#1にレコード群rg(集団U2a)を再配置したときの(点線枠参照)、集団構成テーブルT41を示す。集団構成テーブルT41は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(25.0)および集団間情報量の総合計(18.9)、評価値(43.9)を示す。
【０３１１】
図26は、第2の集団#2にレコード群rg(集団U2a)を再配置したときの(点線枠参照)、集団構成テーブルT42を示す。集団構成テーブルT42は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(23.6)および集団間情報量の総合計(19.1)、評価値(42.7)を示す。
【０３１２】
図27は、第3の集団#3にレコード群rg(集団U2a)を再配置したときの(点線枠参照)、集団構成テーブルT43を示す。集団構成テーブルT43は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(24.9)および集団間情報量の総合計(19.1)、評価値(44.0)を示す。
【０３１３】
再配置部102bは、図25〜図27に示したように、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計および集団間情報量の総合計、評価値を算出しRAM12に記憶する。
【０３１４】
図26に示したように、第2の集団#2にレコード群rg(集団U2a)を再配置したときの評価値が、最も良い(換言すれば、最小)。この最小の評価値を、図26の吹き出し"最小"で示す。従って、再配置部102bは、第2の集団#2にレコード群rg(集団U2a)を再配置する(S5)。図26の集団構成テーブルT42の集団構成欄が、図13の集団構成テーブルT4の集団構成欄に対応する。
【０３１５】
再配置部102bは、レコード集合Q2からレコード群rg(集団U2a)を除外する(S6)。レコード群rg(集団U2a)を除外したレコード集合Q2は、集団U2bを含むので、レコード集合Q2は、空集合ではない(S7/NO)。従って、再配置部102bは、S7でNOと判定し、S4に移る。
【０３１６】
再配置部102bは、除外後のレコード集合Q2の中で、評価値の改善量が最も大きいレコード群rgを取得する(S4)。
【０３１７】
図24の例では、最も大きい評価値の改善量は-0.6であり、最も大きい評価値の改善量になるときの集団Up31(集団U2b)に属するレコードは、レコード{IP1,80},{IP1,8080}である。
【０３１８】
従って、レコード集合Q2の中で、評価値の改善量が最も大きいレコード群rgは、最も大きい評価値の改善量(-0.6)になるときの集団Up31(集団U2b)に属するレコードである。従って、再配置部102bは、レコード群rg(集団U2b)を取得する(S4)。前記したように、再配置部102bは、第1の集団#1〜第3の集団#3にレコード群rg(集団U1a)を再配置した場合における各値を算出する。
【０３１９】
再配置部102bは、第1の集団#1〜第3の集団#3の中の何れか1個の集団にレコード群rg(集団U2b)を再配置したときに、評価値が最も良くなる集団にレコード群rgを再配置する(S5)。この再配置を、図28〜図30を参照して説明する。前記したように、再配置部102bは、第1の集団#1〜第3の集団#3にレコード群rg(集団U2b)を再配置した場合における各値を算出する。
【０３２０】
図28は、第1の集団#1にレコード群rg(集団U2b)を再配置したときの(点線枠参照)、集団構成テーブルT51を示す。集団構成テーブルT51は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(23.6)および集団間情報量の総合計(19.1)、評価値(42.7)を示す。
【０３２１】
図29は、第2の集団#2にレコード群rg(集団U2b)を再配置したときの(点線枠参照)、集団構成テーブルT52を示す。集団構成テーブルT52は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(23.8)および集団間情報量の総合計(19.9)、評価値(43.7)を示す。
【０３２２】
図30は、第3の集団#3にレコード群rg(集団U2b)を再配置したときの(点線枠参照)、集団構成テーブルT53を示す。集団構成テーブルT53は、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計(26.4)および集団間情報量の総合計(21.3)、評価値(47.7)を示す。
【０３２３】
再配置部102bは、図28〜図30に示したように、全レコードの集団内情報量および集団間情報量、各集団における集団内情報量の合計および集団間情報量の合計、集団内情報量の総合計および集団間情報量の総合計、評価値を算出しRAM12に記憶する。
【０３２４】
図28に示したように、第1の集団#1にレコード群rg(集団U2b)を再配置したときの評価値が、最も良い(換言すれば、最小)。この最小の評価値を、図20の吹き出し"最小"で示す。従って、再配置部102bは、第1の集団#1にレコード群rg(集団U2b)を再配置する(S5)。図28の集団構成テーブルT51の集団構成欄が、図13の集団構成テーブルT5の集団構成欄に対応する。
【０３２５】
再配置部102bは、レコード集合Q2からレコード群rg(集団U2b)を除外する(S6)。レコード群rg(集団U2b)を除外したレコード集合Q2は、空集合である(S7/YES)。従って、再配置部102bは、S7でYESと判定し、S8に移る。再配置部102bは、再配置後の評価値e(42.7)を算出する(S8)。
【０３２６】
再配置部102bは、再配置後の評価値e(42.7)は、元の評価値e_pre(図20の評価値43.9参照)未満なので(S9/NO)、S10に移る。
【０３２７】
再配置部102bは、S2〜S3のステップをR回(例えば2回)繰り返したか判定する。図14〜図22の例では、再配置部102bは、S2〜S3のステップを2回実行しているので、S10でYESと判定し、処理を終了する。
【０３２８】
再配置部102bは、再配置後の集団を示す図28の集団構成テーブルT51を出力部103に入力する。出力部103は、図28の集団構成テーブルT51に示す集団欄に記憶した集団識別子と、この集団識別子により識別される集団に属するレコードを端末装置TAに出力する。換言すれば、再配置部104は、図28の集団構成テーブルT51に示す、集団欄に記憶した集団識別子と集団構成欄に記憶した分類されたレコードとを、端末装置TAに出力する。
【０３２９】
以上説明したように、本実施の形態のデータ分類装置は、集団内情報量だけでなく、集団間情報量をも考慮した離散データの分類処理を実行している。その結果、分析者の目的を容易に達成できる最適な集団に離散データを分類できる。
【０３３０】
また、本実施の形態のデータ分類装置は、評価値の減少量が最も大きくなると概算できる1以上のレコードを選択し、選択した1つ以上のレコードを再配置用のレコードとしている(図12のS36、図15、図16、図23、図24参照)。
【０３３１】
一方、再配置するレコード群をランダムに作成し、作成したレコード群を、評価値が最も小さくなるように集団(例えば、第1の集団#1〜第3の集団#3)に再配置する方法も考えられる。しかし、多数のレコードに対してかかる方法を実行すると、計算量が膨大になり、現実的ではない。しかし、本実施の形態のデータ分類装置は、評価値の減少量が最も大きくなると概算できる1以上のレコードを選択し、その後、選択した1以上のレコードを評価値が最も小さくなるように集団に再配置している。従って、計算量の増大を抑制でき、処理負荷を削減できる。
【０３３２】
また、本実施の形態のデータ分類装置は、再配置用のレコードを複数個選択することができる。そのため、異なる集団に属する同一変数値の数(共有数)がなるべく少なくなるように分類できる。
【０３３３】
例えば、複数のレコードを含むレコード群が、ある集団に併合されていまうと、図2〜図7で説明した一方法により離散データを分類した場合、異なる集団に属する同一変数値の数の増加を抑制できなくなる。その結果、ある集団に属する前記したレコード群を他の集団に配置することが困難になる。しかし、再配置用のレコードを複数個選択することができるので、前記した同一変数値の数の増加を抑制できる。
【０３３４】
以上の実施の形態をまとめると、次の付記のとおりである。
【０３３５】
（付記１）
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得する取得部と、
前記取得部により取得された前記データに含まれる複数のレコードを複数のグループに分類する分類部とを有し、
前記分類部は、グループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類する
ことを特徴とするデータ分類装置。
【０３３６】
（付記２）
前記分類部は、前記グループに属するレコードに含まれる変数値の当該グループにおける出現確率に基づき算出した、当該レコードの当該グループにおける出現確率が多くなり、かつ、前記共有値が少なくなるように、前記複数のレコードを前記複数のグループに分類する
ことを特徴とする付記1に記載のデータ分類装置。
【０３３７】
（付記３）
前記分類部は、前記複数のレコードの分類において、前記レコードの各々の出現確率の逆数の合計を算出し、さらに、前記異なる集団に属する同一変数値の数と前記集団の各々に属する相互に異なる変数値の総数とに基づき算出した前記共有値を、前記集団の各々に属する変数値の各々について算出し、前記レコードの各々の出現確率の逆数の合計と前記変数値の各々の共有値の合計との総合計が少なくなるように、前記複数のレコードを前記複数の集団に分類する
ことを特徴とする付記2に記載のデータ分類装置。
【０３３８】
（付記４）
前記分類部は、前記複数のレコードの分類において、前記レコードの各々の出現確率の逆数の対数の第1の合計を算出し、さらに、前記変数値の各々の共有値の対数の第2の合計を算出し、前記第1の合計と前記第2の合計との総合計が少なくなるように、前記複数のレコードを前記複数のグループに分類する
ことを特徴とする付記3に記載のデータ分類装置。
【０３３９】
（付記５）
前記分類部は、
前記複数のレコードの分類において、前記取得部により取得された前記データに含まれる複数のレコードの中から、相互に共有する変数値が少なくなるようにNa(Naは2以上の整数)個のレコードをランダムに選択してNa個のグループを生成し、前記グループに属するレコードが当該グループに出現する出現確率が多くなるように、前記複数のレコードにおいて前記Na個のレコード以外のレコードを、前記Na個のグループに配置したグループを生成する生成部と、
前記複数のレコードの分類において、前記Na個のグループに属するレコードの中から、レコードを異なるグループに配置した場合に、前記第1の合計と前記第2の合計との総合計の減少量が最大になる1以上のレコードを選択し、選択した前記1以上のレコードを、選択した前記1以上のレコードが属する第1のグループから、前記第1の合計と前記第2の合計との総合計の減少量が最大になる第2のグループに配置する配置部とを有する
ことを特徴とする付記4に記載のデータ分類装置。
【０３４０】
（付記６）
前記配置部は、
前記1以上のレコードの選択において、相互に変数値を共有しないレコードを、前記出現確率の逆数の対数が高い順に選択し、選択した第1のレコードを前記Na個のグループ以外の他のグループに追加する第1の追加処理を実行し、さらに、前記データに含まれるレコードの中から、前記第1のレコードに含まれる複数の変数値の何れか1つの変数値を含む第2のレコードを選択し、選択した前記第2のレコードを前記他のグループに追加する第2の追加処理を実行し、
前記他のグループにレコードを追加する度に、前記減少量を概算し、最大の減算値を概算した場合の前記他のグループを前記1以上のレコードとして選択する
ことを特徴とする付記5に記載のデータ分類装置。
【０３４１】
（付記７）
前記配置部は、前記減少量の概算において、前記他のグループにレコードを追加する度に、前記他のグループに属する1以上の第3のレコードの各々の前記Na個のグループにおける出現確率の逆数の対数の和から当該第3のレコードの各々の前記他のグループにおける出現確率の逆数の対数の和を減算した第1の値を算出し、前記他のグループに含まれる相互に異なる変数値の総数から、前記第3のレコードの各々を当該第3のレコードが属する前記グループから除外した際に当該第3のレコードに含まれる変数値が当該グループに含まれなくなる場合における当該変数値の個数を減算した第2の値を算出し、前記第1の値から前記第2の値を減算した減算値を算出し、当該減算値を前記減少量の概算とする
ことを特徴とする付記6に記載のデータ分類装置。
【０３４２】
（付記８）
前記配置部は、
前記第1の追加処理において、相互に変数値を共有しないレコードを、前記Na個のグループに属する複数のレコードの中からNb(Nbは1以上の整数)個選択し、前記記出現確率の逆数の対数が高い順に1個のレコードを前記他のグループに追加し、
前記第2の追加処理において、Nc(Ncは1以上の整数)個の前記第2のレコードを他のグループに追加し、前記Nc個の前記第2のレコードの追加が終了すると当該他のグループを配置用のグループとして記憶部に記憶して当該他のグループを空集合にし、
さらに、前記第1、第2の追加処理を繰り返し行い、前記1以上のレコードの選択において、前記相互に変数値を共有しない前記Nb個のレコードを全て前記他のグループに追加すると、前記記憶部に記憶した前記配置用のグループを前記1以上のレコードとして選択する
ことを特徴とする付記7に記載のデータ分類装置。
【０３４３】
（付記９）
前記配置部は、前記減算値の算出において、前記第1の値から、前記第2の値に重み付け係数を乗算した値を減算した値を前記減算値とする
ことを特徴とする付記7に記載のデータ分類装置。
【０３４４】
（付記１０）
前記分類部は、前記レコードの出現確率の算出において、当該レコードが属するグループに属するレコードに含まれる変数値の各々の当該グループにおける出現確率の積を算出し、前記積の算出値を当該レコードの出現確率とする
ことを特徴とする付記3に記載のデータ分類装置。
【０３４５】
（付記１１）
前記分類部は、前記変数値の共有値の算出において、当該変数値を含むグループの数を、各グループに属している相互に異なる変数値の個数の合計で除算した値の逆数を、前記変数値の共有値とする
ことを特徴とする付記4に記載のデータ分類装置。
【０３４６】
（付記１２）
コンピュータに、
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得し、
取得された前記データに含まれる複数のレコードを複数のグループに分類する処理において、グループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類する
処理を実行させることを特徴とするデータ分類プログラム。
【０３４７】
（付記１３）
複数の種類の変数値を其々が含む複数のレコードを含むデータを取得し、
取得された前記データに含まれる複数のレコードを複数のグループに分類する処理において、グループ間の変数値の共有の程度を示す共有値に基づき、前記複数のレコードを前記複数のグループに分類する
ことを特徴とするデータ分類方法。
【符号の説明】
【０３４８】
DV…データ分類装置、11…CPU、12…RAM、13…ROM、14…通信装置、15…ストレージ装置、16…外部記憶媒体読み取り装置、101…入力部、102…分類部、102a…集団生成部、102b…再配置部、103…出力部。
【図１】
0006600939.tif 000002
【図２】
0006600939.tif 000003
【図３】
0006600939.tif 000004
【図４】
0006600939.tif 000005
【図５】
0006600939.tif 000006
【図６】
0006600939.tif 000007
【図７】
0006600939.tif 000008
【図８】
0006600939.tif 000009
【図９】
0006600939.tif 000010
【図１０】
0006600939.tif 000011
【図１１】
0006600939.tif 000012
【図１２】
0006600939.tif 000013
【図１３】
0006600939.tif 000014
【図１４】
0006600939.tif 000015
【図１５】
0006600939.tif 000016
【図１６】
0006600939.tif 000017
【図１７】
0006600939.tif 000018
【図１８】
0006600939.tif 000019
【図１９】
0006600939.tif 000020
【図２０】
0006600939.tif 000021
【図２１】
0006600939.tif 000022
【図２２】
0006600939.tif 000023
【図２３】
0006600939.tif 000024
【図２４】
0006600939.tif 000025
【図２５】
0006600939.tif 000026
【図２６】
0006600939.tif 000027
【図２７】
0006600939.tif 000028
【図２８】
0006600939.tif 000029
【図２９】
0006600939.tif 000030
【図３０】
0006600939.tif 000031