基于小波變換的K-DBSCAN隱私保護(hù)聚類(lèi)算法.pdf

1、近年來(lái)，網(wǎng)絡(luò)技術(shù)不斷發(fā)展，數(shù)據(jù)規(guī)模成幾何增長(zhǎng)，通過(guò)數(shù)據(jù)挖掘技術(shù)對(duì)原始數(shù)據(jù)提取分析，獲得了有價(jià)值的知識(shí)。然而數(shù)據(jù)的隱私問(wèn)題引起了挖掘應(yīng)用者的高度重視，尤其是在分布式環(huán)境下。數(shù)據(jù)擾動(dòng)技術(shù)是簡(jiǎn)單高效的隱私保護(hù)方法，為了達(dá)到隱藏保密信息的效果，多使用噪聲對(duì)原始數(shù)據(jù)進(jìn)行擾動(dòng)，但其適用于集中式環(huán)境中。DBSCAN對(duì)簇集使用基于密度的定義，因此它受數(shù)據(jù)對(duì)象中的噪聲點(diǎn)影響較小，并且對(duì)簇集的形狀和大小沒(méi)有特殊要求。該特性使得DBSCAN算法在隱私保護(hù)技術(shù)

2、下能夠發(fā)現(xiàn)更多的簇。然而DBSCAN算法并不是完美無(wú)缺的，其算法自身仍存在計(jì)算復(fù)雜度高、對(duì)高維和變密度簇的處理能力差等缺陷，當(dāng)數(shù)據(jù)集趨向于海量、稀疏分布時(shí)，這種缺陷表現(xiàn)的更為明顯。
　　針對(duì)上述問(wèn)題，本文使用小波變換作為隱私保護(hù)方法，其對(duì)原始數(shù)據(jù)擾動(dòng)的同時(shí)降低數(shù)據(jù)的維度，并使用相應(yīng)的安全協(xié)議保證分布式環(huán)境下的交互安全。重新定義臨近性度量和核心密度可達(dá)鏈，對(duì)基于密度的聚類(lèi)算法進(jìn)行改進(jìn)。進(jìn)一步降低簇鄰接數(shù)據(jù)對(duì)聚類(lèi)準(zhǔn)確度的影響，與基于小

3、波的隱私保護(hù)技術(shù)形成一個(gè)整體，為分布式環(huán)境下的數(shù)據(jù)提供良好的處理環(huán)境。本文的主要工作如下:
　　1)針對(duì)DBSCAN算法計(jì)算復(fù)雜度高、對(duì)高維和變密度簇的處理能力差的問(wèn)題，提出改進(jìn)的K-DBSCAN算法。使用K近鄰來(lái)反映數(shù)據(jù)對(duì)象之間的相似性關(guān)系，減少對(duì)高維和變密度數(shù)據(jù)的聚類(lèi)誤差。而構(gòu)建K最近鄰時(shí)間復(fù)雜度較高，為了提高算法的效率，使用kd樹(shù)的方法有效找出K最近鄰，降低計(jì)算復(fù)雜度。定義核心密度可達(dá)鏈替代密度可達(dá)鏈，用一個(gè)僅包含核心點(diǎn)的核

4、心密度可達(dá)鏈來(lái)進(jìn)行擴(kuò)展聚類(lèi)，以此提高聚類(lèi)的準(zhǔn)確性;
　　2)針對(duì)現(xiàn)有分布式隱私保護(hù)算法無(wú)法滿足效率與隱私之間較好折衷的問(wèn)題，提出基于安全多方計(jì)算與小波數(shù)據(jù)擾動(dòng)相結(jié)合的分布式隱私保護(hù)聚類(lèi)算法。各數(shù)據(jù)方使用小波變換實(shí)現(xiàn)數(shù)據(jù)壓縮和信息隱藏，并用屬性列的隨機(jī)重排來(lái)防止數(shù)據(jù)重構(gòu)可能產(chǎn)生的信息泄露。該算法僅使用壓縮重排后的數(shù)據(jù)參與分布聚類(lèi)計(jì)算，因此計(jì)算量和通信量小，算法效率高，而多重保護(hù)措施有效保護(hù)了隱私數(shù)據(jù)。因小波變換具有高保真性，所以聚類(lèi)