曹禮園　李深洛

(1.廣東財(cái)經(jīng)大學(xué)華商學(xué)院　廣州　510006)(2.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院　桂林　541004)

?

一個(gè)基于高內(nèi)聚和低耦合的多數(shù)據(jù)庫(kù)分類(lèi)方法*

曹禮園1李深洛2

(1.廣東財(cái)經(jīng)大學(xué)華商學(xué)院廣州510006)(2.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院桂林541004)

摘要數(shù)據(jù)庫(kù)分類(lèi)是多數(shù)據(jù)庫(kù)存儲(chǔ)、管理和挖掘的預(yù)處理技術(shù)。目前,不依賴(lài)具體應(yīng)用的多數(shù)據(jù)庫(kù)分類(lèi)的研究甚少,并且忽略?xún)?nèi)聚度和耦合度,復(fù)雜度高。論文提出一個(gè)基于高內(nèi)聚和低耦合的多數(shù)據(jù)庫(kù)分類(lèi)方法,該方法不依賴(lài)于具體的應(yīng)用,避免了聚類(lèi)結(jié)果的不穩(wěn)定性,且降低了時(shí)間復(fù)雜度。具體地,該方法名為DHC首先構(gòu)造一個(gè)多目標(biāo)優(yōu)化問(wèn)題,然后利用層次聚類(lèi)思想構(gòu)造算法查找最優(yōu)聚類(lèi)。利用一個(gè)人工數(shù)據(jù)庫(kù)和一個(gè)現(xiàn)實(shí)數(shù)據(jù)庫(kù)相似度二維表進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)表明該方法聚類(lèi)穩(wěn)定性強(qiáng),時(shí)間復(fù)雜度比BestClassification低,泛化能力強(qiáng)。

關(guān)鍵詞數(shù)據(jù)庫(kù)聚類(lèi); 多目標(biāo)最優(yōu)化; 多數(shù)據(jù)庫(kù)挖掘; 層次聚類(lèi)

Class NumberTP391

1引言

當(dāng)今,有很多大機(jī)構(gòu)有著不同的數(shù)據(jù)庫(kù)分布在其不同的分支機(jī)構(gòu),因此多數(shù)據(jù)庫(kù)挖掘作為數(shù)據(jù)挖掘的一個(gè)重要分支變得越來(lái)越重要。為了減小搜索成本,需要確定哪些數(shù)據(jù)庫(kù)是與我們的數(shù)據(jù)挖掘應(yīng)用相關(guān)聯(lián)的。這一重要步驟稱(chēng)之為數(shù)據(jù)庫(kù)選擇[1]。進(jìn)一步,考慮一個(gè)需要處理多個(gè)大型數(shù)據(jù)庫(kù)的跨國(guó)公司。該公司可能需要進(jìn)行關(guān)聯(lián)分析找出非盈利的項(xiàng)目(產(chǎn)品)。最終的目標(biāo)是識(shí)別那些本身沒(méi)有多大的利潤(rùn)也沒(méi)有促進(jìn)其他產(chǎn)品盈利的產(chǎn)品。關(guān)聯(lián)分析可能找出這樣的產(chǎn)品,從而公司可終止該產(chǎn)品的交易。這種性質(zhì)的分析可能需要識(shí)別類(lèi)似的數(shù)據(jù)庫(kù)。我們注意到,如果兩個(gè)數(shù)據(jù)庫(kù)包含許多類(lèi)似的交易,則兩個(gè)數(shù)據(jù)庫(kù)被認(rèn)為是類(lèi)似的。進(jìn)而,如果兩個(gè)事務(wù)交易包含很多相同的物品,則這兩個(gè)交易是類(lèi)似的。所以,兩個(gè)數(shù)據(jù)庫(kù)包含越多的相同的頻繁項(xiàng)集,它們?cè)较嗨芠2]。我們可以聚集多數(shù)據(jù)庫(kù)根據(jù)兩個(gè)數(shù)據(jù)庫(kù)之間的相似性;然后,挖掘在同一個(gè)類(lèi)中的數(shù)據(jù)庫(kù)。多數(shù)據(jù)庫(kù)聚類(lèi)是模式發(fā)現(xiàn)、分組、決策選擇和機(jī)器學(xué)習(xí)的重要組成部分。本文主要探討事務(wù)數(shù)據(jù)庫(kù)的聚類(lèi)。

2相關(guān)工作

對(duì)于多數(shù)據(jù)庫(kù)挖掘,第一個(gè)方法(單數(shù)據(jù)庫(kù)挖掘技術(shù))是把多數(shù)據(jù)庫(kù)中的數(shù)據(jù)聚集在一起構(gòu)成一個(gè)單一的數(shù)據(jù)集[1]。Liu et al.[12]提出了一個(gè)只搜索相關(guān)數(shù)據(jù)庫(kù)的多數(shù)據(jù)庫(kù)挖掘技術(shù)。他們的研究側(cè)重于識(shí)別與某一應(yīng)用相關(guān)的數(shù)據(jù)庫(kù)。

Zhang et al.[11]提出了一個(gè)新的多數(shù)據(jù)庫(kù)挖掘方法,首先是數(shù)據(jù)庫(kù)聚類(lèi),然后進(jìn)行局部模式發(fā)現(xiàn)。相應(yīng)地,Zhang et al.[1]提出了一個(gè)基于數(shù)據(jù)庫(kù)間的相似度的獨(dú)立于某一個(gè)應(yīng)用過(guò)的多數(shù)據(jù)庫(kù)聚類(lèi)方法。該文首先提出了一個(gè)基于事務(wù)項(xiàng)集或高頻繁規(guī)則的數(shù)據(jù)庫(kù)相似度量,然后設(shè)計(jì)了兩個(gè)名為GreedyClass和BestClassification的算法找出最佳聚類(lèi)。H.Li et al.[13]設(shè)計(jì)了一個(gè)BestClassification的改進(jìn)算法。該算法把BestClassification的時(shí)間復(fù)雜度從O(n2m2+m4)提到了O(n2m2+m3)。

區(qū)別于文獻(xiàn)[1,13],Animesh Adhikari et al.[2]提出了兩個(gè)基于頻繁項(xiàng)集的相似度度量,并提出了一個(gè)效率高于BestClassification的聚類(lèi)算法。Yuan et al.[4]提出了一個(gè)基于高類(lèi)內(nèi)凝聚低類(lèi)間耦合的獨(dú)立于應(yīng)用的多數(shù)據(jù)聚類(lèi)方法。更多地,Wu et al.[14]提出了一個(gè)多數(shù)據(jù)庫(kù)中通過(guò)加權(quán)的模式識(shí)別方法。Yin and Han[15]提出了一個(gè)新的策略對(duì)于高維異構(gòu)數(shù)據(jù)庫(kù),此策略可能不適用于聚集事務(wù)數(shù)據(jù)庫(kù)。Yin et al.[16]提出了兩個(gè)可擴(kuò)展的高相關(guān)分類(lèi)算法CrossMine-Rule(基于關(guān)聯(lián)規(guī)則的)和CrossMine-Tree(基于決策樹(shù)的)。Bandyopadhyay et al.[17]提出了一個(gè)基于K均值算法的聚集適用于像傳感器網(wǎng)絡(luò)這樣點(diǎn)對(duì)點(diǎn)環(huán)境下的同構(gòu)的數(shù)據(jù)技術(shù)。

3聚集多數(shù)據(jù)庫(kù)

3.1相似度度量

定義1數(shù)據(jù)庫(kù)Di和Dj在閾值α下的相似度sim定義為

(1)

一個(gè)數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集能很好地刻畫(huà)一個(gè)數(shù)據(jù)庫(kù)[3],兩個(gè)數(shù)據(jù)庫(kù)中包含的頻繁項(xiàng)集越多,則這兩個(gè)數(shù)據(jù)庫(kù)越相似。

定義2D={D1,D2,…,Dm}是所有數(shù)據(jù)庫(kù)的集合。D的相似矩陣DSM(D,α)和距離矩陣DDM(D,α)分別通過(guò)相似度sim和距離度1-sim描述,兩個(gè)矩陣都是m階方矩陣。其中,它們的第(i,j)個(gè)元素分別是DSMi,j(D,α)=sim(Di,Dj,α)和DDMi,j(D,α)=1-sim(Di,Dj,α),而Di,Dj∈D,i,j=1,2,…,m。

定義3D是m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合。則C={c1,c2,…,cn},(1≤n≤m)為D1,D2,…,Dm的一個(gè)備選聚集(劃分),如果C滿(mǎn)足以下三點(diǎn):

1)ci≠Φ,1≤i≤n;

2)c1∪c2∪…∪cn=D;

3)ci∩cj=Φ,i≠j,1≤i,j≤n。

其中,ci(1≤i≤n)為C中的類(lèi)。

定義4D為m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)為D的一個(gè)備選聚集。在閾值α下C中兩個(gè)類(lèi)之間的相似度定義如下

sim(ci,cj,α)=

(2)

定義5D為m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)為D的一個(gè)備選聚集。則C中類(lèi)間距離矩陣CDM(C,α)用1-sim描述,為一個(gè)n階方陣。其中,第(i,j)個(gè)元素CDMi,j(C,α)=1-sim(ci,cj,α),i,j=1,2,…,n。

3.2數(shù)據(jù)庫(kù)關(guān)聯(lián)度量

定義6D為m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)為D的一個(gè)備選聚集。ci(1≤i≤n)為C中的類(lèi),則ci中數(shù)據(jù)庫(kù)間總的距離定義如下

(3)

定義7D為m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)為D的一個(gè)備選聚集。則C中數(shù)據(jù)庫(kù)間總的距離定義如下

(4)

以上的定義通過(guò)類(lèi)間的距離得到了一個(gè)聚類(lèi)總的距離,用距離衡量?jī)?nèi)聚,距離越小意味著越高內(nèi)聚。

定義8D為m個(gè)數(shù)據(jù)庫(kù)D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)為D的一個(gè)備選聚集。聚集C的耦合定義為

(5)

3.3最佳聚類(lèi)的查找

一個(gè)優(yōu)異的多數(shù)據(jù)庫(kù)聚類(lèi)必定是高內(nèi)聚、低耦合,并且聚類(lèi)個(gè)數(shù)相對(duì)少[1～2,4]。最好的聚類(lèi)是從備選聚類(lèi)中選出來(lái)的。我們的任務(wù)就是利用相似矩陣DSM(D,α)和距離矩陣DDM(D,α)找到一個(gè)聚類(lèi)函數(shù)g:D→C使得Class(C,α,distance),Class(C,α,coupling)和|C|取到最小值?？梢詫?xiě)成:

(6)

這樣的問(wèn)題屬于多目標(biāo)(標(biāo)準(zhǔn))最優(yōu)化問(wèn)題[5],而這里的問(wèn)題是三目標(biāo)最優(yōu)化。通過(guò)線(xiàn)性加權(quán)和法[8]把它轉(zhuǎn)化為單目標(biāo)最優(yōu)化問(wèn)題,如下:

min(λ1Class(C,α,distance)+λ2Class(C,α,coupling)

+λ3|C|),subject to all fesibleg,

(7)

其中,λi≥0,(i=1,2,3)是第i標(biāo)準(zhǔn)的權(quán)重。

通過(guò)利用下面的線(xiàn)性方程:

(8)

把目標(biāo)函數(shù)標(biāo)準(zhǔn)化,得到如下標(biāo)準(zhǔn)化后的目標(biāo)函數(shù):

(9)

通過(guò)式(6)、式(8),給出最優(yōu)的聚類(lèi)定義:

定義9一個(gè)備選聚類(lèi)C={c1,c2,…,cn}的優(yōu)秀度可定義如下goodness(C)=min(λ1Class′(C,α,distance)

+λ2Class′(C,α,coupling)+λ3|C|′)

(10)

其中,當(dāng)λi=1,(i=1,2,3)時(shí),意味著三個(gè)標(biāo)準(zhǔn)的重要程度一樣。本文把distance,coupling和|C|均衡對(duì)待。

令F(C,α)=Class′(C,α,distance)+Class′(C,α,coupling)+|C|′,則有

goodness(C)=minF(C,α)

(11)

4算法實(shí)現(xiàn)

由于備選聚類(lèi)的數(shù)目是相當(dāng)大,沒(méi)有必要把所有的備選聚類(lèi)都求出。高相似度的兩個(gè)數(shù)據(jù)庫(kù)應(yīng)該聚集到同一個(gè)類(lèi)中,所以可以利用相似度有層次地聚集備選聚類(lèi)。我們的算法DatabaseHierarchicalClustering(DHC)產(chǎn)生備選聚類(lèi)并從中選出最優(yōu)聚類(lèi)。

Procedure 1. DatabaseHierarchicalClustering(DHC)

begin

Input:Di(1≤i≤m):databases,α: threshold value;

Output:Cbest: the best cluster;

(1)find the frequent itemsets of eachDiunder thresholdα;

(2)construct the database similarity matrixDSM(D,α) and the database distance matrixDDM(D,α);

(3)letk=1;

(4)construct a candidate clusterCk.Ck={c1,c2,…,cm} whereci={Di}, 1≤i≤m;

(5) letCDM(Ck,α)=DDM(D,α), calculateF(Ck,α)=Class′(Ck,α,distance)+

Class′(Ck,α,coupling)+|Ck|′;

(6)letgoodness(Cbest)=F(Ck,α),Cbest=Ck;

(7)while (k

begin

(7.1)find the pair of classes (cp,cq), the distance valueCDMp,q(Ck,α) of which is the minimum in the upper triangle ofCDM(Ck,α);

(7.2)letk=k+1;

(7.3)letc=cp∪cq;

(7.4)letCk=Ck(1({cp}({cq}+{c};

(7.5)ifk≠m

begin

constructCDM(Ck,α) and calculateF(Ck,α);

else

calculateF(Ck,α);

end if

(7.6)ifF(Ck,α)

begin

letgoodness(Cbest)=F(Ck,α),Cbest=Ck;

end if

end for

(8)output the best clusterCbest;

end procedure

5實(shí)驗(yàn)

一系列的實(shí)驗(yàn)驗(yàn)證論文方法的有效性。首先通過(guò)利用一個(gè)合成的數(shù)據(jù)庫(kù)T10I4D100K把其拆分成十個(gè)數(shù)據(jù)庫(kù)對(duì)論文所提的算法有效性進(jìn)行實(shí)驗(yàn)。然后表3的相似度量,本文提出的算法與BestClassification進(jìn)行對(duì)比實(shí)驗(yàn)。

把T10I4D100K拆分成十個(gè)數(shù)據(jù)庫(kù),十個(gè)數(shù)據(jù)庫(kù)的基本特征如表1所示。數(shù)據(jù)庫(kù)集D={DB1,…,DB10},根據(jù)閥值α的變化,得到不同最佳聚類(lèi),α越小,算法運(yùn)行的時(shí)間越長(zhǎng),如表2所示。繼續(xù)用文獻(xiàn)[13]中的一個(gè)相似度二維表(表3),把論文的算法與BestClassification進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果在表4中給出。由于對(duì)于別的α值BestClassification并沒(méi)有最有聚類(lèi),所以只給出了兩個(gè)α值下兩個(gè)算法的比較。由表4可看出,論文的算法DHC優(yōu)于BestClassification。

表1　輸入數(shù)據(jù)庫(kù)特征

表2　輸入數(shù)據(jù)庫(kù)特征

表3　相似度關(guān)系表(Table 6. in [13])

表4　對(duì)表3相似度的實(shí)驗(yàn)結(jié)果

6結(jié)語(yǔ)

本文提出一個(gè)基于高內(nèi)聚和低耦合的多數(shù)據(jù)庫(kù)分類(lèi)方法,定義了距離用以衡量?jī)?nèi)聚性,定義耦合度用于衡量首先構(gòu)造一個(gè)多目標(biāo)優(yōu)化問(wèn)題,然后利用利用線(xiàn)性加權(quán)和法把多目標(biāo)最優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)最優(yōu)化,用層次聚類(lèi)思想構(gòu)造算法查找最優(yōu)聚類(lèi)。利用一個(gè)人工數(shù)據(jù)庫(kù)T10I4D100K和一個(gè)現(xiàn)實(shí)數(shù)據(jù)庫(kù)相似度二維表對(duì)算法的有效性進(jìn)行驗(yàn)證,并且與BestClassification算法進(jìn)行對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)表明論文的方法聚類(lèi)穩(wěn)定性強(qiáng),時(shí)間復(fù)雜度比BestClassification低,泛化能力強(qiáng)。

參 考 文 獻(xiàn)

[1] X. Wu, C. Zhang, S. Zhang. Database. classification for multidatabase mining[J]. Information Systems,2005,30(1):71-88.

[2] Animesh Adhikari, P. R. Rao. Efficient clustering of databases induced by local patterns[J]. Decision Support Systems,2008,44:33-36.

[3] R. Agrawal, T. Imielinski, A. Swami. Mining association rules between sets of items in large databases[J]. Proceedings of ACM SIGMOD Conferenc Management of Data,1993,66(1):207-216.

[4] Bandyopadhyay S, Giannella C, Maulik U, et al. Clustering distributed data streams in peer-to-peer environments[J]. Information Sciences,2006,176(14):1952-1985.

[5] C. Hillermeier. Nonlinear multiobjective optimization[M]. Birkhauser,2001:33-35.

[6] K. Deb, A. Pratap, S. Agarwal, et al. A fast and elitist multiobjective genetic algorithm[J]. NSGA-Ⅱ. IEEE TEC,2002,6(2):182-197.

[7] D. Corne, N. Jerram, J. Knowles, et al. PESA-Ⅱ: Region-based selection in evolutionary multiobjective optimization[M]. In Proc. GECCO,2001:99-101.

[8] L. Zadeh. Optimality and non-scalar-valued performance criteria[J]. IEEE TAC,1963,8(1):59-60.

[9] X. Lu. The base of optimization method application[J]. Tongji University Press,2003,(8):33-34.

[10] JS. Farris. On the cophenetic correlation coefficient[J]. Systematic Zoology,2010,18(3):279-285.

[11] S. Zhang, X. Wu, C. Zhang. Multi-database mining[J]. IEEE Computational Intelligence Bulletin,2003,2(1):5-13.

[12] H. Liu, H. Lu, J. Yao. Toward multidatabase mining: identifying relevant databases[J]. IEEE Transactions on Knowledge and Data Engineering,2001,13(4):541-553.

[13] H. Li, X. Hu, Y. Zhang. An improved database classication algorithm for multi-database min-ing[C]//Proc. of Frontiers of Algorithmics Workshop in LNCS. Hefei, China,2009,1(1):187-199.

[14] Xindong Wu, Shichao Zhang. Synthesizing high-frequencyrules from different data sources[J]. IEEE Trans. Knowledge Data Eng.,2003,15(2):353-367.

[15] X. Yin, J. Han. Efficient classification from m ultiple heterogeneous databases[C]//Proceedings of 9-th European Conf. on Principles and Practice of Knowledge Discovery in Databases,2005,1(1):404-416.

[16] X. Yin, J. Han, J. Yang, et al. Efficient classification across multiple database relations: A crossmine approach[J]. IEEE Transactions on Knowledge and Data E ngineering,2005,18(6):770-783.

收稿日期:2016年1月11日,修回日期:2016年2月14日

作者簡(jiǎn)介:曹禮園,女,碩士,助教,研究方向:智能軟件。李深洛,男,碩士研究生,研究方向:智能軟件。

中圖分類(lèi)號(hào)TP391

DOI:10.3969/j.issn.1672-9722.2016.07.007

An Application-independent Database Classification Method Based on High Cohesion and Low Coupling

CAO Liyuan1LI Shenluo2

(1. Huashang College Guangdong University of Finance & Economics, Guangzhou510006)(2. School of Computer Information and Engineering, Guangxi Normal University, Guilin541004)

AbstractDatabase classification is a preprocess technology for multi-database storage, management and mining. At present, there is a few related works for multi-database classification which is application-independent. However, they ignore the inter-class coupling or intra-class cohesion, and have a higher complexity. In this paper, an application-independent database classification method based on high intra-class cohesion and low inter-class coupling is proposed. Which uses hierarchical clustering method to avoid the instability and reduce the time complexity. The methodology, called Database Hierarchical Clustering, is established from a multi-criteria optimization problem of the sum of distance of classes and the coupling of classes and the number of classes,and uses hierarchical clustering method to find the best cluster. Experiments on a synthetic database and the real-world databases show that the proposed methodology indeed is efficient in finding clusters in a set of databases.

Key Wordsdatabase clustering, multicriteria optimization, multi-database mining, hierarchical clustering