论文部分内容阅读
聚类分析作为数据挖掘的一个重要研究领域，可以有效地帮助分析数据的分布、了解数据的特征、确定所感兴趣的数据类，寻找隐藏在数据中的结构，以便作迸一步分析和利用。一个好的聚类算法能够将一系列对象按照其内在特性分为不同的组，使得组内的对象相似程度高，而组间的对象相似程度低。 近邻传播算法（Affinity Propagation，AP）是近年来提出的一种新型聚类分析算法，相较与传统的聚类算法，AP算法能够在较短时间内完成大规模、多类别的数据集的聚类，且该算法能够很好的解决非欧空间问题。因此，自AP算法提出以来便受到了广泛的关注及应用。尽管如此，AP算法仍然存在一些应用上的局限性:1）AP算法作为一个基于距离的划分算法，只适合处理球形、凸状类簇结构的聚类问题，当数据集的结构复杂，呈现出非球形、非凸类簇结构时，该算法不能给出理想的聚类结果;2）AP算法只适合处理连续或离散类型数据集的聚类问题，在遇到混合类型的数据集时，不能直接用该算法求解;3）AP算法无法接受用户指定的聚类数目作为输入参数进行聚类。本文针对上述问题展开专门研究。 本文的主要研究成果如下: (1)为了使得AP算法能够处理复杂结构的类簇聚类问题，提出了一种数据空间内数据点密度分布的计算方法，并将其应用于数据间的相似度度量准则，生成一种基于数据点局部密度信息的相似度矩阵用于AP算法聚类。该算法受基于密度的聚类方法的启发，通过测量数据集中每个对象的局部密度，生成若干相互重叠的密度域;然后采用一定准则，将各个小型密度子域合并为较大的密度主域，从而生成数据空间中连续分布的、互相独立的密度区域。基于处于相同密度域中的点之间具有更高相似性的原则，提出了一种新的相似度矩阵生成算法，同时自动生成AP算法的偏向参数，达到可自动产生合适的聚类数的目的。实验结果表明了所提算法有效的解决了非凸形数据集的聚类问题。 (2)客观世界中的数据并不像实验室中的一样，仅仅包含连续的数值型或离散的分类型数据，通常情况下，数据集中会同时存在不同类型的数据。针对AP算法还不能够处理混合类型数据聚类的问题，采用了一种基于概率的分类属性值之间距离的度量方法，并将其应用于AP聚类的相似度矩阵生成算法中。同时提出了一种连续数值类型数据的AP离散化方法，使得离散后的数值数据能够利用上述距离度量方法，为该数值属性自动分配合适的目标函数权重。实验的结果表明所提算法在处理混合类型数据聚类问题上有较好的效果。 (3)聚类问题本质上作为一个最优化问题，理论上是可以使用近年来流行的群智能优化算法来求解的。本文提出了一种新型的组搜索优化(Group Search Optimizer,GSO)算法——快速全局组搜索优化算法(Fast Global Group Search Optimizer, FGGSO)，该算法对原GSO算法各个步骤的更新策略进行了改进，采用了竞选策略、破坏——重建策略、加速与跳跃策略，使得所提算法从全局和局部搜索能力上都对原算法有了较大改进，并且缩短了算法运行时间。同时，基于该改进的组搜索算法，提出了一种基于AP算法的改进组搜索优化聚类算法。针对AP算法不能设定输出类数的不足，通过将其与FGGSO算法结合，先使用AP算法得到候选类中心点，再利用FGGSO优化聚类结果，得到确定类数的聚类。实验结果表明所提算法能够获得预期的聚类效果。 (4)环境保护已经成为中国面临的重大问题之一，为了研究全国不同区域的城市空气质量分布状况，本文采用AP算法对全国主要城市进行聚类分析，发现大气污染具有区域相关性。同时提出了一种按预先指定的类数输出聚类结果的AP算法，并将其应用于研究不同区域划分精度的条件下的全国空气质量状况的分布。通过对相同区域内不同城市间同类污染物项目所占比例的比较以及不同区域间的污染物项目的比较，得出该区域划分的有效性，为今后的分区域、差异性环境污染治理的决策提供指导和帮助。 本文分别从三个角度为AP聚类算法提供了新的改进，使其能够处理更多不同种类的复杂聚类问题，并从实际应用的角度出发，验证了算法的实用性。有助于AP算法在更广范围内的研究与应用，具有重要的理论与实际意义。