基于相似度的多數(shù)據(jù)庫(kù)分類

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

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

中圖分類號(hào)：TP311.13

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

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

1 相關(guān)概念

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

D為一個(gè)大量多元數(shù)據(jù)庫(kù)的集合，且D={D1，D2，…，Dm}，Item（Di）為數(shù)據(jù)庫(kù)Di（i=1，2，…，m）中所有項(xiàng)目的集合：定義1. 令Class（D，α）={class1α，class2α，…，classnα}為多數(shù)據(jù)庫(kù)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ù)庫(kù)D（={D1，D2，…，Dm}）在α劃分下的分類集合，α∈[0，1]，Goodness與|Class（D，α）|間的絕對(duì)距離為：

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

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

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

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

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

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

，

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

，1≤i

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

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

算法1：IdentifyCompleteClass

輸入：數(shù)組SimArray[12m（m?1）]；閾值α；輸出：Class（D，α）：多數(shù)據(jù)庫(kù)D在閾值α下的分類；（1）定義數(shù)組a[m]，且所有元素初始值為0；（2）令n←0；//n為完全分類集的當(dāng)前子類數(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ù)庫(kù)間的相似度值在SimArray數(shù)組中的存儲(chǔ)索引，并判斷其相似度值是否都大于或等于α，若是則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算法只需對(duì)SimArray數(shù)組遍歷一次即可得到多數(shù)據(jù)庫(kù)D在閾值α下的完全分類，共需12 m（m?1）次。在最壞情況下，算法在第（5）步中需要再做m次比較，則該算法的復(fù)雜度為O（m3），而GreedyClass需要O（m4）。

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

算法2：IdentifyBestClassification

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

（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 實(shí)驗(yàn)

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

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

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

參考文獻(xiàn)：

[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ù)庫(kù)挖掘中獨(dú)立于應(yīng)用的數(shù)據(jù)庫(kù)分類研究[J].廣西師范大學(xué)學(xué)報(bào)，2003（01）：32-36.

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

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

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