基于譜聚類矩陣的改進DNALA算法

鄧劍勛，熊忠陽，鄧 欣

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

0 引 言

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

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

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

1 本文算法

1.1 DNALA算法

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

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

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

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

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

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

1.2.1 聚類

譜聚類算法是一種基于圖論的聚類方法。在譜聚類算法內，通常用高斯核函數計算相似矩陣S，同時高斯核函數也是徑向基函數(沿徑向對稱的標量函數)。

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

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

圖1 無相加權圖Fig.1 No phase weighted graph

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

(1)

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

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

(2)

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

(3)

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

采用該評價標準有利于獲取最佳劃分，其優勢為充分借助各種類包含的內、外部關系，以確保狀態得到最優平衡。

1.2.2 基于譜聚類的規范Laplace矩陣

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

(4)

頂點集的度矩陣為：

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

(5)

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

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

S?W

(6)

Laplace矩陣為：

L?D-S

(7)

轉移概率矩陣為：

Srw?D-1S

(8)

非對稱規范Laplace矩陣為：

Lrw?D-1(D-S)

(9)

規范相似矩陣為：

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

(10)

對稱規范Laplace矩陣為：

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

(11)

在轉移概率矩陣Srw中，按照從大到小的順序對特征值進行排列，構建Srw的前K項特征向量組；在規范Laplace矩陣中，按照從小到大的順序對特征值進行排列，構建規范Laplace矩陣的前K項特征向量組。

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

(12)

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

(13)

1.3 DNALA-I距離矩陣算法

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

1.3.1 DNALA-I序列對比

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

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

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

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

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

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

(14)

式中：

(15)

(16)

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

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

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

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

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

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

1.3.2 DNALA-I距離矩陣計算

就DNALA序列而言，如果兩個字符被泛化，需要通過距離衡量信息受到的損失。本文基于規范Laplace矩陣全面改進DNALA序列矩陣。字符a和b在經過泛化后其結果以g(a，b)表示，那么，S與T序列長度相同，并且經過泛化后，可以將其結果定義成根據g(S[1]，T[1]，g(S[2]，T[2]，…，g(S[n]，T[n])構建的序列組合。并且，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轉化為相似矩陣R′：

(19)

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

Step2 相似矩陣R′的轉變需要通過以下公式：

(20)

式中：rij為相似距離。

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

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

2 算法驗證

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

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

2.1 序列對齊所需時間對比

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

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

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

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

Table1Meandistancebetweensequenceandits

generalizationresultsusingdifferent

methods

聚類方法數據集多序列對比平均距離雙序列對比平均距離DNALA中的貪心算法I13.7915.57 DNALA中的貪心算法II3.333.35 基于最大權匹配的算法I13.3913.18 基于最大權匹配的算法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

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

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

3 結束語

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

參考文獻：

[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.