论文部分内容阅读
[摘 要] 本文针对信息系统中冗余数据主要集中在数据库重复记录的特点,对这部分的冗余数据进行精简。对数据库重复记录分别进行:预处理、表内精简、用SOM-BP网络在异构数据库间建立同类型字段的匹配关系、求取匹配记录对、对共享池进行精简这5个步骤实现共享池数据的精简。建立了高校信息管理系统共享池建设中异构数据库的精简范式。这套精简系统满足了高校信息集成过程中对数据精简的需求,提高了效率。
[关键词] 数据精简;数据整合;共享池
doi : 10 . 3969 / j . issn . 1673 - 0194 . 2016 . 01. 098
[中图分类号] G250.76 [文献标识码] A [文章编号] 1673 - 0194(2016)01- 0189- 06
0 引 言
高校数据集成是目前高校信息共享工程中的一个核心的构成,而信息集成前的异构数据含有大量冗余数据,这些冗余数据在数据库中以重复字段的形式存在,重复数据直接影响数据的质量,进而影响到信息决策的准确性和成本的投入量。本文以高校信息系统的数据库属性级、记录级的脏数据为研究对象,展开研究并提出了一套建立数据精简整合系统的范式。
1 相关工作
范式是符合某一种级别的关系模式的集合,在本文中“范式”指的是数据集成过程中对异构数据库中的冗余数据进行精简的处理流程、逻辑顺序和处理对象的关系集合。目前国内外对数据库的数据精简范式的研究较少,主要着眼于数据精简算法的效率和复杂度的优化,相关技术主要涉及以下几个方面。
1.1 单表数据库的数据精简算法研究
目前的研究主要针对单数据源进行,采用统计方法来对单一数据库内的记录检测数值型数据的属性,通过对字段值的均值和标准差,并设置每个字段的置信区间来识别异常字段和记录。主要集中于算法的研究上。缺少对多数据源环境下的数据精简和整合,而高校信息集成系统的数据必然是来自于多数据源的,因此本文将单数据源去重算法应用于多数据源,并将精简的结果汇集到共享库,以满足高校数据集成环境下的应用需求。
由于多表精简还涉及字段之间的对应,已有方案是手动对字段进行匹配,工作量大且容易出错,因此本文引入了SOM-BP网络在预处理结束后对各个异构库之间的相似字段进行自动匹配,提高了工作效率。
1.2 特定领域的数据精简
不少数据精简方案和算法都是针对特定应用问题的,例如在求取相似度算法中的递归的字段匹配算法,与应用领域密切相关,只适用于较小的范围。在复制记录检测中的SNM(排序邻居算法)中,需要抽取键值进行排序,如果键值包含错误,排序的结果将不如人意,进而影响到复制记录检测的效果,当前的工作中通用的、与应用领域无关的算法和方案较少。所以本文探讨使用二步聚类法:第一步粗聚类,采用倒排检索方法和TF-IDF算法求相似度进行,第二步为精确聚类,采用编辑距离算法求取相似度,并用Canopy聚类技术进行记录配对。由于倒排检索方法的粗聚类不需要抽取键值进行排序,而是把整个数据记录看成文本,所以避免了键值抽取不当带来的排序误差。
2 数据精简整合系统范式建立的步骤
2.1 业务理解
业务理解指的是从业务角度理解数据精简的目的和需求。主要任务是把项目的目标和需求转化为一个数据精简问题的定义和实现这些目标的初步计划。这一阶段包含的一般性任务如下:
2.1.1 确定业务对象
即系统的处理对象是什么,对于本项目而言,业务对象是高校信息管理系统中的脏数据,这些脏数据包括了数据库中的属性级的不一致、不完整和错误数据及重复数据。
2.1.2 评估环境
指的是对数据精简应用场景,包括软件和硬件两方面的资源、约束、假设和其他因素进行详细分析和评估,以便下一步确定数据目标分析和项目计划。
2.1.3 确定数据精简目标
对于本项目而言,数据精简的目标是对高校异构数据库中的重复记录、重复属性进行去冗余。使得校园信息系统的运转效率提高,节约资源占用。
2.2 数据理解
数据理解是对数据精简所需数据的全面调查。它包括以下步骤:
2.2.1 收集原始数据
对于本方案而言数据精简系统的处理对象根据其粒度区分可以分为两个方面,一是属性级的脏数据,即来自各个异构数据库中的字段和属性值,异构数据库根据其平台的不同可以分为Oracle、SQL Server等。一个是记录级的脏数据,记录由属于不同字段的属性值所构成。其他包括所需要整合到共享池中的所有异构库的数据源格式、拥有者、存储方式、字节数、物理存储方式、隐私需求等。
2.2.2 描述数据
调查各个异构数据库中的所有字段,包括其数据类型、长度、是否为空、精度、小数位数、标准差。这些参数归一化后将作为字段自动匹配计算的指标。
2.2.3 检验数据质量
这一步骤主要是检查数据是否满足数据精简的需求。例如,数据中空值的多少,错误率的高低,过多空值和高错误率的数据不可用。
2.3 建立模型
确立精简系统的输入和输出,以及实现这些输入、输出的模块和顺序。对于本系统而言,输入是异构数据库的脏数据,输出就是精简系统对脏数据进行处理后的输出的干净数据。这些干净数据应具有如下特征:
(1)共享库中的记录应是完全没有重复的。
(2)共享库中的字段是完全无重复的。
(3)共享库的数据结构应该是标准化的,能够提供给校园网中的各个子系统作为共享资源。
2.4 评价
对数据精简的效率和成果进行评估。数据精简系统的评价标准包括了用召回率和查准率对数据精简的结果和传统的精简模型进行比较检验。 3 高校信息系统共享池的精简框架
目前在高校的信息系统应用中兴起了数据集成的热潮,所谓的数据集成,就是把不同来源、格式、特点性质的数据在逻辑上或物理上有机地集中,使这些异构信息在共享池中存放,从而为高校提供全面的数据共享。共享池与各个异构数据库间的关系如图1所示。
我校的信息集成系统是以共享池作为信息集成和共享的中介,各个部门的异构数据库的数据在共享池中汇集,完成字段和记录的重组。共享池的建立首先要经历的步骤是对遗留数据的清洗,将有价值的信息保存在共享池中,数据清洗的步骤也包括了数据精简,使共享池中的每一条记录都具有唯一性。第二步才是将原先各个系统的以各自信息资源库为存储对象转换为以共享库为存储对象,也就是在共享池建立之后,所有部门都将这个共享池作为数据源,各个部门不再拥有各自的独立数据源。
数据集成中存在的问题就是脏数据的困扰,所谓脏数据就是不一致或不准确数据、不完整数据以及人为造成的错误数据以及冗余数据等。具体的按照脏数据的粒度粗细,可以分为属性级和记录级两个层面,属性级的脏数据包括空缺值、噪音值和不一致值,记录级的脏数据主要是指重复记录,重复记录指的是那些客观上表示现实世界同一实体的,但是由于在格式、拼写上有些差异而导致数据库管理系统不能正确识别的记录。数据精简就是对属性级和记录级脏数据进行处理,纠正可以纠正错误的数据,补充遗漏的数据,将不一致的数据统一格式,去除数据仓库中冗余的记录,从而得到数据共享池所需要的数据集合。
如图2所示为高校信息集成精简环境下的精简系统的框架结构,它大致可以分为预处理、表内数据精简、异构数据库的字段匹配、记录级精简这4个环节,下面分别介绍。
3.1 预处理
预处理目的是在进行记录级精简之前对记录中的空白值、异常值和不一致值进行处理,这些脏数据可能会对求取相似度和匹配的运算造成负面影响。由于这些处理主要是针对各个记录中的具体属性值的,所以也称为属性级精简以区别于记录级精简。
3.1.1 空白值的处理
在数据输入的时候,可能由于漏输入的原因导致有的字段属性值为空。这些空值必须被填充才参与后续的匹配度计算。所以我们可以采用最接近空白值的值来替代空白值,本文采用聚类法的方式对空白值求取近似值。
①首先对原始数据集进行数据筛选:剔除具有较多缺失数据的属性,因为这样的属性作为后续的匹配依据是不合适的。并且将有较多缺失值的记录提交给用户,让用户手工对这些数据进行处理,因为具有较多缺失值的记录使用算法处理可能产生较大误差。②将原始数据集分为完整数据集Dc和不完整数据集Di。③对完整数据集使用CANOPY算法进行聚类,产生K个聚类。④计算不完整数据集Di中每条记录和Dc中的K个聚类重心的相似度,将Di中的记录赋予距离该记录最近的那个重心所属的聚类,并且用该聚类的均值或出现频率最高的值来填充该记录的空白值。如果无法填充该记录则对此记录进行删除。
对于数值型数据,空白值取距离最近的那个聚类的平均值,Ai为该空白值最接近的聚类的所有成员,n为该聚类的成员总数。当空白值为离散型数据时,空白值取最接近的聚类的出现频率最高的成员值。
空白值=■Ai n 空白值为数值型数据Ai 空白值为离散型数据,取出现频率最高的Ai
⑤最终将经过填充后的Di′和完整数据集Dc整合为新的完整数据集。
3.1.2 异常值的处理
记录中可能存在姓名在输入的时候的拼写错误,属于异常值。这里用一个包含完全正确的数据的外部文件来作为判别依据。
由于高校管理信息系统中,一般记录都包含有学号,而学号具有唯一性,所以,我们可以将学号作为主键,也就是以学号为依据与外部文件进行对比。①对于在数据库中有的学号,在外部文件中找不到,将记录提交给用户判断处理。②对于字段的键值间对应关系和外部文件中的对应关系有出入的,采用领域权值的方式计算数据表记录与外部文件记录的相似度。如果相似度大于等于阈值则认定数据库记录和外部文件记录是同一个实体,用外部文件记录替代数据库记录。如果低于阈值,则提交用户判断处理,判断是否应该采用外部文件的属性值进行替换或者保留原值。领域相似度用编辑距离算法得出。
3.1.3 不一致值的处理
不一致数据是指由于系统和应用的不同在数据类型、格式、粒度和编码方式上的不同。本文中这部分工作由一个标准化字符集转换完成,将各个异构库中的属性值转换为标准的字符集,以便于后续的相似属性、相似字段的比较。例如有的异构数据库中的“男”“女”用“M”“F”表示,有的用“man”“woman”表示,我们可以通过标准化信息标准将这些代码转换为“1”“0”表示。这样做的好处是方便后续的字段相似度比较和记录相似度的比较。另外,如果万一后期各个异构数据库中对这些字段属性值有新的表达方式,也可以通过这个映射表变更映射关系很容易地实现键值定义的转换。
3.2 表内数据精简
由于在各个异构数据库的内部可能存在有大量的重复实体记录,这些实体记录在后续的表间记录匹配合并的工作中可能带来困难。所以需要对各个异构数据库各自的数据进一步的精简以去冗余。
把整个数据记录看成文本,采用倒排检索方法,粗糙、快速地把数据分成一些重叠的子集,称为Canopy。然后是一个更严格的阶段,这个阶段对Canopy内的点用精确的计算方法进行再次聚类。
最后,按照一定规则对相似记录进行剔除或保留。
3.3 异构数据库的字段匹配
在经过前面的表内数据精简后,各个异构数据库中的数据已经具备了可以进行相似度运算的条件,接下来的工作是用SOM(Self-organizing feature Map,自组织特征映射)-BP(Back Propagation,前馈)网络对各个异构数据库中的字段建立匹配关系。 如图3所示,SOM-BP网络的作用主要是对异构数据库数据表中的相似字段进行匹配,提供给共享池,作为共享池字段。这个过程的步骤包括:
①从异构数据库中抽取属性的特征向量,包括数据模式和数据内容统计。特征向量就是如属性值的数据类型、长度、是否为空、精度、小数位数、标准差这些参数。这些特征向量将作为SOM-BP网络运算匹配度的参数。②将特征向量归一化。③建立SOM网络模型,将属性特征向量进行分类,分为M类。④建立BP属性匹配模型,用样本数据库对SOM分类后的每一类别(共M个类别)进行训练直至收敛,保存BP网络权值和阈值,建立M个BP网络模型。⑤同样,目标库数据通过①②③步骤完成输入向量分类,分为M类,将分M类后的数据对应M个BP网络进行模拟,完成相似度匹配。⑥将完成匹配的数据库属性按照匹配的结果在共享数据库中添加“表名”“库名”字段,使匹配工作中被识别为同一属性的异构属性能够实现快速对应。⑦将上述完成匹配的字段匹配情况作为后续求记录相似度的特征字段选择依据。
从表1我们看到,当各异构库中的字段被SOM-BP网络发现相似的时候,这个匹配结果将提交给人工,由人工选择保留哪个数据源作为共享池中的字段,当字段没被发现匹配对象,即这个字段为唯一字段时,将此字段作为共享池中的字段。
3.4 记录级精简
在上一步确定在共享池中需要保留的字段之后,接下来是将各个异构库中存在的相同实体记录进行精简,保留唯一实体记录存入共享池,使得共享池中的记录都属于完全不同的实体。
3.4.1 字段选择
字段选择的目的是作为进行相似度比较的记录的标识,一个记录可能包含有许多相似属性,我们不能全部作为比较的内容,必须对其进行选择。考虑特征字段,应考虑进行比较的两个异构数据库中都有的语义相同的字段,如字段“ID”和“XH”都指的是学号,还要考虑到字段的“重要性”,在记录与记录之间区别越大的字段属性值越能够更好的标识一个记录。例如,“学号”字段比“性别”字段能更好的标识记录,因为相对于比较“性别”字段,“学号”字段的取值更能够唯一地标识一个记录。综上所述特征字段选择的依据包括:
①SOM-BP匹配的结果。我们要对异构数据库记录进行比较首先要找到在两个数据库中都存在的能够比较的属性值,前期SOM-BP网络已经得出异构数据库间的字段匹配结果,例如XH和ID都指的是“学号”这一属性。所以教务处表中的XH和学工处表中的ID这一对就可以选为教务处表—学工处表要进行记录匹配的特征字段。②字段排序的结果:对字段属性的值域进行统计,值域越大的字段,说明其属性值越多,更具有区分性。从属性值值域由高到低对字段进行排序的结果:选择前k个属性组成属性集。后续的相似度计算就针对这k个字段进行。
3.4.2 粗聚类
粗聚类是将字段聚类形成Canopy簇,图4中V1m表示A属性值粗聚类后的聚类集合,V2m表示A’属性簇聚类后形成的聚类集合。
第一阶段粗聚类,对于案例中的数据库D1和D2而言,首先抽取若干特征字段来表征不同的记录,建立表L1和L2,并定义相似距离阈值H1>=H2。将L1和L2融合成为一个整体的表L,接下来借用信息检索中倒排检索方法,采用基于TF-IDF 相似度的计算方法来计算记录与记录之间的相似度,选取与相似距离小于等于H1的(d,d’)放到一个Canopy中,之后从中心点列表中删除已经使用过的中心点d和与d点相似距离小于H2的点d’……如此反复,直到中心点列表为空集,停止操作。最后得到的是诸多围绕各个中心点d的d’的集合(Canopyi)。这样的粗聚类对大数据集特别有效,减少了全表逐个比较对内存的大占用,提高了系统运行的效率。
3.4.3 精确聚类
使用精确聚类提取匹配记录。就是对第一步粗聚类形成的每一个Canopy中的所有记录用编辑距离算法计算相似度。假设Canopyi中一共有n(n>=2)个点,di和dj为Canopyi中的任意两点,将每一点作为一类,在每一个Canopy中求这任意两类gi和gj间的最小距离,取最小值,当每一个Canopy中的类的个数大于1且类间的最小距离小于k时,标记满足最小距离小于k的两个类(gi,gj)作为匹配结果输出,并从Canopyi中剔除掉已经建立匹配关系的(gi,gj),接下来再计算Canopyi中其余的类间距离,判断是否小于k,一直到Canopyi中的类个数小于等于1或者类间最小距离大于k为止,此时跳出循环并返回最终的匹配对。
3.4.4 匹配结果注入共享池
找到匹配对之后的操作就是将同属同一实体的数据注入共享池。例如在教务处数据库中学号N101121011下有该生各学年的成绩,但是没有该生的籍贯、违纪情况的信息,这些信息分别存放在学生处、后勤处的数据库中,那么在经过上述的聚类算法匹配后,学生处、后勤处的数据被辨识到属于该生,接下来的操作就是将这些属性值合并到同一条目中,并存放在共享池中。
4 实验环节
本文所有的程序均用JAVA语言编写,并在CPU为INTEL Core i5,主频为2.5GHz,内存为8GB的机器上运行,所用的操作系统为Windows 7,数据结构采用链表存储复制记录。数据表存放于SQL Server中。
实验比较的对象是传统的排序—删除算法的代表SNM算法和Canopy聚类算法在多表精简中的应用,实验数据共有5000 条记录,对比的两个表分别来自教务处和学生处。5000条记录有1000条重复记录。教务处数据表中的特征字段为ID(学号)、NAME(姓名)、NMPY(姓名拼音)、ADDRESS(地址),对应的学生处中的特征字段为XH(学号)、XM(姓名)、XMPY(姓名拼音)、ADD(地址)。
那么考察的指标就是对两种方法与是否叠加预处理的组合对教务处和学生处两个表重复记录识别的召回率和查准率,取10组数据,重复10次试验后求平均值得出召回率和查准率。借此判断哪种方法在召回率和查准率上的表现更优秀。
从表2可以看出,经过预处理的复制记录检测方法的准确率要高于未经过预处理的复制记录检测方法,在本实验中,经过预处理的Canopy聚类的复制记录检测方法的查准率高于经过预处理的排序邻居方法,且Canopy方法具有更高的召回率,表明它能得到更多的复制记录,算法效率更高。
5 结 语
本文提出了基于共享池的高校信息集成环境下的共享池精简范式。通过预处理提高记录匹配的准确性,通过Canopy聚类算法作为数据库记录求取相似匹配的基础算法。该算法不局限于特定应用领域具有较好的普遍适应性,且比较传统的排序—比较法,聚类法的运算量较小,召回率和准确率较高。经过实验,本框架达到了预定的设计要求。
在高校信息系统中,不仅存在着数据库的重复记录类型的冗余数据,还有不同部门/相同部门的信息系统中的重复文件,以及在数据备份的过程中由于全局备份产生的大量冗余数据,这部分重复数据的识别与精简,被称为文件级的精简,这将是下一阶段研究的课题。
主要参考文献
[1]戴东波,汤春蕾,熊簧.基于整体和局部相似性的序列聚类算法[J].软件学报,2010,21(4):702-717.
[2]张枢.基于数据仓库的数据清洗算法研究[J].煤炭技术, 2010, 29(7): 192-194.
[关键词] 数据精简;数据整合;共享池
doi : 10 . 3969 / j . issn . 1673 - 0194 . 2016 . 01. 098
[中图分类号] G250.76 [文献标识码] A [文章编号] 1673 - 0194(2016)01- 0189- 06
0 引 言
高校数据集成是目前高校信息共享工程中的一个核心的构成,而信息集成前的异构数据含有大量冗余数据,这些冗余数据在数据库中以重复字段的形式存在,重复数据直接影响数据的质量,进而影响到信息决策的准确性和成本的投入量。本文以高校信息系统的数据库属性级、记录级的脏数据为研究对象,展开研究并提出了一套建立数据精简整合系统的范式。
1 相关工作
范式是符合某一种级别的关系模式的集合,在本文中“范式”指的是数据集成过程中对异构数据库中的冗余数据进行精简的处理流程、逻辑顺序和处理对象的关系集合。目前国内外对数据库的数据精简范式的研究较少,主要着眼于数据精简算法的效率和复杂度的优化,相关技术主要涉及以下几个方面。
1.1 单表数据库的数据精简算法研究
目前的研究主要针对单数据源进行,采用统计方法来对单一数据库内的记录检测数值型数据的属性,通过对字段值的均值和标准差,并设置每个字段的置信区间来识别异常字段和记录。主要集中于算法的研究上。缺少对多数据源环境下的数据精简和整合,而高校信息集成系统的数据必然是来自于多数据源的,因此本文将单数据源去重算法应用于多数据源,并将精简的结果汇集到共享库,以满足高校数据集成环境下的应用需求。
由于多表精简还涉及字段之间的对应,已有方案是手动对字段进行匹配,工作量大且容易出错,因此本文引入了SOM-BP网络在预处理结束后对各个异构库之间的相似字段进行自动匹配,提高了工作效率。
1.2 特定领域的数据精简
不少数据精简方案和算法都是针对特定应用问题的,例如在求取相似度算法中的递归的字段匹配算法,与应用领域密切相关,只适用于较小的范围。在复制记录检测中的SNM(排序邻居算法)中,需要抽取键值进行排序,如果键值包含错误,排序的结果将不如人意,进而影响到复制记录检测的效果,当前的工作中通用的、与应用领域无关的算法和方案较少。所以本文探讨使用二步聚类法:第一步粗聚类,采用倒排检索方法和TF-IDF算法求相似度进行,第二步为精确聚类,采用编辑距离算法求取相似度,并用Canopy聚类技术进行记录配对。由于倒排检索方法的粗聚类不需要抽取键值进行排序,而是把整个数据记录看成文本,所以避免了键值抽取不当带来的排序误差。
2 数据精简整合系统范式建立的步骤
2.1 业务理解
业务理解指的是从业务角度理解数据精简的目的和需求。主要任务是把项目的目标和需求转化为一个数据精简问题的定义和实现这些目标的初步计划。这一阶段包含的一般性任务如下:
2.1.1 确定业务对象
即系统的处理对象是什么,对于本项目而言,业务对象是高校信息管理系统中的脏数据,这些脏数据包括了数据库中的属性级的不一致、不完整和错误数据及重复数据。
2.1.2 评估环境
指的是对数据精简应用场景,包括软件和硬件两方面的资源、约束、假设和其他因素进行详细分析和评估,以便下一步确定数据目标分析和项目计划。
2.1.3 确定数据精简目标
对于本项目而言,数据精简的目标是对高校异构数据库中的重复记录、重复属性进行去冗余。使得校园信息系统的运转效率提高,节约资源占用。
2.2 数据理解
数据理解是对数据精简所需数据的全面调查。它包括以下步骤:
2.2.1 收集原始数据
对于本方案而言数据精简系统的处理对象根据其粒度区分可以分为两个方面,一是属性级的脏数据,即来自各个异构数据库中的字段和属性值,异构数据库根据其平台的不同可以分为Oracle、SQL Server等。一个是记录级的脏数据,记录由属于不同字段的属性值所构成。其他包括所需要整合到共享池中的所有异构库的数据源格式、拥有者、存储方式、字节数、物理存储方式、隐私需求等。
2.2.2 描述数据
调查各个异构数据库中的所有字段,包括其数据类型、长度、是否为空、精度、小数位数、标准差。这些参数归一化后将作为字段自动匹配计算的指标。
2.2.3 检验数据质量
这一步骤主要是检查数据是否满足数据精简的需求。例如,数据中空值的多少,错误率的高低,过多空值和高错误率的数据不可用。
2.3 建立模型
确立精简系统的输入和输出,以及实现这些输入、输出的模块和顺序。对于本系统而言,输入是异构数据库的脏数据,输出就是精简系统对脏数据进行处理后的输出的干净数据。这些干净数据应具有如下特征:
(1)共享库中的记录应是完全没有重复的。
(2)共享库中的字段是完全无重复的。
(3)共享库的数据结构应该是标准化的,能够提供给校园网中的各个子系统作为共享资源。
2.4 评价
对数据精简的效率和成果进行评估。数据精简系统的评价标准包括了用召回率和查准率对数据精简的结果和传统的精简模型进行比较检验。 3 高校信息系统共享池的精简框架
目前在高校的信息系统应用中兴起了数据集成的热潮,所谓的数据集成,就是把不同来源、格式、特点性质的数据在逻辑上或物理上有机地集中,使这些异构信息在共享池中存放,从而为高校提供全面的数据共享。共享池与各个异构数据库间的关系如图1所示。
我校的信息集成系统是以共享池作为信息集成和共享的中介,各个部门的异构数据库的数据在共享池中汇集,完成字段和记录的重组。共享池的建立首先要经历的步骤是对遗留数据的清洗,将有价值的信息保存在共享池中,数据清洗的步骤也包括了数据精简,使共享池中的每一条记录都具有唯一性。第二步才是将原先各个系统的以各自信息资源库为存储对象转换为以共享库为存储对象,也就是在共享池建立之后,所有部门都将这个共享池作为数据源,各个部门不再拥有各自的独立数据源。
数据集成中存在的问题就是脏数据的困扰,所谓脏数据就是不一致或不准确数据、不完整数据以及人为造成的错误数据以及冗余数据等。具体的按照脏数据的粒度粗细,可以分为属性级和记录级两个层面,属性级的脏数据包括空缺值、噪音值和不一致值,记录级的脏数据主要是指重复记录,重复记录指的是那些客观上表示现实世界同一实体的,但是由于在格式、拼写上有些差异而导致数据库管理系统不能正确识别的记录。数据精简就是对属性级和记录级脏数据进行处理,纠正可以纠正错误的数据,补充遗漏的数据,将不一致的数据统一格式,去除数据仓库中冗余的记录,从而得到数据共享池所需要的数据集合。
如图2所示为高校信息集成精简环境下的精简系统的框架结构,它大致可以分为预处理、表内数据精简、异构数据库的字段匹配、记录级精简这4个环节,下面分别介绍。
3.1 预处理
预处理目的是在进行记录级精简之前对记录中的空白值、异常值和不一致值进行处理,这些脏数据可能会对求取相似度和匹配的运算造成负面影响。由于这些处理主要是针对各个记录中的具体属性值的,所以也称为属性级精简以区别于记录级精简。
3.1.1 空白值的处理
在数据输入的时候,可能由于漏输入的原因导致有的字段属性值为空。这些空值必须被填充才参与后续的匹配度计算。所以我们可以采用最接近空白值的值来替代空白值,本文采用聚类法的方式对空白值求取近似值。
①首先对原始数据集进行数据筛选:剔除具有较多缺失数据的属性,因为这样的属性作为后续的匹配依据是不合适的。并且将有较多缺失值的记录提交给用户,让用户手工对这些数据进行处理,因为具有较多缺失值的记录使用算法处理可能产生较大误差。②将原始数据集分为完整数据集Dc和不完整数据集Di。③对完整数据集使用CANOPY算法进行聚类,产生K个聚类。④计算不完整数据集Di中每条记录和Dc中的K个聚类重心的相似度,将Di中的记录赋予距离该记录最近的那个重心所属的聚类,并且用该聚类的均值或出现频率最高的值来填充该记录的空白值。如果无法填充该记录则对此记录进行删除。
对于数值型数据,空白值取距离最近的那个聚类的平均值,Ai为该空白值最接近的聚类的所有成员,n为该聚类的成员总数。当空白值为离散型数据时,空白值取最接近的聚类的出现频率最高的成员值。
空白值=■Ai n 空白值为数值型数据Ai 空白值为离散型数据,取出现频率最高的Ai
⑤最终将经过填充后的Di′和完整数据集Dc整合为新的完整数据集。
3.1.2 异常值的处理
记录中可能存在姓名在输入的时候的拼写错误,属于异常值。这里用一个包含完全正确的数据的外部文件来作为判别依据。
由于高校管理信息系统中,一般记录都包含有学号,而学号具有唯一性,所以,我们可以将学号作为主键,也就是以学号为依据与外部文件进行对比。①对于在数据库中有的学号,在外部文件中找不到,将记录提交给用户判断处理。②对于字段的键值间对应关系和外部文件中的对应关系有出入的,采用领域权值的方式计算数据表记录与外部文件记录的相似度。如果相似度大于等于阈值则认定数据库记录和外部文件记录是同一个实体,用外部文件记录替代数据库记录。如果低于阈值,则提交用户判断处理,判断是否应该采用外部文件的属性值进行替换或者保留原值。领域相似度用编辑距离算法得出。
3.1.3 不一致值的处理
不一致数据是指由于系统和应用的不同在数据类型、格式、粒度和编码方式上的不同。本文中这部分工作由一个标准化字符集转换完成,将各个异构库中的属性值转换为标准的字符集,以便于后续的相似属性、相似字段的比较。例如有的异构数据库中的“男”“女”用“M”“F”表示,有的用“man”“woman”表示,我们可以通过标准化信息标准将这些代码转换为“1”“0”表示。这样做的好处是方便后续的字段相似度比较和记录相似度的比较。另外,如果万一后期各个异构数据库中对这些字段属性值有新的表达方式,也可以通过这个映射表变更映射关系很容易地实现键值定义的转换。
3.2 表内数据精简
由于在各个异构数据库的内部可能存在有大量的重复实体记录,这些实体记录在后续的表间记录匹配合并的工作中可能带来困难。所以需要对各个异构数据库各自的数据进一步的精简以去冗余。
把整个数据记录看成文本,采用倒排检索方法,粗糙、快速地把数据分成一些重叠的子集,称为Canopy。然后是一个更严格的阶段,这个阶段对Canopy内的点用精确的计算方法进行再次聚类。
最后,按照一定规则对相似记录进行剔除或保留。
3.3 异构数据库的字段匹配
在经过前面的表内数据精简后,各个异构数据库中的数据已经具备了可以进行相似度运算的条件,接下来的工作是用SOM(Self-organizing feature Map,自组织特征映射)-BP(Back Propagation,前馈)网络对各个异构数据库中的字段建立匹配关系。 如图3所示,SOM-BP网络的作用主要是对异构数据库数据表中的相似字段进行匹配,提供给共享池,作为共享池字段。这个过程的步骤包括:
①从异构数据库中抽取属性的特征向量,包括数据模式和数据内容统计。特征向量就是如属性值的数据类型、长度、是否为空、精度、小数位数、标准差这些参数。这些特征向量将作为SOM-BP网络运算匹配度的参数。②将特征向量归一化。③建立SOM网络模型,将属性特征向量进行分类,分为M类。④建立BP属性匹配模型,用样本数据库对SOM分类后的每一类别(共M个类别)进行训练直至收敛,保存BP网络权值和阈值,建立M个BP网络模型。⑤同样,目标库数据通过①②③步骤完成输入向量分类,分为M类,将分M类后的数据对应M个BP网络进行模拟,完成相似度匹配。⑥将完成匹配的数据库属性按照匹配的结果在共享数据库中添加“表名”“库名”字段,使匹配工作中被识别为同一属性的异构属性能够实现快速对应。⑦将上述完成匹配的字段匹配情况作为后续求记录相似度的特征字段选择依据。
从表1我们看到,当各异构库中的字段被SOM-BP网络发现相似的时候,这个匹配结果将提交给人工,由人工选择保留哪个数据源作为共享池中的字段,当字段没被发现匹配对象,即这个字段为唯一字段时,将此字段作为共享池中的字段。
3.4 记录级精简
在上一步确定在共享池中需要保留的字段之后,接下来是将各个异构库中存在的相同实体记录进行精简,保留唯一实体记录存入共享池,使得共享池中的记录都属于完全不同的实体。
3.4.1 字段选择
字段选择的目的是作为进行相似度比较的记录的标识,一个记录可能包含有许多相似属性,我们不能全部作为比较的内容,必须对其进行选择。考虑特征字段,应考虑进行比较的两个异构数据库中都有的语义相同的字段,如字段“ID”和“XH”都指的是学号,还要考虑到字段的“重要性”,在记录与记录之间区别越大的字段属性值越能够更好的标识一个记录。例如,“学号”字段比“性别”字段能更好的标识记录,因为相对于比较“性别”字段,“学号”字段的取值更能够唯一地标识一个记录。综上所述特征字段选择的依据包括:
①SOM-BP匹配的结果。我们要对异构数据库记录进行比较首先要找到在两个数据库中都存在的能够比较的属性值,前期SOM-BP网络已经得出异构数据库间的字段匹配结果,例如XH和ID都指的是“学号”这一属性。所以教务处表中的XH和学工处表中的ID这一对就可以选为教务处表—学工处表要进行记录匹配的特征字段。②字段排序的结果:对字段属性的值域进行统计,值域越大的字段,说明其属性值越多,更具有区分性。从属性值值域由高到低对字段进行排序的结果:选择前k个属性组成属性集。后续的相似度计算就针对这k个字段进行。
3.4.2 粗聚类
粗聚类是将字段聚类形成Canopy簇,图4中V1m表示A属性值粗聚类后的聚类集合,V2m表示A’属性簇聚类后形成的聚类集合。
第一阶段粗聚类,对于案例中的数据库D1和D2而言,首先抽取若干特征字段来表征不同的记录,建立表L1和L2,并定义相似距离阈值H1>=H2。将L1和L2融合成为一个整体的表L,接下来借用信息检索中倒排检索方法,采用基于TF-IDF 相似度的计算方法来计算记录与记录之间的相似度,选取与相似距离小于等于H1的(d,d’)放到一个Canopy中,之后从中心点列表中删除已经使用过的中心点d和与d点相似距离小于H2的点d’……如此反复,直到中心点列表为空集,停止操作。最后得到的是诸多围绕各个中心点d的d’的集合(Canopyi)。这样的粗聚类对大数据集特别有效,减少了全表逐个比较对内存的大占用,提高了系统运行的效率。
3.4.3 精确聚类
使用精确聚类提取匹配记录。就是对第一步粗聚类形成的每一个Canopy中的所有记录用编辑距离算法计算相似度。假设Canopyi中一共有n(n>=2)个点,di和dj为Canopyi中的任意两点,将每一点作为一类,在每一个Canopy中求这任意两类gi和gj间的最小距离,取最小值,当每一个Canopy中的类的个数大于1且类间的最小距离小于k时,标记满足最小距离小于k的两个类(gi,gj)作为匹配结果输出,并从Canopyi中剔除掉已经建立匹配关系的(gi,gj),接下来再计算Canopyi中其余的类间距离,判断是否小于k,一直到Canopyi中的类个数小于等于1或者类间最小距离大于k为止,此时跳出循环并返回最终的匹配对。
3.4.4 匹配结果注入共享池
找到匹配对之后的操作就是将同属同一实体的数据注入共享池。例如在教务处数据库中学号N101121011下有该生各学年的成绩,但是没有该生的籍贯、违纪情况的信息,这些信息分别存放在学生处、后勤处的数据库中,那么在经过上述的聚类算法匹配后,学生处、后勤处的数据被辨识到属于该生,接下来的操作就是将这些属性值合并到同一条目中,并存放在共享池中。
4 实验环节
本文所有的程序均用JAVA语言编写,并在CPU为INTEL Core i5,主频为2.5GHz,内存为8GB的机器上运行,所用的操作系统为Windows 7,数据结构采用链表存储复制记录。数据表存放于SQL Server中。
实验比较的对象是传统的排序—删除算法的代表SNM算法和Canopy聚类算法在多表精简中的应用,实验数据共有5000 条记录,对比的两个表分别来自教务处和学生处。5000条记录有1000条重复记录。教务处数据表中的特征字段为ID(学号)、NAME(姓名)、NMPY(姓名拼音)、ADDRESS(地址),对应的学生处中的特征字段为XH(学号)、XM(姓名)、XMPY(姓名拼音)、ADD(地址)。
那么考察的指标就是对两种方法与是否叠加预处理的组合对教务处和学生处两个表重复记录识别的召回率和查准率,取10组数据,重复10次试验后求平均值得出召回率和查准率。借此判断哪种方法在召回率和查准率上的表现更优秀。
从表2可以看出,经过预处理的复制记录检测方法的准确率要高于未经过预处理的复制记录检测方法,在本实验中,经过预处理的Canopy聚类的复制记录检测方法的查准率高于经过预处理的排序邻居方法,且Canopy方法具有更高的召回率,表明它能得到更多的复制记录,算法效率更高。
5 结 语
本文提出了基于共享池的高校信息集成环境下的共享池精简范式。通过预处理提高记录匹配的准确性,通过Canopy聚类算法作为数据库记录求取相似匹配的基础算法。该算法不局限于特定应用领域具有较好的普遍适应性,且比较传统的排序—比较法,聚类法的运算量较小,召回率和准确率较高。经过实验,本框架达到了预定的设计要求。
在高校信息系统中,不仅存在着数据库的重复记录类型的冗余数据,还有不同部门/相同部门的信息系统中的重复文件,以及在数据备份的过程中由于全局备份产生的大量冗余数据,这部分重复数据的识别与精简,被称为文件级的精简,这将是下一阶段研究的课题。
主要参考文献
[1]戴东波,汤春蕾,熊簧.基于整体和局部相似性的序列聚类算法[J].软件学报,2010,21(4):702-717.
[2]张枢.基于数据仓库的数据清洗算法研究[J].煤炭技术, 2010, 29(7): 192-194.