DNA計算在數(shù)據(jù)挖掘中的應用研究

束建華，殷志祥

（1.安徽中醫(yī)學院 醫(yī)藥信息工程學院，安徽 合肥 230008；2.安徽理工大學 理學院，安徽 淮南 232001）

1 引言

數(shù)據(jù)挖掘[1（]Data Mining），也稱為數(shù)據(jù)庫上的知識發(fā)現(xiàn)（Knowledge Discovery in Database），其可描述為從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中的大量數(shù)據(jù)中挖掘出潛在有用的、先前未知的、最終可理解的知識的過程.數(shù)據(jù)挖掘的重要任務是發(fā)現(xiàn)數(shù)據(jù)中潛在的模式.主要技術方法有：聚類、關聯(lián)分析、分類、序列分析、異常檢測等.數(shù)據(jù)挖掘在零售業(yè)、金融數(shù)據(jù)分析、醫(yī)學、農(nóng)業(yè)生產(chǎn)各商業(yè)領域都存在廣泛的使用價值，通過改進數(shù)據(jù)挖掘算法或者引入新的方法來提高數(shù)據(jù)挖掘方法的效率是非常有必要的.

DNA計算模型[2]是由美國加利福尼大學的Adleman博士于1994年提出來的，利用DNA（脫氧核糖核酸）對一個圖論中的NP-完全問題-有向圖的Hamilton路問題進行編碼，借助連接、變性、復性、PCR擴增、電泳等生物操作可以求解出這一問題.DNA計算是作為一種新型的分子生物計算方法，以DNA作為信息的載體，具有存儲容量大、高度的并行性、運算速度快等的優(yōu)點，其在圖論和組合優(yōu)化問題的解決中發(fā)揮了極大的優(yōu)勢[3-5].將DNA計算應用于解決數(shù)據(jù)挖掘問題是一個非常好的思路，逐漸引起人們的關注.目前，DNA計算在數(shù)據(jù)挖掘領域應用主要有聚類問題和分類模型的建立，本文將分別討論DNA計算在聚類分析和分類模型構造中的原理、方法及應用.

2 DNA 計算在聚類中的應用

聚類是一種對數(shù)據(jù)進行自動組織的方法，即按照數(shù)據(jù)的相似性和差異性，將數(shù)據(jù)劃分為若干組(組內(nèi)還可以再分組)，同組的數(shù)據(jù)盡量相似，不同組的數(shù)據(jù)盡量相異.廣泛使用的聚類算法有：K-means聚類方法、基于層次的聚類方法、基于網(wǎng)格的聚類方法等.隨著DNA計算研究的興起，人們發(fā)現(xiàn)其在解決圖和組合優(yōu)化問題時已顯示出極大的潛力，盡管我們很難直接利用DNA計算的思想解決聚類問題，但把聚類問題轉化為圖和組合優(yōu)化問題就能較好的利用DNA計算進行解決[6].

2.1 聚類算法的DNA計算解決思路

聚類的分析方法的核心是分析數(shù)據(jù)集中各數(shù)據(jù)的相似性.聚類方法轉化為圖論問題的思路是：我們把數(shù)據(jù)對象看作是圖中的頂點，數(shù)據(jù)之間的相似度看作是圖中的帶權邊，聚類即在圖中尋找滿足屬于同一簇的路徑最短而連接不同簇之間的路徑最長的路徑.而聚類方法轉化為圖論問題的思路是：對數(shù)據(jù)對象的聚類看作是尋找一種最優(yōu)組合方式的組合優(yōu)化問題，即組合中的每個簇內(nèi)每兩個數(shù)據(jù)點之間的相似度最大而組合中的兩個簇之間的數(shù)據(jù)點的相似度最小.因此，我們可通過先把聚類轉化為圖論問題或組合優(yōu)化問題，就可以利用DNA計算來解決.

2.2 聚類算法轉化為哈密頓圖問題

DNA計算用來解決的第一個問題是圖論中的哈密爾頓圖問題，Adleman的解決方案基于如下非確定性算法[2]：隨機產(chǎn)生生成圖的各種路徑，只保留由始點開始并且有終點結束的哪些路徑，再只保留包含n（假設圖中有n個節(jié)點）個節(jié)點且每個節(jié)點只進入一次的路徑，最后選擇最短路徑.聚類分析中，我們把數(shù)據(jù)集中的數(shù)據(jù)對象作為頂點而數(shù)據(jù)間的相似性作為帶權邊即可以組成一個完全圖，在完全圖中尋找一條包含了所有數(shù)據(jù)點的最短路徑，這條最短路徑即為聚類結果.在這條最短路徑中，相離較遠的數(shù)據(jù)點（即相似性?。殖刹煌拇?，而相距較近的數(shù)據(jù)點（即相似性大）就屬于同一簇.

2.3 聚類問題的DNA計算實驗主要步驟

聚類問題可以轉換為哈密爾頓路徑（回路）問題，也可以轉換為生成樹問題，都是可以通過DNA計算來解決的，并且有多種模型選擇：過濾模型（Adleman實驗所采用的DNA計算模型）、粘貼模型等.

我們設圖中每個頂點用一個隨機的長度為20的DNA串表示，以此作為一個模板，將生成相關聯(lián)、由連接反應連接起來的邊的DNA串.最終，連接反應將形成各種DNA分子，這些DNA分子可看作是對應圖中的隨機路徑的編碼，通過PCR擴增前面的產(chǎn)物得出只含起點和終點的DNA分子，最終電泳分離得分子量最小者.值得注意的是在生物實驗使用的基本技術：熔化、退火、混合、分離或提取、擴增、檢測和長度分離（這兩種操作都應用凝膠電泳技術）對每一個操作都很重要.

算法描述步驟如下[12]：

輸入：問題編碼，輸入試管T1,T2，圖G

1：T←merge(T1,T2)：將包含圖中每個頂點的試管與包含邊的連接鏈試管合并后，放入試管T，進行充分反應

2：T←prefix(T,v1)：從試管T中提取出所有含有頂點v1DNA分子.

3:T←prefix(T,vn)：從試管T中提取出所有含有頂點vn的DNA分子.

4：T←amplify(T)：PCR擴增得出含有頂點v1和vn的DNA分子.

5：T←length-separate(T，m*n)：提取所有包含n個頂DNA分子（路徑）.

6：for i←1 to n do

7：T←separate(T,vi)：提取包含圖中每個頂點的DNA分子.

8：end for

9：return detect(T)：找出最短路徑，即電泳分離，得分子量最小者.

2.4 DNA計算在聚類算法中的主要應用

Bakar等人將DNA計算用于解決k-means聚類問題，是首次提出利用DNA計算解決聚類分析問題的方法[6].該文的解決思路是：對中心點和各點的距離設計DNA編碼，將包含中心點的試管和包含各點的距離的連接鏈試管合并，進行連接和混合反應，從而得到各種包含了各點、各中心點的DNA分子，分離出包含全部中心點的最短的DNA分子即為聚類結果.而后陸續(xù)有DNA計算應用于聚類分析的文章[7-10]，主要從編碼、生化反應等方面進行改進研究，以提高聚類效率.

國內(nèi)劉希玉教授帶領的團隊近幾年開始研究將DNA計算應用于聚類中[6,11,12].在聚類中，整個圖作為初始簇，用單鏈DNA 表示頂點和各頂點間的邊，轉化為最小生成樹的問題，得出的各可連通的子圖即聚類結果，或者轉化為哈密爾頓問題，最短哈密爾頓路徑即為聚類結果.

綜上，我們知道只要能把聚類算法轉化為圖的問題或組合優(yōu)化的問題，就可以使用DNA計算的方法，提高聚類效率和得到更好的聚類結果.

3 基于DNA 計算的分類模型

分類(classification)是另一個重要的數(shù)據(jù)挖掘任務，它會產(chǎn)生一組以自然的方式描述每個類的規(guī)則或類別.進化算法已經(jīng)廣泛應用于分類器構造中，眾所周知的基于進化算法的分類學習系統(tǒng)有：神經(jīng)網(wǎng)絡、遺傳算法、模糊集合方法、粗糙集方法等分類算法[13].直接使用DNA計算解決分類問題的文獻尚未發(fā)現(xiàn)，主要通過DNA計算與其他方法（如遺傳算法[14]、模糊推理[15]）融合研究的方式應用于分類模型的構造中.

DNA計算模型由兩部分構成：DNA編碼和DNA基因操作.將DNA計算引入到分類中，是利用DNA編碼模型表達重要特征信息,通過DNA操作對DNA編碼的調(diào)節(jié)與控制,獲取最典型編碼,實現(xiàn)編碼匹配的最優(yōu)化，其基本流程如圖1所示[14].

圖1 基于DNA計算分類方法的流程圖

圖中核心操作是第一步，即DNA計算模型初始化：(1)DNA種群參數(shù)選擇:DNA模型需要設定DNA種群個體數(shù)量,交叉概率,變異概率,循環(huán)終止條件.(2)樣本選擇:樣本分為兩部分,包括訓練樣本與測試樣本.從訓練樣本中選擇一定數(shù)量的樣本,作為DNA初始種群.

DNA編碼方式采用四值(T、C、A、G)編碼形式,提取了數(shù)據(jù)的重要特征.

DNA轉譯部分則是通過引入DNA鏈密碼子轉譯框架,構建DNA鏈模糊匹配規(guī)則,將原始特征DNA編碼轉換為氨基酸參數(shù)鏈;在蛋白質(zhì)層次上進行樣本訓練和分類操作.DNA轉譯機制進一步加強了編碼系統(tǒng)的穩(wěn)定性和容差性能.

適應度計算：通過衡量DNA種群個體與DNA操作訓練樣本之間氨基酸參數(shù)的絕對實際距離之和,獲得種群中個體適應度.

遺傳操作：按照與DNA種群個體適應度相應的概率,從DNA訓練樣本中選取部分個體,組成新DNA種群.對DNA種群進行交叉和變異操作,重新計算種群適應度,并將新種群中適應度最高的個體標記為最佳DNA個體.種群最佳DNA個體適應度達到設定閾值或循環(huán)次數(shù)達到最大循環(huán)次數(shù).如不滿足循環(huán)終止條件,則繼續(xù)進行DNA操作.

從生物進化理論的角度看，基于DNA計算的分類模型和基于遺傳算法的分類模型的基本思路和原理是相似的，但是DNA計算分類方法的核心在于利用DNA編碼{A,G,C,T}提取各個類別數(shù)據(jù)的典型特征,實現(xiàn)主要特征的有效表達，并使用DNA操作對DNA編碼的調(diào)節(jié)與控制，體現(xiàn)了DNA計算解決復雜問題的優(yōu)勢.

基于DNA計算的模糊推理方法應用于分類中，同樣利用DNA編碼和DNA基因操作得到模糊的IF-THEN規(guī)則達到分類的目的[15].

4 結論

由于DNA計算具有存儲容量大、高度的并行性、運算速度快等的優(yōu)點，使其在解決NP-問題上發(fā)揮極大的優(yōu)勢.數(shù)據(jù)挖掘主要應用于信息量大、需要知識進行控制和決策的領域，在數(shù)據(jù)存儲和處理速度等方面都提出了更高的要求，DNA計算在存儲能力和計算能力上都有著極大的潛力，DNA計算為數(shù)據(jù)挖掘問題的解決中提供一種新的思路.將DNA計算應用于數(shù)據(jù)挖掘中需要從以下幾個方面進行進一步研究：（1）目前，研究人員只給出了少數(shù)分類和聚類算法的DNA計算解決方案，可對其他的數(shù)據(jù)挖掘算法做進一步研究；（2）目前只有關于聚類問題轉換為圖和組合優(yōu)化問題后，使用DNA計算解決的方案；分類算法則是使用DNA計算結合遺傳算法、模糊系統(tǒng)等的方式解決，下一步可以考慮把分類算法轉換為圖和組合優(yōu)化問題后給出DNA計算模型；（3）與軟計算進一步的集成，如DNA計算與遺傳算法、模糊系統(tǒng)和神經(jīng)網(wǎng)絡等融合算法的研究，以及進一步整合在統(tǒng)一的框架模型；（4）與計算機技術的結合：可利用計算機技術幫助處理DNA計算機研究過程的很多輔助性技術（如顯示問題等）、生化實驗的計算機模擬實驗等.

〔1〕倪志偉,李鋒剛,毛雪岷.智能管理技術與方法[M].北京:科學出版社,2007.180-191.

〔2〕Adleman L M. Molecular computation of solutions to combinatorial problems [J]. Science, 1994,266 (5187):1021-1024.

〔3〕許進,et al.,DNA 計算機原理、進展及難點（IV）：論DNA計算機模型[J].計算機學報,2007，30(6):881-893.

〔4〕殷志祥,董亞非,許進.組合優(yōu)化中的DNA 計算[J].計算機工程與應用,2002,38(19):25-27.

〔5〕張勛才,趙海蘭,崔光照，等.DNA 計算的研究進展及展望[J].計算機工程與應用,2007,43(10):44-47.

〔6〕張鴻雁.基于DNA 計算的聚類算法研究[D].山東師范大學,濟南,2011.

〔7〕Bakar,R.B.A.,J.Watada,Biological Clustering Method for Logistic Place Decision Making [J].Knowledge-Based Intelligent Information and Engineering Systems,2008(5179): 136-143.

〔8〕Bakar,R.B.A.,J.Watada,A Biologically Inspired Computing Approach to Solve Cluster-Based Determination of Logistic Problem[J].Biomedical Soft Computing and Human Sciences,2008.13(2):59-66.

〔9〕Bakar,R.B.A.,J.Watada,W.Pedrycz,DNA approach to solve clustering problem based on a mutual order[J].BioSystems,2008(91):1-12.

〔10〕Kim,I.,J.Watada.A DNA -Based Clustering Method Based on Statistics Adapted to Heterogeneous Coordinate Data [C].in International Conference on Complex,Intelligence and Software Intensive Systems(2009).2009::892-897.

〔11〕Xue Jie ,Liu xiyu ,Applying DNA Computing to Clustering in Graph,2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce,2011,986-989.

〔12〕薛潔,劉希玉.基于DNA 計算的層次圖聚類算法[J].計算機工程,2012,38(12):188-190.

〔13〕束建華.群體智能及其在分布式知識管理中的應用研究[D].合肥工業(yè)大學,2007.

〔14〕JIAO Hongzan, ZHONG Yanfei, ZHANG Liangpei,et al. Classification of hyperspectral remote sensing data based on DNA computing [C].Journal of Remote Sensing, 2010, 14(5):865-871.

〔15〕KUMAR S, Mondal M. Classification Of Sodar Data By Dna Computing [J]. New Mathematics and Natural Computation, 2011, 7(03): 413-432.