论文部分内容阅读
随着信息技术的发展,各行各业在实际应用中都产生了大量的数据,为了能在这些海量数据中发现对其所属领域有用的信息和知识,作为知识发现的一个重要过程,数据挖掘技术研究得到了广泛的关注。而作为数据挖掘的一种方法,聚类分析技术也自然成为了数据挖掘领域中一个非常活跃的研究课题。聚类分析作为非监督的机器学习算法,将对象集合按照相似度分为多个类别(簇),使得同一类别中的对象间相似度较大,而不同类别中的对象间相似度较小。聚类分析可用于发现数据的内部结构,并通过观察每个聚簇的特点,对某些特定的聚簇做进一步的分析,还可作为其他算法的预处理步骤,使其在生成的聚簇上做进一步的处理。大多数聚类算法仅适用于存储于单关系表中的数据,而在许多实际应用中,结构化数据多存放于关系数据库的多个关系表中,虽然可通过连接或聚合操作将多张关系表合并为一张单表,但这种处理方式不仅会产生高维数据,而且整合后数据点可能会分布在不同维的子空间中,导致位于不同维的数据对象间距离相等,失去距离度量的意义;还很难体现不同表间的联系对聚类造成的影响。多关系数据聚类正是面向该应用需求而产生的。然而关于多关系数据聚类算法的研究在面对对象间存在一对多的联系、表间对应信息不完全使得各目标对象可能由不同阶数的信息描述,多关系数据集中各关系表间的联系存在回路等问题时,尚未给出有效的解决方案。另外一个完整的聚类分析过程在聚类结束后,仍需评价聚类结果的质量,确定结果是否符合数据的内在分布特性,即验证聚类结果的有效性;并且利用合理有效的方法分析解释该结果,以有助于为数据分析人员提供决策支持。因此针对多关系数据聚类算法以及聚类结果评价、解释方法中存在的主要问题,本文展开了以下几个方面的研究工作。(1)针对多关系数据聚类中利用统计方法提取一对多联系对应的信息会忽略数据的原始特征、不同关系表间的联系出现的回路可能导致信息重复利用的问题,研究有效的层次多关系聚类算法。首先引起数据集中存在上述问题是由表间联系的种类不同而引起的,而IDEF1x模型中描述的联系可用于解释其原因,因此基于该模型研究多关系数据聚类的层次框架,然后研究框架中不同种类的联系对聚类结果传递的影响,以及整合多个子节点聚类结果的方法,并提出新的多关系数据聚类算法,以实现最终有效辅助目标对象聚类的目的。(2)针对多关系聚类中目标对象可能由不同阶数信息描述的问题,研究尽量不损失数据信息的多关系聚类算法。仍以基于IDEF1x的关联层次模型作为多关系聚类的基础框架,并将描述信息不完整的目标对象视为不确定数据。首先基于Kripke结构构建多关系不确定数据模型以刻画数据描述信息的完整性;并基于概率约束区域进一步描述其不确定性,然后定义不确定数据间的距离度量方法,最后提出基于概率约束区域的多关系数据聚类算法,使得在不破坏原始数据特征的前提下,保证多关系聚类的有效性。(3)传统的聚类评价方法几乎均根据评价指标的值分析聚类结果的有效性,使其具有一定的局限性。因此着眼于聚类过程,提出有效的聚类结果所对应的聚类过程应满足的状态性质,并基于程序图以及迁移系统对聚类过程进行抽象建模;然后基于模型检测算法将判断聚类结果的有效性问题转换为利用模型检测技术验证描述聚类过程的模型是否满足给定性质的问题,使得该算法不仅能够直接指出聚类结果是否有效,若结果不理想,还能根据反例分析过程指出是由哪次迭代导致的问题。即试图构建聚类分析与模型检测技术间的桥梁。(4)常见的聚类结果解释方法如分析属性值的分布特征、数据的分布情况等,缺少对聚簇间基于各属性差异的定量度量,而这种差异恰能体现属性对聚类结果的影响程度,并可进一步分析属性影响聚簇生成的显著性。因此基于单因素方差分析方法的思想,提出一种聚类结果分析算法,比较各聚簇关于每个属性的簇间差异与簇内差异的,然后基于此定义一种单个属性以及相关属性对聚簇生成影响程度的度量方式,并将该影响程度作为聚簇影响因子。最后,总结论文工作,并提出了进一步的研究重点。