【作者】 孙焕良；

【导师】 于戈；

【作者基本信息】 东北大学 ， 计算机软件与理论， 2005， 博士

【摘要】 数据挖掘是在海量的数据中提取隐含的、未知的、潜在有用的知识或信息模式的决策支持方法，是20世纪90年代初针对“数据丰富、知识贫乏”问题应运而生的一种新技术。为了有效地从海量数据中提取信息，数据挖掘算法必须具有良好的可伸缩性，也就是说，数据挖掘算法的运行时间必须是可预计的、可接受的。 在众多方法中，基于空间划分的方法是一种有效处理海量数据的数据挖掘方法，其主要应用于聚类分析算法与孤立点检测算法。然而，现有的基于空间划分的方法却存在如下问题：第一，由于空间划分时产生的单元数与维数呈指数增长，该方法多适用于维数相对较低的数据。第二，在一些基于空间划分的数据挖掘方法中，如基于单元的聚类算法，如果划分粒度越细，则聚类精度越高，但同时粒度越细生成的单元数也越多，造成算法效率下降。如果划分的粒度变粗，则算法精度难以保证。 针对目前基于空间划分的方法存在的问题，本文提出了一种新的基于空间划分的索引结构CD-Tree。为了降低空间复杂度，在保持单元间关系的条件下，CD-Tree只保存了非空单元，使得聚类与孤立点检测过程易于实现。文中给出了CD-Tree详细定义，设计了CD-Tree的构建、节点删除、树合并等相关算法，分析了CD-Tree相关算法的时间复杂度，并与其它存储结构的时间复杂度进行了对比。通过理论分析，对于空间划分问题，CD-Tree结构要优于其它可用于存储划分后单元的结构。 CD-Tree适用于当空间划分产生较多的空单元情况，而空单元的数量与数据的偏斜程度有关，数据偏斜程度越高，则生成的空单元数越多。为了确定CD-Tree的适用条件，需要一个度量来衡量空间划分下的数据偏斜程度。现有的衡量数据偏斜的度量不能用于衡量空间划分下的数据偏斜程度，本文提出了一种新的偏斜度的度量DSF(Data Skew Factor)。DSF相当于划分后空单元所占的比例，可用来估计生成非空单元数目。另外，DSF还可用于优化CD-Tree结构及在数据流聚类中动态调整划分的粒度。 在CD-Tree及DSF基础上，本文研究了基于空间划分的优化聚类算法及相关技术，具体包括：基于空间划分的聚类算法；基于空间划分的数据流聚类算法；基于空间划分的孤立点检测算法。 在基于空间划分的聚类算法方面，分析现有的基于空间划分的聚类方法的特更多还原

【Abstract】 Data mining is a decision support approach that extracts hidden, unknown, potentially useful knowledge and pattern from huge volume of data. It is a new technique that appeared in 1990s for solving the problem of "rich data but poor information". To meet the requirement of discovering knowledge in very massive dataset efficiently, the algorithms of data mining are required to have excellent scalability, i.e. the runtime of algorithm should be predictable and acceptable.The space partitioning-based approach can deal with massive datasets efficiently, and is mainly used to clustering analysis and outlier detection. However, there are some problems in previous works. Firstly, the number of cells will increase exponentially varied with the size of data dimension, so they are generally used to deal with low-dimensional data. Secondly, for some space partitioning-based methods, such as the cell-based clustering algorithm, the finer the partition granularity is, then the higher clustering accuracy is, meanwhile the more cells are generated and the lower the efficiency of algorithm is. On the contrary, if the partition granularity is coarse, then the algorithm’s accuracy should not to be satisfying.To solve the above issues, the thesis proposes a novel index structure named CD-Tree (Cell Dimension Tree for Streams). Without the loss of position relationship among the cells, CD-Tree only stores the non-empty cells to reduce the space complexity, which makes it very convenient to execute the procedures of clustering analysis and outlier detection. In the thesis, a definition of CD-Tree is given, related algorithms, such as tree construction, node deletion and tree merge, are developed, and the time complexity of the algorithms is analyzed and compared with other structures. In theory, for the special issue such as space partitioning, CD-Tree outperforms other structures.CD-Tree is more efficient when there are many empty cells generated under a partitioning. The number of empty cells is relevant to the degree of data skew, and for the more skewed dataset, the more empty cells will be generated. Naturally a measure更多还原