程文琛， 胡學鋼

（合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009）

一個大型組織擁有多個分支，每個分支有本地數(shù)據(jù)庫。如果將全部分支的數(shù)據(jù)庫合并成一個大數(shù)據(jù)庫，然后挖掘這個大數(shù)據(jù)庫，則存在如下問題：

（1）網(wǎng)絡傳輸安全性低，且通信代價高。

（2）數(shù)據(jù)總量龐大，磁盤挖掘算法效率低。

（3）全部分支數(shù)據(jù)匯總成一張大表，表的屬性個數(shù)非常多，使用Apriori算法挖掘會形成組合爆炸；表中存在很多缺失值，無法設置最小支持度等挖掘指標。

上述3個缺陷使得簡單合并數(shù)據(jù)庫的挖掘方法不可行，多數(shù)據(jù)庫挖掘技術［1］必須重新設計。

面向應用的數(shù)據(jù)庫選擇合并挖掘技術［2］必須針對具體的每一個應用遍歷一次所有的數(shù)據(jù)庫，方法效率低下。而分布式并行挖掘技術［3］不產(chǎn)生中間規(guī)則，并行算法部署困難。

事實上，多數(shù)據(jù)庫挖掘過程滿足一般的數(shù)據(jù)挖掘過程。首先必須進行數(shù)據(jù)準備工作，除了數(shù)據(jù)清洗，消除屬性歧義等步驟，最重要的是根據(jù)數(shù)據(jù)庫間相似度對多數(shù)據(jù)庫進行劃分［4－5］。

1 數(shù)據(jù)庫間相似度

1.1 多數(shù)據(jù)庫特征

（1）存在若干個事務類型，每個事務類型包括1個或多個數(shù)據(jù)庫。

（2）隸屬于同一個事務類型的多個數(shù)據(jù)庫之間有著密切的關系，它們都反映該事務的本質(zhì)，包含著許多共有事務項，又根據(jù)本地的實際情況擴展或簡化了一些事務項。

（3）隸屬于同一個事務的每個數(shù)據(jù)庫包含的事務項個數(shù)不等。

（4）隸屬于不同事務的數(shù)據(jù)庫間共有事務項很少，因為很少相同事務項反映不同事務類型。

（5）相似度能很好地反映數(shù)據(jù)庫間的關系。

用特征指代對象是一種通用技術。因此，能通過比較2個數(shù)據(jù)庫的特征集來測量數(shù)據(jù)庫間的相似度。數(shù)據(jù)庫類型多樣，本文針對的是事務數(shù)據(jù)庫，事務數(shù)據(jù)庫的屬性集（也可以是關聯(lián)規(guī)則集的屬性集）能夠當作其特征來指代該數(shù)據(jù)庫（大型數(shù)據(jù)庫特征集可以用抽樣技術［6］獲得）。2個事務數(shù)據(jù)庫的屬性集可以被看作非對稱二元變量［7］，2個事務數(shù)據(jù)庫的相似度可以采用非對稱二元變量的相似度計算方法得到。

1.2 相似度測量

多個數(shù)據(jù)庫的屬性結構用二元屬性描述的關系見表1所列。

表1 用二元屬性描述的多數(shù)據(jù)庫結構

表1說明了給定m個數(shù)據(jù)庫，所有數(shù)據(jù)庫屬性并集長度為L的屬性包含情況。Y表示該數(shù)據(jù)庫包含此屬性，N表示該數(shù)據(jù)庫不包含此屬性。任意2個數(shù)據(jù)庫Di和Dj的相似度測量公式如下：

其中，系數(shù)sim（i，j）稱作Jaccard系數(shù)；q表示Di、Dj都包含的屬性個數(shù)；r表示Di包含、Dj不包含的屬性個數(shù)；s表示Dj包含、Di不包含的屬性個數(shù)。不計Di、Dj都不包含的屬性個數(shù)。

若數(shù)據(jù)庫的特征是與關聯(lián)規(guī)則集有關的屬性項集，則仍然可以采用sim（i，j）表示任意2個數(shù)據(jù)庫Di和Dj的相似度。其中q表示Di、Dj的關聯(lián)規(guī)則集都包含的屬性個數(shù)；r表示Di的關聯(lián)規(guī)則集包含、Dj的關聯(lián)規(guī)則集不包含的屬性個數(shù)；s表示Dj的關聯(lián)規(guī)則集包含、Di的關聯(lián)規(guī)則集不包含的屬性個數(shù)；（1）式不計Di、Dj的關聯(lián)規(guī)則集都不包含的屬性個數(shù)。

關聯(lián)規(guī)則集相關的相似度測量方法受事務記錄的影響較大，得到的相似度值較低，因此本文的實驗采用直接屬性項集相似度測量方法。

2 多數(shù)據(jù)庫的最優(yōu)劃分

2.1 多數(shù)據(jù)庫完全劃分與簇中心

分裂層次聚類［8］首先將所有對象置于一個簇中，然后將它逐步細分為越來越小的簇，直到每個對象自成一簇。在沒有給定具體終止條件的情況下，任何一次分裂滿足以下4個條件（α為分裂閾值）：

（2）對于clusterk中任意2個數(shù)據(jù)庫Di和Dj，sim（i，j）≥α。

設D是M個數(shù)據(jù)庫D1，D2，…，Dm的集合。若滿足上述4個條件，則該劃分是測度sim下的一個完全劃分。

一個完全劃分中，每個數(shù)據(jù)庫只屬于一個簇，且必須屬于一個簇。按照不同的α值得到不同的完全劃分或不完全劃分。當α＝0或α＝1時，多數(shù)據(jù)庫劃分為1個簇或m個簇，可以得到2個完全劃分，這2個完全劃分稱為平凡劃分；其他完全劃分稱為非平凡劃分。

m個對象通過k中心點法［9］得到k個簇，每個簇選出一個對象作為簇中心。同理，m個數(shù)據(jù)庫對于給定閾值α的完全劃分有c個簇，且數(shù)據(jù)庫的特征向量是分類數(shù)據(jù)，則可采用最大樹方法得到對應的簇中心。

定義1 簇的最大樹是簇內(nèi)一個數(shù)據(jù)庫與其他數(shù)據(jù)庫之間的相似度和T最大的所有邊和所有數(shù)據(jù)庫構成的樹。

該數(shù)據(jù)庫是這棵最大樹的根，簇的最大樹的高度是2，如圖1所示。一個簇可能存在多棵最大樹；簇的所有最大樹的根集合是簇中心候選集，如圖2所示，圖2中，該簇的簇中心候選集是｛D1，D2｝。如果簇只有一棵最大樹，那么這棵最大樹的根就是這個簇的簇中心。只有一棵最大樹的簇的簇中心候選集就是包含唯一最大樹根的集合。多數(shù)情況中，簇的最大樹是唯一的。

圖1 簇的最大樹

圖2 一個簇的不同最大樹

2.2 多數(shù)據(jù)庫最優(yōu)劃分

m個數(shù)據(jù)庫D1，D2，…，Dm一次完全劃分產(chǎn)生的簇中心候選集的集合中，每個簇的候選簇中心的所有不同組合中，使S取最小值的組合就是本次完全劃分的聚類中心，同時該S值就是本次完全劃分的評價值［10－11］，即

根據(jù)AFCMC算法可得，m個數(shù)據(jù)庫D1，D2，…，Dm最優(yōu)劃分的S值是所有完全劃分的S值中的最小值，m個數(shù)據(jù)庫D1，D2，…，Dm的最優(yōu)劃分可以通過搜索所有完全劃分的評價值的最小S值確定。

當m個數(shù)據(jù)庫的非平凡完全劃分不存在時，必須選擇一種平凡劃分。如果選擇Cluster0，S值?。?，因此，只能選擇Cluster1，將每個數(shù)據(jù)庫劃分成一個簇。

2.3 最優(yōu)劃分算法

BestPartition程序如下：

程序BestPartition搜索m個給定數(shù)據(jù)庫D1，D2，…，Dm所有的完全劃分中的最優(yōu)劃分。步驟（1）初始化，創(chuàng)建相似度關系表。步驟（2）根據(jù)相似度關系表創(chuàng)建相似度序列，該序列按從小到大的順序?qū)Ρ碇械南嗨贫葻o重復地排序。步驟（3）根據(jù)相似度序列中相似度先后順序，對給定數(shù)據(jù)庫進行劃分，若能得到完全劃分，計算該次完全劃分的S值。步驟（4）查找所有完全劃分的S值中最小S值。步驟（5）輸出最小S值對應的完全劃分。

3 實驗與分析

BestPartition程序已經(jīng)使用Java語言開發(fā)完成，實驗條件是雙核處理器2.8GHz，內(nèi)存2G的Acer臺式PC。

3.1 聚類算法時間性能比較

根據(jù)多個事務數(shù)據(jù)庫的特點，并且參照著名的蘑菇數(shù)據(jù)集，合成一個200條記錄的數(shù)據(jù)集。數(shù)據(jù)集中的每條記錄表示一個事務數(shù)據(jù)庫的項集，記錄的長度不相等，大約為30。記錄的項表示事務的項，用英文字母表示。數(shù)據(jù)集經(jīng)過標記后有60個簇，每個簇的數(shù)據(jù)庫個數(shù)為2～9。數(shù)據(jù)集的規(guī)模和內(nèi)部結構與實際應用比較接近。

合成數(shù)據(jù)集的參數(shù)沒有作為先驗知識用于設置實驗算法的參數(shù)；KMediods的k值遍歷1～200，DBSCAN的minPts設為1，DIANA的α值和DBSCAN的ε值遍歷相似度表中所有不同的值。

使用sim（i，j）得到數(shù)據(jù)集的相似度表，采用DIANA、KMediods和DBSCAN 3種算法進行聚類時間性能比較，結果如圖3所示。

圖3 聚類算法時間性能比較

由圖3可知，KMediods的時間增長非?？?，＄KMediods限定了聚類的個數(shù)處于的大致區(qū)間，情況仍然比較糟糕，這是由于算法的時間復雜度和缺乏先驗知識造成的；DBSCAN的時間略高于DIANA。KMediods和DBSCAN得到的聚類結果都包含預先標記的聚類結果，但是都產(chǎn)生了過多的錯誤聚類；在沒有給定k值的前提下，KMediods遍歷了所有可能的k取值，顯然使用該方法選取多數(shù)據(jù)庫進行分組是不可行的；DBSCAN獲得的聚類結果是重復的，多次聚類了高閾值的不完全劃分，與低閾值的完全劃分是重復的，而評價重復的劃分沒有任何意義，因此該方法比DIANA要差一些。DIANA很好地符合了多數(shù)據(jù)庫的特點，因此它是最高效的聚類算法，這就是選擇DIANA的原因。

3.2 應用實例

實驗數(shù)據(jù)來自http：／／www.kdnuggets.com／網(wǎng)站的真實數(shù)據(jù)集，包括DB1、DB2、DB3、DB4、DB5、DB66個數(shù)據(jù)庫。其中，DB1、DB2來自博物館；DB3、DB4、DB5、DB6來自銀行。6個數(shù)據(jù)庫的參數(shù)比較接近，屬性個數(shù)約為300，記錄條數(shù)約為10 000，相似（異）度見表2、表3所列。

表2 測度sim下6個數(shù)據(jù)庫的相似度

表3 測度sim下6個數(shù)據(jù)庫的相異度

程序BestPartition根據(jù)相似（異）度表計算得到6個數(shù)據(jù)庫所有的劃分和S值，見表4所列。

表4 程序BestPartition運行結果

表4中，“－”表示對該閾值α沒有完全劃分，因此沒有S值。

程序BestPartition通過搜索所有S值得到：當閾 值 α ＝0.537，最 優(yōu) 劃 分同時還可以得到最優(yōu)劃分的聚類中心為｛｛D1｝，｛D4｝｝，相應的隸屬度（membership）矩陣見表5所列，最優(yōu)劃分如圖4所示。

表5 最優(yōu)劃分對應的隸屬度矩陣

圖4 6個數(shù)據(jù)庫的最優(yōu)劃分

上述實驗結果證實了來自博物館的數(shù)據(jù)庫DB1、DB2與來自銀行的數(shù)據(jù)庫DB3、DB4、DB5、DB6是不相關的，最優(yōu)劃分與實際情況完全吻合，程序運行時間為0.001 3s。該實驗成功證明了本文提出的多數(shù)據(jù)庫的最優(yōu)劃分方法是正確的。

3.3 最優(yōu)劃分時間性能比較

由于相似度矩陣的復雜性和簇中心候選集組合次數(shù)的不確定性，多數(shù)據(jù)庫最優(yōu)劃分的時間復雜度很難估計；圖5所示為聚類中心組合次數(shù)對多數(shù)據(jù)庫最優(yōu)劃分過程消耗時間的影響（使用了2個合成數(shù)據(jù)集，不包括相似度計算時間）。

圖5 最優(yōu)劃分時間比較

通過觀察實驗結果可以看出，最優(yōu)分組與預先的數(shù)據(jù)標記完全一致，沒有產(chǎn)生錯誤率。96條記錄以內(nèi)，消耗的時間非常少；隨著聚類中心組合次數(shù)的增加，記錄條數(shù)達到96～112范圍內(nèi)，消耗的時間稍有增加；超過112條記錄，時間迅速增長，但仍然可接受。因此可以得出如下結論：

（1）多數(shù)據(jù)庫最優(yōu)分組方法是正確的，得到全局最優(yōu)解。

（2）最優(yōu)分組方法的時間效率很高，適合實際應用中的小規(guī)模數(shù)據(jù)集，即使在聚類中心組合次數(shù)很多的情況下，算法的時間仍然是可接受的。

（3）通過減少聚類中心的組合次數(shù)可以有效地降低算法的運行時間，該算法具有較好的擴展性。

（4）該算法不依賴先驗知識，具有較高的自適應性，是Chameleon等方法無法比較的。

4 結束語

多數(shù)據(jù)庫挖掘過程分為3個階段：① 數(shù)據(jù)庫劃分；② 挖掘單個數(shù)據(jù)庫；③ 規(guī)則分析與合成。數(shù)據(jù)庫聚類技術是多數(shù)據(jù)庫挖掘系統(tǒng)中的一個關鍵技術。本文提出的劃分策略搜索代價較低，能提高多數(shù)據(jù)庫挖掘系統(tǒng)的性能；給設計應用獨立的多數(shù)據(jù)庫挖掘系統(tǒng)提供了一條途徑，具有較高的理論實用價值。下一步研究將注重數(shù)據(jù)庫間相似度、距離測量方法和隸屬函數(shù)及模糊指數(shù)確定方法。

［1］Zhang Shichao，Zhang Chengqi，Wu Xindong.Knowledge discovery in multiple databases［M］.Springer，2004：79－135.

［2］Liu H，Lu H，Yao J.Identifying relevent databases for multi－databases mining［C］／／Proceedings of the Second Pacific－Asia Conference on Knowledge Discovery and Data mining，April 15－18，1998：210－221.

［3］Cheung D，Ng V，F(xiàn)u A，et al.Efficient mining of association rules in distributed databases［J］.IEEE Transactions on Knowledge and Data Engineering，1996，8 （6）：911－922.

［4］Wu Xindong，Zhang Chengqi，Zhang Shichao.Database classification for multi－database mining［J］.Information System，2005，30：71－88.

［5］曹 慧.一種基于聚類的多數(shù)據(jù)庫分類方法設計［J］.網(wǎng)絡安全技術與應用，2010（6）：79－81.

［6］Zhang S，Zhang C.Estimating itemsets of interest by sampling［C］／／Proceedings of the 10th IEEE International Conference on Fuzzy Systems，2001：131－134.

［7］Han Jiawei，Kamber M.數(shù)據(jù)挖掘概念與技術［M］.第2版.范 明，孟小峰，譯.北京：機械工業(yè)出版社，2007：255－256.

［8］陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法［J］.軟件學報，2008，19（1）：62－72.

［9］劉金嶺.k中心點聚類算法在層次數(shù)據(jù)的應用［J］.計算機工程與設計，2008，29（24）：6418－6422.

［10］熊和金，陳德軍.智能信息處理［M］.北京：國防工業(yè)出版社，2006：12－14.

［11］李為民，朱永峰，付 強.基于自適應模糊聚類分析的目標冗余信息處理［J］.計算機應用，2005，25（4）：949－951.

［12］劉小芳，何彬彬.近鄰樣本密度和隸屬度加權FCM算法的遙感圖像分類方法［J］.儀器儀表學報，2011，32（10）：2242－2247.

［13］高新波，裴繼紅，謝維信.模糊C－均值聚類算法中加權指數(shù)M的研究［J］.電子學報，2000，28（4）：80－84.