半结构化数据频繁模式挖掘相关技术研究

《半结构化数据频繁模式挖掘相关技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类譬TP．⋯⋯密级⋯一公开UDC600@．，姻爨雾荽静缵卷婆j，：≥论文题目：半结构化数据频繁模式挖掘相关技术研究论文作者：杨厚群专业：计算机科学与j支术论文导师：何中市教授答辩日期：2010年5月l4日半结构化数据频繁模式挖掘相关技术研究⑧重庆大学博士学位论文学生姓名：杨厚群指导教师：何中市教授专业：计算机科学与技术学科门类：工学重庆大学计算机学院二O一0年二月ResearchonRelatedTechnologyofFrequentPatternMiningforSemi--structuredData⑧

2、AThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheDegreeofDoctorofEngineeringByYangHouqunSupervisedbyProf．HeZhongshiMajor：ComputerScienceandTechnologyCollegeofComputerScienceofChongqingUniversity,Chongqing，ChinaFeb，2010摘要数据挖掘技术在进

3、步的同时，也遇到了许多挑战，面对非传统的数据，如含有半结构化、非结构化文本和超链接的Web页面集、XML文档、具有序列和三维结构的DNA数据、时间序列测量值的气象数据等，其结构以及数据之间包含的许多复杂联系，而这也正是我们挖掘模式、发现知识的关键所在，舍此别无选择。为了挖掘这些半结构化和非结构化数据，算法就需要考虑数据间的联系，如时间和空间的自相关性、图的连通性、半结构化、非结构化文本中元素之间的联系。树、图和格作为常用的半结构化数据表达方式，通过节点和边表达实体、属性，以及实体之间的联系，因此可借助它们来描述

4、研究对象的关系，便于半结构化数据的处理。本文对半结构化数据频繁模式挖掘的若干技术进行了研究。重点研究了以下几个问题：首先源于以树结构描述XML文档的简洁性，研究树结构数据频繁模式和基于约束的树结构数据频繁模式的挖掘方法；然后针对具有复杂链接关系的XML文档结构数据标记的缺失问题，研究部分标记图结构数据的频繁模式挖掘方法，以及基于支持度弱化约束的图结构数据频繁模式挖掘方法。本文研究内容和创新工作主要包括以下五个方面：①基于子树编码聚类的频繁诱导子树挖掘算法。提出频繁诱导子树挖掘算法XMLMiner，将模式增长方法

5、应用于频繁子树模式挖掘算法中。采用了一种新的基于子树编码聚类的最小一般概化，对树进行关系编码，计算其最小一般概化，找出最大公共子树。算法直接构造频繁子树，无须多次扫描树集，利用编码把对子树挖掘转移到对聚类集合的挖掘；由于避免了树匹配操作，降低了算法时间复杂度。②基于项集表达的频繁嵌入子树挖掘算法。提出频繁嵌入子树挖掘算法EXMLMiner。算法基于频繁子树编码序列增长的方法，先将初始树集作为项集，通过路径交运算，生成带子树特征的频繁项，并在频繁项上挖掘带有频繁特征的子树，然后将频繁子树结构进行压缩，还原成真实子

6、树形式并计算其支持度。算法基于最右路径扩展技术在有序树中发现所有频繁模式，只在树的最右分支上增加新节点生成新树，同时充分利用已生成的频繁模式信息，使得产生的候选模式数量较少。③部分标记频繁子图挖掘算法。提出一种模式增长的部分标记频繁子图挖掘有效算法PLSM。其特点是t建立glDX索引结构，提高访问效率。通过弱化操作，构造部分标记候选模式，通过重庆大学博士学位论文计算支持度找出频繁模式；采用深度优先，最右模式增长的策略，挖掘任务只在部分标记图上进行。④约束条件下树结构数据频繁模式挖掘算法。提出一种基于约束的频繁子

7、树挖掘算法CTreeMiner。基于给出的约束定义，利用约束的简洁性在数据预处理阶段对数据进行修剪，如基于项约束的原则设置权重支持度，根据权重支持度和频繁度检查模式项是否满足约束要求。在挖掘过程中，根据约束集的要求对搜索空间进行修剪，降低匹配测试代价；同时，为了进一步减少生成模式的数量，将需求限制在闭模式的挖掘上。⑤约束条件下图结构数据的频繁模式挖掘。具有较高的支持度但仅包含几个子图的小模式与支持度较低的大模式都可能是有趣的。因此在频繁子图挖掘过程中，利用支持度约束弱化来针对性地生成所需要的子图是一个较好的解决

8、办法。提出一个基于模式弱化支持度约束和基于近似最大频繁独立集度量支持度的部分标记频繁子图挖掘方法，其思想是将支持度约束应用到挖掘的过程中，使得大小不等的子图可以在挖掘结果中匹配较为合适的支持度，满足用户的需求。关键词：数据挖掘，频繁模式，半结构化数据，部分标记子图，约束Ⅱ英文摘要ABSTRACTDatamininghasencounteredmanychallenges．Inorder