一種基于聚類的多數(shù)據(jù)庫分類方法設(shè)計(jì)

曹慧

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

0 引言

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

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

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

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

2 AN-DBC算法

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

2.1 相關(guān)定義

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

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

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

或

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

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

（2）對于概念屬性

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

結(jié)論3

2.2 AN-DBC算法描述

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

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

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

圖1 AN-DBC算法

3 算法分析

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

4 下一步的工作與展望

在本文中我們介紹了一種基于聚類的數(shù)據(jù)庫分類方法AN-DBC算法，用于對多數(shù)據(jù)庫進(jìn)行分類。實(shí)驗(yàn)證明該方法是正確的并且是可行的。對數(shù)據(jù)庫進(jìn)行分類之后，下一步的工作就是對各個(gè)類別的數(shù)據(jù)庫進(jìn)行挖掘，而最后也是非常關(guān)鍵的一步，是對各類數(shù)據(jù)庫中的局部模式進(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ù)庫挖掘的研究.廣西師范大學(xué)學(xué)報(bào).2003.

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

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

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

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

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