密度基準に基づく高速な定量的相関規則導出手法
光永 悠紀

鷲尾 隆

藤本 敦

元田 浩

大阪大学産業科学研究所高次推論方式

はじめにデータマイニングの分野においては，データ間の共起事象を相関規則として求めるバスケット分析が主流の つになっていアルゴリズム はる．バスケット分析で用いられるアイテム間の共起相関を高速に抽出できる．しかし，アイテムで表現されるデータ構造には制限があり，数値を含むデータをアルゴリズムでは解析できない．数値を含むデータを扱うことができれば，バスケット分析を適用できる問題の範囲は飛躍的に広がるはずである．そこで，現在までに数値属性アイテムを含むデータについての相関ルール抽出を行う方法について様々な研究が行われてきたが，現実的な時間計算量で個別の相関規則に最適な数値区間分割の完全探索を行いルールを抽出する手法は存在しなかった．そこで，我々は数値を含むトランザクションデータについて現実的な時間計算量で個別の相関規則に最適な数値区間分割の完全探索を行う定量的多頻度アイテム集合導出法を提案した ．しかし，この手法にはまだ計算時間の削減・メモリ使用量の低減という課題が存在した．本稿ではこの課題を克服するために開発した改良アルゴリ
ズムの提案及び，それに対して実際にデータに適用した性能評価を行う．

定量的多頻度アイテム集合導出手法の課題
多頻度アイテム集合と多頻度領域あるデータベース において，最小支持度を超える頻度で各トランザクションに共起するアイテム集合を「多）」と呼ぶ．
アル
頻度アイテム集合（
ゴリズムを 年齢 のような数値アイテムを含めて多頻度なアイテム集合を探索できるように拡張する．まず，それぞれの数値アイテムの値を除いた部分，つまり属性を記号アイテムとして考え，最小支持度を超える多頻度アイテム集合を探索する．次に，得られた多頻度アイテム集合 に含まれる全ての数値属性 に注目し， を含む各トランザクション の持つ数値属性の値 が密集している区間を抽出する．つまり，連絡先 大阪大学産業科学研究所
大阪府茨木市美穂ヶ丘〒

ある密集基準を満たしを満足する領域を抽出すればよい．ただし，である．これによって得られた領域を本稿では「多頻度領域）」と呼ぶ．
（
多頻度領域を探索するためには，トランザクションが密集していると判断する基準が必要である．そこで本稿では，各数値属性 ごとに「それぞれのトランザクション の持つ数値属性の値 同士が特定の値 より離れていなければ近いとみなす」という基準を設定する．この を数値属性 に関）」と呼ぶ．
する「許容距離（旧手法

多頻度アイテム集合に含まれる全ての数値属性に関して，トランザクション から許容距離 以内であるトランザクショとし，すべての について求まったンの集合を近傍集合
近傍集合の集合を とする．ここで，任意の，（）の積集合が空集合でないとき， と を結合する．この近傍集合の集合 をもとにして得られる多頻度集合の候補 はとなる．このような は から複数得られる．これによって生成された多頻度集合の候補 に含まれる要素数が最小支持度以上であるとき，その多頻度集合の候補を多頻度集合と呼び， における各属性 の最大値と最小値で囲まれた範囲が多頻度領域 となる．

ただし， は直積記号である．例えば 種類の数値アイテの多頻度領域を求めると図 のようになる．ただし，ム最小支持度は とする．図におけるそれぞれの点をトランザクションとすると，（１）では各数値アイテムに対して許容距離 及び 以下であるトランザクションを結合してゆけば多頻度集合の候補の要素数は となる．よって，最小支持度を上回るので図のような長方形の多頻度領域が得られる．また，

（１）密集している場合

図 旧手法で得られる領域の問題点（２）密集していない場合

図における多頻度領域（２）においては幾つかのトランザクションの結合はされるが，多頻度集合の候補の要素数が であり最小支持度を下回るために多頻度領域は得られない．

定量的多頻度アイテム集合導出手法の改良

本研究では定量的多頻度アイテム集合導出手法の性能向上による多頻度アイテム集合候補作成手法ののために改良，多頻度領域導出手法の改良及び新しい密度基準の導入を行う．以下，これらの内容につき詳しく説明する

多頻度アイテム集合候補作成手法の改良

多頻度アイテム集合の候補の作成にはアルゴリズム
アルゴリズムは，要素数 の多頻が用いられている．
度アイテム集合からはじめて，ボトムアップ的に要素数 の多頻度アイテム集合から要素数 の多頻度アイテム集合の候補を作り出すことを行う．具体的に述べると 個の要素が共通な要素数 の２つの多頻度アイテム集合
より要素数 の多頻度アイテム集合の候補を上記の２つのアイテム集合の和集合ｋとする．さらに候補を絞り込むために，このようにして候補にのアイテム集合に対して，要素数 のあがった要素数アイテム集合からなる各部分集合が全て多頻度アイテム集合として存在しているかどうかをチェックする．これは多頻度アイテム集合であるためには，その部分集合は全て多頻度アイテム集合でなければならないためである．要素数 の多頻度アイテム集合は前段階の処理で全て取り出されており既知であるので，このチェックは効率的に実行することが可能である．このようにして残った各候補についてのみ，実際の支持度をデータから検索して計算することで効率的に多頻度アイテム集合を求めることができる．
ここで，多頻度領域の性質を用いることにより、より効率的では，候補に候補生成を行う手法を提案する．通常のを作成したあとに要素数の一つ少ないアイテム集合が全て多頻度アイテム集合であるかをチェックする．しかし，数値属性アイテムを含む多頻度アイテム集合の候補を作成する場合を考えると， ， に共通する数値アイテムそれぞれについて，そのアイテムを属性とする数値軸上に 及び の多頻度領域をそれぞれ正射影した区間がトランザクションデータを含まない場合， ， を結合しててできる多頻度領域は存在しないという性質がある．よって，この性質を用いて多頻度アイテム集合候補の生成の枝狩りを行うことにより計算時間を短縮することができる．
このチェックの簡単化のために各多頻度領域に，とを付加する
は各多頻度領域に付けは候補作成の際にそられたユニークな であり，とする との領域の元となった多頻度領域のの多頻度領域にが一致するするものが一つもなかった場合次のレベルの候補は生成せず，一つでもあった場合に前述のように共通データの存否のチェックを行う
最後に，作成された多頻度集合の候補に対して，全てのアイテムを記号アイテムとした場合に ， を両方含むトランザクション数をカウントしこれが最小支持度を超えない場合は更なる枝狩りを行う

多頻度領域導出手法の拡張

以前の手法は各トランザクションについて全ての数値属性アイテムにおいて許容距離 以内のトランザクションからなる近傍集合を求め，それをマージしていくことで多頻度領域を求めていた．この手法だと近傍集合を求める際に，各トランザクションについて近傍であるトランザクションの情報をメモリ上に全て記憶するのでメモリの使用量が非常に大きくなっていた．また，距離 以内のものを全て結合していき領域を求める方法には，実際には密度が薄い部分まで同じ領域として取り込んでしまい，図 に示すような分布の少ない領域が続くようなデータでは適切な領域を探索できないという問題があった．
この問題に対し，以下の改良を施した．
密度の濃い領域を適切に探索するために， に加えて新たを採用しな密度の評価の指標として最小データ点数を用いるにあたって必要な定義を導入する．
た．まず，

定義あるトランザクション について許容距離 以内に以上のトランザクションが存在する時トランザクション をと呼ぶ．

定義

トランザクション が であり，トランザクション からトランザクション までの距離が 以内であるとき， はからであるとする．

定義

トランザクションの集合 ， ， において，任意の にであるとついて が からき， ではないトランザクション が ， ， のうちのいずれかからの距離が 以内であった時， は ， ， からであるとする．

定義

ある つのトランザクション ， がトランザクション かであるとき と をらであると呼ぶ．
以上の定義の下で，多頻度領域を導出する拡張アルゴリズムを定式化した．要素数 の多頻度アイテム集合 に含まれるとする．
数値アイテム属性の集合をデータ から を含むトランザクションを抜き出したリストを とする．
である各数値アイテム属性 について，について をソートする．
を について互いにである極大なトランザクション集合に分割し，各々をとする．
各 についてとして を再帰的に実行し， の中のどのアイテムに対して操作を行っても に含まれるトランザクション数に変化がなくなるまで操作を繰り返す．
この操作を行って残ったリストの長さが最小支持度を超えていた場合，その各属性について最小値と最大値を求めたものが多頻度領域となる．
トランザクション数を とすると，以前の手法では各トラ個の近傍集合を記憶するンザクション毎に最悪の場合ためのメモリが必要であったが，改良手法では最悪でも全てのトランザクションに共通した 全てのトランザクションがリストに含まれる場合 個の要素を記憶するための領域しか必要としない このためメモリ使用量の大幅な低減が可能である．
により距離 内に個以上のトランザクまた，ションが密集した密集性の高い領域を見つけることができる．

図 手法改良前のトランザクション数に対する計算時間

性能評価

データの概要パラメータの変化による性能の評価を行うために人工データを用いて性能評価を行った．人工データはトランザクション数，トランザクションの平均サイズ，アイテムの種類数，人工的に埋め込む多頻度パターンの種類数を指定して生成した．
今回は，トランザクション数の大きなデータに適用できるよ
うに計算時間の短縮とメモリ使用量の低減を目的として手法の改良を行ったので，トランザクション数の増加に対する計算時間及びメモリ使用量の変化に着目し性能評価を行う．今回はは として評価を行った．

分析結果と考察

図 に改良前の手法によるトランザクション数と計算時間の関係のグラフを，図 に今回提案した手法のトランザクション数に対する計算時間・メモリ使用量の変化のグラフを示す．
程度の必要計算時間を示しているのに改良前の手法が程度の計算量を対し、今回の提案手法は ～である．以下示している．またメモリ使用量は，ほぼにこれらに関する理論的考察を示す．
前述の拡張アルゴリズム中のステップ は明らかにである．ステップ はリスト のソートであるが，高々であるのでである ステップ では
各属性 の数直線上でトランザクションの分布に基づき，各個以上のトランザクショトランザクションの周囲にンが存在する多頻度領域を求める 各トランザクションについ個の他のトランザクションのカウントが必要であてるため， に含まれる数値属性数を とすると，このスの計算時間がかかり， についテップは最大である．ステップ では，新たに作成されたリてはストに対して多頻度領域が収束するまで，ステップ が深さ優先探索で再帰的に実行される．途中 から まで再帰的処理が終わっても収束しない場合には，再度 から再帰的処理が続けられる．ここで，多頻度領域が収束するまでに最悪どのくらいの計算量が必要か考察する． に含まれる属性全てについてステップ ～ を行うことを サイクルとすると，収束するまでに計算量が最も多くなるのは サイクルでリストから一つずつトランザクションが減っていく場合である．
このとき収束するまでに サイクルかかるため，計算時間はとなる．しかし，このようなことは起こり難くく，実際には各サイクルでトランザクションの一部がリストから減っていくことが殆どである．各サイクルでトランザク

参考文献回）

人工知能学会 知識ベースシステム研究会（第（１）計算時間（２）メモリ使用量

図 トランザクション数に対する計算時間・メモリ使用量の変化
ションが減っていく割合の期待値を α α ，収束するまでに必要なサイクル数を とする．探索は領域内のトランザクション数が最小支持度未満になると打ち切られるため，は高々α を満たす程度である．この等式をについて解くととなる．よって全体として計算時間となり に対してはではある．この結果は図 と整合する．
次に，メモリ使用量に関して考察する．メモリは主に各トランザクションに含まれるアイテムの記憶と，求められた多頻度アイテム集合及び多頻度領域の記憶に使われる．各トランザクションに含まれる平均のアイテム数を とするとメモリ使用量は に比例して増えていく．一方，多頻度アイテム集合・多頻度領域の記憶に用いられるメモリ量は，トランザクション数に直接依存しない．よって，メモリ使用量は全体としてであるといえる．この結果は図 と整合する．
以上のように，本稿で提案した手法を用いるとトランザク，メモリ使用量ション数 に対して，計算時間で定量的多頻度アイテム集合を導出することが可能である．

むすび

本研究では以前考案した定量的多頻度アイテム導出手法の高速化・メモリ使用量の低減を目的とした改良手法の提案を行った．テストデータを用いて提案手法の性能評価を行った結果，実行速度・メモリ使用量共に大幅に改善されることがわかった．
今回提案した手法の枠内では，定量的多頻度アイテム集合を導出することはできるが，アソシエーションルールを導出することはできない．このための拡張が課題として挙げられる。

全 眞嬉 加藤直樹 徳山 豪 高次元ピラミッド構築問題とデータマイニングへの応用 情報処理学会誌
アルゴリズム