数据特征化技术研究

《数据特征化技术研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分类号学校代码TP311.510487学号2005512100034密级博士学位论文数据特征化技术研究学位申请人：孙翀学科专业：计算机软件与理论指导教师：卢炎生教授答辩日期：2013年5月21日ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinEngineeringResearchonDataCharacterizationPh.D.CandidateMajorSupervisor：SunChong：Comp

2、uterSoftwareandTheory：Prof.LuYanshengHuazhongUniversityofScience&TechnologyWuhan430074,P.R.ChinaMay,2013独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本

3、学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学博士学位论文摘要数据特征化在数据管理领域和数据挖掘领域具有重要的用途。数据特征化旨在保留数据特征的情况下减小原

4、始数据的规模。根据不同的数据类型和应用背景，数据特征化技术主要分为：数值型数值数据特征化，关系型数据特征化和（半）结构化数据特征化三大类。数值型数据特征化主要被数据库（流）管理系统中的查询引擎用于选择度估算或者近似查询处理，其主要包括直方图技术和小波技术；关系型数据特征化主要应用于数据库归档和数据浏览领域（如在手持设备上浏览大型的数据表），其使用基于语义的表汇总技术；现实世界的大量对象被建模成图模型，实际应用中的图模型往往是巨大的(具有成千上万甚至上百万的节点和边)，去理解被编码在这些（巨大的）图中的信息需要使用图汇总技术。这些数据的特征化问题具有

5、相同的共性：其目标是缩减数据规模且尽可能的保留数据原有特征，数据的特征均由给定的函数来度量。如何使得特征化数据的度量函数取得最优值从而提高汇总数据的质量，如何提高数据特征化算法的时间和空间效率以及如何在特定应用背景下调整通用的数据特征化算法是数据特征化问题面临的主要挑战。L2范数误差度量是基于统计分布中任意数据点是等概率被访问的假设，然而，在实际应用中该假设往往不成立。例如：数据库中的数据通常会出现帕累托法则的现象：20%的数据具有80%的访问量。那么构造基于工作负荷的直方图能够使得查询优化模块获得更准确的选择度估算值。另一方面，最优直方图构造算法

6、的时间开销通常为多项式级的。在时间敏感的数据库系统中（例如实时环境下）为了将算法的时间开销降至线性时间，可考虑牺牲直方图的估算质量来换取算法时间效率上的提高，这样的直方图称作近似直方图。现有的小波概要构造算法均只关注如何确定被保留小波系数却忽略如何有效地处理被抛弃（未被保留的）小波系数（只是简单将未被选择的小波系数当作0来处理）。经过分析与证明发现：合理地处理被抛弃的小波系数对改进近似数据集质量I华中科技大学博士学位论文和提高估算精度起着同样重要的作用。针对L2范数误差度量和MinMax绝对值度量的小波概要的被抛弃小波系数缺省值计算方法需要被研究。

7、现有的表语义汇总技术将表的语义汇总作为K匿名进行处理，这样的解决方法会导致语义汇总表的质量下降，且存在转换开销大、算法框架复杂和不易扩展到高维属性等缺点。通过将表语义汇总建模成多维层次空间聚类问题进行求解能有效克服上述缺点。将原始图中节点分配到多个分组并根据原始边来确立分组间关系，这样得到的图称作汇总图。汇总图的规模可以由用户设定，用户可以通过浏览小规模的汇总图来获得原始图的相关信息。然而，现有算法存在汇总图规模设定受限问题。为了解决该问题，可引入节点的属性值概念分层来增加图汇总过程中节点分组的灵活性：不仅可以合并同值的节点还可合并具有相似值的节点

8、。除了关注汇总过程中边的信息损失外，节点的语义信息损失也需要被关注。改进的方法将图汇总问题建模成多目标规划问题，并通过分层