摘 要：許多大型組織擁有大量的子公司，進行事務(wù)處理時會產(chǎn)生大量的多源數(shù)據(jù)庫，然而現(xiàn)有的數(shù)據(jù)挖掘只致力于對單個數(shù)據(jù)庫的挖掘，由此，提出了多數(shù)據(jù)庫挖掘技術(shù)。為了減少尋找相關(guān)數(shù)據(jù)的檢索代價，在對多數(shù)據(jù)庫進行挖掘和分析之前，首先要對多數(shù)據(jù)庫進行分類。由于多數(shù)據(jù)庫中包含大量數(shù)據(jù)，現(xiàn)有的分類算法GreedyClass的時間復(fù)雜度可達到O（m4），所需代價非常大。由此提出了IdentifyCompleteclass算法用于對多數(shù)據(jù)庫分類，其時間復(fù)雜度降為O（m3），并提出了相應(yīng)的尋找最優(yōu)完全分類算法IdentifyBestClassification，實驗證明改進后的算法有較高的運行效率。

關(guān)鍵詞：多數(shù)據(jù)挖掘；多數(shù)據(jù)庫分類；IdentifyCompleteclass算法；IdentifyBestClassification算法

中圖分類號：TP311.13

許多大型組織擁有多個分布在不同地區(qū)的子公司，而各個子公司具有不同類型的數(shù)據(jù)庫，因此總公司需要挖掘不同數(shù)據(jù)元結(jié)構(gòu)的數(shù)據(jù)庫然后作相關(guān)決策。由此，怎樣從多數(shù)據(jù)庫中有效的確定知識特性[1-2]成為亟待解決的問題。在對數(shù)據(jù)進行挖掘和分析之前，首先要對多數(shù)據(jù)庫進行分類。

然而現(xiàn)有獨立于應(yīng)用的多數(shù)據(jù)分類算法存在著一些問題。例如算法時間復(fù)雜度高[3，5]，不一定能得到最優(yōu)分類[3]，浪費存儲空間[4]等。本文針對以上問題提出了可行性的改進算法，使得對多數(shù)據(jù)庫的分類更快、更準、更節(jié)省空間。

1 相關(guān)概念

文獻[3-5]中對多數(shù)據(jù)庫分類提出了相關(guān)理論概念并進行了理論證明，下面給出相關(guān)定義。

D為一個大量多元數(shù)據(jù)庫的集合，且D={D1，D2，…，Dm}，Item（Di）為數(shù)據(jù)庫Di（i=1，2，…，m）中所有項目的集合：定義1. 令Class（D，α）={class1α，class2α，…，classnα}為多數(shù)據(jù)庫D={D1，D2，…，Dm}在α劃分下的分類集合，如果Class（D，α）滿足以下條件則其為完全分類（complete classification）：

（1）class1α∪class2α∪…∪ classnα=D；

（2）若∨–Di∈classxα，∨–Dj∈classyα（x≠y，1≤x，y≤n），則classxα∩classyα=且sim（Di，Dj）<α。

定義2.令Class（D，α）={class1α，class2α，…，classnα}為多數(shù)據(jù)庫D（={D1，D2，…，Dm}）在α劃分下的分類集合，α∈[0，1]，Goodness與|Class（D，α）|間的絕對距離為：

其中在Goodness（α）為α劃分下的分類集合中各個類別子集之間的距離。

定義3.多數(shù)據(jù)庫D={D1，D2，…，Dm}，設(shè)在相似度α下，當αi<αj<αk（α∈[0，1]）時，若D的最優(yōu)分類為Class（D，αj）={class1αj ，class2αj ，…，classnαj}，則需滿足以下條件為：（1）Class（D，αi），Class（D，αj），Class（D，αk）都為完全分類；（2）對∨–αx∈（αi，αk），且αx≠αj，多數(shù)據(jù)庫D不存在其它的完全分類；（3）Distance（αi）>Distance（αj），且Distance（αj）

2 現(xiàn)有算法存在的問題

文獻[3]中所提出的GreedyClass算法及BestClassification算法存在以下缺點：（1）GreedyClass算法時間復(fù)雜度高。在對于給定閾值α產(chǎn)生分類時，程序沒有最大的優(yōu)化算法，對不完全分類沒有做處理，增加了程序的運行時間。（2）算法BestClassification不一定能得到最優(yōu)分類。變量step為閾值α的步長，并在算法初始時定義，而step值的選擇具有盲目性，有可能導(dǎo)致選擇到錯誤的最優(yōu)分類，甚至使程序陷入死循環(huán)。針對以上問題，本文提出了新的多數(shù)據(jù)分類算法。

3 基于相似度的多數(shù)據(jù)庫分類新算法

3.1 數(shù)據(jù)庫相似度值的存儲。文獻[3][4][5]中對多數(shù)據(jù)庫分類時，首先計算數(shù)據(jù)庫之間的相似度值，然后存儲在二維對稱矩陣中，利用矩陣尋找最優(yōu)分類。但實際尋找最優(yōu)分類時只用到了m（m?1）/2+1個相似度值，即對稱矩陣的小上三角元素和相似度值1。因此在計算數(shù)據(jù)庫之間的相似度時，我們采用上小三角矩陣壓縮存儲方法。對于m階對稱矩陣A，其中aii=1（1≤i≤m），aij=aji（i≠j）。將其壓縮存儲到一維數(shù)組需要12m（m?1）+1個元素空間。即實際存儲的元素（非零元素）為：

，

設(shè)用一維數(shù)組B[1···12m（m?1）]來存儲上小三角矩陣A，采用行主順序壓縮存儲方法，則由文獻[10]中給定了從A到B的映射對應(yīng)關(guān)系。給定A中任一元素aij（1≤i

，1≤i

利用該方法可以輕易得到任意兩數(shù)據(jù)庫間的相似度，相似度值的存儲空間從m2[3，4，5]減少到了12 m（m?1）。

3.2 尋找完全分類。尋找多數(shù)據(jù)庫D在閾值α下的完全分類時，只需按索引順序遍歷數(shù)組SimArray，并分析值大于或等于α的索引。數(shù)組a[m]用來判斷數(shù)據(jù)庫是否已經(jīng)被劃分到某個分類中，所有元素的初始值為0，表示未被劃分。根據(jù)以上性質(zhì)尋找多數(shù)據(jù)庫D在閾值α下的完全分類，算法1為具體的實現(xiàn)算法。

算法1：IdentifyCompleteClass

輸入：數(shù)組SimArray[12m（m?1）]；閾值α；輸出：Class（D，α）：多數(shù)據(jù)庫D在閾值α下的分類；（1）定義數(shù)組a[m]，且所有元素初始值為0；（2）令n←0；//n為完全分類集的當前子類數(shù)目；（3）令k←1；//數(shù)組SimArray索引；（4）for i=1 tom?1do；（5）forj=i+1 to m do

如果SimArray[k]<α，則k←k+1并轉(zhuǎn)（5）繼續(xù)循環(huán)；否則

①如果a[i]=0且a[j]=0，則n←n+1，classnα←classnα∪{ Di，Dj }，且a[i]←1，a[j]←1，k←k+1并轉(zhuǎn)（5）；②如果a[i]=0且a[j]=1，結(jié)束程序，在閾值α下不能得到完全分類；③如果a[i]=1且a[j]=0，尋找Dj與classnα中所有數(shù)據(jù)庫間的相似度值在SimArray數(shù)組中的存儲索引，并判斷其相似度值是否都大于或等于α，若是則classnα←classnα∪{Dj}，k←k+1并轉(zhuǎn)（5）繼續(xù)循環(huán)；否則結(jié)束程序，即在閾值α下不能得到完全分類。④如果a[i]=1且a[j]=1，則k←k+1并轉(zhuǎn)（5）繼續(xù)循環(huán)。

（6）for s=1 to m do，如果a[s]=0，則n←n+1，classnα←classnα∪{Ds}。

（7）輸出Class（D，α），其中Class（D，α）={class1α，class2α，…，classnα}。

IdentifyCompleteClass算法只需對SimArray數(shù)組遍歷一次即可得到多數(shù)據(jù)庫D在閾值α下的完全分類，共需12 m（m?1）次。在最壞情況下，算法在第（5）步中需要再做m次比較，則該算法的復(fù)雜度為O（m3），而GreedyClass需要O（m4）。

3.3 尋找最優(yōu)分類。根據(jù)定義3，基于小上三角存儲特征，算法IdentifyBestClassification是尋找最優(yōu)分類的過程。

算法2：IdentifyBestClassification

輸入： 多數(shù)據(jù)庫D，D={D1，D2，…，Dm}；輸出：Class（D，α），多數(shù)據(jù)庫D的最優(yōu)完全分類；（1）將SimArray數(shù)組的不重復(fù)元素復(fù)制到SortList數(shù)組中，并將SortList數(shù)組按升序排序；//SortList數(shù)組存儲的是需要分類的閾值α

（2）min_α←0；// min_α表示分類距離最小的α值，調(diào)用算法IdentifyCompletclass，尋找min_α的完全分類，minDistance←Distance（min_α）；

（3）for i=1 to SortList.Lenght do

α←SortList[i]，調(diào)用算法IdentifyCompletclass尋找α的分類；

如果Class（D，α）為完全分類且Distance（α）>minDistance，則Class（D，min_α）為最優(yōu)完全分類；如果Class（D，α）為完全分類且Distance（α）

（4）α←1，調(diào)用算法IdentifyCompletclass尋找α的分類；如果Distance（α）

（5）輸出最優(yōu)完全分類Class（D，min_α）。

4 實驗

為了證明算法IdentifyCompletclass與算法IdentifyBestClassification的有效性，本文分別與文獻[3][4]中算法的運行結(jié)果作對比，所有算法由C#語言實現(xiàn)。多數(shù)據(jù)庫由網(wǎng)站（http：//www.kdnuggets.com/）上的綜合分類數(shù)據(jù)集生成，共8個數(shù)據(jù)庫：DB1～DB8。多數(shù)據(jù)庫共有|R|=1000個屬性，每一行的屬性平均數(shù)T=7，且共有|r|=1000行。文獻[4]中的BestCompleteClass算法可以總是得到最優(yōu)完全分類，但是在用算法CompletClass尋找完全分類時會產(chǎn)生多余空類，降低算法效率。而用IdentifyBestClassification算法尋找完全分類時不會產(chǎn)生空類，并且分類結(jié)果清楚明了，耗時較短。

5 結(jié)束語

本文針對現(xiàn)有算法的不足，并根據(jù)文獻[3][4]中所提出的概念，提出IdentifyCompleteclass算法與IdentifyBestClassification算法。該算法首先將數(shù)據(jù)庫間的相似度值存儲到一維數(shù)組中以減少存儲空間，進一步根據(jù)存儲方式的特點尋找完全分類及最優(yōu)分類，整體上提高了分類效率。由于對多數(shù)據(jù)庫進行分類可以減少尋找相關(guān)數(shù)據(jù)的檢索代價，使得研究成果更具有實際意義。

參考文獻：

[1]Wu Xindong，Synthesizing High-Frequency Rules from Different Data Sources[J].IEEE Transactions on Knowledge and Data Engineering，2003（02）：353-367.

[2]Zhang Chengqi，Zhang Shichao.Association Rules Mining： Models and Algorithms[J].Lecture Notes in Artificial Intelligence，2002，2307（07）：238.

[3]Wu Xindong，Zhang Chengqi，Zhang Shichao.Database classification for multi-database mining[J].Information Systems，2005（30）：71–88.

[4]Li Hong，Hu Xuegang，Zhang Yanming.An improved database classification algorithm for multi-database mining[C].Hefei，China：Proc.of Frontiers of Algorithmics Workshop in LNCS，2009：187-199.

[5]唐懿芳，牛力，鐘智.多數(shù)據(jù)庫挖掘中獨立于應(yīng)用的數(shù)據(jù)庫分類研究[J].廣西師范大學(xué)學(xué)報，2003（01）：32-36.

作者簡介：李園園（1986-），女，湖南邵陽人，工程師，計算機軟件與理論專業(yè)，研究方向：數(shù)據(jù)庫；張綠云（1987-），女，湖南永州人，助教，計算機軟件與理論專業(yè)，研究方向：圖像識別。

作者單位：南華大學(xué)附屬第一醫(yī)院信息科，湖南衡陽 421001；河池學(xué)院計算機與信息工程學(xué)院，廣西河池 546300

基金項目：河池學(xué)院青年課題（項目編號：2014QN-N009）的階段性成果。