论文部分内容阅读
数据挖掘是当今研究热点,它是从大量的、不完全的、有噪声的实际应用数据中,提取隐含在其中的、事先未知的、但又潜在有用的知识的过程。
随着技术的进步,数据挖掘的对象发生很大变化,已由静态数据集变化为动态数据流,本文研究对象正是这种大规模连续动态环境,其数据通常是GB级甚至是TB级的,数据按照一定的规律不断更新。在这种环境中,已有的知识发现方法面临新的问题,主要体现在以下几点:(1)数据挖掘效率不高。(2)处理能力跟不上。面对大规模数据,囿于原有挖掘模型,很多传统算法根本无法处理。(3)无法满足实时更新的需求。数据是动态的,而且频繁更新,因此挖掘过程需要不断进行,来跟踪数据的变化。而传统算法无法实现快速更新,满足这种实时需求。
针对上述困难,围绕聚类问题,本文采用可继承的观点来处理大规模动态环境的数据聚类分析,不仅采用内存中的增量继承方式,而且把挖掘过程中有价值的知识固化为外存的永久继承,实现知识产生知识,从而提供快速灵活查询。主要工作包括:
(1)提出知识发现中可继承问题,给出其中关键定义:进化基、进化冲量、进化操作、继承度和继承灵活性,并以此为基础,把可继承问题进行分类,给出不同类型可继承的研究方向和重点。分析了传统Fayyad模型、强度挖掘模型和简单增量模型对处理大规模连续动态环境的不适应性,剖析传统挖掘过程中挖掘算法的参数依赖,提出基于中间知识库的可继承聚类模型并给出其中中间知识的定义,界定其可加减性、等价性、浓缩性。
(2)给出聚类中间知识的设计:EDS(ExtendedDataSummary)和ECF(ExtendedClusteringFeature),给出他们的统计学基础,分析其加减性、压缩性和时空代价,说明其合理性和对可继承聚类模型的适用性;给出三种中间知识获取方法:1)基于距离的方法,根据每个单元簇的均方根半径判断新加入的点的归属2)基于网格的方法,采用动态的网格来获取中间知识,针对网格的稀疏特性,使用哈希技术来定位每个项目。3)动态自组织特征影射方法。根据计数器变量并引入累积误差,来决定神经元的增加与删除,从而更好的适应动态环境。
(3)给出外存中中间知识元数据、时间索引、中间知识库、中间知识表的结构定义,采用扩展的BNF语法给出中间知识结构化模式查询语言IKMQL,进行中间知识的管理和查询。在分析时间粒度的基础上,给出三种中间知识保存方法,分别计算其时效误差,分析和证明了每种方法在中间知识保存过程中的存储容量和查询精度。
(4)设计了基于中间知识库的划分聚类方法,给出中心变化时的聚类质量变化公式;在层次算法中,给出相异度矩阵的递推公式,并改进其合并策略以提高效率;在基于密度的算法中,给出同质密度和密度相连的定义,以发现不同密度层次的聚类;在基于模型的算法中,把标准方差插入到密度函数,给出单元簇成员在M步中发生的简化公式。在基于窗口操作的算法中,本文给出窗口相减操作过程。
(5)开发原型系统,验证中间知识获取、存储和维护方法以及本文提出的运行于其上的各类算法的正确性和效率,分别跟采样以及传统算法作对比,证明了本文提出聚类模型对大规模连续动态环境的处理能力;通过对噪声和起伏数据的输入,验证模型的稳定性。通过在不同数据规模和维度上的运行,分析其可伸缩性。