論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――は考慮していないからである．よって，数値属性を含む結合ルールを求めるには別のアルゴリズムを用いる必要がある．
福田ら［FMMT01］は領域切り分けを用いて数値属性とカテゴリ属性間の結合ルールの生成を行う手法を提案している．この手法では「x∈R ならば B である」(R はいくつかの数値属性の値の空間の部分領域)のようなルールを発見している．
HigherHigher-Dimensional Pyramid Construction
福田らによる領域として切り出しを行うと，領域に入っていProblem and Application to Data Mining
るかいないかだけで判定を行うため，境界線上のデータと中央部のデータが同じ扱いをされるといった位置情報の損失があ
全 眞嬉1
Danny Z. Chen2
る．領域切り分けを用いて生成された結合ルールを学習に用いると，制限が強く，学習データに入っているノイズ（離れ値）
加藤 直樹3
徳山 豪4を排除してしまうため，学習データ以外のデータに対して生成
Jinhee CHUN
Danny Z. CHEN
されるルールは不自然な領域ルールを生成するといった，過学
Naoki KATOH
Takeshi TOKUYAMA
習の問題点がある．また，属性を3つ以上与えると，計算量が福田らによって提案された最適領域ルールは数値属性デー 多く計算が困難になる．すなわち，属性次元の制限の問題があタ で構成されるデータベースに対する有効なデータマイニン る．ここで，本来は切り取るべきものは多次元正規分布のようグツールである[FMMT99,FMMT01]
グツールである[FMMT99,FMMT01]．しかしながら，従前の方法[FMMT99,FMMT01]．しかしながら，従前の方法 な特徴をもったデータ分布であり，領域として切り取るより，
では 2 つの欠点がある：(1)各ルールは高々(1)各ルールは高々2
各ルールは高々2 変数の数値属性に 性質の良い関数として捉える事が望ましい．
対応でき(2)対応でき(2)判定は与えられたデータの正確な位置ではなく，(2)判定は与えられたデータの正確な位置ではなく，本論文では，以上の問題を解決するために，最適ピラミッド
単純に領域 R の中にあるか，外にあるかだけに基づき行われる． による結合ルールの表現法を提案する．つまり，領域として切
本論文では，これらの欠点を取り除くための新しい方法の提案 り出すのではなく，性質の良い関数として切り出しを行う．数をする．具体的にはグラフアルゴリズムを用いて，2をする．具体的にはグラフアルゴリズムを用いて，2 つ以上の 値属性または複数の数値属性に関しての最適な階層構造でデ属性を持つ最適数値属性結合ルールと階層構造の数値属性結 ータの近似を行い，階層的な数値結合ルール，すなわち最適ピ合ルールを与える．又，本論文の手法は異常なデータの除去と合ルールを与える．又，本論文の手法は異常なデータの除去と ラミッドを用いた数値属性結合ルールの提案をする．
データクラスタリングに適切である．
手段として，幾何学的なアルゴリズムを用いた最適ピラミッ
Optimized region rules developed by Fukuda et ド構築問題への定式化を行う．最適ピラミッドとは，入力デー
al.[al.[FMMT99,FMMT01]
FMMT99,FMMT01] are effective tools for data mining in タが持っている位置情報の損失を最小にする（最小の近似エラ
databases with numeric data. However, there are two ーを持つ），すなわち，パラメトリックゲインを最大にする領
drawbacks in the previous methods: (1) each rule can 域を積み重ねた単峰な図形への変更である．
contain at most two numericnumeric conditional attributes, and (2)the decision is made based only on whether a given data is
inside or outside a region R, but not on the exact position of 2. 結合ルール
the data. In this paper, we propose a new method for
結合ルールは，タプル内の属性間の相関関係である．X,Y が属
removing these drawbacks. Indeed, by applying
applying graph 性に関する命題式のとき，(X →Y)を結合ルールと呼ぶ．「X ならばalgorithms, we give optimized numeric association rules Y である」という意味である．Y は通常，単一属性に関する命題式でwith more than two attributes, and give layeredlayered-structure ある．
numeric association rules. Our method is also applicable to
健康診断データベースを例として考える．正常体重域を超えた体
removal of exceptional data and data clustering.
重を肥満，正常血糖値を超えた血糖値を異常血糖値と呼ぶことにする．「肥満で異常血糖値である人は糖尿病の検査が必要である」
1. はじめにような診断法則があるとする．健康診断データベースの診断法則のデータマイングの手法として「AならばBである」といったデ 結合ルールは(肥満 = yes ∧ 異常血糖値 = yes)→(糖尿病検査ータベースの属性間の相関関係を求める結合ルールがあり，= yes) と表現される．
Aprioriアルゴリズム［AIM］が提案された．現行のデータベー
X が単一属性に関する命題式のとき，(X→Y)は 1 次元結合ルー
スには性別，血液型といったカテゴリ属性と年齢，体重といっ ルと呼び，(X1∧X2→Y)のように前提条件に X1, X2 の 2 つの属性をた数値でとられる数値属性が含まれているが，Aprioriアルゴリ 用いた場合は 2 次元結合ルールと呼ぶ．
ズムはカテゴリ属性間の結合ルールを求めるためのものであ結合ルールの尺度である，確信度とサポートについて述べる．結り，数値属性に対しては直接適用することはできない．なぜな 合ルール X→Y の確信度(confidence)とは，データベース D の X
ら，数値属性は値に順序があるため，値を連続した区間で表す を含むトランザクションのうち，Y を同時に含む割合のことである．すことが重要であるが，Aprioriアルゴリズムではそのようなこと なわち，|X∧Y|/|X| が c%であることを，conf(X→Y)=c%と表記
する．「結合ルール X→Y は c%の確信度である」という意味を持つ．
結合ルール X→Y のサポート(support)とは，データベース D の(X)
1 学生会員東北大学大学院情報科学研究科システム情報科
を含むトランザクションの，トランザクション全体に対する割合のこと
jinhee@dais.is.tohoku.ac.jp
学専攻である．
2 非会員 University of Notre Dame，Dept. of Computer
このとき，support(X→Y)=s%と表記する．「結合ルール X→Y はScience and Engineering
chen@cse.nd.edu
s%のサポートである」という意味を持つ．
3 非会員 京都大学大学院工学研究科建築工学専攻
各項目間の関連に説得力のある根拠を提示することで，抽出さnaoki@archi.kyoto-u.ac.jp
れた規則はユーザに判断基準を与える説明性を持つ．このような規4 非会員 東北大学大学院情報科学研究科システム情報科学
則の根拠を確信度とサポートを用いて表す．
専攻 tokuyama@dais.is.tohoku.ac.jp

高次元最適ピラミッドを用いた数
値属性ルールの生成とデータマイニングへの応用

1

日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
本研究では，新しい領域族を階層最適化し，より高次元のルールの効率的な生成を行う．本研究の結果は，結合ルール生成だけでなくデータビジュアル化およびデータマイニングへのファジーアプローチにおいても有効に応用できる．階層構造は決定論的な決定ルール(x∈R)→(C = yes)に比較して，強いルールの影響を縮小する方法を適用する．拘束力の弱いルールで判定をする，非決定性を持たせた柔軟な決定システムの構築を行う．

直感的には t が増加する場合，Ropt(t)は減少する．{Ropt(t)}(正確には，関数 Ropt(t)の閉包)がピラミッドを形成する場合，それは明らかに最適ピラミッドである．ところが，最大ゲイン領域 Ropt(t)を積み重ねるとき，Ropt(t)⊂Ropt(t’)が t > t'に対して成立するとは限らないので，それらは必ずしもピラミッドを形成するとは限られない．これは，最適ピラミッドを計算することを非常に難しくする．

3.2

閉集合族に対する考察

ある集合族 S が G =[0,n]d の閉集合族であるとは，G∈S, ∅∈S,
3. 最適ピラミッド問題[X, Y∈S → X Y∈S] かつ [X,Y∈S →X∩Y∈S] である事を階層的結合ルール生成問題を定式化するためにより一般の幾何 言う．
Theorem F が閉集合族であれば，各々の t に対しρ (R) – t･μ学問題を与え，データマイニングでの利用をその応用として行う．
μとρを n = md セルの d 次元ボクセルグリッドΓ上の非負整数値 (R) を最大にする 領域 R∈F をΨ(t)とすると，Ψは単調条件を満たし，従って，最適ピラミッドになる．
□関数とする．すべてのセル c∈Γ に対し μ(c)≥n かつμ(c) ≥ρ(c)と仮定する．データマイニングへの応用ではμはセル c Proof t > t' のとき A=Ψ(t)⊆B= Ψ(t')である．R⊂R'の場合，t にに対応するデータの数，すなわちサポート（support）の関数を表し， 対して関数 gt(R,ρ,μ) - gt (R',ρ,μ)は増加しない関数である．A
ρはセル c において条件属性と目的属性を同時に満たすデータの ＼ B が空集合でない場合，0≧gt’(A∪B,ρ,μ)- gt’(B,ρ,μ)=数，すなわちヒット（hit）関数を表す．また，確信度（confidence）は gt’(A,ρ,μ)- gt’(A∩B,ρ,μ)≧gt(A,ρ,μ)- gt(A∩B,ρ,μ)である．
A=Ψ(t)なので，gt(A,ρ,μ)≧gt(A∩B,ρ,μ)になる．従って 0≧
サポートをヒットで割ったもので，conf(c)=ρ(c)/μ(c)とする．
N に領域族 F を固定する．一般性を失わず，∅∈F および Γ∈ gt(A,ρ,μ)- gt (A∩B,ρ,μ)≧0 であり，gt(A,ρ,μ)= gt(A∩B,ρ,F と仮定できる．
μ ) に な る ． 従 っ て A=A ∩ B で あ り ， A(B で あ る
Definition 1 P(t0) = Γ および t>t'のとき P(t)⊆P(t')を満たす F の領 □域の列 P=P(ti) (i=0,1,2, ... ,h)を考える．ここで t0<t1<t2<…<th は高従って，集合族 F が閉集合族で構築される場合，Fさと呼ばれる実数である．P(th+1)=∅で conf(P(ti) - P(ti+1)) = ti の場の最適のピラミッドを計算するための効率的なアル合，P をμに関して conf=ρ/μを近似する．ρに近似するピラミッド（あるいはピラミッド構造）と言う．P の近似エラーは∑ ∑(conf (c ) − ti ) 2 µ (c ) によって定義される．

hi=0c∈P ( t i ) − P ( ti +1 )これは確率密度関数として μ を考えたとき，確信度ρ/μと，[fP(x)=ti if x∈P(ti) - P(ti+1)]によって定義されたピラミッドの表面関数 fP の間の 2 乗された L2 距離である．すべてのピラミッド中で最小近似エラーを持つとき，ピラミッド P を最適であると言う．
μがユークリッド空間の体質を与える密度関数であるとき，最適ピラミッドは，位置ポテンシャルの損失を最小限にするρ/μの単峰な変更と見なすことができる．これは計算幾何学および地理学(特にd=2 の場合)の基礎的な問題となる．最適ピラミッドの構築は領域切り出し問題の自然な拡張であり，データマイニングに加えて多くのアプリケーションにおいて有用になる．

ゴリズムの設計が必要である．

4. 2 次元の場合
nをピクセルの数，Nをサポート値の和（すなわち，データの数）とする．2次元の領域族でもっとも基本的なのは軸方向長方形の族の場合である．しかし，この場合ではO (n5)の計算時間のアルゴリズムしか知られていない[CKT02]．ここでは，実用的な多くの領域族についてより効率的な手法を考える．

Definition 2 2次元ピクセル面G = [0,m]2( m = n ） 内
で，適当な関数y = h(x) より真に下にあるピクセル全体の和に□なっている領域を下半切断領域と呼ぶ．
Definition 3
2次元ピクセル面G = [0,m]2 内の1点p に対し，pを含む長方形たちの和集合をp を中心にする矩形和楕円□型領域（rectilinear ellipsoid）と呼ぶ．
3.1 最適ピラミッドとパラメトリックゲイン
点pを中心とする矩形和楕円型領域の族は，点pを含む矩形全Lemma 1 領域を値に持つ写像 P(t):(0,∞)→F で，単調条件［t >体の族の集合和，集合積に対する閉包になっている．矩形和楕
t' の と き P(t)⊆P(t') ］ を 満 た し ， 目 的 関 数 J(P) =円型領域の族は直交凸領域の族の部分族であるが，軸方向楕円∞∫0 ( ρ ( P ( t )) − t ⋅ µ ( P ( t ))) dt を最大にする関数 P(t)を考える．□ の離散化を含む広い領域族であり，指数個の領域を持つ．例とこのとき，P(t)は t∈(ti-1, ti]のとき P(t) = P(ti)及び t>th のとき して，単調減少関数の下半切断領域は原点を中心とする矩形和P(t)=∅を満たす，高々n+1 の変化値 0=t-1<t0<t1<…< th を持ち，さら 楕円型領域となる．
Lemma 2 点pを中心とする矩形和楕円型領域全体の集合は閉に P(t0), P(t1),...,P(th)から成る P は最適ピラミッドである．
□
Proof Γに n = md 個のピクセルがあるので，t∈n (0, ∞)のとき 集合族である．
Proof
矩形和楕円型領域は点 pを含む長方形の和集合とP(t)の中に高々n+1 の異なる領域がある．したがって，変化値の数が n+1 以下であることは明らかである．目的関数を最大にするため してとられる領域である．点pを中心とする矩形和楕円型領域Fに，ρ(P(ti))-t･μ(P(ti))と μ(P(ti)) = ρ(P(ti-1)) - t ・μ(P(ti-1))は変 とし，Fの任意の領域RとR'に対して，R∩R'∈F および R∪R'
化値 t = ti-1 で等しい ti-1=conf(P(ti-1) ＼P(ti))であり，P は ρ のピ ∈F である．すなわち，Fの任意の領域RとR'は和集合と共通□集合に閉じているので，Rdの領域族Fは閉集合族である．
ラミッドである．2 乗された L2 エラーE(P):=Lemma
3
与えられた点pを中心とする矩形和楕円型領域
はと等しい．従って，J(P)2h(c ) − ti ) ⋅ µ (c )) ( confi 0c∈ P ( t ) P ( tで与えられたtに対して利得を最大にする領域はO (n)で計算∑∑を最大にする関数 P(t)は，E(P)を最小にするピラミッド P を定義する．
□できる．
よって証明された．
Proof まず，p=(0,0) の場合を考える．この場合，矩形和
したがって，直観的に最適ピラミッド P は，できるだけ大きなパラメ
楕円型領域は単調非減少関数で区切られた階段状の領域になトリックゲインを持つ横断面を積み重ねることにより得られる．パラメト
る．まず，最初の行における最初のi個のピクセルのゲインの和リックゲイン gt(R, ρ, μ)を最大にする F の領域 Ropt(t)を考える．
i2i 1

日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――f ( i , j ) = ∑ s = 1 ρ (( s , j )) − t ⋅ µ (( s , j ))（Prefix和）であるを計算する．これはすべての(i,j)に対してO (n)時間で計算できる．
□α(i,j)をpが中心で(i,j)を含み，y座標がjより大きい領域を含まないような矩形和楕円型領域の中でゲインが最大になるもののゲインと定義する．すると，pを中心とする矩形和楕円型
i領域の中でゲインが最大になるもののゲインは maxmj=1 α(1,j)
によって求まる．α(i,j)は以下のダイナミックプログラミングによりすべての(i,j)に対してO (n)時間で求まる:
β( i, j )= α( i-1, j ) + f( i, j )(1)α( i, j )= max{β( i, j ), α( i, j+1)}(2)
そして，領域はダイナミックプログラミングプロセスのバックトラッキングにより計算できる．
一般のp=(xp, yp)の場合は，ピクセル領域をx=xpとy = yp で4分し，各象現で上記と同じ操作を行い，得られた領域の和領域を求めればよい．
Theorem 2 指定された一点pを中心とする矩形和楕円型領域全体の集合に関する最適ピラミッドは， O (n log N)時間で計算される．ここでN は問題の出力精度であり，1/Nの近似精度で最大な積分値を持つ解が出力される．（従って，N が入力精度以上なら最適解を出力する）．
□Proof 閉集合族なので，各t に関して，利得を最大にする領域を求めればよい．これはO (n)時間でできる．更に，ある tでの最適領域を計算した時に，これがGを領域の内部と外部に分割するため，各部分を独立に，対応する部分に問題を縮小して解ける．従って分割統治が可能である．tはプロセスの分岐を用いる事により，深さ log N の再帰で全ての部分での最適領域の計算が終了する．各深さでの全ての部分領域での最適領域は計算時間は O (n) で求まる．
従って，全体に関する最適ピラミッドは深さがlog N なのでO (n log N) 時間で計算できる．
□5. 高次元の場合
5.1小さい領域の場合

F が M 個の異なる領域を持っている場合，最適ピラミッドは d 次元の場合 M と n についての多項式時間で計算できる．
頂点集合と F とする閉路を持たない有向グラフ H(F) = (F, E)を構築する．各 F のペア R と R' が R⊃R' を満たすとき，グラフに有向辺 e = (R, R')を加える．
そしてρ(R＼R') = t(e)・μ( R＼R')を計算する．
値 t(e)は e の高さラベルと呼び，r(e) = t2(e) ρ(R＼ R') /2 は e の利得と呼ぶ．
t(ei-1) < t(ei)が i=1,2, …,q で成立する場合，有向路 p = e0, e1,…, eq を許容有向路(admissible)と呼ぶ．許容有向路の利得は辺の利得の総和である．
Lemma 4 最適ピラミッドは，(R, R')が経路上の辺である場
合のみ R＼R'がピラミッドの面である場合，H(F)の最大利得の許容路（admissible path）に対応する．
□したがって，最適ピラミッド問題を循環路を持たない有向グラフ H(F)の最大重み経路(maximum-weight-path)問題にすることができる．H(F)の各有向閉路が大部分で n 辺を持っていることに注意する．ダイナミックプログラミングアルゴリズムを使うことによって，次の結果を得る：
Theorem 3 M 個の異なる領域の F のための最適ピラミッ
ドは O(M2 n) 時間で計算できる．
□
しかし，上記のアルゴリズムは実用的ではない．例えば，長方形の領域族は O(n2)領域を持っている．従って，上記の計算

3

時間は O(n５)である．さらに，正確な階層状の領域ルール計算のために，M が n において幾何級数的に大きい族を考える．
したがって，特別な領域族のために，より効率的なアルゴリズムを考える．

5.2

直交領域の stabbed union

Γの領域の典型的な閉集合族について考える．Γの固定セル
c については，各々が含んでいる直交領域の結合として R を表わすことができる，Γの領域 R は c で直交領域の stabbedunion と呼ぶ．セル c は R の中心セルと呼ぶ．2 次元の場合は矩形和楕円型領域とほぼ同一で，相異はグリッド点の替わりにセルを考える点である．
セル c のすべての stabbed union 族が閉集合族であることは明らかである; 実際，c を含んでいるすべての長方形集合族に対して閉じている．与えられたピラミッドは，中心セルでのstabbed union 族に基づいている．当然，中心セル(あるいは点)は，ピラミッドのピークである．最適ピラミッドを計算するためのアルゴリズムを設計するためには，stabbed unions 族の最大パラメトリックゲイン領域計算のために効率的なアルゴリズムを必要とする．上記の目的のために，問題を一般化し，グラフアルゴリズムを適用する．

5.3

グリッドグラフ推移は閉包

ボクセルグリッΓにおいて，中心セル c = (c1, c2,…,cｄ)を固定し，頂点セットがΓのすべてのボクセルから成る有向グラフ
G(c)を定義する．ボクセル p = (p1, p2,…, pｄ)および q = (q1, q2,…, q ｄ ) に つ い て ， p と q の 間 の L1 距 離 はdist ( p, q )∑ i =1| pi − qi | である．p の近隣のセルとは p からdの L1 距離が 1 のセルである．セル p およびその近隣 q について，有向辺が定義される.その方向は dist(p,c)= dist(q,c)+1 の場合(p,q)(つまり p から q まで) であり，そうでなければ (q,p)
である．グラフ G(c)は d(m-1)×md-1=O(n) 辺(d は定数とする)の弱い連結有向グラフであり，また，c はそのユニークな sink頂点(つまり出発する辺のない頂点)である．
G(c)の部分グラフ H=(V,E)において，V の各頂点 v から c までの H に有向路が存在する場合，H を根付き部分グラフ(rootedsubgraph)と呼ぶ．
G(c)の根付き部分グラフ H=(V,E) が与えられ，H に v から uまでの有向路が存在する場合，頂点 u が頂点 v によって H において支配されると言う．頂点の集合 W において，W のすべての頂点 V に対し,V に支配される頂点がすべて W に含まれる
とき，W を H-閉包と言う．各 H-閉包はΓ中でセル c を含んでいる連結領域を定義する．
与えられた G(c)の根付き部分グラフ H の，すべての H-閉包の集合族 FH を考える．推移閉包であるという性質は集合和と集合積について閉じているので，次の命題が示せる:
Proposition 1 G(c)の根付き部分グラフ H について，FH は閉集合領域族である．
□次の補題は，G(c)および FH の定義からなる．
Lemma 5 Γの中の領域 R は，G(c)-推移閉包の場合のみ cの stabbed union である．
□Lemma 6 H と H'を G(c)の全域根付き部分グラフとする．
このとき，H が H'の部分グラフならば FH ⊇FH'である．
□5.4

FH の最適ピラミッド計算アルゴリズム

G(c)の根付き部分グラフ H を固定する．FH に関しての最適ピラミッドの面の高さを定義するパラメーター値 t を考える．
また，各ボクセル p(H の対応する頂点)に重さρ(p) – t・μ(p) を与える．次の補題により，面の高さを与える t が小さな分母お日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
よび分子を持つ有理数であると仮定できる．
Lemma 7 t がある領域族のための最適ピラミッド面を定義する高さである場合，t は N 以下の 2 つの整数の比によって表わされる有理数である．
□Proof t が面 Pi を定義すると仮定すると，ρ(Pi＼Pi+1) = t・μ(Pi ＼Pi+1)である．ρとμは N 以下の整数値をとるので，補題は成り立つ．
□定義によって，最大(パラメトリック)ゲイン領域 Popt (t)∈FHは，領域のボクセル重みの合計を最大限にする H-閉包である．
グラフ理論的な用語では，重み付き有向グラフ H の最大推移閉包であり，辺の集合(cut set)の削除により c を含んでいる H の連結成分として得られる．
Theorem 4 ( Hochbaum )実数頂点重みを持つ n 頂点と m 辺からなる有向グラフ G の最大重み閉包は O(T(n,m))時間で計算できる．ここで，T(n,m)は非負辺重みを持つ n 頂点と m 辺からなる有向グラフ H の最小 s-t カット計算時間である．□
Theorem 5 集合族 FH のための最適ピラミッドは O(n1.5 log□
n log2 N)時間で計算できる．
Proof N 以下の N 整数の対によって定義された有理数の集合 S の中のすべての可能な面の高さを知るために，2 分探索の一般化を適用する．プロセスは多くの部分プロセスに分岐するので，2 分分岐探索と呼ぶ．t0 < t1 に対し，Popt(t0)と Popt(t1)をすでに計算していると仮定する．
Popt(t0) = Popt (t1)の場合，区間 I = (t0, t1)を inactive にする．
そうでなければ，アクティブと呼ぶ．区間がアクティブならば，t01 を t(t0,t1)の中央値(正確には，中央値近似する S の要素)とする．FH 族が閉集合族なので，Popt(t1)⊂Popt(t01) ⊂ Popt(t0)である．したがって，Popt(t01)の計算に際しては，H から Popt(t0)の外側の頂点をすべて取り除き，Popt(t1)の内部の頂点を単一頂点へ縮約できる．したがって，|Popt(t0)|-|Popt(t1)|個の頂点を持つ有向グラフ H(I)の最大推移閉包を計算すれば十分である．
2 分分岐探索は各レベルにおいて，前のレベルで作られたアクティブな区間を 2 つの区間へ分離する．初期の全区間の長さは高々N であり，葉区間の長さは少なくとも 1/(N-1) - 1/N =1/N(N-1)であるので，レベルの数は O( log N3 ) = O(log N)である．各レベルで，すべてのアクティブな区間 I の H(I)の頂点の数の合計は O(n)である．大きさ n のグラフの最大推移閉包を求める計算時間は T(n,n)= O( n1.5log n log N)である．
したがって，各レベルを処理する計算時間は O( n1.5log n log N)である．し□たがって，総計算時間は O( n1.5log n log2N)である．
Theorem 6 与えられたセル c の直交領域 stabbed union の集合族に対する最適ピラミッドは O( n1.5log n log2N)時間で計算できる．
□6. まとめと今後の課題
ピラミッド構造はいくつかの分野で有用である．まず，確信度分布の傾向の良いビジュアル化を与える．次に，しきい値の高さ t 以上のピラミッドの一部の選択によって(このオペレーションを切り取りと呼ぶ)，領域内部のその実際幾何学的な位置に依存する各データに対するルールの影響に基づいた情報と一緒に結合ルールを与える領域を生成することができる.
一旦領域ルールを得れば，オリジナルのデータ分布からピラミッドを引き平均確信度をもって同じ先行のサポートを補充することにより，容易にこのルールの影響を削除することができる.さらに，より弱いルールを抽出することができる．また，異なるピークを備えたピラミッドを同時に考えることにより，データから 2 つ以上の階層化ルールを抽出できる．
これにより，

4各々のそのようなピラミッドからの高い一部分を切り取ることにより，データの大多数をカバーするクラスタリングを自動的に与える．第 4 に，すべてのピークでのピラミッド近似で離れ値であるデータアイテムを，例外的なデータ(恐らくある入力エラー)あるいはあいまいなデータと見なすことができるので,データクリーニングのために潜在的に使用することができる．
適切な領域族の選択は非常に重要な問題である．
データマイニングアプリケーションのための良い族を定義することに役に立ち，d ≧3(特に d=3)の時，頂点の各出次数，入次数の良いパラメーターを発見する実験を行う．

[文献］[AIM] R. Agrawal, T. Imielinski, A. Swami, Mining Association Rules
between Sets of Items in Large Databases, Proc. SIGMOD (1993)
207--216.
[CCKT02] D. Chen,J. Chun, N. Katoh, and T. Tokuyama, Layered Data
Segmentation for Numeric Data Mining, Presented at Submitted．
[CKT02] J. Chun, N. Katoh, and T. Tokuyama, How to Reform a Terrain
into a Pyramid, Presented at DIMACS Workshop on Geometric GraphTheory (2002).
[CST02] J. Chun, K. Sadakane, T. Tokuyama,Improved Algorithms forConstructing Pyramids from Terrains. Presented at Japan Conference on
Discrete and Computational Geometry(2002).
[FMMT96b] T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama,
SONAR: System for Optimized Numeric Association Rules, Proc. SIGMOD
1996 (1996) p.553.
[FMMT99] T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama,
Mining Optimized Association Rules for Numeric Attributes, Journal ofComputer and System Sciences 58 (1999) 1-12.
[FMMT01] T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama,
Data Mining with Optimized Two-Dimensional Association Rules, ACM
Transaction of Database Systems 26 (2001) 179-213.
[YFMMT97]K. Yoda, T. Fukuda, Y. Morimoto, S. Morishita, andT. Tokuyama,Computing Optimized Rectilinear Regions for AssociationRules, Proc. KDD97 (1997) 96-103.

全 眞嬉Jinhee CHUN

東北大学大学院情報科学研究科システム情報科学専攻博士後期課程在学中．2003 年東北大学大学院情報科学研究科システム情報科学専攻博士前期課程修了．データマイニングに関する研究．電子情報通信学会学生会員，日本データベース学会学生会員．

Danny Z. CHEN
Notre Dame 大 学 Dep. of Computer Science andEngineering 教授．1992 年 Purdue 大学(Ph.D., ComputerScience)．アルゴリズム，計算幾何学，データマイニング等の研究に従事．ACM 会員，IEEE シニア会員．

加藤 直樹

Naoki KATOH

京都大学大学院工学研究科建築学専攻教授．1977 年 9 月京都
大学大学院高額研究科博士後期課程中途退学（工学博士）．組合せ最適化，離散アルゴリズム，計算幾何学，建築システム最適化，データマイニング等の研究に従事．情報処理学会，電子情報通信学会，建築学会，ACM 各会員．

徳山 豪

Takeshi TOKUYAMA東北大学大学院情報科学研究科情報システム評価学分野教授．
1985 年東京大学理学系大学院数学専門課程卒(理学博士）．理論計算機科学（特に計算幾何学を中心とした離散アルゴリズム理論），離散数学，データマイニング等の研究を行う．情報処理学会アルゴリズム研究会主査．電子情報通信学会，日本数学会，日本ＯＲ学会，応用数理学会，ＡＣＭ各会員．

日本データベース学会 Letters Vol.2, No.1