論文

DBSJ Letters Vol.6, No.1

プライバシーを保護するカウント演算の多値属性分類への適用について
On Applying Privacy Preserving Count
Aggregate Queries to k-Classification

たレコードをサーバに送信する．サーバは，すべてのクライアン
トから受信した n 個の摂動されたレコードから，テーブル T 0 を構成する．すなわち，サーバは各クライアントにおいて摂動されたレコードの値は知ることができるが，各クライアントが所持する元のレコードの値を知ることはできない．したがって，このモデルでは摂動されていない元のテーブル T が構成されることはない．ただし，以降は説明を簡略化するため，テーブル T の各

高見澤 秀久 ♥有次 正義 ♦

Hidehisa TAKAMIZAWA

Masayoshi ARITSUGI

レコードを独立に摂動することで，テーブル T 0 を構成するものと考える．
本研究の目的は，摂動されたテーブルから，目的属性が 3 値以上の決定木を構築するために必要なカウント演算結果を再構築することである．本研究と同じモデルで摂動されたテーブルからカプライバシーを保護しながらデータを効果的に処理することはウント演算結果を再構築する手法は文献 [3] においても提案され重要な課題である．本稿では，プライバシー保護のために摂動さている．文献 [3] では，ある一定の確率で同じ属性の定義域内のれたテーブルから，目的属性が 3 値以上の決定木を構築するため別のランダムな値に置き換える方法により摂動されたテーブルかに必要なカウント演算結果を再構築する手法を提案する．目的属

ら，決定木を構築するために必要なカウント演算結果を再構築す性が 3 値以上の場合，従来手法では目的属性の各値の演算結果をる手法を提案している．

それぞれ独立に再構築しなければならない．そこで，本稿では従しかしながら，文献 [3] で提案されている手法を用いて，摂動来手法を拡張し，目的属性の各値の演算結果を一括して再構築すされたテーブルから目的属性が 3 値以上である決定木を構築する手法を提案する．

るために必要なカウント演算結果を再構築する場合，目的属性の各値の演算結果をそれぞれ独立に再構築しなければならない．

It is important to process data effectively while
preserving privacy. In this paper, we propose a reconstruction technique of count aggregate queries,
which are necessary for building a decision tree, froma perturbed table in cases where a target attributeis more than binary. In the conventional technique,
we must reconstruct the results of target values fromthose of each value calculated independently when adecision tree has a non-binary target attribute. In
this paper, we borrow and extend the conventional
technique to reconstruct the results of target values
at once.

そこで，本稿では文献 [3] で提案されている再構築手法を拡張して，目的属性の各値の演算結果を一括して再構築する手法を提案する．

2.

準備

2.1

関連研究

本研究におけるプライバシー保護モデルは，文献 [1, 3] で扱われている．文献 [1] では，各クライアントがもつレコードに対して，属性ごとに独立な乱数をノイズとして加算することでプライバシー保護を行う．そして，摂動されたテーブルから各属性の分布を再構築する．しかしながら，文献 [1] では，元の分布の再構築は各属性で独立に行わなければならないという問題がある．文献 [3] では，ある一定の確率で同じ属性の定義域内の別のランダ

1.

はじめにムな値に置き換える手法により，各クライアントがもつレコードを摂動する．そして，摂動されたテーブルから，決定木を構築す

近年，プライバシー保護データマイニングの研究が盛んに行わるために必要なカウント演算結果を再構築する．本研究は文献れている [1, 2, 3]．本研究では，サーバと，そのサーバに接続さ[3] を基に考える．以下では，文献 [3] で提案されている摂動手法

れた n 個のクライアント Client1 ，Client2 ，· · ·，Clientn にと再構築手法について説明する．

より構成されるモデルを考える．各クライアントは m + 1 個の2.2

属性 Attr0 ，Attr1 ，Attr2 ，· · ·，Attrm からなるレコードをそ■維持‐置換摂動 文献 [3] では，各レコードを摂動するためにれぞれ 1 つずつもっている．ここで，属性 Attr0 は決定木分類

維持‐置換摂動（Retention Replacement Perturbation）を用における目的属性でカテゴリ属性である．他の属性 Attr1 ，· · ·，いている．維持‐置換摂動は，レコードの各属性値を，属性ご

Attrm は説明属性である．各クライアントは自身がもつレコードのプライバシーを保護するために，摂動（perturbation）されとに共通なある一定の確率で同じ属性の定義域内の別の値に置♥♦

学生会員

群馬大学大学院工学研究科博士後期課程

takamiza@dbms.cs.gunma-u.ac.jp
正 会 員

熊 本 大 学 大 学 院 自 然 科 学 研 究 科

プライバシー保護 OLAP換する手法である．すなわち，この手法では摂動後も元の値がある一定の確率で維持される．この確率を維持確率（retentionprobability）として属性ごとに設定する．ここでは，ある属性Attrj における維持確率を rpj (0 ≤ rpj ≤ 1) と表現する．維持

aritsugi@cs.kumamoto-u.ac.jp1

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

論文

DBSJ Letters Vol.6, No.1

確率が小さい，つまり元の値が維持されずに他の値に置換される確率が高くなるほど摂動の割合も高くなり，プライバシーが保護されることになる．
ここで，tij は元のテーブル T の i 番目のレコードにおける j番目の属性値，そして t0ij は摂動されたテーブル T 0 の i 番目のレコードにおける j 番目の属性値とすれば，t0ij の値は確率 rpjで tij に，そして確率 1 − rpj で定義域内の他の値に置換される．
なお，本研究におけるモデルでは，各クライアントはすべての属性の維持確率と定義域を知っているものとし，それにより各クライアントは自身がもつレコードを独立に摂動することができる．
■反復ベイズ手法 続いて，文献 [3] で提案されている，維持‐置換摂動により摂動されたテーブル T 0 からカウント演算結果

minr は，それぞれ属性 Attrr の定義域の上限値と下限値である．属性 Attrr がカテゴリ属性の場合，cr は属性 Attrr の属性値の個数である．δ(i,j) は i と j の値が等しければ 1 を，そうでなければ 0 とする．
続いて，これらの式を用いて，摂動されたテーブル T 0 におけるカウント演算結果 y から元のテーブル T におけるカウント演算結果 x を再構築する手順を示す．まず，テーブル T における n 個の各レコードの状態をそれぞれ U1 , U2 , ..., Un ，テーブル
T 0 における n 個の各レコードの状態をそれぞれ V1 , V2 , ..., Vnとする．すなわち，0 ≤ p, q ≤ 2k − 1 および 1 ≤ i ≤ n に対して，P (Ui = p) = xp /n，P (Vi = q) = yq /n となる．また，
P (Ui = p) は以下の式で表すことができる．

を再構築する手法である，反復ベイズ手法（Iterative BayesianTechnique）について説明する．ここでは，テーブル T におけるk 個の属性に対してカウント演算 COU N T (P1 ∧ P2 ∧ . . . ∧ Pk )を実行した結果を再構築することを考える．なお，Pj はテーブ
ル T における j 番目の属性に対する条件式であり，例えば数値属性の場合は 25 ≤ age ≤ 40，カテゴリ属性の場合は risk = highP (Ui = p) =t
X

P (Vi = q)P (Ui = p|Vi = q)

ここで，P (Ui = p|Vi = q) は，ベイズの定理を用いて以下の式により表すことができる．

といった条件式となる．

P (Ui = p|Vi = q) =まず，元のテーブルにおけるカウント演算結果を表すベクトル

P (Vi = q|Ui = p)P (Ui = p)
P (Vi = q)
P (Vi = q|Ui = p)P (Ui = p)

x = (x0 , x1 , ..., xt ) と，摂動されたテーブルにおけるカウント演算結果を表すベクトル y = (y0 , y1 , ..., yt ) を以下のように定義

= Pt

する．

= P
xi = COU N T (∧kr=1 Q(r, bit(i, r)))in T , for 0 ≤ i ≤ t

yi = COU N T (∧kr=1 Q(r, bit(i, r)))


0(1)

xTp +1 =する条件式であり，i の値が 0 ならば ¬Pr に，そして i の値が 1ならば Pr となる．bit(i, r) は，整数 i を k ビットの二進数で表現した値の左から r 番目のビットである．そして，あるレコードが条件 ∧kr=1 Q(r, bit(i, r)) を満たすとき，そのレコードの状態をi とする．
次に，元のテーブル T での状態が p であったレコードが，摂動されたテーブル T 0 での状態が q となる遷移確率 apq は，以下の式により計算することができる．

(1 − rpr ) · Rr,bit(q,r) + rpr · δ(bit(p,r),bit(q,r))ªtXapq xTpyq Pt
a xT
r=0 rq r
q=0(6)

ここで，xT は，T 番目の繰返しを，xT +1 は，T + 1 番目の繰返しをそれぞれ示しており，初期値を x0 =y として，連続するx の違いが少なくなるまで，繰返し x を計算する．

3.

摂動されたテーブルからの決定木の構築

決定木 [4, 5, 6] における最適な分割点を決定するための評価指標としては，一般に相互情報量（mutual information），ジニ係数（gini index），χ2 （chi square）値等が用いられる [6, 7, 8]．
いずれの評価関数も，分割前後の各属性値の個数の関数として表

r=1(2)
ここで，Rr,i は，i の値が 0 ならば 1 − br ，i の値が 1 ならば brと定義する．br は条件式の範囲を表すものであり，以下の式により計算する．

現することができるため，最適な分割を探索する際にはカウント演算結果を定数として扱うことができる．

3.1

2 値属性分類のためのカウント演算

まず，反復ベイズ手法を用いて，目的属性が 2 値 C0 ，C1 の決 highr − lowr , （Attrr が数値属性の場合）

maxr − minr
br = 1,cr

(5)

そして，式 (4) に，式 (5) を代入することで，以下の式を求める

ここで，t = 2k − 1 である．また，Q(r, i) は r 番目の属性に対kY©

P (V = q|Ui = r)P (Ui = r)ir=0
apq xpta xr=0 rq r

ことができる．

in T , for 0 ≤ i ≤ t

apq =(4)q=0

定木を構築するために必要なカウント演算結果を摂動されたテーブルから再構築する手順を説明する．

（Attrr がカテゴリ属性の場合）

目的属性が 2 値の場合は，C1 = ¬C0 である．したがって，条(3)件 P1 により分割する場合，目的属性が 2 値の決定木を構築する

属性 Attrr が数値属性の場合，highr ，lowr は，それぞれ属ために必要なカウント演算は反復ベイズ手法により，一度に計算性 Attrr に対する条件式 Pr の上限値と下限値であり，maxr ，することができる．

2

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

論文
3.2

DBSJ Letters Vol.6, No.1

4.1

多値属性分類のためのカウント演算

レコードの状態の再定義

続いて，反復ベイズ手法を用いて，目的属性が 3 値以上の決定

まず，2. で定義したレコードの状態を再定義する．従来手法で木を構築するために必要なカウント演算結果を摂動されたテーブ

は，各属性の状態を示すビットにより，条件 Pi ，¬Pi を満たす

ルから再構築する手順を説明する．目的属性が 3 値以上の場合かどうかをそれぞれ 1，0 として表現していた．目的属性が 2 値は，属性値ごとのカウント演算結果が必要となる．例えば，目的の場合には，あるレコードの目的属性が「一方の属性値をもつ／属性が 3 値 C0 , C1 , C2 である集合を条件 P1 により分割する場もたない」として，目的属性の状態を 1 ビットで表現することが合，表 1 のカウント演算が必要となる．

できた．しかしながら，目的属性が 3 値以上の場合には，目的属性の状態を 1 ビットで表現することはできない．そこで，本研究

表 1 3 値属性分類のためのカウント演算

では目的属性の状態をビット列として表現する．

Table 1 Count aggregate queries for a 3-values target attribute.

目的属性

条件 P1 で分割する場合のがって，レコードの状態は，目的属性の状態を表す長さ dlog2 ce

カウント演算のビット列と，m 個の説明属性の状態を表す長さ m のビット列

COU N T (P00 ∧ ¬P1 )COU N T (P00 ∧ P1 )COU N T (P01 ∧ ¬P1 )COU N T (P01 ∧ P1 )COU N T (P02 ∧ ¬P1 )COU N T (P02 ∧ P1 )C0C1C2

目的属性の属性値の個数を c とすれば，目的属性の状態を表すために必要となるビット数は，dlog2 ce により計算できる．したを連結したものとなる．
例として，3 値 C0 , C1 , C2 を属性値としてもつ目的属性と，1つの説明属性からなるレコードが取り得る状態を，その状態に対する条件式と対応付けて表 3 に示す．ここで，P0i は目的属性の属性値が Ci であることを表す条件式，そして P1 は説明属性に対する条件式である．

ここで，P0i は目的属性の属性値が Ci であることを表す条件

表3ント演算を表 2 に示す．なお，xi を，目的属性の属性値が Ci であるか否かの条件 P0i または ¬P0i をもつカウント演算の結果を表すベクトルとする．

Table 2 Reconstructable count aggregate queries by the

条件式

000001

P00 ∧ ¬P1P00 ∧ P1
P01 ∧ ¬P1P01 ∧ P1
P02 ∧ ¬P1
P02 ∧ P1

100101conventional technique.

条件 P1 で分割する場合の状態

010
011

表 2 従来手法によって再構築可能なカウント演算

目的属性

提案手法におけるレコードの状態

Table 3 Status of a record in our proposal.

式である．また，従来手法により一回の処理で再構築できるカウxi

目的属性の値

C0
C1
C2

カウント演算Ci

COU N T (¬P0i ∧ ¬P1 )COU N T (¬P0i ∧ P1 )COU N T (P0i ∧ ¬P1 )COU N T (P0i ∧ P1 )xi00xi01xi10xi11

こ こ で は ，目 的 属 性 が 3 値 で あ る た め ，目 的 属 性 の 状 態 はdlog2 3e = 2 ビットで表現することができる．また，説明属性の状態は 1 ビットで表現することができるため，レコードの状
態は 2 + 1 = 3 ビットで表現することができる．

4.2

カウント演算の定式化

次に，4.1 で定義した各状態に対するカウント演算を定式化す
そのため，従来手法では，目的属性の各値のカウント演算結果

る．反復ベイズ手法と同様に，元のテーブルにおけるカウント演x1 ，x2 ，x3 をそれぞれ独立に再構築しなければ，表 1 に示すすべてのカウント演算，すなわち，COU N T (P0i ∧ · · ·) の結果を得

ルにおけるカウント演算結果を表すベクトル y = (y0 , y1 , ..., yt )ることができない．

を以下のように定義する．

4.

提案手法

前述の通り，摂動されたテーブルから，目的属性が 3 値以上の決定木を構築するために必要なカウント演算結果を従来手法を算結果を表すベクトル x = (x0 , x1 , ..., xt ) と，摂動されたテーブ


lef t(i,dlog2 ce) k
xi = COU N T (P0∧r=1 Q(r, bit(i, r)))

0in T , for 0 ≤ i ≤ t

lef t(i,dlog2 ce) k
y = COU N T (P0∧r=1 Q(r, bit(i, r)))
 i00(7)in T , for 0 ≤ i ≤ t

用いて再構築する場合，目的属性の各値においてそれぞれ独立に再構築処理を行わなくてはならない．そこで，本節では，目的属

ここで t0 = c · 2k − 1 である．また，lef t(i, r) を i の左から r性の各値のカウント演算結果を一括して再構築する手法を提案

ビットの整数表現とする．したがって，lef t(i, dlog2 ce) は，値i の左から dlog2 ce ビット，すなわち目的属性の属性値を表してする．

3

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

論文

DBSJ Letters Vol.6, No.1
lef t(i,dlog2 ce)いるため，式 P0は lef t(i, dlog2 ce) によって表される属性値を選択するための条件式となる．例えば，目的属性が 3lef t(010(2) ,2)

値，i = 010(2) の場合，P001= P0 (2) = P01 となる．

なお，Q(r, i) および bit(i, j) の定義は反復ベイズ手法と同様である．
例として，3 値の目的属性と 1 つの説明属性からなるテーブルを考えた場合，x および y に対応するカウント演算を表 4 に示す．
表 4 提案手法によって再構築可能なカウント演算

本稿では，維持‐置換摂動によって摂動されたテーブルから，目的属性が 3 値以上の決定木を構築するために必要なカウント演算結果を再構築する手法を提案した．従来手法を用いて目的属性が 3 値以上のカウント演算結果を摂動されたテーブルから再構築する場合，目的属性の各属性値で独立に再構築処理を行う必要があった．そこで，本稿では目的属性の各属性値を一括して再構築[謝辞]
本研究の一部は，科学研究費補助金基盤研究 (C)(18500073)

proposed technique.

により行なわれた．

カウント演算xy

目的属性

COU N T (P00 ∧ ¬P1 )COU N T (P00 ∧ P1 )

x000
x001

y000
y001

C0

COU N T (P01 ∧ ¬P1 )COU N T (P01 ∧ P1 )

x010
x011

y010
y011

C1COU N T (P02 ∧ ¬P1 )COU N T (P02 ∧ P1 )x100x101y100y101

C2[文献]

ここでは，目的属性の状態は，lef t(i, dlog2 3e) = 2 ビットにより表すことができるため，i の左から 2 ビットは目的属性，そして残りの 1 ビットは説明属性の状態として表される．

遷移確率の再定義

続いて，状態 p のレコードが状態 q となる遷移確率 a0pq を以下に示す．

©

a0pq = (1 − rp0 ) · b0 + rp0 · δ(lef t(p,dlog2 ce),lef t(q,dlog2 ce))·kY©

(1 − rpr ) · Rr,bit(q,r) + rpr · δ(bit(p,r),bit(q,r))ªªr=1(8)
説明属性においては，条件 Pr と ¬Pr の範囲が一致するとは限らないので，置換された値が元の状態ではなくなる確率 1 − brと，元の状態と同じになる確率 br が一致するわけではない．一方，目的属性においては，条件 P0i の範囲はすべて等しくなるため，置換された値が各属性値になる確率は均一に b0 = 1/c である．また，説明属性の状態の変化は 1 ビットを比較することで判別できるが，目的属性の状態の変化は目的属性の状態を表す長さlef t(i, dlog2 ce) のビット列を比較する必要がある．

4.4

おわりにする手法を提案した．

Table 4 Reconstructable count aggregate queries by the4.3

5.

再構築の計算式は，従来手法の式 (6) の遷移確率 apq を式 (8)の遷移確率 a0pq に置き換える．すなわち，以下の式により表さ
0xpT +1 =tXq=0a0pq xTpyq Pt0a0 xT
r=0 rq r

高見澤 秀久 Hidehisa TAKAMIZAWA群馬大学大学院工学研究科電子情報工学専攻博士後期課程在学
中．2001 群馬大学工学部情報工学科卒．プライバシー保護等に再構築の計算式れる．

[1] R. Agrawal and R. Srikant: “Privacy-Preserving DataMining.”, SIGMOD Conference, ACM, pp. 439–450(2000).
[2] A. V. Evfimievski, R. Srikant, R. Agrawal and J. Gehrke:“Privacy preserving mining of association rules.”, Inf.
Syst., 29, 4, pp. 343–364 (2004).
[3] R. Agrawal, R. Srikant and D. Thomas: “Privacy Preserving OLAP.”, SIGMOD Conference, ACM, pp. 251–262 (2005).
[4] L. Breiman, J. H. Friedman, R. A. Olshen andC. J. Stone: “Classification and Regression Trees.”,Wadsworth (1984).
[5] J. Han and M. Kamber: “Data Mining: Concepts andTechniques”, Morgan Kaufmann (2000).
[6] 福田剛志, 森本康彦, 徳山豪：“データサイエンスシリーズ 3データマイニング”, 共立出版 (2001).
[7] 福田剛志, 森本康彦, 徳山豪：“多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム”, 電子情報通信学会技術研究報告, 98, 316, pp. 83–91 (1998).
[8] Y. Morimoto, T. Fukuda, H. Matsuzawa, T. Tokuyamaand K. Yoda: “Algorithms for Mining Association
Rules for Binary Segmentations of Huge CategoricalDatabases.”, VLDB, pp. 380–391 (1998).

興味を持つ．

有次 正義 Masayoshi ARITSUGI
熊本大学大学院自然科学研究科教授．1991 九州大学工学部情報工学科卒．1996 同大大学院了．博士 (工学)．同年群馬大学助手．

(9)

同助教授を経て，2007 より現職．データベースシステム，分散並列データ処理等に興味を持つ．

そして，反復ベイズ手法と同様に，x を繰返し計算すればよい．

4

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