幾何学的制約に基づいた高相関変数集合導出手法

幾何学的制約に基づいた高相関変数集合導出手法

Derivation of High Correlation Coefficients based on Geometric

Constraints

中西耕太郎

1∗

鷲尾隆

1

Kotaro Nakanishi

1

_{and Takashi Washio}

1

1

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

1

_{Department of Advanced Reasoning,}

The Institute of Scientific and Industrial Research, Osaka University.

Abstract: Correlation analysis among variables are frequently used in various approaches of statistics and data mining. However, its application to the data obtained from the recent ubiquitous sensing system consisting of massive sensors is often intractable, since its computational complexity is proportional to the square number of variables. On the other hand, the strong correlations among the variables are usually sparse in various data such as small world data. In this report, we propose a novel method to efficiently estimate the correlations among massive variables under this sparseness. Its experimental evaluations show excellent performance in efficiency comparing with the direct computation of all correlation coefficients.

1

はじめに

相関解析は統計的因果推論に代表されるように，デー タマイニングや統計数理の様々な分野で用いられる基 礎的解析手法である [1, 2]．例えば，最新鋭の発電所や 自動化が進む自動車工場での異常検出 [3, 4] 等では，人 間の知覚に代わる異常監視センサから得られるデータ を解析し，”異常 X はセンサ A, B, C にのみ多大な影 響を与える．”といった，センサの値と異常との相関関 係を導出して知識ベース化することにより，異常診断 の自動化が可能となる．このように，相関解析は学術 的基礎手法であるのみならず，様々な工学的分野で多 用されている． 相関解析は，変数を列，事例を行とした二次元配列 の形式で構成されるデータを対象とする．例えば，変数 個数 M ，事例数 N のデータは以下の形式で表される． 但し，i 番目の事例における変数 j の値を xijとする． 変数1 · · · · · · 変数M 事例1 .. . .. . 事例N        x11 · · · · · · x1M .. . . .. ... .. . . .. ... xN 1 · · · · · · xN M        ∗_{連絡先：大阪大学産業科学研究所}       〒 567–0047 大阪府茨木市美穂ヶ丘 8-1        E-mail: [email protected] 相関解析の目的は，このようなデータから強い関連を 有するすべての変数ペアを導出することである． 相関解析では，解析対称データに含まれる M 個の変 数から構成しうる全ての変数ペアに関して，相関係数 を計算しなければならない．即ち，MC2個の相関係数 を計算しなければならない．また，その都度，それぞ れ N 事例分存在する各変数の値にアクセスしなければ ならない．故に，相関解析の時間計算量は O(M2N ) と なる．故に，相関解析が解析対象とし得るデータの変 数個数は，実用的観点から制限される． しかしながら，今日，計算機の処理能力の向上，大容 量記憶媒体の低価格化，情報通信技術の急速な発展等 により，データの大規模次元化が進んでいる．例えば， 先程述べた発電所や自動車工場では，より詳細な異常 監視のために数万個を超えるセンサを含む最新鋭の異 常診断設備が導入され，センサ数が爆発的に増加してい る．また，最近の新しい技術動向として，RFID((Radio Frequency Identification) タグによる物流管理に代表さ れるように，ユビキタスセンシング技術の普及により， 膨大な変数によって事象を詳細にデータ化できるよう になって来た．このようなデータに相関解析を適用す れば，これまでの解析対象データからでは得ることが 出来なかったより詳細で有意な相関関係を知識として 導出できるであろう．しかしながら，先述のように従 来の相関解析では変数個数が増大すると計算量が著し く増大するため，大規模次元データに対する適用が困

人工知能学会研究会資料

SIG-DMSM-A603-17 (2/28)

難である． 一方，相関解析が対象とするデータでは，強い相関 関係を有する変数の組み合わせが限られる，即ち，強 い相関関係が疎であることが多い．例えば，数万近いセ ンサによって異常検出を行う発電所の異常診断等でも， タービンの温度やガス圧などに大きな影響を与える他 の物理的主要変数は多くても１０に満たないことが多 い．例え大規模次元データであっても，効率よく高い 相関係数を持つ変数関係の集合のみを導出することが できれば，相関解析の適用範囲は飛躍的に広がるはず である．そこで本研究では，疎な高相関関係を有する データについて，相関係数が持つ幾何学的制約に基づ いて変数間の高い相関関係を効率的に推定する．提案 手法では，相関係数を全ての変数の事例データにアク セスして直接計算するのでは無く，既に求めた相関係 数値から推定する．提案手法は各事例へのアクセス及 び相関係数の直接計算量を削減することによって，効 率的に高相関関係の集合を導出する．

2

相関係数の幾何学的制約

はじめに，当研究における変数ペア間の相関関係と その強弱について定義する． 定義 1 (相関係数) N 個の事例に関する変数 X, Y の 相関係数 γXY は下式で表される．但し，xi, yiはそれ ぞれ i 番目の事例に関する変数 X, Y の値であり，¯x, ¯y はそれぞれ x, y の平均値を表し，ベクトル ~X = (x1− ¯ x, x2− ¯x, ..., xN− ¯x)T，~Y = (y1− ¯y, y2− ¯y, ..., yN− ¯y)T がなす角度を θ_{X ~}~_Y とする． γXY = PN i=1(xi− ¯x)(yi− ¯y) qP_N i=1(xi− ¯x)2 qP_N i=1(yi− ¯y)2 = X · ~~ Y | ~X||~Y | = cosθX ~~Y 相関係数は変数間の相関関係が高いとき，その絶対値 が１に近づき，相関関係が弱いとき，その絶対値が０ に近づく．定義 1 の式は相関係数が２つの変数値ベク トルのなす角度という幾何学的意味を持つことを表し ている． 定義 2 (相関の強弱) ある変数 A, B 間の相関係数 γAB について，|γAB| が閾値 γth(0 ≤ γth< 1) 以上であると

き，変数 (A, B) 間は強い相関を持つ (Stlongly

Corre-lated) とする．また，|γAB| が γth未満であるとき，変

数 (A, B) 間は弱い相関を持つ (Weakly Correlated) とする．全ての変数のペアは強い相関，若しくは弱い 当研究では，強い相関を持つ変数ペアを高相関関係集 合として導出する． 次に，前述した相関係数の幾何学的意味に基づき相 関係数を推定する原理について述べる． 定理 1 (相関係数の推定区間) ある変数 A, B, C に関 して，(A, B) 間の相関係数 γAB= cosθAB，(A, C) 間

の相関係数 γAC= cosθACが既知であるとする．この とき，(B, C) 間の相関係数 γBC = cosθBCがとり得る 値は以下の区間に制限される． cos(θAB+ θAC) ≤ γBC≤ cos(θAB− θAC) 上記定理の厳密な証明は割愛し，ここではより直感的に 分かりやすい幾何学的説明を行う．定義 1 より，相関係 数は N 次元のベクトルがなす角に対応することを述べ た．その性質を用いて定理 1 を説明する．先ず，定義 1 と同様に，変数 A, B, C をそれぞれベクトル ~A = (a1−

¯a, x2− ¯a, ..., aN− ¯a)T，~B = (b1−¯b, b2−¯b, ..., bN−¯b)T，

~ C = (c1− ¯c, c2− ¯c, ..., cN− ¯c)Tとする．ここで，３本の ベクトルの位置関係を γAB= cosθAB，γAC= cosθAC より，図 1 の様に ~A を z 軸とする三次元直行座標空間 に射影する．このとき，(B, C) 間の相関係数 γBC が とる値は，ベクトル ~B, ~C がなす角 θBCによって定ま る．ここで，θBCの最大値と最小値を考える．図 1 の x − y 平面において， ~B, ~C が x 軸と反時計回りになす 角を φB, φCとする．θBC は φC = φB のとき最小値 をとり，そのとき γBC は最大値 cos(θAB− θAC) をと る．即ち， ~C が図 1 の ~Cmaxである．同様に，θBC は φC= φB+ π のとき最大値をとり，そのとき γBCは最 小値 cos(θAB+ θAC) をとる．即ち， ~C が図 1 の ~Cmin である． 定理 1 に示す相関係数の推定区間が閾値以上の区間 [γth, 1] 若しくは [−1, −γth] に存在すれば，その相関係 図 1: ３次元空間への射影

数の真値を計算せずとも強い相関であることがわかり， 逆に閾値以下の区間 (−γth, γth) のみに存在すれば，相 関係数の真値を計算せずとも弱い相関を持つことがわ かる．但し，相関係数の推定区間がこれらに当てはま らない場合は，相関が強いか弱いか判定できない．尚， 幾何学的制約によって変数 B, C 間の相関関係を推定す る際には，ある変数 A と B, C との相関係数がそえぞ れ明らかになっている必要がある．ここでは幾何学的 制約を仲介する変数 A を Moderator と呼ぶ．

3

高相関関係集合の効率的探索

3.1

探索処理の概要

提案する探索処理の概要を図 2 に示す．はじめに，解 析するデータと閾値を入力する．入力されたデータは， 主記憶上に二次元配列の形式で格納し，後に相関係数 を計算する際の演算回数節約や計算精度向上のため，i 番目の事例における j 番目の変数 Xjの値 xij を以下の 式に基づいて x0ijに正規化する．但し，変数 X の各事 例に関する平均を ¯X，同じく，標準偏差を σXとする． x0ij= xij− ¯Xj σX j 次に，ある Moderator を仲介として定理 1 の幾何学 的制約を適用し，Moderator 以外の変数同士の相関係数 の区間を推定する．ここで，データ中の全変数の集合を X = {Xi|i = 1, ..., M } とする．そして，これらの変数全 ペアの集合を P = {< Xi, Xj > |∀Xi, Xj ∈ X, j > i} とする．このとき，P の要素数 |P | はMC2となる．は じめにある Moderator 変数 A1∈ X を選択し，X から A = {A1} を除いた変数集合 XA= X − A の全ての変 数と A1の相関係数を求める．次に XA内の全ての変数 ペアの集合 PA= {< Xi, Xj > |∀Xi, Xj ∈ XA, j > i} について定理 1 に示した幾何学的制約を用いて相関係 図 2: 探索処理の概要 数値の区間を計算する．但し，実際には PAに含まれる 全ての変数ペアに関して，その相関係数値の区間を導 出するのではなく，後述する幾何学的制約の効率的適 用法に基づいて，相関が強いか弱いかを判定する．そ して，幾何学的制約の適用結果として，強い相関と判 定された全ての変数ペア集合を SA，弱い相関と判定さ れた全ての変数ペア集合を WAとする．次に，SA, WA を PAから除いた P0= PA− SA− WAを得る．次に， |P0_{| = 0 であれば計算を終了し，|P}0_{| 6= 0 であれば，以} 下，同様に Moderator 変数 Ak ∈ X(k = 2, ...) を選択

し，A = A∪{Ak} と A を更新し，XA= X−A に含まれ

る全ての変数と Akとの相関係数を計算する．そして，先 程と同様に PA= {< Xi, Xj > |∀Xi, Xj ∈ XA, j > i} として，PA∩ P0について，幾何学的制約を適用して SA, WAを導出する．このときも，PAに含まれる全ての 変数ペアの相関係数値の区間を計算するのではなく，後 述する効率的幾何学的制約適用法を用い，演算回数を最 小限に抑える．SA, WAより P0 = (PA∩P0)−SA−WA を計算し，|P0| = 0 になれば，計算を終了し，|P0| 6= 0 であれば，新たな Moderator を選出し，同様の処理を 繰り返す．尚，提案手法では既に Moderator との相関 が強いか弱いか判明した変数に関して，Moderator と の相関係数を計算しないため，Moderator との相関が 強いか弱いか判明している変数が少なければ，幾何学 的制約によって相関の強弱を推定できる変数ペアの数 が減ってしまう．故に，Moderator の選出基準は，P0 において自己と相関が強いか弱いか不明な変数が最も 多い変数とする． 提案手法の流れを具体例を通じて解説する．例えば， X = { 気温 T, 湿度 D, 日射量 H, 風速 V } の場合を考え る．はじめに Moderator 変数を A1= 気温 T とすると， A = { 気温 T } より XA= { 湿度 D, 日射量 H, 風速 V }， PA= {< 湿度 D, 日射量 H >, < 湿度 D, 風速 V >, < 日射量 H, 風速 V >} である．定理 1 の幾何学的制約を 用いた PAの各変数ペアの相関係数値の区間計算から， 例えば SA= < 湿度 D, 日射量 H >,WA= φ であった とする．これより P0 = {< 湿度 D, 風速 V >, < 日射 量 H, 風速 V >} である．P0中では 風速 V と他変数との ペアが最も多いため，次の Moderator 変数として A2= 風速 V を選択し，A = A ∪ { 風速 V } = { 気温 T, 風 速 V } と更新する．これにより XA = { 湿度 D, 日射 量 H}，PA = {< 湿度 D, 日射量 H >} となる．し かし，PA∩ P0 = φ であるため，SA = φ, WA = φ, P0_{= P} A∩ P0− SA− WA= φ となり処理を終了する．

3.2

効率的探索の実現

3.2.1 幾何学的制約適用上の問題点 本節では，前節で述べた Moderator を介した幾何学 的制約に基づく処理の問題点について述べる．相関係 数の幾何学的な性質によって，相関が強いか弱いか推 定できる．しかしながら，推定された相関係数値の領 域が，閾値以上の領域と閾値以下の領域にまたがって いれば，相関が強いか弱いか判定できない．仮にある Moderator に関して，Moderator との相関が強いか弱 いか未知である全ての変数との相関係数を計算し，そ れらの変数ペア全てについて幾何学的制約を適用した 結果，一切強弱の判定を得ることができなかったとす る．以後の Moderator に関しても，同様の処理を繰り 返し，一切幾何学的制約によって強弱の判定を得るこ とができずに，アルゴリズムが終了したとする．その とき，相関係数の時間計算量は，変数個数 M ，事例数 N に対して O(M2_{N ) となる．それに加え，幾何学的} 制約の適用回数は， M −1C2+M −2C2+ ... +2C2 = ΣM −1i=1 iC2 = ΣM −1 i=1 M (M − 1) 2 = M 6 (M − 1)(M − 2) となる．故に，幾何学的制約の適用に関する時間計算量 は O(M3) となり，提案手法全体の時間計算量は O(M2 N + M3_{) となるので，相関係数を直接計算した場合よ} り大きくなってしまう．これでは，提案手法は実用に 耐えない． 3.2.2 効率的な幾何学的制約適用の実現 前述した時間計算量の問題は強弱判定結果を得るこ とができない多数の幾何学的制約の適用が原因である． そこで，当研究では強弱判定結果を得ることができな い変数ペアに幾何学的制約を適用せず，有意な結果を 得ることができる変数ペアのみに幾何学的制約を適用 する．以下，この実現方法について述べる．幾何学的 制約で全ての変数ペアの相関の強弱を判定するのでは なく，Moderator とある変数 B 間の相関係数値より， 幾何学的制約によって B との相関が強いか弱いか判定 される任意の変数 X が Moderator との間でとり得る 相関係数値の区間を導出する．ここで，この変数 B の ことを Base と呼ぶことにする．このとき，A との相関 係数値が先程導出した区間内に存在する変数は，幾何 学的制約によって相関が強いか弱いか判定できる．以 下に，相関が強いと判定可能な区間に関する定理を述 べる． 定理 2 Moderator を変数 A として，ある Base 変数 B との相関係数 γAB = cosθAB が既知であるとする． このとき，相関が強いか弱いか判定する閾値を γthに 対して |γAB| > γthであるとき，幾何学的制約によっ て B との相関が強いと判定できる任意の変数 X がと り得る相関係数値 |γ| の区間は以下の様になる．但し， ˆ θAB(0 ≤ ˆθAB ≤ π₂) は |γAB| = cosˆθABである角とし， θthは γth= cosθthである角とする． {γ|cos(θth− ˆθAB) ≤ |γ| ≤ 1} 証明は省くが，この区間は相関係数の絶対値で表現で きる．同様に，相関が弱いときに判定可能な区間に関 する定理も存在するが，紙面の都合上省略する．Base との相関係数がこの区間を満たす変数 X のみについて 幾何学的制約を適用すれば，Base と X の相関係数値 の強弱判定結果を得ることができない幾何学的制約の 適用回数が減少する． しかしながら，探索条件を満たす変数ペアのみに幾 何学的制約を効率的に適用するためには，それに特化 したデータ構造とアルゴリズムが必要である．そこで， 当提案手法ではソートを導入し，Moderator との相関 係数値によって変数を整列した上で幾何学的制約を適 用する．図 3 に，Moderator と他の変数の間の相関係 数をソートしたときの状態を示す．このとき，探索条 件は Moderator である変数 A との相関係数 γ につい て，0.906 ≤ |γ| ≤ 1 とする．この条件を満たす変数を 探索するとき，図 3 の様に，ソートされた相関係数値 の先頭と末尾から変数を調べれば，有意な判定結果を 得ることが出来ない変数の数え上げを最小限に抑える ことができる．しかしながら，仮にソートを用いても， ソートの時間計算量が大きければ，幾何学的制約を適 用する変数を減らすことによる計算時間削減の効果は 薄い．故に，提案手法では高速なソートが求められる． 更に，ソートの適用頻度に関して述べる．３．１節 で述べた記法に従い，ある Moderator を Akとし，Ak を含めこれまで Moderator として用いた変数の集合を A としたとき，まだ相関係数が未知である集合 XA内 の各変数と Akの相関係数をデータから計算して，これ ら相関係数値によって XA内の各変数を X1, X2, ... の 図 3: 探索条件とソート

図 4: 提案手法で採用するデータ構造 ようにソートしたとする．ここで，例えば最初の変数 X1を Base B1とし，(B1, X2) の相関の強弱が幾何学 的制約によって判定できたとする．このとき，その次 に変数 X2を新たな Base B2とし，B2との相関の強弱 を幾何学的制約によって判定できる変数を探索したと する．しかしながら，この場合，X1を Base としたと きに得た (B1, X2) を (B2, X1) として二度得ることと なる．このように，Moderator との相関係数値を全て 導出した後にソートをしたのでは，同じ判定断結果を 二度得てしまい非効率である．この問題を解決するた め，先ず XAにおいて，X1より順次 Xiと Akとの相 関係数値を計算したとき，既に Akとの相関係数値を 計算した変数 Xj (j < i) で構成される順列を {X} と する．但し，{X} は既に Xj と Akとの相関係数値に よってソートされている．提案手法では Akを選出し た後，X1より順次 Xiと Akとの相関係数値を計算し てソートしながらかつ Xiを Base 変数 Biと見なした 場合の {X} に対する幾何学的制約が適用可能な変数の 探索を実行する．そして，Base として幾何学的制約が 適用可能な変数の探索を終了した Biを {X} に挿入す る．先に述べたように Xiが Base 変数 Biの時 {X} は Xj (j < i) のみで構成されるが，例えば X1を Base 変 数 B1とする探索では該当する j < 1 の変数が存在せ ず |{X}| = 0 であるため，(B1, X2) 間の判定を行うこ とはないが，変数 X2を Base 変数 B2とする幾何学的 制約が適用可能な変数の探索では，{X} の要素である X1より，(X1, B2) 間の判定断結果を得る． ここで，{X} のソートは既にソートされた X1から Xjまでの変数の中に，新たに一つの変数 Xiを挿入す る形になる．このとき，Xiを挿入する箇所に直接アク セス可能であれば，ソートに関する計算量を低く抑え ることが可能である．このような挿入を行いやすく，か つ時間計算量の少ないソートとしてバケットソートが ある．バケットソートは，ソートすべき要素のすべて値 域に対して，一定区間刻みのバケットを用意する．ソー トする要素を各々の値を含む区間のバケットに格納す ることでソートを実現する．バケットソートはその時 間計算量が O(M) であると同時に，各バケットとそれ が含む要素の間のインデキシングが容易であるため効 率的に要素参照や挿入が可能で，提案手法に適すると 図 5: Moderator に関する幾何学的制約適用処理 考えられる．ただし，バケットソートを適用する際に は，ソートする要素の値域が予め限定されていなけれ ばならない．提案手法では-1 から 1 までの連続値であ る相関係数をソートするため，適切なバケットの区間 を設定する必要がある．そこで，提案手法では有効桁 の概念を導入した．有効桁以下の値を無視すれば，相 関係数がとり得る値を離散化でき，バケットソートを 適用できる．人間にはせいぜい相関係数の有効数字は ３桁までなので，妥当な有効桁の設定により，提案手 法より得られる情報が人間にとって意味を失うことは ない．尚，提案手法では，ユーザが有効桁を設定する． これまで，当研究で採用するバケットソートとバケッ トソートを採用するための有効桁について説明した．図 4 に，ある Mediator 変数 Akに関して XA内の変数を ソートした結果を格納するデータ構造の例を示す．図 中最上段の配列は各バケットに対応する相関係数値の 絶対値を表す．その下に位置する配列がバケットに相 当するリスト配列であり，それぞれには上段の各要素 から伸びた矢印で接続される変数 Xiが格納される．例 えばこの図から，変数 x1, x9はそれぞれ ModeratorAk との相関係数が 0 であることがわかる．ここで，Base と強い相関を持つ変数の探索区間が 0.98 ≤ |γ| ≤ 1 で あるとする．このとき，図中の 0.98 と 0.99 に対応する バケット内のリスト配列のみにアクセスすれば，Base と強い相関を持つ変数 x2, x5を効率的に抽出できる． 提案手法では，このように有効桁の概念とデータ構造 を導入することにより，効率的相関関係の探索を実現 する．

3.2.3 効率的幾何学的制約アルゴリズム 以上の説明を踏まえ，図 2 の Moderator に関する幾 何学的制約適用処理に相当する効率的な幾何学的制約 適用アルゴリズムについて述べる．その概略を図 5 に 示す． 先ず，バケットを初期化し，Moderator との相関係 数値に従い，変数を格納する準備を整える．尚，バケッ トは前節にて説明したバケットソートをベースとした データ構造である．次に Base に関するループに移る． Base に関するループでは，Moderator との相関の強弱 が未知である全ての変数を順次 Base として，前節で解 説した原理に基づいて，効率的に幾何学的制約を適用 する．このループでは，先ず，Base と Moderator 間の 相関係数を計算する．次に，導出した相関係数値に基 づいて探索条件を導出する．この条件に従い，バケッ トに格納された Base との相関関係が判定可能な変数を 探索する．この探索が終了した後，Base を Moderator との相関係数値に準じてバケットに挿入格納する．こ れらの処理を，Moderator との相関の強度が不明な変 数が無くなるまで繰り返し，Moderator に関する処理 を終了する． 最後に，本節で提案した効率的幾何学的制約適用処 理の最良時間計算量と最悪時間計算量について述べる． 最良時間計算量はある Moderator を通じた効率的幾何 学的制約適用処理で，全ての変数ペアの相関が強いか 弱いか判明したときである．このとき相関係数の計算 回数は M − 1 回であり，各相関係数の計算はデータ数 N に比例するため (M-1)N となる．また，幾何学的制 約の適用回数はM −1C2 = (M −1)(M −2)₂ であり，以上 を合計するとその時間計算量は O(M N + M2) となる． また，最悪時間計算量は幾何学的制約が一切適用され なかったときである．このとき幾何学的制約の適用は ない．しかし，相関係数の計算回数はMC2=M (M −1)₂ 回となり，各相関係数の計算はデータ数 N に比例する ため最悪時間計算量は O(M2N ) となる．

4

人工データへの適用

提案手法の性能評価実験として，３種類の人工デー タを用意した．相関が強い変数のペアが存在しないデー タ，全ての変数のペア間における相関が強いデータ，幾 つかの高相関変数集合が混在するデータの３種類であ る．これらの３種類のデータを，それぞれ random デー タ，dense データ，middle データと呼ぶ．以下に，各々 の生成方法を簡潔に述べる．random データは，デー タ中の全事例の変数値に無作為に乱数値を割り当てる． 従って，任意の変数のペアにおける相関は存在しない． 次に，dense データの生成方法について述べる．事例 j 図 6: rand データの相関係数分布 図 7: dense データの相関係数分布 図 8: middle データの相関係数分布 次の式で決定する． xij = air1j+ (1 − ai)r2j 但し，r1j, r2jは事例 j ごとに与えられ，全ての変数 Xi に亘って一定な乱数であり，aiは各変数毎に与えられ る値である．aiが大きな変数同士は乱数 r1jの成分を 共有するので，互いに高い相関を有する．同じく aiが 小さな変数同士は乱数 r2jの成分を共有するので，互い に高い相関を有する．そして，これら２つの変数グルー プ間では，乱数成分を共有しないので相関が低くなる． 最後の midlle データは，変数個数 M/5，事例数 N が 等しい５つの dense データを結合して生成する．１つ の dense データに含まれる変数と異なる dense データ に含まれる変数間の相関はきわめて弱い．それに対し て，それぞれの dense データ内における相関は極めて 高い．これら３種類のデータに対して，それぞれの相 関係数分布を図 6, 7, 8 に示す． 各々のデータにつき，事例数を 10000 に固定し変数 個数を変動させた場合について，提案手法を適用して

図 9: random データの変数個数と計算時間の関係 図 10: dense データの変数個数と計算時間の関係 図 11: middle データの変数個数と計算時間の関係 的に導出した場合と比較する．尚，提案手法の閾値は 0.85 とした．random，dense，middle の各データに対 する結果をそれぞれ，図 9, 10, 11 に示す．但し，図 10 では提案手法の計算時間の変化がわかり辛いため，図 12 に提案手法に関する図 10 の拡大図を示す． 図 9 より，random データでは提案手法の計算時間は 概ね変数個数の２乗に比例することがわかる．また，提 案手法の計算時間は，相関係数値を直接計算したとき の時間計算量より僅かに大きい．図 6 に示した random データにおける相関係数分布では，相関係数値は絶対 値が 0.05 以内の領域のみに分布する．このとき，強い 相関に関する幾何学的制約は random データに絶対値 が 0.85 以上の相関係数がないため適用されることは無 い．また，弱い相関に関する幾何学的制約については， 詳細は割愛するが，Moderator とその他の変数の相関 係数の分布が絶対値 0.05 以下で，かつ Moderator と Base の相関係数がゼロに近いとき，Base とその他の変 数の相関係数が弱いと判定可能な Moderator とその他 図 12: 図 10 の提案手法に関する拡大図 の変数の相関係数の区間が最も広くなる．しかし，そ の場合の区間も 0.527 以上であり，何れの相関係数値 の絶対値も 0.05 以内である dense データでは，判定可 能な変数ペアは存在しない。従って，提案手法は最悪 時間計算量をとる．前節の最後に述べたように，提案 手法の最悪時間計算量は理論上 O(M2N ) となる．こ れは相関係数を直接計算する場合の計算量に等しいが， 探索条件を求めるオーバヘッドの分だけ提案手法は直 接計算時間より遅くなる． 次に dense データと middle データに対する適用結果 に関して考察する．図 10，11 より，これらのデータに おいては提案手法の計算時間は直接計算に比べて少な い．これは幾何学的制約によって，大半の相関関係が判 定できたことを示している．このときの時間計算量は， 図 11，12 より，概ね変数個数の２乗に比例している ことがわかる．紙面の都合上詳細説明は省くが，dense データに関しては幾何学的制約の適用回数はM −1C2回 となり，最良時間計算量を実現している．このときの時 間計算量のオーダは理論上 O(M N + M2) である．こ れは，相関係数を直接計算する場合の O(M2N ) と変 数個数 M の二乗に比例する点では同じだが，データ数 N には大きく依存しないため，直接計算に比べて実計 算時間は遥かに少なくなっている．

5

実データへの適用

２種類の実データに，閾値を変化させながら提案手 法を適用した．そのときの計算時間を測定し，相関係数 値を直接計算した場合と性能比較した．２種類のデー タは片方は音声信号を表す Isolet データ，もう片方は 化学構造を表す MUSK データである．Isolet データは 事例数が 6238，変数個数が 618 であり，図 13 に示す 相関係数分布を持つ．MUSK データは事例数が 6598， 変数個数は元データから事例名を表す変数等を省いた 166 変数とした．これは図 14 に示す相関係数分布を持 つ．図 15, 16 に，Isolet データ，MUSK データに対す る提案手法のと直接計算の計算時間の比較結果を示す． これらより，Isolet, MUSK 共に閾値の値にかかわらず，

図 13: Isolet データの相関係数分布 図 14: MUSK データの相関係数分布 提案手法が直接計算する場合より高速に高相関変数集 合を導出できることがわかる． 提案手法では，閾値が大きいほど計算時間は減少す る．これは，閾値の増加に従い大半を占める相関係数 が低い変数ペアが多くなるためである．一方，閾値を 大きくすることで強い相関の判定数は減少するが，解 析対象データでは高相関な変数ペアは元々疎であるた め，閾値を大きくしても強い相関の判定数はあまり減 少しない．従って，強い相関の判定数の減少よりも弱 い相関の判定数の増加が勝り，全体として相関の強弱 の判定数が増大してより効率的に相関係数の判定が行 われる． 本手法を Isolet データ，MUSK データにそれぞれ適 用し，導出された高相関変数ペア集合を図 17, 18 に示 す．但し，相関の強弱を決める閾値を 0.96 とした．元 データに変数の性質が記されていないため，これらの 変数の関連性を解説することは出来ないが，それぞれ のデータに関して，強い相関関係を持つごく一部の変 数ペアのみを効率的に限定することに成功した．この ような強い相関を有する変数ペアから，対象を支配す るメカニズムを明らかにする手がかりが得られると考 えられる． 図 15: Isolet データの閾値と計算時間の関係 図 16: MUSK データの閾値と計算時間の関係

6

今後の課題

当研究では，最大１万次元のデータに対して，提案 手法を適用し，効率的に高相関変数集合を導出した．し かしながら，提案手法はその全ての処理を主記憶上で 行うため，適用できるデータの容量には限りがある．そ こで，補助記憶上に存在するデータから，必要に応じ て適宜，必要最低限の値のみを主記憶上に読み込むこ とで，提案手法が適用可能なデータ規模は広がると考 えられる．

7

まとめ

当研究では幾何学的制約に基づいた効率的な高相関 変数集合導出手法を提案した．提案手法は相関係数が 持つ幾何学的な性質に基づき，高相関か否か推定可能 な変数のペアを探索することにより，効率的に高相関 変数集合を抽出することが可能である． 提案手法にテストデータを適用して性能評価実験を 行い，更に２つの実データに適用した．１つは音声信 号データに対する適用評価であり，相関係数を直接計 算したときより高速に高相関変数集合を抽出できる事 が分かった．もう一方は分子構造のデータに適用した 場合であり，こちらのデータに関しても効率的に高相 関変数集合を抽出できた． 今後，提案手法を基に，大規模次元データ解析の適

図 17: Isolet データから導出した高相関変数ペア集合

図 18: Isolet データから導出した高相関変数ペア集合

用が期待できる．

参考文献

[1] Simon, H. Causal Ordering and Identifiability. In Models of Discovery, pages 53-80. D. Reidel, Der-drecht, Holland, (1953).

[2] Blalock, H. M. Causal Inferences in Nonexperimental Research. The Univ. of North Carolina Press, Chapel Hill, North Carolina, (1961).

[3] Z. Sun, R. Miller, G. Bebis, and D. DiMeo. A real-time precrash vehicle detection system. Proc of the 2002 IEEE Workshop on Applications of Computer Vision, pp.171–176, (2002).

[4] K. Sycara and M. Lewis. From data to actionable knowledge and decision. Proc. of the 5th Int. Conf. on Information Fusion, Vol.1, pp.577–581, (2002). [5] Newman, D.J., Hettich, S., Blake, C.L., and Merz,

C.J. UCI Repository of machine learning databases [http://www.ics.uci.edu/ mlearn/MLRepository.html]. Irvine, CA: University of California, Department of Information and Computer Science, (1998).