張友能，王德兵，汪偉

（安徽工貿(mào)職業(yè)技術(shù)學(xué)院，安徽淮南 232001）

Parzen窗核密度估計(jì)的模式分類隱私保護(hù)方法

張友能，王德兵，汪偉

（安徽工貿(mào)職業(yè)技術(shù)學(xué)院，安徽淮南 232001）

針對(duì)大規(guī)模數(shù)據(jù)集上的模式分類任務(wù)，提出了一種基于Parzen窗核密度估計(jì)的模式分類隱私保護(hù)算法。該算法首先利用Parzen窗算法對(duì)原始大規(guī)模訓(xùn)練集服從的概率密度進(jìn)行估計(jì)，然后根據(jù)估計(jì)的概率密度函數(shù)構(gòu)造la個(gè)替換訓(xùn)練樣本，其中l(wèi)為原始樣本的數(shù)目，a通過(guò)10折交叉驗(yàn)證方式確定。最后發(fā)布替換訓(xùn)練樣本進(jìn)行模式分類，以實(shí)現(xiàn)原始數(shù)據(jù)上的隱私保護(hù)。在Adult數(shù)據(jù)集上的仿真實(shí)驗(yàn)充分驗(yàn)證了該算法的有效性。

parzen窗；核密度估計(jì)；數(shù)據(jù)發(fā)布；隱私保護(hù)

數(shù)據(jù)挖掘①Han J W,Kamber，Data Mining Concepts and Techniques，北京：機(jī)械工業(yè)出版社，2001年，第257-259頁(yè)。技術(shù)的發(fā)展極大地促進(jìn)了人們對(duì)海量數(shù)據(jù)的利用，同時(shí)也引起了數(shù)據(jù)隱私的泄露。為了進(jìn)行隱私保護(hù)②周水庚，李豐，陶宇飛，肖小奎：《面向數(shù)據(jù)庫(kù)應(yīng)用的隱私保護(hù)研究綜述》，《計(jì)算機(jī)學(xué)報(bào)》2009年第5期，第847-861頁(yè)。，同時(shí)又能對(duì)數(shù)據(jù)中隱藏的有用信息進(jìn)行挖掘，面向隱私保護(hù)的數(shù)據(jù)挖掘應(yīng)運(yùn)而生。本文針對(duì)大規(guī)模數(shù)據(jù)集上的模式分類任務(wù)，提出了一種基于Parzen窗③周恩策,劉純平,張玲燕,龔聲蓉,劉全：《基于時(shí)間窗的自適應(yīng)核密度估計(jì)運(yùn)動(dòng)檢測(cè)方法》，《通信學(xué)報(bào)》2011年第2期，第106-114,124頁(yè)。核密度估計(jì)的模式分類隱私保護(hù)算法，避免了原始數(shù)據(jù)上的隱私泄露。

模式分類就是指對(duì)表征事物或現(xiàn)象的各種形式的信息進(jìn)行處理和分析，以對(duì)事物或現(xiàn)象進(jìn)行描述、辨認(rèn)、分類和解釋的過(guò)程，是人類以及動(dòng)物的最基本的智能表現(xiàn)。隨著人類收集和存儲(chǔ)數(shù)據(jù)能力的不斷增長(zhǎng)以及計(jì)算機(jī)運(yùn)算能力的飛速發(fā)展，利用計(jì)算機(jī)來(lái)分析數(shù)據(jù)進(jìn)行模式分類的要求越來(lái)越廣泛，越來(lái)越迫切。近些年隨著研究人員的深入研究，出現(xiàn)了許多優(yōu)秀的分類算法。如人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）④Yang J,Yu X,Xie Z Q，A novel virtual sample generation method based on Gaussian distribution，Knowledge-Based Systems,2011,24(6).pp.740-748.，支持向量機(jī)（Support Vector Machines，SVMs）⑤Cortes C,Vapnik V.Support vector networks,Machine Learning,1995,20(8).pp.273-297.和決策樹(shù)（Decision Tree，DT）⑥Quinlan J R,C4.5:Programs for Machine Learning,San Mateo,CA:Morgan Kaufmann,1993.等。這些算法的出現(xiàn)極大促進(jìn)了模式分類技術(shù)在生活中各領(lǐng)域的應(yīng)用。

訓(xùn)練樣本數(shù)據(jù)的獲取是模式分類工作的基礎(chǔ)，所以模式分類任務(wù)很容易造成一些敏感數(shù)據(jù)的泄露。為了保護(hù)用來(lái)分類的訓(xùn)練數(shù)據(jù)，同時(shí)又盡可能不影響模式分類算法的性能，本文提出了一種基于Parzen窗核密度估計(jì)的模式分類隱私保護(hù)算法。該算法的主要思想是通過(guò)核密度估計(jì)方法估計(jì)原始數(shù)據(jù)的概率密度分布，然后根據(jù)這一密度函數(shù)生成一定數(shù)目的新樣本，最后用這些新樣本替換原始樣本進(jìn)行訓(xùn)練，實(shí)現(xiàn)原始數(shù)據(jù)的隱藏。因?yàn)楸疚乃惴ㄡ槍?duì)的是大規(guī)模數(shù)據(jù)集，所以通過(guò)Parzen窗核密度估計(jì)算法可以較為準(zhǔn)確地對(duì)原始數(shù)據(jù)集服從的密度函數(shù)進(jìn)行估計(jì)，從而保障了分類器在替換數(shù)據(jù)集上的學(xué)習(xí)性能。

1 核密度估計(jì)介紹

核密度估計(jì)是在概率論中用來(lái)估計(jì)未知的密度函數(shù)，屬于非參數(shù)檢驗(yàn)方法之一，由國(guó)外學(xué)者Rosenblatt和Parzen提出。該方法又被叫做Parzen窗方法。核密度估計(jì)的主要思想是通過(guò)某范圍內(nèi)各點(diǎn)密度的均值對(duì)總體密度函數(shù)進(jìn)行估計(jì)，該方法能夠較好地描述多維數(shù)據(jù)的分布狀態(tài)。

一個(gè)向量x落在區(qū)域R中的概率P為：

因此，可以通過(guò)統(tǒng)計(jì)概率P來(lái)估計(jì)概率密度函數(shù)p(x)。假設(shè)N個(gè)樣本的集合X={x1，…，xN}是根據(jù)概率密度函數(shù)為p(x)的分布獨(dú)立抽取得到的。那么，有k個(gè)樣本落在區(qū)域R中的概率服從二項(xiàng)式定理：

假設(shè)p(x)是連續(xù)的，且R足夠小使得p(x)在R內(nèi)幾乎沒(méi)有變化。令R是包含樣本點(diǎn)x的一個(gè)區(qū)域，其體積為V，設(shè)有N個(gè)訓(xùn)練樣本，其中有k落在區(qū)域R中，則可對(duì)概率密度作出一個(gè)估計(jì)：

當(dāng)樣本數(shù)量N固定時(shí)，體積V的大小對(duì)估計(jì)的效果影響很大。過(guò)大則平滑過(guò)多，不夠精確；過(guò)小則可能導(dǎo)致在此區(qū)域內(nèi)無(wú)樣本點(diǎn)，k=0。

落入以X為中心的立方體區(qū)域的樣本數(shù)為：Parzen窗估計(jì)過(guò)程是一個(gè)內(nèi)插過(guò)程，樣本xi距離x越近，對(duì)概率密度估計(jì)的貢獻(xiàn)越大，越遠(yuǎn)貢獻(xiàn)越小。

只要滿足如下條件，就可以作為窗函數(shù)：

常見(jiàn)的窗函數(shù)如下：

2 算法設(shè)計(jì)

模式分類中的訓(xùn)練數(shù)據(jù)通常包括很多屬性，其中有很多涉及到個(gè)人的隱私信息，如收入和信用級(jí)別等，所以原始數(shù)據(jù)的公開(kāi)很容易造成個(gè)人隱私的泄露。如何在不泄露原始訓(xùn)練數(shù)據(jù)的情況下得到滿意的分類決策標(biāo)準(zhǔn)，就成了亟需解決的問(wèn)題，具有很高的研究?jī)r(jià)值。

本文提出一種基于Parzen窗核密度估計(jì)的模式分類隱私保護(hù)算法（A pattern Classification Privacy Preserve algorithm based on Parzen Window kernel density estimation，下文簡(jiǎn)稱CPPPW算法）。該算法首先利用Parzen窗核密度估計(jì)算法對(duì)原始訓(xùn)練樣本所服從的數(shù)據(jù)分布進(jìn)行密度估計(jì)，然后根據(jù)該密度函數(shù)生成一定數(shù)目的替換樣本。綜合考慮在替換樣本集上分類算法的分類性能和運(yùn)行效率，本文算法設(shè)定生成la個(gè)替換樣本，其中l(wèi)為原始訓(xùn)練樣本的個(gè)數(shù)，a是一個(gè)百分?jǐn)?shù)且a∈[1，2]。即生成替換樣本的個(gè)數(shù)不少于原始樣本的個(gè)數(shù)，同時(shí)不多于原始樣本數(shù)目的兩倍。本實(shí)驗(yàn)根據(jù)10折交叉驗(yàn)證方式確定最合理的a值。最后用這些新樣本替換原始樣本進(jìn)行分類學(xué)習(xí)。以二分類模式分類為例，本文算法的偽碼實(shí)現(xiàn)如下：

基于核密度估計(jì)原始數(shù)據(jù)替換的數(shù)據(jù)分類隱私保護(hù)算法：

算法1：CPPPW算法

輸入：原始樣本集合

基分類器M，核函數(shù)φ（u）

輸出：分類決策函數(shù)F

方法：

3.f=PWKDE(T,φ（u）)；//對(duì)訓(xùn)練集T利用parzen窗核密度估計(jì)方法估計(jì)密度函數(shù)f。

4.RS=Sample_Generation(f,la)；//根據(jù)密度函數(shù)f生成la個(gè)替換訓(xùn)練樣本，得到替換樣本集RS，其中根據(jù)交叉驗(yàn)證方式確定最合理的a數(shù)值。

5.F=M(RS)；//利用分類器M對(duì)替換樣本集RS進(jìn)行學(xué)習(xí)，獲得分類決策函數(shù)F。

由于本算法針對(duì)的是大規(guī)模數(shù)據(jù)集，概率密度函數(shù)可以得到較為準(zhǔn)確的估計(jì)，從而使得分類器在替換數(shù)據(jù)集的分類性能得到有效的保障。同時(shí)該算法利用替換樣本集RS進(jìn)行分類學(xué)習(xí)，有效地避免了原始樣本數(shù)據(jù)信息的泄露。寫為R）作為本實(shí)驗(yàn)分類的性能評(píng)價(jià)指標(biāo)。具體計(jì)算公式如下：

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)來(lái)源及處理

本實(shí)驗(yàn)選用UCI標(biāo)準(zhǔn)機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Adult數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集的目的是根據(jù)人們的統(tǒng)計(jì)數(shù)據(jù)來(lái)預(yù)測(cè)收入是否超過(guò)50K。該數(shù)據(jù)集共包含48842個(gè)樣本，其中3620個(gè)樣本包含缺失數(shù)據(jù)。數(shù)據(jù)集有14個(gè)屬性，其中6個(gè)為連續(xù)屬性，8個(gè)為標(biāo)稱屬性。本實(shí)驗(yàn)首先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將具有缺失屬性的數(shù)據(jù)記錄刪除，然后從處理后的數(shù)據(jù)中選取了9000個(gè)元組進(jìn)行實(shí)驗(yàn)，其中6000個(gè)元組作為訓(xùn)練樣本，3000個(gè)元組作為測(cè)試樣本。由于數(shù)據(jù)集包括age、work class、education、maritalstatus、occupation等明顯涉及到個(gè)人隱私的屬性，很容易在分類的同時(shí)造成個(gè)人隱私的泄露。

3.2 分類性能評(píng)價(jià)指標(biāo)

為了更精確地對(duì)算法的性能進(jìn)行評(píng)價(jià)，本實(shí)驗(yàn)并不采用傳統(tǒng)的分類準(zhǔn)確率作為評(píng)價(jià)指標(biāo)，而是選擇正確率（precision，簡(jiǎn)寫為P）和召回率（recall，簡(jiǎn)

其中n1表示事實(shí)屬于此類且被分類正確的樣本數(shù)目，n2表示被判為此類的樣本數(shù)，n3表示屬于此類的總樣本數(shù)。很明顯可以看出，只有算法的正確率和召回率都較高時(shí)，算法的性能才更優(yōu)越。

3.3 實(shí)驗(yàn)方法

本實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)為Intel Core2 Duo CPU T6500，2.10GHz，2.00GB RAM，Windows 7操作系統(tǒng)，選擇matlab7.0軟件進(jìn)行實(shí)驗(yàn)。本實(shí)驗(yàn)分別在原始訓(xùn)練集合上和替換數(shù)據(jù)集合上進(jìn)行分類學(xué)習(xí)，其中替換數(shù)據(jù)利用本文算法生成。生成的替換樣本個(gè)數(shù)為la，具體的，生成n0a個(gè)第一類樣本，n1a個(gè)第二類樣本，l=n0+n1。當(dāng)a=1時(shí)表示生成與原始樣本數(shù)目一致的替換樣本，當(dāng)a=2時(shí)表示生成的替換樣本數(shù)目是原始樣本數(shù)目的兩倍。本實(shí)驗(yàn)采用10折交叉驗(yàn)證方式確定最合理的a數(shù)值。

為了說(shuō)明，本文提出的CPPPW算法是一種通用的模式分類隱私保護(hù)算法（即對(duì)各種不同的分類器均有效），本文采取當(dāng)前最為經(jīng)典的三種分類器作為實(shí)驗(yàn)的基分類器，即人工神經(jīng)網(wǎng)絡(luò)分類器、決策樹(shù)分類器和支持向量機(jī)分類器。其中人工神經(jīng)網(wǎng)絡(luò)采用BP算法，并設(shè)定神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)為3層。決策樹(shù)使用C4.5決策樹(shù)算法。支持向量機(jī)采用CSVM分類算法，并使用如下高斯核函數(shù)作為分類核函數(shù)：

其中g(shù)與C(懲罰因子)為可調(diào)參數(shù)，本文同樣通過(guò)10折交叉驗(yàn)證來(lái)求得最合適的g和C值。

3.4 實(shí)驗(yàn)結(jié)果與分析

由于本文算法使用新生成的樣本替換原始樣本進(jìn)行學(xué)習(xí)，所以本文算法隱私保護(hù)的效果是顯然的，下面圖1到圖6僅給出在替換數(shù)據(jù)集和原始數(shù)據(jù)集上，各種分類算法的分類性能。

圖1 兩種數(shù)據(jù)集上C4.5算法分類準(zhǔn)確率對(duì)比

圖2 兩種數(shù)據(jù)集上C4.5算法分類召回率對(duì)比

圖3 兩種數(shù)據(jù)集上SVM算法分類準(zhǔn)確率對(duì)比

圖4 兩種數(shù)據(jù)集上SVM算法分類召回率對(duì)比

圖5 兩種數(shù)據(jù)集上BP算法分類準(zhǔn)確率對(duì)比

圖6 兩種數(shù)據(jù)集上BP算法分類召回率對(duì)比

從圖1到圖6可以看出，三種經(jīng)典的分類算法在替換數(shù)據(jù)集上同樣可以取得較好的分類性能。這主要是因?yàn)榇笠?guī)模數(shù)據(jù)集使得Parzen窗算法能夠較好地對(duì)樣本的分布函數(shù)進(jìn)行估計(jì)，從而保障了替換數(shù)據(jù)集的質(zhì)量。又考慮到本文算法使用替換數(shù)據(jù)集代替原始數(shù)據(jù)集，避免了用戶隱私數(shù)據(jù)的泄露，所以本文算法是一種有效的面向隱私保護(hù)的數(shù)據(jù)分類算法。注意到圖3和圖4，分類器在替換數(shù)據(jù)集上取得了更好的分類性能，這可能是由于分類器在替換樣本集上的分類學(xué)習(xí)一定程度上避免了過(guò)學(xué)習(xí)。本實(shí)驗(yàn)也充分說(shuō)明本文算法是一種獨(dú)立于分類器的模式分類隱私保護(hù)算法，可以與經(jīng)典分類器結(jié)合，構(gòu)建不同分類器算法下的隱私保護(hù)模型。

4 結(jié)論

針對(duì)大規(guī)模數(shù)據(jù)集，本文提出了一種基于Parzen窗核密度估計(jì)的模式分類隱私保護(hù)算法。充足的訓(xùn)練樣本使得Parzen窗核密度估計(jì)算法可以較準(zhǔn)確的估計(jì)密度函數(shù)，保障了替換數(shù)據(jù)集的質(zhì)量。在替換數(shù)據(jù)集進(jìn)行分類學(xué)習(xí)，有效的避免了原始數(shù)據(jù)上的隱私泄露。本文算法有效地前提是數(shù)據(jù)集包含大量的樣本，研究在小樣本數(shù)據(jù)集上有效的模式分類隱私保護(hù)算法將是進(jìn)一步的研究?jī)?nèi)容。

The use of pattern classification for preserving privacy based on Parzen window kernel density estimation

ZHANG Youneng，WANG Debing，WANG Wei

In this paper,we proposed a pattern classification privacy preserve algorithm based on Parzen window kernel density estimation on large scale dataset.Firstly,the probability density followed by the original large scale training set is estimated.Then we can construct replacement training samples by the estimated probability.Finally,the replacement training samples are published for pattern classification training.Thus the privacy on the original training set can be protected effectively.The simulation experiments on Adult datasets fully verify the effectiveness of the proposed algorithm.

Parzen window;kernel density estimation;data publish;privacy preserving

TP309.2

A

1009-9530（2014）05-0093-04

2014-05-25

安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目（KJ2013B037）；安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目（KJ2014A239）

張友能（1973－），男，安徽工貿(mào)職業(yè)技術(shù)學(xué)院電氣與信息工程系副教授，碩士，主要研究方向?yàn)槲C(jī)測(cè)控技術(shù)和物聯(lián)網(wǎng)技術(shù)。