论文部分内容阅读
聚类分析是数据挖掘的主要技术之一，在各种领域的用途广泛，用户借助于对数据集的聚类分析来挖掘数据集中数据对象的分类模式。聚类分析挖掘过程和分类不同，是在无导师监督的情况下进行的，用户不具备对于所处理数据集的先验知识，为了得到满足实际需求的聚类结果，用户需对同一个数据集进行参数改变下的重复聚类，其原因在于：(1)由于缺乏先验知识，用户不能给出聚类算法的适当参数，而当前的聚类算法大都对于输入参数敏感，这时需要通过重复聚类寻找其最佳的参数及对应的聚类结果。(2)用户也常常会人为地调整参数，以了解不同参数下的聚类结果，而有些聚类算法对于初始条件敏感，即使输入参数相同，由于初始条件不同，得到的聚类也是不同的，常会陷入局部最优，参数调整后还需要进行重复聚类以得到较好的一个聚类结果。本文针对重复聚类的优化与效率问题进行研究，给出相应的解决方法，所做的主要创新工作如下：
对上述两种需要进行参数改变的重复聚类的情况进行了概括，给出了其形式化定义，定义其为以输入参数作为决策变量、以评价对应聚类结果的基于相对标准的有效性函数为优化函数的非线性规划问题：
min(max)f(C)s.t.Palg∈D其中，Palg为输入参数，约束条件D表示参数的允许取值范围。对于用户人为调整参数的情况，D表示用户指定特定参数值；在参数未知的情况下，D表示参数可能的取值范围；C为Palg对应的最佳聚类结果。
制定了适用于作为重复聚类问题优化函数的有效性索引函数：IECC索引和ComSep索引，这两个索引函数不仅能够对聚类结果的整体情况作出评价，而且还能够对聚类结果中簇的具体分布情况作出评价。IECC索引速度较快，但是主要适用于只包含凸形簇的聚类结果，应用范围较窄。ComSep索引可以评价出包含任意形状簇的聚类结果的性能，应用范围更加广泛，但是计算时间复杂度比IECC高。
给出了参数改变时重复聚类问题的可继承算法和迭代优化方法。由用户调节的参数改变下的重复聚类问题，主要通过对现有聚类结果的继承，避免新聚类结果受到初始条件的影响而陷入局部最优，以较快的速度得到质量较好的新聚类结果。对于用户未知参数的重复聚类问题，本文深入地研究了有效性索引函数各组成项与输入参数之间的关系，利用在最佳参数附近簇内紧密程度关于输入参数曲线曲率最大这一特性，得到最佳参数的近似值，把参数限定到有效性索引函数包含极小值的单谷部分，利用改进的步长加速法求得极值，即最佳的参数和其对应的聚类结果。
本文对不同参数对应聚类结果中簇的可能变化情况进行分析，指出在参数变化时应该引起用户的注意、需要报告出来的聚类结果变化情况，并提出通过比较聚类结果中各个簇几何信息得到。本文采用CF簇表示方法，通过其储存的信息可以快速有效地得到所需要的几何信息，给了检测聚类结果变化的CA检测算法，实验表明该算法能够有效地检测出不同参数下聚类结果中簇分布情况的变化，提供给用户关于不同聚类模型变化的知识，以指导其更好地进行决策。