一个基于高内聚和低耦合的多数据库分类方法*

曹礼园　李深洛

(1.广东财经大学华商学院　广州　510006)(2.广西师范大学计算机科学与信息工程学院　桂林　541004)



一个基于高内聚和低耦合的多数据库分类方法*

曹礼园1李深洛2

(1.广东财经大学华商学院广州510006)(2.广西师范大学计算机科学与信息工程学院桂林541004)

摘要数据库分类是多数据库存储、管理和挖掘的预处理技术。目前,不依赖具体应用的多数据库分类的研究甚少,并且忽略内聚度和耦合度,复杂度高。论文提出一个基于高内聚和低耦合的多数据库分类方法,该方法不依赖于具体的应用,避免了聚类结果的不稳定性,且降低了时间复杂度。具体地,该方法名为DHC首先构造一个多目标优化问题,然后利用层次聚类思想构造算法查找最优聚类。利用一个人工数据库和一个现实数据库相似度二维表进行实验,实验表明该方法聚类稳定性强,时间复杂度比BestClassification低,泛化能力强。

关键词数据库聚类; 多目标最优化; 多数据库挖掘; 层次聚类

Class NumberTP391

1引言

当今,有很多大机构有着不同的数据库分布在其不同的分支机构,因此多数据库挖掘作为数据挖掘的一个重要分支变得越来越重要。为了减小搜索成本,需要确定哪些数据库是与我们的数据挖掘应用相关联的。这一重要步骤称之为数据库选择[1]。进一步,考虑一个需要处理多个大型数据库的跨国公司。该公司可能需要进行关联分析找出非盈利的项目(产品)。最终的目标是识别那些本身没有多大的利润也没有促进其他产品盈利的产品。关联分析可能找出这样的产品,从而公司可终止该产品的交易。这种性质的分析可能需要识别类似的数据库。我们注意到,如果两个数据库包含许多类似的交易,则两个数据库被认为是类似的。进而,如果两个事务交易包含很多相同的物品,则这两个交易是类似的。所以,两个数据库包含越多的相同的频繁项集,它们越相似[2]。我们可以聚集多数据库根据两个数据库之间的相似性;然后,挖掘在同一个类中的数据库。多数据库聚类是模式发现、分组、决策选择和机器学习的重要组成部分。本文主要探讨事务数据库的聚类。

2相关工作

对于多数据库挖掘,第一个方法(单数据库挖掘技术)是把多数据库中的数据聚集在一起构成一个单一的数据集[1]。Liu et al.[12]提出了一个只搜索相关数据库的多数据库挖掘技术。他们的研究侧重于识别与某一应用相关的数据库。

Zhang et al.[11]提出了一个新的多数据库挖掘方法,首先是数据库聚类,然后进行局部模式发现。相应地,Zhang et al.[1]提出了一个基于数据库间的相似度的独立于某一个应用过的多数据库聚类方法。该文首先提出了一个基于事务项集或高频繁规则的数据库相似度量,然后设计了两个名为GreedyClass和BestClassification的算法找出最佳聚类。H.Li et al.[13]设计了一个BestClassification的改进算法。该算法把BestClassification的时间复杂度从O(n2m2+m4)提到了O(n2m2+m3)。

区别于文献[1,13],Animesh Adhikari et al.[2]提出了两个基于频繁项集的相似度度量,并提出了一个效率高于BestClassification的聚类算法。Yuan et al.[4]提出了一个基于高类内凝聚低类间耦合的独立于应用的多数据聚类方法。更多地,Wu et al.[14]提出了一个多数据库中通过加权的模式识别方法。Yin and Han[15]提出了一个新的策略对于高维异构数据库,此策略可能不适用于聚集事务数据库。Yin et al.[16]提出了两个可扩展的高相关分类算法CrossMine-Rule(基于关联规则的)和CrossMine-Tree(基于决策树的)。Bandyopadhyay et al.[17]提出了一个基于K均值算法的聚集适用于像传感器网络这样点对点环境下的同构的数据技术。

3聚集多数据库

3.1相似度度量

定义1数据库Di和Dj在阈值α下的相似度sim定义为

(1)

一个数据库中的频繁项集能很好地刻画一个数据库[3],两个数据库中包含的频繁项集越多,则这两个数据库越相似。

定义2D={D1,D2,…,Dm}是所有数据库的集合。D的相似矩阵DSM(D,α)和距离矩阵DDM(D,α)分别通过相似度sim和距离度1-sim描述,两个矩阵都是m阶方矩阵。其中,它们的第(i,j)个元素分别是DSMi,j(D,α)=sim(Di,Dj,α)和DDMi,j(D,α)=1-sim(Di,Dj,α),而Di,Dj∈D,i,j=1,2,…,m。

定义3D是m个数据库D1,D2,…,Dm的集合。则C={c1,c2,…,cn},(1≤n≤m)为D1,D2,…,Dm的一个备选聚集(划分),如果C满足以下三点:

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

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

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

其中,ci(1≤i≤n)为C中的类。

定义4D为m个数据库D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)为D的一个备选聚集。在阈值α下C中两个类之间的相似度定义如下

sim(ci,cj,α)=

(2)

定义5D为m个数据库D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)为D的一个备选聚集。则C中类间距离矩阵CDM(C,α)用1-sim描述,为一个n阶方阵。其中,第(i,j)个元素CDMi,j(C,α)=1-sim(ci,cj,α),i,j=1,2,…,n。

3.2数据库关联度量

定义6D为m个数据库D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)为D的一个备选聚集。ci(1≤i≤n)为C中的类,则ci中数据库间总的距离定义如下

(3)

定义7D为m个数据库D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)为D的一个备选聚集。则C中数据库间总的距离定义如下

(4)

以上的定义通过类间的距离得到了一个聚类总的距离,用距离衡量内聚,距离越小意味着越高内聚。

定义8D为m个数据库D1,D2,…,Dm的集合,C={c1,c2,…,cn},(1≤n≤m)为D的一个备选聚集。聚集C的耦合定义为

(5)

3.3最佳聚类的查找

一个优异的多数据库聚类必定是高内聚、低耦合,并且聚类个数相对少[1～2,4]。最好的聚类是从备选聚类中选出来的。我们的任务就是利用相似矩阵DSM(D,α)和距离矩阵DDM(D,α)找到一个聚类函数g:D→C使得Class(C,α,distance),Class(C,α,coupling)和|C|取到最小值。可以写成:

(6)

这样的问题属于多目标(标准)最优化问题[5],而这里的问题是三目标最优化。通过线性加权和法[8]把它转化为单目标最优化问题,如下:

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

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

(7)

其中,λi≥0,(i=1,2,3)是第i标准的权重。

通过利用下面的线性方程:

(8)

把目标函数标准化,得到如下标准化后的目标函数:

(9)

通过式(6)、式(8),给出最优的聚类定义:

定义9一个备选聚类C={c1,c2,…,cn}的优秀度可定义如下goodness(C)=min(λ1Class′(C,α,distance)

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

(10)

其中,当λi=1,(i=1,2,3)时,意味着三个标准的重要程度一样。本文把distance,coupling和|C|均衡对待。

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

goodness(C)=minF(C,α)

(11)

4算法实现

由于备选聚类的数目是相当大,没有必要把所有的备选聚类都求出。高相似度的两个数据库应该聚集到同一个类中,所以可以利用相似度有层次地聚集备选聚类。我们的算法DatabaseHierarchicalClustering(DHC)产生备选聚类并从中选出最优聚类。

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实验

一系列的实验验证论文方法的有效性。首先通过利用一个合成的数据库T10I4D100K把其拆分成十个数据库对论文所提的算法有效性进行实验。然后表3的相似度量,本文提出的算法与BestClassification进行对比实验。

把T10I4D100K拆分成十个数据库,十个数据库的基本特征如表1所示。数据库集D={DB1,…,DB10},根据阀值α的变化,得到不同最佳聚类,α越小,算法运行的时间越长,如表2所示。继续用文献[13]中的一个相似度二维表(表3),把论文的算法与BestClassification进行对比实验,结果在表4中给出。由于对于别的α值BestClassification并没有最有聚类,所以只给出了两个α值下两个算法的比较。由表4可看出,论文的算法DHC优于BestClassification。

表1　输入数据库特征

表2　输入数据库特征

表3　相似度关系表(Table 6. in [13])

表4　对表3相似度的实验结果

6结语

本文提出一个基于高内聚和低耦合的多数据库分类方法,定义了距离用以衡量内聚性,定义耦合度用于衡量首先构造一个多目标优化问题,然后利用利用线性加权和法把多目标最优化问题转化为单目标最优化,用层次聚类思想构造算法查找最优聚类。利用一个人工数据库T10I4D100K和一个现实数据库相似度二维表对算法的有效性进行验证,并且与BestClassification算法进行对比实验,实验表明论文的方法聚类稳定性强,时间复杂度比BestClassification低,泛化能力强。

参 考 文 献

[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日

作者简介:曹礼园,女,硕士,助教,研究方向:智能软件。李深洛,男,硕士研究生,研究方向:智能软件。

中图分类号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