中国职业技术教育杂志社投稿基于相似度的多数据库分类

 　　摘 要：许多大型组织拥有大量的子公司，进行事务处理时会产生大量的多源数据库，然而现有的数据挖掘只致力于对单个数据库的挖掘，由此，提出了多数据库挖掘技术。为了减少寻找相关数据的检索代价，在对多数据库进行挖掘和分析之前，首先要对多数据库进行分类。由于多数据库中包含大量数据，现有的分类算法GreedyClass的时间复杂度可达到O(m4)，所需代价非常大。由此提出了IdentifyCompleteclass算法用于对多数据库分类，其时间复杂度降为O(m3)，并提出了相应的寻找最优完全分类算法IdentifyBestClassification，实验证明改进后的算法有较高的运行效率。

　　关键词：中国职业技术教育杂志社,多数据挖掘,多数据库分类,IdentifyCompleteclass算法,IdentifyBestClassification算法

　　许多大型组织拥有多个分布在不同地区的子公司，而各个子公司具有不同类型的数据库，因此总公司需要挖掘不同数据元结构的数据库然后作相关决策。由此，怎样从多数据库中有效的确定知识特性[1-2]成为亟待解决的问题。在对数据进行挖掘和分析之前，首先要对多数据库进行分类。

　　然而现有独立于应用的多数据分类算法存在着一些问题。例如算法时间复杂度高[3，5]，不一定能得到最优分类[3]，浪费存储空间[4]等。本文针对以上问题提出了可行性的改进算法，使得对多数据库的分类更快、更准、更节省空间。

　　1 相关概念

　　文献[3-5]中对多数据库分类提出了相关理论概念并进行了理论证明，下面给出相关定义。

　　D为一个大量多元数据库的集合，且D={D1，D2，…，Dm}，Item(Di)为数据库Di(i=1，2，…，m)中所有项目的集合：定义1. 令Class(D，α)={class1α，class2α，…，classnα}为多数据库D={D1，D2，…，Dm}在α划分下的分类集合，如果Class(D，α)满足以下条件则其为完全分类(complete classification)：

　　(1)class1α∪class2α∪…∪ classnα=D;

　　(2)若∨�CDi∈classxα，∨�CDj∈classyα(x≠y，1≤x，y≤n)，则classxα∩classyα=且sim(Di，Dj)<α。

　　定义2.令Class(D，α)={class1α，class2α，…，classnα}为多数据库D(={D1，D2，…，Dm})在α划分下的分类集合，α∈[0，1]，Goodness与|Class(D，α)|间的绝对距离为：

　　其中在Goodness(α)为α划分下的分类集合中各个类别子集之间的距离。

　　定义3.多数据库D={D1，D2，…，Dm}，设在相似度α下，当αi<αj<αk(α∈[0，1])时，若D的最优分类为Class(D，αj)={class1αj ，class2αj ，…，classnαj}，则需满足以下条件为：(1)Class(D，αi)，Class(D，αj)，Class(D，αk)都为完全分类;(2)对∨�Cαx∈(αi，αk)，且αx≠αj，多数据库D不存在其它的完全分类;(3)Distance(αi)>Distance(αj)，且Distance(αj)　　2 现有算法存在的问题

　　文献[3]中所提出的GreedyClass算法及BestClassification算法存在以下缺点：(1)GreedyClass算法时间复杂度高。在对于给定阈值α产生分类时，程序没有最大的优化算法，对不完全分类没有做处理，增加了程序的运行时间。(2)算法BestClassification不一定能得到最优分类。变量step为阈值α的步长，并在算法初始时定义，而step值的选择具有盲目性，有可能导致选择到错误的最优分类，甚至使程序陷入死循环。针对以上问题，本文提出了新的多数据分类算法。

　　3 基于相似度的多数据库分类新算法

　　3.1 数据库相似度值的存储。文献[3][4][5]中对多数据库分类时，首先计算数据库之间的相似度值，然后存储在二维对称矩阵中，利用矩阵寻找最优分类。但实际寻找最优分类时只用到了m(m?1)/2+1个相似度值，即对称矩阵的小上三角元素和相似度值1。因此在计算数据库之间的相似度时，我们采用上小三角矩阵压缩存储方法。对于m阶对称矩阵A，其中aii=1(1≤i≤m)，aij=aji(i≠j)。将其压缩存储到一维数组需要12m(m?1)+1个元素空间。即实际存储的元素(非零元素)为：

　　设用一维数组B[1・・・12m(m?1)]来存储上小三角矩阵A，采用行主顺序压缩存储方法，则由文献[10]中给定了从A到B的映射对应关系。给定A中任一元素aij(1≤i　　，1≤i　　利用该方法可以轻易得到任意两数据库间的相似度，相似度值的存储空间从m2[3，4，5]减少到了12 m(m?1)。

　　3.2 寻找完全分类。寻找多数据库D在阈值α下的完全分类时，只需按索引顺序遍历数组SimArray，并分析值大于或等于α的索引。数组a[m]用来判断数据库是否已经被划分到某个分类中，所有元素的初始值为0，表示未被划分。根据以上性质寻找多数据库D在阈值α下的完全分类，算法1为具体的实现算法。

　　算法1：IdentifyCompleteClass

　　输入：数组SimArray[12m(m?1)];阈值α;输出：Class(D，α)：多数据库D在阈值α下的分类;(1)定义数组a[m]，且所有元素初始值为0;(2)令n←0;//n为完全分类集的当前子类数目;(3)令k←1;//数组SimArray索引;(4)for i=1 tom?1do;(5)forj=i+1 to m do

《中国职业技术教育杂志社投稿基于相似度的多数据库分类》

本文由职称驿站首发，您身边的高端学术顾问

文章名称： 中国职业技术教育杂志社投稿基于相似度的多数据库分类

文章地址： https://m.zhichengyz.com/p-28327