基于相似度的多数据库分类

本文是一篇数据库论文范文,数据库方面自考毕业论文开题报告,关于基于相似度的多数据库分类相关本科毕业论文范文。适合数据库及算法及阈值方面的的大学硕士和本科毕业论文以及数据库相关开题报告范文和职称论文写作参考文献资料下载。

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

关 键 词：多数据挖掘；多数据库分类；IdentifyCompleteclass算法；IdentifyBestClassification算法

中图分类号：TP311.13

许多大型组织拥有多个分布在不同地区的子公司,而各个子公司具有不同类型的数据库,因此总公司需要挖掘不同数据元结构的数据库然后作相关决策.由此,怎样从多数据库中有效的确定知识特性[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,α）满足以下条件则其为完全分类（pleteclassification）：

（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（m1）/2+1个相似度值,即对称矩阵的小上三角元素和相似度值1.因此在计算数据库之间的相似度时,我们采用上小三角矩阵压缩存储方法.对于m阶对称矩阵A,其中aii等于1（1≤i≤m）,aij等于aji（i≠j）.将其压缩存储到一维数组需要12m（m1）+1个元素空间.即实际存储的元素（非零元素）为：

,

设用一维数组B[112m（m1）]来存储上小三角矩阵A,采用行主顺序压缩存储方法,则由文献[10]中给定了从A到B的映射对应关系.给定A中任一元素aij（1≤i

,1≤i

利用该方法可以轻易得到任意两数据库间的相似度,相似度值的存储空间从m2[3,4,5]减少到了12m（m1）.

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

算法1：IdentifyCompleteClass

输入：数组SimArray[12m（m1）]；阈值α；输出：Class（D,α）：多数据库D在阈值α下的分类；（1）定义数组a[m],且所有元素初始值为0；（2）令n←0；//n为完全分类集的当前子类数目；（3）令k←1；//数组SimArray索引；（4）fori等于1tom1do；（5）forj等于i+1tomdo