鄧劍勛，熊忠陽，鄧 欣

(1.重慶大學 計算機學院，重慶 400044；2.重慶電子工程職業(yè)學院 軟件學院，重慶 401331；3.重慶郵電大學 計算機學院，重慶 400065)

0 引 言

數(shù)據(jù)庫技術(shù)的飛速發(fā)展導致數(shù)據(jù)量呈指數(shù)級增長[1]。面對巨量的數(shù)據(jù)，單靠人工進行統(tǒng)計分析顯然不現(xiàn)實，這就促進了數(shù)據(jù)挖掘技術(shù)的快速發(fā)展[2]。目前，數(shù)據(jù)挖掘技術(shù)不斷由低精度、低深度向高精度、高深度發(fā)展，當人們利用數(shù)據(jù)挖掘技術(shù)對巨量數(shù)據(jù)進行分析和挖掘時，不得不面對這些數(shù)據(jù)的隱私保護問題[3-5]。

在數(shù)據(jù)挖掘領(lǐng)域已經(jīng)有許多專家學者提出了防止用戶個人隱私數(shù)據(jù)泄露的數(shù)據(jù)挖掘算法，其中事務型數(shù)據(jù)隱私保護問題是一個重要的研究方向。Terrovitis等[6]將關(guān)系型數(shù)據(jù)k-匿名化處理算法應用到事務型數(shù)據(jù)中，提出了km-匿名化算法。該算法的前提是集合里項目的數(shù)目不能大于m，并且該集合必須被數(shù)目不低于k的事務記錄所包含。該算法的缺點是：當巨量數(shù)據(jù)中含有一定量的非正常數(shù)據(jù)項目時，數(shù)據(jù)容易被概化過度，進而導致數(shù)據(jù)信息損失過多，影響最后的信息精度。km-匿名化采用的是全局概化技術(shù)[7]，后來一些專家學者對該算法進行了改進，提出了采用局部概化技術(shù)的事務型匿名原則，該原則要求更為苛刻，但缺點就是破壞了原始數(shù)據(jù)的域互斥性[8]。Xu等[9]提出了一種新的采用全消隱技術(shù)的(h,k,p)-內(nèi)聚原則，該算法的核心是一個集合中公開項目的數(shù)目不能低于p個，并且該集合要出現(xiàn)在數(shù)目不少于k的事務記錄中，同時這些事務記錄中必須保證數(shù)目不高于h×k個事務記錄包括同一個私密項目。km-匿名化實際上是(h,k,p)-內(nèi)聚原則的一個特例。(h,k,p)-內(nèi)聚原則的缺點是：當原始數(shù)據(jù)過于稀疏時，采用該原則會導致數(shù)據(jù)信息損失過大。后來又有學者提出帶寬矩陣方法，基本思想是將事務記錄進行排列分組，在各個組里面將私密項目進行隨機排序處理，以便達到事務多元化，其缺點是最后得到的數(shù)據(jù)挖掘結(jié)果不太合理[10]。

以上幾種數(shù)據(jù)挖掘隱私保護技算法都較為經(jīng)典，并且還有很多其他基于聚類算法的隱私保護技術(shù)[11]。本文提出了一種基于譜聚類矩陣的改進DNALA(DNALA-improved，DNALA-I)算法，對傳統(tǒng)DNALA算法中距離矩陣的計算方法進行了改進，提高了時間效率以及結(jié)果精度。

1 本文算法

1.1 DNALA算法

DNALA算法通常用來保護個人DNA數(shù)據(jù)隱私安全，屬于經(jīng)典的數(shù)據(jù)挖掘中個人數(shù)據(jù)隱私保護算法，原理是在個人的DNA數(shù)據(jù)維護中融入k-匿名(k-Anonymitya)方法，從而得到DNALA算法。它的主要攻擊方式是路徑攻擊，該算法主要是采用模糊化方式處理DNA數(shù)據(jù)，進而確保數(shù)據(jù)庫的序列存在與其相一致的序列(這一序列表示為k-1個，但是在實踐中，一般選擇k=2)，這樣可以有效杜絕路徑的干擾。但是，該方法保證數(shù)據(jù)安全的代價是犧牲了數(shù)據(jù)的準確性[12]。

DNALA算法步驟為：①將數(shù)據(jù)庫的數(shù)據(jù)逐一展開并進行多序列對比，運用的算法和工具有多種，在文獻[2]中的計算方法為CLUSTALW；②距離矩陣由對比結(jié)果和DNA單字符表示法的兼容性兩部分構(gòu)成。

DNALA算法能夠有效保護DNA數(shù)據(jù)中的個人隱私，但也存在明顯缺陷[13]。DNALA算法中通過多序列對比來計算距離矩陣，這種機制屬于純動態(tài)規(guī)劃，缺點是復雜度極高、計算效率較低。從而導致在DNA數(shù)據(jù)預處理階段，算法時間成本太高，必須借助別的算法進行額外加速。并且DNALA算法數(shù)據(jù)預處理階段采用貪心算法對序列進行分組，分組效果不是特別理想[14]。

本文算法將傳統(tǒng)數(shù)據(jù)挖掘算法中的數(shù)據(jù)對象轉(zhuǎn)換為空間數(shù)據(jù)對象，利用頻譜聚類方法中的計算距離矩陣方法對傳統(tǒng)DNALA算法中通過多序列對比計算距離矩陣的方法進行改進。在傳統(tǒng)聚類算法的基礎(chǔ)上，通過譜圖機制分析出聚類結(jié)果，實現(xiàn)了距離矩陣算法與譜聚類算法的有機結(jié)合，大大降低了數(shù)據(jù)預處理階段序列分組的復雜度，節(jié)省了時間，提高了算法效率。同時，該算法采用雙序列對比，相較DNALA算法能夠進一步減少序列排列所花費的時間，并且增加了序列對比的靈活性。

1.2 DNALA-DMA矩陣的譜聚類矩陣

譜聚類算法用于處理圖像空間最優(yōu)劃分數(shù)據(jù)，其機制是將數(shù)據(jù)向數(shù)據(jù)點轉(zhuǎn)變之后連接這些數(shù)據(jù)點，從而組合成圖[15]。DNA序列算法將根據(jù)前文介紹的譜聚類算法的特點，結(jié)合DNA序列可以被認為是儲存于空間的圖像數(shù)據(jù)這一特征來完善DNALA算法，有利于提升算法效率，也有利于完善算法的精準度。本文采用其非對稱規(guī)范Laplace矩陣的方法計算距離矩陣。

1.2.1 聚類

譜聚類算法是一種基于圖論的聚類方法。在譜聚類算法內(nèi)，通常用高斯核函數(shù)計算相似矩陣S，同時高斯核函數(shù)也是徑向基函數(shù)(沿徑向?qū)ΨQ的標量函數(shù))。

G(V，E)為無相加權(quán)圖，V={X1，X2,…，Xn}為點的集合，每個實驗數(shù)據(jù)一一對應集合中的點。兩點之間所構(gòu)成的權(quán)重集合E={W12,W23,…,Wij,Wnn}，該集合是指每個點間的關(guān)系，每兩個點之間的相似度主要是指每兩個點連線間的權(quán)重值。

由圖1可知，該圖能夠視為2個部分構(gòu)成，可以將它們分別做聚類泛化處理得到最佳結(jié)果。但是由于在實際應用中并非全部數(shù)據(jù)都是正常數(shù)據(jù)，常常會出現(xiàn)難于處理的異常數(shù)據(jù)，這時候就會增加劃分數(shù)據(jù)的復雜度。該情況下應當制定標準的數(shù)據(jù)劃分方法，以確保數(shù)據(jù)點能夠得到有效的劃分。

圖1 無相加權(quán)圖Fig.1 No phase weighted graph

定義(劃分) 由于劃分代表著各種類包含的2個點連線形成的邊的集合。因此，其公式為：

(1)

將以上標準問題歸類為獲得最小劃分問題。結(jié)合圖1可知其劃分所采取的公式為：

cut(A，B)=W16+W35=0.3

(2)

全面考慮各類的相互關(guān)系，并對其內(nèi)部的密度性加以權(quán)衡，以便兼顧類的內(nèi)、外部狀態(tài)，那么可得獲取最佳劃分的評價標準公式為：

(3)

式中：Ncut(·)表示最佳劃分；vol(A)、vol(B)分別為類A、B相應點的權(quán)重之和，各種類的相互的關(guān)系是借助該權(quán)重之和進行有效規(guī)范。

采用該評價標準有利于獲取最佳劃分，其優(yōu)勢為充分借助各種類包含的內(nèi)、外部關(guān)系，以確保狀態(tài)得到最優(yōu)平衡。

1.2.2 基于譜聚類的規(guī)范Laplace矩陣

選取Vi代表樣本的頂點，其度的計算公式為：

(4)

頂點集的度矩陣為：

D?diag(d1，d2，…,dn)

(5)

譜聚類算法一般采用的矩陣如下所示。

n×n矩陣的相似矩陣為：

S?W

(6)

Laplace矩陣為：

L?D-S

(7)

轉(zhuǎn)移概率矩陣為：

Srw?D-1S

(8)

非對稱規(guī)范Laplace矩陣為：

Lrw?D-1(D-S)

(9)

規(guī)范相似矩陣為：

Ssym?D-1/2SD-1/2

(10)

對稱規(guī)范Laplace矩陣為：

Lsym?D-1/2(D-S)D-1/2

(11)

在轉(zhuǎn)移概率矩陣Srw中，按照從大到小的順序?qū)μ卣髦颠M行排列，構(gòu)建Srw的前K項特征向量組；在規(guī)范Laplace矩陣中，按照從小到大的順序?qū)μ卣髦颠M行排列，構(gòu)建規(guī)范Laplace矩陣的前K項特征向量組。

在譜聚類算法中，采用高斯核函數(shù)對距離矩陣進行轉(zhuǎn)換來計算相似矩陣。一般而言，相似矩陣S是借助全局高斯核函數(shù)來實現(xiàn)對距離矩陣的轉(zhuǎn)換，其公式為：

(12)

式中：σ為全局高斯核函數(shù)參數(shù)；dij為數(shù)據(jù)點的距離，也就是i與j兩者間的距離，其計算公式為：

(13)

1.3 DNALA-I距離矩陣算法

多路歸一化割普聚類方法屬于普聚類算法之一，它的性能優(yōu)良，且其普聚類矩陣屬于非對稱規(guī)范Laplace矩陣。因此，本文圍繞擾動理論，在DNALA算法中積極融合非對稱規(guī)范Laplace矩陣的優(yōu)勢，改進其計算距離矩陣的方法，一方面加強了算法的運行效率；另一方面提升了信息的安全性，全面保護個人隱私。

1.3.1 DNALA-I序列對比

序列對比通常是用于匯總、分析各類數(shù)據(jù)，并且結(jié)合各類方法來尋求規(guī)律性，在模式識別、機器學習以及數(shù)據(jù)挖掘等領(lǐng)域應用廣泛。

雙序列對比通常是以DNA序列為基礎(chǔ)，對其相應的元素逐一加以對比，確保對比結(jié)果的正確性和準確性，保障個人信息安全。因此，需要事先圍繞原始序列做出相應處理，其具體步驟如下：

(1)插入(Insertion)：將字符插入到DNA序列中，如將幾個空格分別插入到序列中，用“-”表示。

(2)刪除(Deletion)：選擇序列里面的字符，對其進行刪除操作，如選中序列里面包含的空格，對其進行刪除，用“-”表示。

(3)替換(Substitution)：選中序列，將需要的字符進行替換操作。

選取序列S和T，S=(s[1],s[2],…,s[m])、T=(t[1],t[2],…,t[n])，然后對得分情況進行最優(yōu)對比，確認初值以后，通過遞歸公式計算M(i,j)值，即：

(14)

式中：

(15)

(16)

選取S、T兩條DNA序列，已知相似矩陣時，采用回溯法計算最優(yōu)對比，其詳細步驟如下所示。

(1)對序列S、T的兩個相似矩陣進行初始化。

(2)兩個堿基的得分需要根據(jù)得分遞推公式和替換矩陣進行詳細填寫。

(3)以得分矩陣為基礎(chǔ)，從矩陣對應的右下方位開始，由最大分值依次做路線回溯操作。

(4)將回溯路線轉(zhuǎn)化成對比結(jié)果，也就是完成插入空格等相關(guān)操作。

這一序列對比的對象是偶數(shù)序列，但是在實際過程中并非只有偶數(shù)序列，也常出現(xiàn)奇數(shù)序列。假如原始序列集合的序列全部屬于奇數(shù)，則最終一個序列對比包含3條序列，但是本部分僅是針對雙序列為對比對象來進行距離矩陣的計算，所以，在多序列對比時，只要再增加一次對這3個序列的對比即可。由于數(shù)量不多，可以快速獲得其對比結(jié)果。

1.3.2 DNALA-I距離矩陣計算

就DNALA序列而言，如果兩個字符被泛化，需要通過距離衡量信息受到的損失。本文基于規(guī)范Laplace矩陣全面改進DNALA序列矩陣。字符a和b在經(jīng)過泛化后其結(jié)果以g(a，b)表示，那么，S與T序列長度相同，并且經(jīng)過泛化后，可以將其結(jié)果定義成根據(jù)g(S[1]，T[1]，g(S[2]，T[2]，…，g(S[n]，T[n])構(gòu)建的序列組合。并且，n表示序列S和T兩者的總長，S[i]為序列S的第i字符，T[i]為序列T的第i字符，也可以理解為g(S，T)[i]=g(S[i]，T[i])。

用x和y表示兩個字符，則兩者間的距離為：

dis(x,y)=2×lev(g(x,y))-lev(x)-lev(y)

(17)

式中：lev(·)為字符“·”所在的層。

序列S與T的長度相同，將兩個序列間的距離定義為兩個序列各自的字符距離之和，其計算公式為：

(18)

以Laplace矩陣所具備的特點以及擾動原理為中心，計算DNA序列泛化后距離的新算法詳細步驟如下所示。

(1)選取一個矩陣R，通過以下步驟將R轉(zhuǎn)化為相似矩陣R′：

(19)

式中：i、j、k為各種物種，dik∧djk=min{dik,djk}，dik∨djk=max{dik,djk}。

Step2 相似矩陣R′的轉(zhuǎn)變需要通過以下公式：

(20)

式中：rij為相似距離。

(4)當分區(qū)序列值全部選取完畢后，就可以得出一棵進化樹。

DNALA-I算法側(cè)重于聚成含有兩條序列的類，如果前置條件是出現(xiàn)奇數(shù)條序列，一個類就會含有3條序列，每條記錄需要得到有效的區(qū)分。

2 算法驗證

本文的實驗數(shù)據(jù)來自文獻[16]中的數(shù)據(jù)I和數(shù)據(jù)II，通過Matlab軟件實現(xiàn)仿真驗證。本文首先將DNA序列中含有的數(shù)據(jù)流信息放入度量空間；然后通過弱聚類的數(shù)據(jù)流匿名化框架實現(xiàn)數(shù)據(jù)匿名化，以便維護用戶隱私，其原理是將處于DNA數(shù)據(jù)集里面的數(shù)據(jù)流信息視為空間點；最后對其進行距離矩陣和相似度計算。DNA序列數(shù)據(jù)經(jīng)過匿名化處理后，不會嚴重影響原始DNA序列的數(shù)據(jù)信息。

圖2 不同序列對齊方法所需時間的對比Fig.2 Comparisons of time required for different sequential alignment methods

2.1 序列對齊所需時間對比

通過雙序列以及多序列的對比方法，將兩個數(shù)據(jù)集中所含有的子序列進行對比，同時將對齊序列所耗費的時間進行計算，結(jié)果如圖2所示。由圖2可見，與多序列對比而言，雙序列對比更加節(jié)約時間，數(shù)據(jù)集I對該現(xiàn)象的呈現(xiàn)十分顯著。

2.2 原始序列與其泛化序列間的距離計算結(jié)果對比

采用不同算法計算原始序列與其泛化序列間的平均距離，結(jié)果如表1和圖3所示。即使在同一實驗環(huán)境中，得到的值也會有偏差，因此，對一個數(shù)據(jù)進行多次實驗，取3次實驗的平均值。

表1使用不同方法計算序列與其泛化結(jié)果間的平均距離

Table1Meandistancebetweensequenceandits

generalizationresultsusingdifferent

methods

聚類方法數(shù)據(jù)集多序列對比平均距離雙序列對比平均距離DNALA中的貪心算法I13.7915.57 DNALA中的貪心算法II3.333.35 基于最大權(quán)匹配的算法I13.3913.18 基于最大權(quán)匹配的算法II2.992.98 在線算法I16.9316.81 在線算法II3.793.81 混合算法I13.3913.18 混合算法II3.133.11

圖3 原始序列與其泛化序列間的平均距離對比Fig.3 Average distance between original sequence and its generalization sequence

通過多序列、雙序列兩種方法進行序列對比，然后計算其距離矩陣。同時對其進行聚類，并對聚類結(jié)果做泛化處理，取兩者的平均距離。由表1可以看出：在確保聚類算法精度的前提下，若想減少計算距離矩陣平均距離的時間，可以借助多序列、雙序列這兩種對比方法來有效對齊序列，這樣還能夠進一步提升計算結(jié)果的精度。

從上述實驗結(jié)果可以看出：將DNALA-I距離矩陣計算方法運用到DNA序列集合中，能夠大大提升序列對比的時間效率，同時也提升了聚類算法的精度。

3 結(jié)束語

提出了基于譜聚類矩陣的改進的DNALA算法——DNALA-I(DNALA-improved)算法。該算法通過頻譜聚類方法中的計算距離矩陣方法對傳統(tǒng)DNALA算法中通過多序列比來計算距離矩陣的方法進行改進，在不降低數(shù)據(jù)挖掘精度的情況下，本文算法能夠有效減小對齊序列所花費的時間，提高時間效率。仿真實驗結(jié)果表明：本文算法相較傳統(tǒng)的DNALA算法不僅提高了時間效率，并且保證了實驗結(jié)果的計算精度。

參考文獻：

[1] Miao G X, Tatemura J, Hsiung W P, et al. Extracting data records from the web using tag path clustering[C]∥Proceedings of the 18th International Conference on World Wide Web,Madrid,Spain,2009:981-990.

[2] Zhou K,Snyder J M,Guo B N,et al. Stretch-driven mesh parameterization using spectral analysis[J/OL].[2017-02-10]. https:∥www.microsoft.com/en-us/research/wp-content/uploads/2017/01/isochart.pdf.

[3] Atherton P J, Szewczyk N J, Selby A, et al. Cyclic stretch reduces myofibrillar protein synthesis despite increases in FAK and anabolic signalling in L6 cells[J]. The Physiological Society,2009,587(14):3719-3727.

[4] Siahpirani A F, Ay F, Roy S. A multi-task graph-clustering approach for chromosome conformation capture data sets identifies conserved modules of chromosomal interactions[J]. Genome Biology,2016,17(1):114.

[5] Sousa C, Grosso F, Meirinhos-Soares L, et al. Identification of carbapenem-resistant Acinetobacterbaumannii clones using infrared spectroscopy[J]. Journal of Biophotonics,2014,7(5):287-294.

[6] Terrovitis M, Bakiras S, Papadias D, et al. Constrained shortest path computation[C]∥International Conference on Advances in Spatial and Temporal Databases,Angra dos Reis, Brazil,2005:181-199.

[7] Wechsler H. Intelligent biometric information management[J]. Intelligent Information Management,2010,2(9):499-511.

[8] Bettebghor D,Leroy F H. Overlapping radial basis function interpolants for spectrally accurate approximation of functions of eigenvalues with application to buckling of composite plates[J]. Computers & Mathematics with Applications,2014,67(10):1816-1836.

[9] Xu D,Xu D,Luo J. A free-roaming mobile agent security protocol based on anonymous onion routing and k anonymous hops backwards[C]∥International Conference on Autonomic and Trusted Computing. Berlin: Springer-Verlag,2008:588-602.

[10] Bronstein A M, Bronstein M M, Guibas L J, et al. Shape Google: geometric words and expressions for invariant shape retrieval[J]. ACM Transactions on Graphics,2009,28(4):106.

[11] Liu Zhen-qiu,Guo Zhong-min,Tan Ming. Constructing tumor progression pathways and biomarker discovery with fuzzy kernel kmeans and DNA methylation data[J]. Cancer Informatics,2008(6):1-7.

[12] Vega-Pons S, Ruiz-Shulcloper J. A survey of clustering ensemble algorithms[J]. International Journal of Pattern Recognition & Artificial Intelligence,2011,25(3):337-372.

[13] Perry S W,Norman J P,Barbieri J,et al. Mitochondrial membrane potential probes and the proton gradient: a practical usage guide[J]. Biotechniques,2011,50(2):98-115.

[14] Schwarzbach A E,Mcdade L A. Phylogenetic relationships of the mangrove family Avicenniaceae based on chloroplast and nuclear ribosomal DNA sequences[J]. Systematic Botany,2002,27(1):84-98.

[15] Mutwil M, Klie S, Tohge T, et al. PlaNet:combined sequence and expression comparisons across plant networks derived from seven species[J]. Plant Cell,2011,23(3):895-910.

[16] Kannangara R,Branigan C, Liu Y,et al. The transcription factor WIN1/SHN1 regulates cutin biosynthesis in arabidopsisthaliana[J]. Plant Cell,2007,19(4):1278-1294.