曹慧

廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院 廣西 541004

0 引言

數(shù)據(jù)挖掘這一概念最早是在 1995年的美國(guó)計(jì)算機(jī)年會(huì)(ACM)上提出的。數(shù)據(jù)挖掘(Data Mining)又稱知識(shí)發(fā)現(xiàn)，概括來(lái)說(shuō)是指從大量的，不完全的，有噪聲的、隨機(jī)的數(shù)據(jù)中，提取出隱含其中的不為人知的潛在有用的知識(shí)的過(guò)程。數(shù)據(jù)挖掘是一種新型的數(shù)據(jù)分析技術(shù)，被廣泛應(yīng)用在金融、保險(xiǎn)、教育、制造等行業(yè)和國(guó)防科研上，帶來(lái)了巨大的經(jīng)濟(jì)和社會(huì)效益。正因?yàn)槿绱?，?shù)據(jù)挖掘這一研究領(lǐng)域吸引了許多專家和學(xué)者的關(guān)注。隨著研究的深入，越來(lái)越多的新方法被提出，對(duì)整個(gè)數(shù)據(jù)挖掘領(lǐng)域的發(fā)展起到了巨大的推動(dòng)作用。就目前而言，數(shù)據(jù)挖掘的方法大多數(shù)集中在對(duì)單個(gè)的數(shù)據(jù)庫(kù)進(jìn)行挖掘。但是在實(shí)際應(yīng)用中，需要挖掘的數(shù)據(jù)往往不是單一的數(shù)據(jù)庫(kù)，而是多個(gè)數(shù)據(jù)庫(kù)。如許多大型的公司，其下屬的每個(gè)子公司都有自己相應(yīng)的數(shù)據(jù)庫(kù)，當(dāng)總公司需要對(duì)各個(gè)子公司的數(shù)據(jù)進(jìn)行分析的時(shí)候，就必須尋找一種新的方法來(lái)進(jìn)行挖掘，因?yàn)閭鹘y(tǒng)的單數(shù)據(jù)庫(kù)挖掘算法已經(jīng)不再適用了。

總體來(lái)說(shuō)，多數(shù)據(jù)庫(kù)挖掘的方法可以歸結(jié)為以下三類：①先把挖掘任務(wù)涉及到的所有數(shù)據(jù)庫(kù)進(jìn)行集成，生成一個(gè)大數(shù)據(jù)庫(kù)，然后應(yīng)用常規(guī)的數(shù)據(jù)庫(kù)挖掘算法進(jìn)行挖掘；②使用基于歸納邏輯編程的方法(Inductive Logic Programming)，用命題邏輯表示各個(gè)實(shí)例，直接從多個(gè)數(shù)據(jù)庫(kù)中挖掘模式；③對(duì)每個(gè)數(shù)據(jù)庫(kù)進(jìn)行單獨(dú)挖掘，得到局部模式，再通過(guò)模式集成把這些局部模式集成得到一個(gè)全局模式。本文提出一種中間的方法，把多個(gè)數(shù)據(jù)庫(kù)進(jìn)行聚類，結(jié)構(gòu)相似的數(shù)據(jù)庫(kù)聚到同一個(gè)簇中，可以使用同樣的方法進(jìn)行挖掘，最后集成各個(gè)簇中的模式。

1 多數(shù)據(jù)庫(kù)挖掘的相關(guān)研究

最早的多數(shù)據(jù)庫(kù)挖掘算法是將多個(gè)數(shù)據(jù)庫(kù)合并成一個(gè)大數(shù)據(jù)庫(kù)，然后用傳統(tǒng)的數(shù)據(jù)挖掘方法對(duì)這個(gè)大的數(shù)據(jù)庫(kù)進(jìn)行挖掘。但是由于目前的數(shù)據(jù)庫(kù)集成技術(shù)不夠成熟，在集成過(guò)程中會(huì)產(chǎn)生大量的冗余數(shù)據(jù)，結(jié)果有可能陷入組合爆炸的窘境，而且會(huì)生成大量無(wú)用的模式，同時(shí)丟失很多有用的模式。結(jié)合歸納邏輯編程的多數(shù)據(jù)庫(kù)挖掘方法需要將每個(gè)實(shí)例都轉(zhuǎn)換成一階邏輯的形式，模式發(fā)現(xiàn)過(guò)程需要耗費(fèi)相當(dāng)?shù)臅r(shí)間。采用數(shù)據(jù)選擇的方法來(lái)減少總數(shù)據(jù)量，從多個(gè)數(shù)據(jù)庫(kù)中選出與挖掘任務(wù)相關(guān)的數(shù)據(jù)，然后在這些數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘。這個(gè)方法是依賴于特定的數(shù)據(jù)挖掘任務(wù)的，對(duì)于不同的挖掘任務(wù)，需要的數(shù)據(jù)集不同，選擇數(shù)據(jù)會(huì)耗費(fèi)很多時(shí)間。而且，很多挖掘任務(wù)并沒(méi)有詳細(xì)的指明需要的數(shù)據(jù)集。由于各個(gè)數(shù)據(jù)庫(kù)不是同構(gòu)的，單獨(dú)對(duì)每個(gè)數(shù)據(jù)庫(kù)進(jìn)行挖掘得到局部模式，再將局部模式集成為全局模式會(huì)丟失很多重要的模式。還有一種中間的方法就是先把數(shù)據(jù)庫(kù)進(jìn)行分類，然后對(duì)各個(gè)類中的數(shù)據(jù)庫(kù)進(jìn)行挖掘，最后把各個(gè)類中的模式進(jìn)行集成得到全局模式。

2 AN-DBC算法

提出了一種數(shù)據(jù)庫(kù)分類方法，用于事務(wù)數(shù)據(jù)庫(kù)分類：把項(xiàng)集作為數(shù)據(jù)庫(kù)的特征，兩個(gè)數(shù)據(jù)庫(kù)項(xiàng)集中相同項(xiàng)越多，則兩個(gè)數(shù)據(jù)庫(kù)的相似度越大，最后把相似系數(shù)最大的數(shù)據(jù)庫(kù)放在同一個(gè)類中。在本節(jié)中，我們定義了一種新的數(shù)據(jù)庫(kù)相似度(距離)度量，提出了基于聚類的數(shù)據(jù)庫(kù)分類方法，對(duì)于包含任何數(shù)據(jù)類型的數(shù)據(jù)庫(kù)都可以進(jìn)行較好的分類。

2.1 相關(guān)定義

定義 1 假設(shè) D1，D2，…，Dn是數(shù)據(jù)庫(kù)集合 D中的 n個(gè)數(shù)據(jù)庫(kù)，aDi1，aDi2，…，aDim是數(shù)據(jù)庫(kù) Di的m個(gè)屬性。數(shù)據(jù)庫(kù)Di與Dj之間的距離表示為：

其中d(aDik，aDjh)表示的是屬性 aDik與屬性 aDjh之間的距離。

定義 2 假定 aDik與 aDjh分別為數(shù)據(jù)庫(kù) Di和數(shù)據(jù)庫(kù) Dj中的屬性，aDik與aDjh的距離定義如下：

或

若aDik與aDjh均為數(shù)值屬性，則用公式(2)表示，其中表示屬性aDik的均值。若aDik與aDjh為概念屬性，則用公式(3)表示。其中|·|是集合的秩。下面我們對(duì)d(aDik，aDjh)作以下說(shuō)明：

（1）對(duì)于數(shù)值屬性

（2）對(duì)于概念屬性

由定義1和定義2我們可以推出以下結(jié)論：

結(jié)論3

2.2 AN-DBC算法描述

對(duì)于給定的一個(gè)數(shù)據(jù)庫(kù)集合D1，D2，…，Dn，由上述定義的公式(1)可以計(jì)算出其中任意兩個(gè)數(shù)據(jù)庫(kù)Di和Dj之間的距離dis(Di，Dj)，我們可以得到一個(gè)n行n列的矩陣D。很容易看出D滿足如下條件：且數(shù)據(jù)庫(kù)Di與Dj越相似，D[i][j]的值越接近 0，Di與 Dj差距越大，D[i][j]的值越大。因此D是一個(gè)單模的相異度矩陣，我們可以用聚類的方法把D中的數(shù)據(jù)庫(kù)分成幾個(gè)數(shù)據(jù)庫(kù)簇。由于要聚類的對(duì)象是各個(gè)不同的數(shù)據(jù)庫(kù)，這里選擇的聚類方法是基于層次的聚類方法。

層次聚類方法將數(shù)據(jù)對(duì)象組成一顆聚類樹。根據(jù)層次分解是自底向上的方式，還是以自頂向下的方式，層次聚類的方法可以分為凝聚層次聚類(Agglomerative Nesting)和分裂層次聚類(Divisive Analysis)。凝聚層次聚類算法的思想是這樣的：首先把每個(gè)單獨(dú)的對(duì)象作為一個(gè)原子簇，然后基于某個(gè)距離(或相似度)度量合并這些原子簇為更大的簇，如此迭代，直到最終所有的對(duì)象在一個(gè)簇中，或者滿足某個(gè)終止條件。分裂層次聚類算法的思想剛好相反：首先將所有的對(duì)象放在同一個(gè)簇中，然后根據(jù)一定的條件逐步分解，形成越來(lái)越小的簇，直到每個(gè)對(duì)象自成一個(gè)簇或者滿足某個(gè)終止條件。

本文設(shè)計(jì)了一種基于凝聚層次聚類的多數(shù)據(jù)庫(kù)分解算法AN-DBC。算法描述如圖1。其中簇之間的距離用平均距離來(lái)度量：

圖1 AN-DBC算法

3 算法分析

在上述AN-DBC算法中，參數(shù)k表示的是最終分成的數(shù)據(jù)庫(kù)簇的個(gè)數(shù)，是由用戶輸入的。下面我們先分析該算法的可行性。假定有 n個(gè)數(shù)據(jù)庫(kù) D1，D2，…，Dn，每個(gè)數(shù)據(jù)庫(kù)Di有m個(gè)屬性aDi1，aDi2，…，aDim，p條數(shù)據(jù)記錄。如果用傳統(tǒng)的方法，先把所有的數(shù)據(jù)庫(kù)合并成一個(gè)數(shù)據(jù)庫(kù)然后再進(jìn)行挖掘，則算法的復(fù)雜度為o(pn+(n*m)2)。使用AN-DBC算法分類之后再挖掘，算法的復(fù)雜度為o(m2+n2)，由此可見，我們的方法可以大大降低多數(shù)據(jù)庫(kù)挖掘算法的復(fù)雜度。

4 下一步的工作與展望

在本文中我們介紹了一種基于聚類的數(shù)據(jù)庫(kù)分類方法AN-DBC算法，用于對(duì)多數(shù)據(jù)庫(kù)進(jìn)行分類。實(shí)驗(yàn)證明該方法是正確的并且是可行的。對(duì)數(shù)據(jù)庫(kù)進(jìn)行分類之后，下一步的工作就是對(duì)各個(gè)類別的數(shù)據(jù)庫(kù)進(jìn)行挖掘，而最后也是非常關(guān)鍵的一步，是對(duì)各類數(shù)據(jù)庫(kù)中的局部模式進(jìn)行集成。選擇怎樣的集成方法跟分類有著非常緊密的聯(lián)系，如何選擇一種有效的集成方法將是我們下一步的工作。

[1] NingZhong.et al. “Peculiarity Oriented Multi-database Mining”.PKDD’99,LNAI1704.1999.

[2] Kaile Su. et al. “A logical framework for identifying quality knowledge from different data sources.” Decision Support Systems 42.2006.

[3] Xindong Wu. et al. “Database classification for multi-database mining”. Information System 30.2005.

[4] Ireneusz Czarnowski. “Prototype selection algorithms for distributed learing”.Pattern Recognition 43.2010.

[5] H.Liu,H.Lu,J.Yao.Identifying Relevant Database for Multidatabase Mining.In:Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining.1998.

[6] J.Yao and H.Liu,Searching Multiple Database for Interesting Complexes.In:Proc of PAKDD.1997.

[7] 張師超,張成奇.多數(shù)據(jù)庫(kù)挖掘的研究.廣西師范大學(xué)學(xué)報(bào).2003.

[8] 唐懿芳,牛力,鐘智,張成奇.多數(shù)據(jù)庫(kù)挖掘中獨(dú)立于應(yīng)用的數(shù)據(jù)庫(kù)分類研究.廣西師范大學(xué)學(xué)報(bào).2003.

[9] 尚世菊,董祥軍,趙龍.多數(shù)據(jù)庫(kù)中的負(fù)關(guān)聯(lián)規(guī)則挖掘技術(shù)及發(fā)展趨勢(shì).計(jì)算機(jī)工程.2009.

[10] 路松峰,胡和平.多數(shù)據(jù)庫(kù)開采中相關(guān)數(shù)據(jù)庫(kù)的識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用.2000.

[11] 米捷,李可.對(duì)單數(shù)據(jù)庫(kù)和多數(shù)據(jù)庫(kù)中挖掘模式的評(píng)價(jià)[J].電腦知識(shí)與技術(shù).2008.

[12] Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù).機(jī)械工業(yè)出版社.