JP2001167098A - 大量データの分散並列分析方法 - Google Patents

Abstract

(57)【要約】 【課題】大量のデータから知識を発見するデータマイニ
ングの並列分散処理方法に関しては、従来、データを分
割して複数の処理装置に分配するので、処理装置間で分
析対象データの転送が必要となったり、並列分散処理方
法を実行するためには、前処理としてデータベースから
各処理装置へデータを分配する必要があるという問題が
ある。また、処理装置に大容量の主記憶が必要であると
いう問題がある。 【解決手段】単数、または複数のデータ格納手段、分析
結果集計手段、複数のデータ分析手段を用いる。データ
格納手段は分析対象データを一回送信し、複数のデータ
分析手段がこれを受信する。各々のデータ分析手段は受
信したデータを対象として分析を行い、その後、それぞ
れのデータ分析手段において得られた分析結果を分析結
果集計手段が集計し、全体の分析結果とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、大量のデータを対
象とするデータ分析技術に関する。

【０００２】

【従来の技術】大量のデータから知識を発見する技術は
データマイニングと呼ばれている。発見される知識の具
体例として、相関ルール（Association Rule）がよく知
られている。相関ルールの基本的概念は文献「Mining A
ssociation Rules between Setof Items in Large Data
bases」（proceeding of ACM SIGMOD、1993）に説明さ
れている。それによれば、 I_1 から I_m までの m 個
の二値属性（アイテムと呼ばれ、0 か 1 の一方の値を
持つ）と、アイテムに対応する m 個の要素からなる二
値ベクトル（トランザクションと呼ばれる）と、このト
ランザクションの集合 T を考えた時、相関ルールは「X
→ I_j」と記述される。ここで、X は I_1から I_m ま
での m 個のアイテムのうちのいくつかからなるアイテ
ムの集合（アイテムセットと呼ばれる）、 I_j は X に
含まれない単一のアイテムである。１つのトランザクシ
ョン t と、１つのアイテム i を考えた時、 t の要素
のうち、i に対応するものの値が 1 であれば、トラン
ザクション t は アイテム i を満足すると言い、 t が
アイテムセット X に含まれる全てのアイテムを満足す
る時、トランザクション t はアイテムセット X を満足
すると言う。トランザクション集合 T において、アイ
テムセット X を満足するトランザクションの数を K、
アイテムセット X を満足し、かつアイテム I_j をも満
足するトランザクションの数を J とした時、割合 J/K
を相関ルール「X → I_j」の「コンフィデンス」と呼
ぶ。また、トランザクション集合 T の全体に対する上
記 J の割合を相関ルール「X → I_j」の「サポート」
と呼ぶ。また、トランザクション集合 T の全体に対す
る上記 K の割合をアイテムセット X の「サポート」と
呼ぶ。

【０００３】アイテムセット X、アイテム I_j の組合
せは多数ある得るが、その中から、与えられた最小コン
フィデンス c、および最小サポート s 以上のコンフィ
デンスとサポートを持つ相関ルールを発見するための基
本的な手法について文献「Fast Algorithms for Mining
Association Rules」（Proceedings of VLDB、1994）
に述べられている。この文献では、 n 個のアイテムか
らなるアイテムセットのうち、最小サポート s 以上の
サポートを持つものの集合をラージアイテム集合 L_n
と呼び、 L_(k-1) を元に L_k を得る処理を１つのパス
とし、 k の値を1 ずつ増加させながら、新たなラージ
アイテム集合が得られなくなるまでパスを繰り返すこと
によって最小サポート s を満たすアイテムセットの集
合を求める。

【０００４】L_(k-1) を元に L_k を得るには、まず、
L_(k-1) に含まれるうちの k 個のアイテムからなる可
能な全てのアイテムセットを作成し、これらアイテムセ
ットの集合を候補アイテム集合 C_k とし、次にトラン
ザクション集合 T を走査し、C_k のそれぞれのアイテ
ムセットについてアイテムセットを満足するトランザク
ションの数を数え上げ、それによってサポートの値を算
出する。候補アイテム集合 C_k のうちで s 以上のサポ
ートを持つアイテムセットの集合を新たなラージアイテ
ム集合 L_k とする。この処理を、新たなラージアイテ
ム集合が得られなくなるまでパスを繰り返す。ラージア
イテム集合が得られた後、これに含まれるアイテムセッ
トのそれぞれにおいて、含まれるアイテムを用いて作成
可能な相関ルールについてそのコンフィデンスを算出
し、最小コンフィデンス c を満たす相関ルールを選び
出す。こうして得られた相関ルールが最終的な結果とな
る。

【０００５】上記の基本的アルゴリズムを計算機で実行
する際には、トランザクションの集合を２次記憶に保持
し、候補アイテム集合を満たすトランザクションの数を
数え上げるカウンタを主記憶に保持することになる。こ
の時、２つの問題点がある。１つは、１回のパスを実行
するごとにトランザクション集合全体を走査するため、
２次記憶からのデータの読み出しに多くの処理時間を費
やしてしまうという点である。もう１つは、与えられた
トランザクション集合に現れるアイテムの数によって
は、候補アイテム集合が非常に大きくなり、カウンタを
保持するために大容量の主記憶が必要となる点である。
これらの問題を解決するための並列分散処理方法が文献
「Parallel Mining of Association Rules」（IEEE Tra
nsactions on Knowledge and Data Engineering、199
6）に述べられている。この文献には３つの並列アルゴ
リズムが説明されている。これら３つのアルゴリズムは
いずれも、複数の処理装置を有し、トランザクション集
合は分割されて各処理装置に局所的な２次記憶に分配さ
れて保持されることを前提としている。第１の並列アル
ゴリズムは「Count Distribution」と呼ばれ、候補アイ
テム集合のサポートの算出の際のトランザクション集合
の走査を複数の処理装置で並列に行うことによってデー
タの読み出しに要する時間を短縮することが可能であ
る。（しかし、候補アイテム集合のサポートを算出する
際のカウンタを各々の処理装置で全て保持するので、大
容量の主記憶が要求されると言う点は解決されない。）
第２の並列アルゴリズムは「Data Distribution」と呼
ばれ、カウンタを複数の処理装置に分配して保持するこ
とによって、各処理装置において必要となる主記憶量を
削減することが可能である。（しかし、各処理装置に分
配されたトランザクションを処理装置間で転送する必要
があるという別の問題が生じる。）また、 Count Distr
ibution、Data Distribution ともに、各々の処理装置
で得られた候補アイテム集合のサポートを１回のパスご
とに集計するので、処理装置ごとの処理時間に差がある
場合、１回のパスごとに最も遅い処理装置の終了を待た
ねばならず、処理時間の無駄が生じるという問題もあ
る。第３の並列アルゴリズムは「Candidate Distributi
on」と呼ばれ、この問題を解決することを目的としてい
る。あるアイテムセットを満たすトランザクションの集
合をサポートトランザクション集合と呼ぶことにする。

【０００６】Candidate Distribution アルゴリズムで
は途中のパスm（m はヒューリスティックに決定する）
において、候補アイテム集合 C_m に含まれるアイテム
セットをグループ分けする。この時、異なるグループに
属するアイテムセットの間でサポートトランザクション
集合がなるべく重ならないようにする。このグループ分
けにしたがって候補アイテム集合と、そのサポートトラ
ンザクション集合を複数の処理装置へ分配し直す。これ
により、各々の処理装置へ分配されたトランザクション
のみの走査で以降のパスにおけるラージアイテム集合を
得ることができ、全ての処理装置がパスごとに同期を取
る必要がなくなる。

【０００７】相関ルール以外のデータマイニング手法と
して、特徴ルール（CharacteristicRule）と、その発見
法が文献「Characteristic Rule Induction Algorithm
forData Mining」（proceedings of PAKDD、1998）に述
べられている。この文献では、複数のフィールドからな
るレコードの集合を分析対象データとしている。特徴ル
ールは「if A then B」と記述される。 A は１個以上の
条件の組合せ、B は単一の条件である。ここで言う「条
件」とは、フィールドとその値の組であり、例えば、
「X_i」をフィールド、「v_ij」を値とすれば、これら
を組にした物は条件であり、「X_i = v_ij」と記述され
る。また、分析対象のレコードにおいて、フィールド X
_i に値 v_ij を持つ場合、そのレコードは条件「X_i =
v_ij」を満足すると言う。また、特徴ルールは評価値
を持ち、特徴ルール「if A thenB」の評価値は

【０００８】

【数１】P(A)^a log{P(B|A)／P(B)} と定義される。ここで、P(A)、P(B) はそれぞれ、分析
対象レコード全体のうちで条件 A および条件 B を満足
するレコードの割合であり、 P(B|A) は条件 Aを満足す
るレコードのうち、条件 A と 条件 B の両方を満足す
るレコードの割合である。また、指数 a はヒューリス
ティックに定められる正の定数である。

【０００９】この文献で述べられている特徴ルールの発
見法は、分析対象データと then 部の条件、if 部に含
まれる条件数の上限、ルール数 M が与えられた時に、
特徴ルールの生成と評価値の算出を繰り返し、評価値の
最も大きい M 個の特徴ルールを発見する方法である。

【００１０】上記の文献に述べられている特徴ルール発
見法では、１つの特徴ルールを生成し、その評価値を算
出するごとに分析対象データの全体、または一部を走査
する必要があり、相関ルールの場合と同じように、２次
記憶からのデータの読み出しに時間がかかるという問題
がある。これを解決するために、分析対象データの走査
を一回のみ行う方法が特開平11−3360号「大規模データ
分析方法」である。この方法は、可能な全ての条件につ
いて、これを満足するレコードの数を数え上げるための
カウンタを用意し、一回のデータ走査で全ての条件につ
いてのレコードの数え上げを行うというものである。こ
れによれば、データの読み出しにかかる時間を削減する
ことができる。しかし一方、カウンタを保持するために
大容量の主記憶が必要になるという問題がある。

【００１１】

【発明が解決しようとする課題】相関ルール、特徴ルー
ルのいずれの場合も、基本的な発見方法においては、分
析対象データの走査にかかる処理時間とカウンタ保持に
必要な主記憶の容量の問題があり、一方を小さくしよう
とすると、他方が大きくなるという問題がある。これを
解決するための並列分散処理方法がいくつかあるが、相
関ルール発見の並列分散処理方法に関しては、データを
分割して複数の処理装置に分配するので、分析対象デー
タの走査にかかる処理時間は小さくできるものの、処理
装置間で分析対象データの転送が必要となったり、カウ
ンタを保持するために、依然として各々の処理装置にお
いて大容量の主記憶が必要となる。また、データマイニ
ング機能を持たない通常のデータベースシステムに分析
対象データが保持されている場合、並列分散処理方法を
実行するためには、前処理としてデータベースから各処
理装置へデータを分配する必要があり、このための処理
時間が余計にかかるという問題がある。

【００１２】本発明の目的は、複数の処理装置を用いた
並列分散処理において、分析対象データの転送量、転送
回数を少なく抑え、かつ、各々の処理装置において必要
となる主記憶の量を少なく抑え、かつ、通常のデータベ
ースシステムに接続して実行可能なデータマイニングの
方法を提供することである。

【００１３】

【課題を解決するための手段】本発明の並列分散分析方
法では、単数、または複数のデータ格納手段と複数のデ
ータ分析手段を用いる。単数のデータ格納手段を用いる
場合、全ての分析対象データは単数のデータ格納手段に
格納される。複数のデータ格納手段を用いる場合、分析
対象データは分割され、複数のデータ格納手段に分配さ
れて格納される。

【００１４】データ格納手段は分析対象データを複数の
データ分析手段に対して送信する。複数のデータ分析手
段は同一のデータを受信し、受信したデータを対象とし
てそれぞれのデータ分析手段において分析を行う。その
後、それぞれのデータ分析手段において得られた分析結
果をまとめて、全体の分析結果とする。

【００１５】データ格納手段は分析対象データを複数の
データ分析手段に対してまとめて一回送信し、複数のデ
ータ分析手段はこれを共有する。すなわち、データ格納
手段は複数のデータ分析手段の各々に対して個別に分析
対象データを送信することはしない。

【００１６】また、本発明の並列分散分析方法では、複
数のデータ分析手段が共有する共有記憶手段を用いる場
合がある。複数のデータ分析手段は、それぞれの分析結
果を共有記憶手段上に保持する。したがって、共有記憶
手段に保持された分析結果を読み出すことによって全体
の分析結果を得ることができる。

【００１７】

【発明の実施の形態】本発明の第一の実施の形態を説明
する。図１に本実施形態の構成を示す。本実施形態は、
データ格納装置１０１、複数のデータ分析装置１０２、
分析結果集計装置１０３がバス型通信路１０４によって
接続されている。分析対象データはデータ格納装置に格
納されている。

【００１８】図２にデータ分析の手順をしめす。データ
分析装置の準備処理２０１では、データ分析装置のそれ
ぞれにおいてデータ分析の準備を行い、分析対象データ
を受信する準備が完了したら、準備完了の信号をデータ
格納装置へ送信する。データ格納装置では、全てのデー
タ分析装置からの準備完了信号を受信するのを待つ（処
理２０２）。全てのデータ分析装置からの準備完了信号
を受信後、処理２０３において、データ格納装置は分析
対象データを走査し、まだ送信していないデータが残っ
ている場合は処理２０４へ、残っていない場合（全ての
分析対象データを送信し終わった場合）は処理２０６へ
進む。レコード送信処理２０４では、データ格納装置
は、まだ送信していないデータのうちの１レコードを送
信する。

【００１９】一度送信されたレコードは送信済みとして
扱われる。送信されたレコードはバス型通信路を介して
複数のデータ分析装置へ伝送される。通信路がバス型で
あるため、レコードはデータ格納装置からの１回の送信
で、通信路に接続された全てのデータ分析装置へ伝送さ
れる。データ受信、分析処理２０５では、データ格納装
置から送信されたレコードをそれぞれのデータ分析装置
において受信する。レコードの受信後、データ分析装置
では次のレコードを受信する準備を行い、受信準備が完
了したら、準備完了の信号をデータ格納装置へ送信す
る。また、既に受信済みのレコードとともに受信したレ
コードを対象としてデータ分析を行う。データ受信、分
析処理２０５の後は処理２０２へ戻る。分析結果集計処
理２０６では、分析結果集計装置はデータ分析装置から
分析結果を受け取り、これを集計して全体の分析結果を
得る。以上が、分析方法の概要である。このように、複
数の装置が互いに協調しながら、データ分析を行う。以
下に、特徴ルールの発見を例にとり、各装置において行
われる処理を詳細に説明する。

【００２０】分析対象データは複数のフィールドからな
るレコードの集合であり、全てのレコードは同数のフィ
ールドを持つ。レコードは分析の対象となる対象物、フ
ィールドは対象物の持つ属性に対応する。商店の顧客情
報を例にとると、１つのレコードは１人の顧客、各フィ
ールドは性別、年齢などの、顧客の属性に対応する。特
徴ルール発見では前処理として、各属性値を少数のカテ
ゴリに変換する。例えば、「年齢」は通常１０〜１００
程度の範囲の値を取り得るが、これを「３５歳以下」、
「３６歳以上５５歳以下」、「５６歳以上」のような少
数のカテゴリに変換する。また、「性別」は、もともと
「男」「女」の２つの値しか取り得ないので、このまま
２つのカテゴリとして用いることが多い。このようにカ
テゴリへの変換を施した分析対象データの例を図３に示
す。

【００２１】特徴ルールは、次のように書き表される。

【００２２】「if 性別=男 and 年齢=56以上 then 購入
額=大」すなわち、対象物の属性とカテゴリ化された値
の組からなる if-then ルールである。特徴ルールの if
部に現れる属性を「条件項目」、 then 部に現れる属
性を「結論項目」と呼ぶ。１つの属性が同時に条件項目
と結論項目の両方になることはない。また、特徴ルール
は評価値を持つ。一般に特徴ルールを「if A then B」
と表した時、その評価値は次式で定義される。

【００２３】

【数２】P(A)^a log{P(B|A)／P(B)} ここで、P(A)、P(B) はそれぞれ、分析対象データ全体
のうちで条件 A および条件 B を満足するレコードの割
合であり、 P(B|A) は条件 A を満足するレコードのう
ち、条件 A と 条件 B の両方を満足するレコードの割
合である。また、指数 a はヒューリスティックに定め
られる正の定数である。また、評価値の別の定義とし
て、次の式を用いる場合もある。

【００２４】

【数３】P(A)^a P(B|A)log{P(B|A)／P(B)} 数１、数２のいずれにおいても、ルールに現れる条件を
満たすレコード、および分析対象データ全体のレコード
の数を知ることによって評価値を算出することができ
る。

【００２５】特徴ルール発見とは、上記で定義したルー
ル評価値に基づき、評価値の大きい特徴ルールを発見す
る処理である。この時、発見すべき特徴ルールの数の上
限、結論項目となるフィールドとその値、条件項目の候
補となる複数のフィールド、１つの特徴ルールに現れる
条件項目の数の上限が分析者によって与えられているも
のとする。図４、５、６にルール発見の手順を示す。図
４はデータ格納装置における処理手順、図５はデータ分
析装置における処理手順、図６は分析結果集計装置にお
ける処理手順である。分析対象データとして図３に示し
たデータを例にとり、結論項目を「購入額」、その値を
「大」、条件項目の候補を「性別」、「年齢」、「職
業」、条件項目の条件数の上限を２とする。また、「性
別」は「男」、「女」の２値、「年齢」は「３５歳以
下」、「３６歳から５５歳」、「５６歳以上」の３値、
「職業」は「有」、「無」の２値を取り得るものとす
る。

【００２６】まず、データ格納装置、データ分析装置、
分析結果集計装置の全てにおいて、割り当て設定処理４
０１、５０１、６０１を行う。割り当て設定処理におい
ては、指定された条件項目の候補と、条件数の上限にし
たがって、可能な全ての特徴ルールに対応するカウンタ
を用意する。上記の条件項目候補と条件数の上限を用い
た場合、条件項目の可能な組合せは２３通りであり、図
７に示す２３通りの特徴ルールが可能である。特徴ルー
ルの評価値算出には、前述の P(A)、P(B|A)、P(B) が必
要である。ここで、結論項目となるフィールドとその値
は１つに指定されているため、 P(B) は全ての特徴ルー
ルについて同じである。したがって、各特徴ルールにつ
いて、 P(A)、P(B|A) を知るための２つのカウンタを用
意することになる。これらのカウンタは複数のデータ分
析装置に分配して割り当てられる。

【００２７】どのデータ分析装置にどの特徴ルールのカ
ウンタを割り当てるかはデータ分析装置のうちの１つ、
または、分析結果集計装置、またはデータ格納装置のい
ずれかによって決定される。そして、カウンタを割り当
てられたデータ分析装置のそれぞれの識別名、または、
カウンタを割り当てられたデータ分析装置の数がデータ
格納装置へ通知される。各データ分析装置では割り当て
にしたがってカウンタを用意する。

【００２８】データ格納装置では割り当て設定処理４０
１の後、カウンタを割り当てられた全てのデータ分析装
置と分析結果集計装置から、準備完了の信号を受信する
のを待ち（処理４０２）、準備完了の信号を全て受信し
たら、処理４０３へ進む。処理４０３では、未送信のデ
ータがあるかどうかを確認し、未送信のデータがある場
合はレコード送信処理４０４へ、全てのデータが送信済
みである場合は送信終了処理４０５へ進む。レコード送
信処理４０４では、まだ送信していないデータのうちの
１個のレコードを通信路へ送信し、処理４０２へ戻る。
送信終了処理４０５では、全てのデータを送信し終わっ
たことを示す信号を通信路へ送信する。

【００２９】以上で、データ格納装置における処理は終
了する。

【００３０】データ分析装置では割り当て設定処理５０
１の後、分析対象データを受信する準備が完了したこと
を示す信号をデータ格納装置へ送信する（処理５０
２）。データ受信待ち処理５０３では、データ格納装置
からデータを受信するのを待ち、データを受信したら、
処理５０４へ進む。処理５０４においては、受信したデ
ータがデータの終了を示す信号であるかどうかを判定
し、データ終了信号であればルール評価処理５０７へ、
そうでなければカウンタ更新処理５０５へ進む。カウン
タ更新処理５０５では、受信したデータは分析対象デー
タのレコードであるとして、そのフィールドの値を評価
する。そして、フィールドの値が、データ分析装置に割
り当てられた特徴ルールの条件と一致していれば、該当
するカウンタの値を更新する。一般に、１個のレコード
は、複数の特徴ルールの条件と一致し得る。すなわち、
１個のレコードの処理において、複数の特徴ルールのカ
ウンタ更新が行われる。データ受信準備処理５０６で
は、処理５０３で受信したレコードを破棄し、次のレコ
ードを受信する準備をし、処理５０２へ戻る。ルール評
価処理５０７では、データ分析装置に割り当てられたル
ールの評価値をカウンタの値に基づいて算出し、評価値
の大きい順に、発見すべき特徴ルールの数の上限として
指定された数の特徴ルールを取り出す。ただし、評価値
が 0 よりも小さい特徴ルールは取り出されない。した
がって、指定された数よりも少数の特徴ルールしか取り
出されない場合がある。この後、分析結果集計装置から
の指示を待つ処理５０８へ進む。分析結果集計装置から
の指示が終了指示である場合（処理５０９）は、データ
分析装置における処理を終了する。分析結果集計装置か
らの指示が分析結果送信指示である場合（処理５１０）
は、取り出しておいた特徴ルールとその評価値を分析結
果集計装置へ送信し（処理５１１）、指示を待つ処理５
０８へ戻る。

【００３１】分析結果集計装置では割り当て設定処理６
０１の後、分析対象データを受信する準備が完了したこ
とを示す信号をデータ格納装置へ送信する（処理６０
２）。データ受信待ち処理６０３では、データ格納装置
からデータを受信するのを待ち、データを受信したら、
処理６０４へ進む。処理６０４においては、受信したデ
ータがデータの終了を示す信号であるかどうかを判定
し、データ終了信号であれば分析結果収集処理６０６
へ、そうでなければ受信準備処理６０５へ進む。受信準
備処理６０５では、データ格納装置から受信したデータ
を破棄し、次のデータを受信する準備をし、処理６０２
へ戻る。分析結果収集処理６０６では、全てのデータ分
析装置へ順に分析結果送信指示を送り、それぞれのデー
タ分析装置で取り出された特徴ルールとその評価値を収
集する。分析結果集計処理６０７では、収集した特徴ル
ールの中から、評価値の大きい順に、発見すべき特徴ル
ールの数の上限として指定された数の特徴ルールを取り
出し、これを特徴ルール発見の結果とする。終了指示処
理６０８では、全てのデータ分析装置へ終了指示を送信
する。以上で、分析結果集計装置における処理を終了す
る。

【００３２】図８に本発明の第二の実施の形態の構成を
示す。第一の形態ではバス型の通信路を使用していた
が、第二の形態ではリング型の通信路を使用している。
リング型通信路では、全ての装置は送信端子と受信端子
を持ち、装置の送信端子は別の装置の受信端子と単方向
の通信路を介して接続されている。データ格納装置、デ
ータ分析装置、分析結果集計装置はいずれも、データを
発信する場合は、発信する装置の識別子をデータに付加
して、送信端子からデータを送出する。データを受信す
る場合は、受信端子からデータを受け取る。そして、そ
のデータに付加された識別子が自分のものであれば、そ
のデータを破棄し、識別子が自分のものでなければ、必
要に応じてそのデータを装置内に取り込むとともに、デ
ータと識別子を自分の送信端子から送出する。このよう
に、ある装置から送信されたデータは全ての装置の間を
順に転送されて送信元の装置へ戻り、そこで転送が終了
する。

【００３３】したがって、バス型の通信路と同様に、送
信元の装置からの１回の送信で、他の全ての装置にデー
タが伝送される。

【００３４】図９に本発明の第三の実施の形態の構成を
示す。第二の形態ではスター型の通信路を使用してい
る。スター型通信路では、全ての装置は双方向の通信路
を介して集線装置９０１と接続されている。集線装置は
複数の接続端子を持ち、１つの接続端子において受信し
た信号を他の全ての接続端子から送信する機能を持つ。
したがって、バス型の通信路と同様に、送信元の装置か
らの１回の送信で、他の全ての装置にデータが伝送され
る。

【００３５】図１０に本発明の第四の実施の形態の構成
を示す。データ管理装置１００４、複数のデータ分析装
置１００２、分析結果集計装置１００３が１つの共有メ
モリ１００５に接続され、データ管理装置１００４は通
信路を介してデータ格納装置１００１に接続されてい
る。分析対象データはデータ格納装置に格納されてい
る。

【００３６】共有メモリは、データ区画１００６、カウ
ンタ区画１００７、分析結果区画１００８に分けられて
いる。

【００３７】図１１、１２、１３に本実施形態における
特徴ルール発見の手順を示す。図１１はデータ管理装置
における手順、図１２はデータ分析装置における手順、
図１３は分析結果集計装置における手順である。まず、
データ管理装置、データ分析装置、分析結果集計装置の
全てにおいて、割り当て設定処理１１０１、１２０１、
１３０１を行う。割り当て設定処理においては、指定さ
れた条件項目の候補と、条件数の上限にしたがって、可
能な全ての特徴ルールに対応するカウンタを共有メモリ
のカウンタ区画内に用意する。また、特徴ルールのそれ
ぞれについて、そのカウンタ更新処理を担当するデータ
分析装置を決める。どのデータ分析装置にどの特徴ルー
ルのカウンタ更新処理を割り当てるかはデータ分析装置
のうちの１つ、または、分析結果集計装置のいずれかに
よって決定される。また、データ分析装置のそれぞれの
分析結果を書き込む領域を分析結果区画に用意する。ま
た、データ管理装置において、共有メモリのデータ区画
内に複数のレコードバッファ１００９を用意する。１つ
のレコードバッファは１つのレコードを格納できるレコ
ード領域と、カウンタ更新処理を割り当てられた複数の
データ分析装置の１つ１つと対応するフラグ領域からな
る。フラグの１つ１つは「データ無効」、「データ有
効」のどちらかの状態を取る。１つのレコードバッファ
のフラグが全て「データ無効」である場合、そのレコー
ドバッファは「空いている」と言う。初期状態では、全
てのレコードバッファは空いている。また、レコードバ
ッファとは別に、データ区画内にデータ終了フラグ１０
１０を用意する。データ終了フラグは「真」、「偽」の
２つの状態の一方を取ることができ、初期状態は「偽」
である。

【００３８】データ管理装置では、データ格納装置から
分析対象データのレコードを１個入力する（処理１１０
２）。この時、データ格納装置からデータの終了を示す
信号を受信した場合は処理１１０６へ、そうでなければ
処理１１０４へ進む（処理１１０３）。処理１１０４で
は、共有メモリのレコードバッファを走査し、空いてい
るレコードバッファを１つ探し出す。これが見つからな
かった場合は、見つかるまで走査を繰り返す。空いてい
るレコードバッファが見つかった場合は処理１１０５へ
進む。処理１１０５では、処理１１０４で見つかったレ
コードバッファのレコード領域にデータ格納装置から入
力したレコードを格納し、そのレコードバッファの全て
のフラグに「データ有効」を示す値を設定する。その
後、処理１１０２へ戻る。処理１１０６では、データ区
画のデータ終了フラグを「真」の状態にする。以上でデ
ータ管理装置における処理を終了する。

【００３９】データ分析装置では、共有メモリのレコー
ドバッファを走査し、自データ分析装置に対応するフラ
グが「データ有効」であるレコードバッファを１つ探す
（処理１２０２）。これが見つかった場合は処理１２０
３へ、見つからなかった場合は処理１２０５へ進む。処
理１２０３では、処理１２０２で見つかったレコードバ
ッファからレコードを読み込み、そのフィールドの値
が、データ分析装置に割り当てられた特徴ルールの条件
と一致していれば、該当する特徴ルールのカウンタの値
を更新する。処理１２０４では、処理１２０２で見つか
ったレコードバッファ内の、自データ分析装置に対応す
るフラグを「データ無効」に更新する。その後、処理１
２０２へ戻る。処理１２０５では、共有メモリ内のデー
タ終了フラグを調べ、状態が「真」であれば処理１２０
６へ進み、状態が「偽」であれば処理１２０２へ戻る。
処理１２０６では、データ分析装置に割り当てられたル
ールの評価値をカウンタの値に基づいて算出し、評価値
の大きい順に、発見すべき特徴ルールの数の上限として
指定された数の特徴ルールを取り出す。ただし、評価値
が 0 よりも小さい特徴ルールは取り出されない。処理
１２０７では、取り出した特徴ルールとその評価値を共
有メモリの分析結果領域に書き込む。以上でデータ分析
装置における処理を終了する。

【００４０】分析結果集計装置では、共有メモリの分析
結果領域を調べ、全てのデータ分析装置の分析結果が分
析結果領域に書き込まれるのを待つ（処理１３０２）。
全てのデータ分析装置の分析結果が揃ったら、分析結果
領域に書き込まれた特徴ルールの中から、評価値の大き
い順に、発見すべき特徴ルールの数の上限として指定さ
れた数の特徴ルールを取り出し、これを特徴ルール発見
の結果とする（処理１３０３）。以上で分析結果集計装
置における処理を終了する。

【００４１】なお、以上で説明した第四の実施の形態は
カウンタを共有メモリ内に置く形態であったが、データ
分析装置のそれぞれが局所メモリ１４０１を持っている
場合は、カウンタを局所メモリ内に置くこともできる
（図１４）。

【００４２】

【発明の効果】本発明によれば、大量のデータを多面的
に分析するデータマイニングなどのデータ分析処理を複
数の処理装置を並列に動作させて実行する場合に、分析
対象データの転送量、転送回数を少なく抑え、かつ、各
々の処理装置において必要となる主記憶の量を少なく抑
えることができる。また、大量データ分析方法に適する
ように設計されたデータ格納方法を特に必要としないの
で、一般のデータベースシステムに格納されたデータを
分析対象とすることができる。

【図面の簡単な説明】

【図１】第１の実施形態の構成図。

【図２】分析方法の概要を示す流れ図。

【図３】分析対象データの例を示す図。

【図４】第１の実施形態のデータ格納装置における処理
を示す流れ図。

【図５】第１の実施形態のデータ分析装置における処理
を示す流れ図。

【図６】第１の実施形態の分析結果集計装置における処
理を示す流れ図。

【図７】全ての可能な特徴ルールを列挙した図。

【図８】第２の実施形態の構成図。

【図９】第３の実施形態の構成図。

【図１０】第４の実施形態の構成図。

【図１１】第４の実施形態のデータ管理装置における処
理を示す流れ図。

【図１２】第４の実施形態のデータ分析装置における処
理を示す流れ図。

【図１３】第４の実施形態の分析結果集計装置における
処理を示す流れ図。

【図１４】第４の実施形態において、局所メモリにカウ
ンタを置く構成図。

【符号の説明】

１０１…データ格納装置、１０２…データ分析装置、１
０３…分析結果集計装置、１０４…バス型通信路、１０
０４…データ管理装置、１００５…共有メモリ、 １０
０６…共有メモリ内のデータ区画、１００７…共有メモ
リ内のカウンタ区画、１００８…共有メモリ内の分析結
果区画、１００９…レコードバッファ、１０１０…終了
フラグ、１４０１…局所メモリ内のカウンタ。

フロントページの続き (72)発明者 伊藤 幸康 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソフトウェア事業部内 Ｆターム(参考） 5B075 KK02 PQ05 QS05

Claims (4)

【特許請求の範囲】
1. 【請求項１】 単数、または複数のデータ格納手段に格
   納されたデータを対象とし、複数のデータ分析手段を用
   いるデータ分析において、前記の複数のデータ分析手段
   は前記のデータ格納手段から同一のデータを入力し、前
   記複数のデータ分析手段のそれぞれにおいて分析を行
   い、前記複数のデータ分析手段のそれぞれにおける分析
   結果をまとめて全体の分析結果をすることを特徴とする
   データ分析方法。
2. 【請求項２】 前記複数のデータ分析手段は前記のデー
   タ格納手段が一回出力した分析対象データを共有するこ
   とを特徴とする請求項１に記載のデータ分析方法。
3. 【請求項３】 複数のデータ分析手段が共有する共有記
   憶手段を用い、前記複数のデータ分析手段は各々の分析
   結果を前記共有記憶手段へ出力することを特徴とする請
   求項１、および請求項２に記載のデータ分析方法。
4. 【請求項４】 請求項１、２、および３に記載の並列分
   散分析方法を計算機で実行するための計算機プログラム
   を格納した記憶媒体。