【作者】 李巍；

【导师】 李雄飞；

【作者基本信息】 吉林大学 ， 计算机软件与理论， 2013， 博士

【摘要】 随着计算机网络的发展，半结构化数据因其层次性、自述性、动态可变性等特点，被广泛应用。网络上的HTML文档、XML文档、SGML文档、Web数据以及由异构数据集成而产生的数据等都是半结构化数据。半结构化数据编码方式与结构化数据（如关系型数据库中的数据、Excel数据等）不同。面对海量的半结构化数据，传统的数据挖掘算法不能够很好地利用其自述性、动态可变性和层次性等特点。传统的结构化数据处理技术并不适用于半结构化数据，所以，有必要研究挖掘半结构化数据的新方法。本文根据半结构化数据的特点，以XML文档和树形数据结构为例，主要研究半结构化频繁模式、动态频繁模式、聚类、动态数据集聚类和民族织物模型等领域，并提出解决半结构化数据挖掘若干问题的方法。为了有效的挖掘树形结构数据集频繁模式，本文首先提出压缩链结构，压缩链可映射为无序标签树，之后提出基于压缩链的压缩树模型，压缩树节点标签是一压缩链结构，因此可对压缩树进行压缩而不丢失原树信息。进一步，提出一种带有数据集压缩的频繁闭合诱导子树挖掘方法CITMinerC。CITMinerC算法基于模式增长策略，首先对原始数据集进行压缩树建模并进行剪边预处理，然后反复迭代数据集将最大频繁度的边压缩为单压缩节点并将边信息保存在压缩节点的压缩链中，最后对压缩链进行闭合化，得到原始数据集的频繁闭合诱导子树集。CITMinerC优点在于随最小频繁度阈值降低计算量成线性增长。实验表明，在人工数据集及真实数据集上进行频繁子树挖掘，CITMinerC算法均优于DryadeParent算法。XML数据在实际使用过程中不断发生改变，针对XML数据动态可变的特点，提出一种根据XML数据变化过程挖掘XML空间频繁变化结构SFCS（Spatial FrequentlyChanging Structure）的方法，首先提出XML子结构空间度量方法，通过结构空间变化度SSCD、版本空间变化度VSCD和空间变化程度SCD三个度量值衡量XML子结构的空间变化频繁性并提出SFCS定义。进一步，提出一种用于保存XML空间变化信息和发现SFCS的数据模型SC-DOM，论证了XML编辑操作对子结构空间的影响并据此提出SC-DOM状态动态迁移方式，最后提出根据SC-DOM发现SFCS的算法并讨论算法复杂度。实验结果表明SFCS是频繁的，使用SC-DOM模型进行SFCS挖掘是有效且可扩展的。以XML为代表的半结构化数据的处理与管理是比较热门的研究课题。目前关于XML文档数据集聚类的方法大多忽略XML层数特性，认为不同层数操作是等费用的。本文提出一种层数敏感的XML文档数据集聚类方法CXLI。首先提出结构表概念，消除XML文档的重复和嵌套结构。然后提出考虑层数信息的XML文档基本编辑操作约束。进一步给出考虑层数信息的XML文档间相似性度量方法。最后使用凝聚型层次聚类方法对XML文档数据集进行聚类。实验在ACM SIGMOD数据集和人工生成的数据集上进行，实验结果表明，在基本相同的时间消耗情况下，CXLI方法具有更好的精确度。在实际应用中，XML文档中的一些结构经常被改变。为了挖掘XML文档在历史变化过程中经常改变的结构所蕴含的知识，本文首先提出了发现频繁变化结构的方法，然后使用一组频繁变化结构组成的文档向量模型代表一个XML文档，将频繁变化结构在簇中的出现比例作为权值，使用加权余弦相似度对XML文档进行聚类。经过实验分析，根据XML文档历史变化过程中的频繁变化结构能够较好的将XML文档进行聚类。使用加权余弦相似度对XML文档进行聚类，聚类结果的正确率、召回率和簇内部距离均优于使用非加权余弦相似度对XML文档进行聚类得到的结果。所以使用加权余弦相似度对XML文档进行聚类是有效的。少数民族民间织物图案蕴含大量民族文化信息。目前，民族织物图案使用位图格式存储，进行精确的数据挖掘存在较大难度。本文首先讨论民族织物图案形状特点，提出带有文化信息的矢量图基因模型。进一步，讨论民族织物图案基因组成的构图模式，提出一种基于半结构化数据的民族织物图案模型，该模型描述民族织物图案的外形信息、文化信息和基因间关系信息。经实验证明，本文模型能够正确完备的描述以哈萨克族、柯尔克孜族、蒙古族和维吾尔族为例民族织物图案，并具备数据挖掘能力。更多还原

【Abstract】 With the development of computer networks, semi-structured data are widelyused as its hierarchy, readme, dynamic variability characteristics. The HTMLdocuments, XML documents, SGML documents, Web data, and the data generated bythe integration of heterogeneous data are semi-structured data.The encoding method of semistructured data is different from structured data(such as data in relational databases, Excel data, etc.). Faced with a flood ofsemi-structured data, traditional data mining algorithms can not be a good use forsemi-structured data due to its readme dynamic variability and hierarchicalcharacteristics. Traditional structured data processing technology is not applicable tosemi-structured data, therefore, necessary to study new methods for miningsemi-structured data.This paper demonstrated all the algorithms with XML and tree data. Accordingto the feature of semi-structured data, this paper research the frequent pattern,dynamic frequent pattern, clustering, dynamic XML clustering and national fabricpattern, and proposed some solution for semi-structured data mining.With the widely use of semi-structured data, frequent tree pattern mining becomea research hotspot. This paper proposed a compression list structure that can representan unordered labeled tree, and then proposed a compression tree model which basedon compression list, the label of each node of compression tree is a compression list,so compression tree can be compressed and lost no information. what is more, thispaper proposed a closed induced frequent subtree mining method with datasetcompression that named CITMinerC. CITMinerC algorithm belongs to pattern-growthstrategy. CITMinerC run cut-edge reprocess first, and then iterate the dataset tocompress a edge to a compressed node and save the information of edge to thecompression list of compressed node, and finally CITMinerC obtain the frequentsubtree set by using closure of compression lists. The advantage of CITMinerC is thatthe computation costs grow linearly with the frequent threshold decrease. Experimentresults show that the CITMinerC algorithm is better than DryadeParent algorithmwhether using artificial dataset or real dataset. In practice, XML data changes itself frequently, according to the dynamiccharacteristic of XML, this paper proposed a method to mining SFCS (SpatialFrequently Changing Structure) from historical structural changing process of XMLdata, first, we proposed a method to measure the space of XML substructure, wemeasured the spatial changing frequency by using structural spatial changing degree(SSCD), version spatial changing degree (VSCD) and spatial changing degree (SCD),and we proposed the definition of SFCS. Further, we proposed a data model calledSC-DOM which used to store XML change information and discover SFCS, and wedemonstrated the effect of editing operations to space of substructures of XML anddefined the maintenance method of SC-DOM, finally, we proposed the algorithm tomining SFCS base on SC-DOM and discuss the complexity of the algorithm.Experimental results show that the SFCS is a frequent, as well as mining SFCS basedon the SC-DOM is effective and scalable.Processing and managerment of semi-structured data is a hot research topic.However, Previous similarity detecting methods on XML ignored the characteristicsof XML layer layer, that layer does not affect the similarity of XML data. This paperproposes a layer-sensitive XML documents collection clustering method CXLI. Wefirst proposed structural tabel to clear up duplication structures, and then proposed theconstraints of editing operations. Finally, we proposed a XML clustering method byusing agglomerative hierarchical clustering method. Experiment executes on ACMSIGMOD data set and synthetic data set, experimental results show that CXLI hasbetter precision under the similar time cost.In practical applications, some structures of an XML document are often changed.In order to mining knowledge hiden in the freduently changing structures in the XMLdocument history changes, this paper propose a method to found the frequentlychanging structures, then uses a document-vector model which composition by a setof frequently changing structures to represent an XML document, to proportion thatfrequently changing structures appearance in the cluster as weight, and cluster XMLdocuments use weighted cosine similarity. After experimental analysis, according tofrequently changing structures which found in the XML document historical changeprocess will be better able to cluster XML documents. Cluster XML document usingthe weighted cosine similarity, the precision rate, recall rate and cluster internaldistance of cluster result are all better than the result obtained by use non-weightedcosine similarity. so using weighted cosine similarity to clustering XML documents is valid.The fabric pattern of Chinese national minority contains a large number ofnational cultures. Currently, most all the fabric patterns using a bitmap format to store,and accurate data mining is a big difficulty. This paper first discusses the nationalfabric pattern shape characteristics, proposed the vector gene model with culturalinformation. Further, discuss the composition of the genetic structural mode of thenational fabric pattern, and proposed a national fabric pattern model based onsemi-structured data model, the model describes the relationship between the nationalfabric pattern shape information, cultural information and gene information. Theexperiments show that the proposed model can correctly complete descriptionexample to Kazak, Kirgiz, Mongolian and Uygur fabric patterns, and have the abilityof data mining.更多还原