聚类分析是数据挖掘的一项重要功能,是对数据进行合理归类的一种重要手段。聚类是根据数据的某些属性,按照某种相似度量将其划分为若干类,使得类内数据对象的相似性尽量大,类间数据对象的相似性尽量小,目的是寻找隐藏在数据中的信息。近年来,聚类分析已经成为数据挖掘领域中十分活跃的研究课题。由于聚类是与应用紧密联系的技术,因此基于不同的应用目的,研究者们运用不同的模型定义聚类问题。对同一模型描述的聚类问题,可以用不同的方法对其求解,因此产生了一系列聚类算法。在实际应用中,这些算法经常受到初始解敏感、参数约束等问题的影响而无法保障聚类结果的质量。本文以提高聚类质量为目的,尝试着从描述聚类问题的模型及其求解方法的角度出发,分析影响聚类算法质量的原因。通过引入新的方法和技术来设计能克服这些影响因素的新的聚类算法,达到提高聚类质量的目的。本文的研究具有一定的理论意义和实际应用价值。
本文尝试用如下几种方法提高聚类质量：
（1）以空间平滑技术降低局部极小值对启发式聚类算法的影响,提高其聚类质量。对以组合优化模型描述的聚类问题,采用启发式搜索策略求解该模型,产生了启发式聚类算法。启发式聚类算法具有收敛速度快等优点,但是初始解敏感和“早熟”等问题使得启发式聚类算法无法保证聚类质量。通过对启发式聚类算法的求解方式进行分析后发现,影响启发式聚类算法质量的原因是分布在搜索空间中的局部极小值“陷阱”。为了降低搜索空间中局部极小值对启发式聚类算法的影响,我们在启发式聚类算法的设计中引入了多空间策略。在保持解结构不变的前提下,给出了3种平滑算子以完成“填平”搜索空间中局部极小值“陷阱”的任务。由平滑算子重构后的搜索空间中包含的局部极小值个数越少,该搜索空间就越平滑。为了控制搜索空间的平滑程度,我们引入了平滑因子参数来控制平滑算子。以不同的平滑因子调用平滑算子,将产生一系列平滑程度不同的重构搜索空间。在任意搜索空间中,当前层搜索空间中的搜索总是以前一层搜索空间的聚类结果为基础来完成的。多空间平滑技术减少了搜索空间中的局部极小值的个数,降低了启发式聚类算法受其影响的程度,增大了获得高质量聚类结果的概率。由于算法需要多次重构搜索空间,因此该算法的时间消耗较大。
（2）以近似骨架捕获数据集的共有信息,并利用共有信息设计启发式聚类算法提高聚类质量。启发式聚类算法采用局部搜索策略求解以组合优化模型描述的聚类问题,获得使得目标函数取局部极小值的局部最优聚类结果。为了提高启发式聚类算法的质量,研究者们要么以随机重启技术多次执行聚类算法并保留最好的聚类结果,要么从多个局部最优聚类结果中发现最一致的聚类结果。前一种方法虽然可以获得较好的聚类结果,却忽略了多个局部最优聚类结果之间的关系,而后者从多个局部最优聚类结果中发现最一致信息,却割裂了已有聚类结果与原始数据集之间的联系。局部最优聚类结果是启发式聚类算法的收敛结果,反映了数据集的侧面特征。多个局部最优聚类结果之间共有信息反映了数据集的共同特征,因此共有信息对捕获数据集的真实聚类结果有着重要的意义。本文引入近似骨架来捕获多个局部最优聚类结果中的共有信息,并利用近似骨架设计启发式聚类算法,主要完成：①定义了启发式聚类算法的骨架和近似骨架；②研究了影响近似骨架质量的因素,并给出发现近似骨架的快速算法；③在近似骨架的基础上给出了BK-means:基于骨架初始解的聚类算法和近似骨架导向的规约聚类算法。由于算法需要预先产生多个局部最优聚类结果,因此时间消耗较大。
（3）在核密度估计和空间统计理论的基础上,设计局部显著单元结构捕获空间数据分布以提高子空间聚类算法的质量。对以空间密度估计模型描述的高维子空间聚类问题,等宽或随机宽度的超方体结构是用来捕获空间密度分布的重要结构。核密度估计是空间密度估计的重要方法,但是能反映数据分布的核宽度却很难获得。大部分子空间聚类算法先用等宽或随机宽度来限制核宽度,然后用超方体结构的密度来模拟核密度估计值。等宽或随机宽度的限制虽然解决了核宽度确定问题,但是不能反映空间中数据的真实分布,从而导致以等宽或随机宽度为基础的子空间聚类算法无法保证聚类质量。本文在局部核密度估计方法Rodeo和空间统计理论的基础上,给出了一种局部显著单元（Local Significant Unit, LSU）结构来捕获局部数据分布。局部显著单元是一个由密集超方体及其对应的属性子集所组成的二元组,其中属性子集和超方体的宽度由局部核密度方法Rodeo确定,而超方体的密集程度则由空间统计测试完成。以贪心策略为基础的算法GALSU （Greedy Algorithm for LSU）快速地发现能覆盖数据分布的局部显著单元。对具有相同属性子集的局部显著单元二元组,执行Single-linkage算法合并密集超方体并形成聚类结果。
