獨(dú)立于應(yīng)用的數(shù)據(jù)庫(kù)聚類技術(shù)

程文琛， 胡學(xué)鋼

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

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

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

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

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

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

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

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

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

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

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

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

（3）隸屬于同一個(gè)事務(wù)的每個(gè)數(shù)據(jù)庫(kù)包含的事務(wù)項(xiàng)個(gè)數(shù)不等。

（4）隸屬于不同事務(wù)的數(shù)據(jù)庫(kù)間共有事務(wù)項(xiàng)很少，因?yàn)楹苌傧嗤聞?wù)項(xiàng)反映不同事務(wù)類型。

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

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

1.2 相似度測(cè)量

多個(gè)數(shù)據(jù)庫(kù)的屬性結(jié)構(gòu)用二元屬性描述的關(guān)系見(jiàn)表1所列。

表1 用二元屬性描述的多數(shù)據(jù)庫(kù)結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 簇的最大樹(shù)

圖2 一個(gè)簇的不同最大樹(shù)

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

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

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

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

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

BestPartition程序如下：

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

3 實(shí)驗(yàn)與分析

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

3.1 聚類算法時(shí)間性能比較

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

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

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

圖3 聚類算法時(shí)間性能比較

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

3.2 應(yīng)用實(shí)例

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

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

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

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

表4 程序BestPartition運(yùn)行結(jié)果

表4中，“－”表示對(duì)該閾值α沒(méi)有完全劃分，因此沒(méi)有S值。

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

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

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

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

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

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

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

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

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

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

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

（4）該算法不依賴先驗(yàn)知識(shí)，具有較高的自適應(yīng)性，是Chameleon等方法無(wú)法比較的。

4 結(jié)束語(yǔ)

多數(shù)據(jù)庫(kù)挖掘過(guò)程分為3個(gè)階段：① 數(shù)據(jù)庫(kù)劃分；② 挖掘單個(gè)數(shù)據(jù)庫(kù)；③ 規(guī)則分析與合成。數(shù)據(jù)庫(kù)聚類技術(shù)是多數(shù)據(jù)庫(kù)挖掘系統(tǒng)中的一個(gè)關(guān)鍵技術(shù)。本文提出的劃分策略搜索代價(jià)較低，能提高多數(shù)據(jù)庫(kù)挖掘系統(tǒng)的性能；給設(shè)計(jì)應(yīng)用獨(dú)立的多數(shù)據(jù)庫(kù)挖掘系統(tǒng)提供了一條途徑，具有較高的理論實(shí)用價(jià)值。下一步研究將注重?cái)?shù)據(jù)庫(kù)間相似度、距離測(cè)量方法和隸屬函數(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ù)庫(kù)分類方法設(shè)計(jì)［J］.網(wǎng)絡(luò)安全技術(shù)與應(yī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ù)挖掘概念與技術(shù)［M］.第2版.范 明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2007：255－256.

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

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

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

［11］李為民，朱永峰，付 強(qiáng).基于自適應(yīng)模糊聚類分析的目標(biāo)冗余信息處理［J］.計(jì)算機(jī)應(yīng)用，2005，25（4）：949－951.

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

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