一種基于聚類的多數據庫分類方法設計

曹慧

廣西師范大學計算機科學與信息工程學院 廣西 541004

0 引言

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

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

1 多數據庫挖掘的相關研究

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

2 AN-DBC算法

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

2.1 相關定義

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

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

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

或

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

（1）對于數值屬性

（2）對于概念屬性

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

結論3

2.2 AN-DBC算法描述

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

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

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

圖1 AN-DBC算法

3 算法分析

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

4 下一步的工作與展望

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

[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] 張師超,張成奇.多數據庫挖掘的研究.廣西師范大學學報.2003.

[8] 唐懿芳,牛力,鐘智,張成奇.多數據庫挖掘中獨立于應用的數據庫分類研究.廣西師范大學學報.2003.

[9] 尚世菊,董祥軍,趙龍.多數據庫中的負關聯規則挖掘技術及發展趨勢.計算機工程.2009.

[10] 路松峰,胡和平.多數據庫開采中相關數據庫的識別[J].計算機工程與應用.2000.

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

[12] Jiawei Han,Micheline Kamber.數據挖掘概念與技術.機械工業出版社.