高维数据聚类算法的研究及应用

发布时间：2017-04-17 15:18

第一章 绪论

现实生活中所产生的数据根据不同的行业有着不同的属性和特点，因此往往在没有任何信息指导的前提下很难进行分析处理。聚类分析(Cluster Analysis, CA)可以对目标数据集的所有数据对象进行聚类并找出具有干扰性的噪声。其在指导基础教育过程中，可以使用分析学生成绩的各种因素，从而分析出主要因素来作出更加高效的教育模式[4]；在城市交通规划上，规划者可以使用有效的聚类分析方法对人群的集中流向进行分析，从而合理地分布城市的公交站点和道路。聚类分析是现今社会中发现数据信息的最为常用且重要的方法之一，主要用于从大量真实的高维数据中获得未知的、潜在的、有价值的知识，它根据数据对象的数学特征或者现实意义等关系，将数据对象进行分类成簇，使得簇内的数据对象具有相同或较高的相似度，而尽可能的降低簇间的对象相似度。传统聚类算法[5]如基于密度和基于划分的算法等在低维数据聚类中获得较好的结果，然而由于高维数据空间的稀疏性和空空间现象的存在[6]，这些方法对高维数据聚类分析的过程时，会导致传统聚类算法失去了聚类分析的意义。
.........

第二章 高维数据聚类分析方法的研究

2.1 经典的基本聚类算法

EM(Exception-Maximization)算法是一种基于模型的聚类方法[31]，该算法主要分为两步，期望步和最大化步。期望步先给定当前的簇中心，将每个数据对象划分到距离簇中心最近的簇，然后最大化步调整每个簇中心，使得该分派的数据对象到新中心的距离之和最小化，直到聚类收敛或改变充分小。该算法对于给定的数据集的每个数据对象所属的每个类簇进行迭代，表现出较好的聚类效果，但 EM 算法可能收敛不到最优的解，可以收敛到局部极大。我们可以在初始时设置不同的随机初始值，运行多次 EM 过程，这个过程计算开销较大，需要消耗较多的时间。如果可以选择较为适合的概率分布函数的话，该算法可以较好地处理不同的多种数据类型的数据集。

2.2 高维数据集的处理方法

PCA 由 20 世纪初的学者 Hotelling 提出[33]，其主要思想为使用一个特殊的，由数据对象决定的坐标系，将第一个坐标设置在数据对象的方差最大的方向上，在二维空间中，第二维的坐标轴方向与第一个坐标轴正交，但是在三维空间中，它在与第一个坐标轴平面上的任意位置，其始终受到第一个坐标轴正交的限制，在更高维度上会有更多的选择。其实现起来也不是很难，首先计算数据对象的协方差矩阵，并进行对角化，然后找到特征向量，，按照特征值进行排列，取出较大的一些轴分量，即主成分，丢弃其余的分量，尽量使得这些分量担负原数据属性的 95%以上，从而实现降维过程。PCA 的实现的流程图如下图 2-1，具体的实现过程将在下面章节详细展开分析。

第三章 基于加权距离计算的自适应粗糙 K 均值算法..........16

3.1 基于带权距离的粗糙 K-means 聚类算法 ...... 16
3.2 基于加权距离计算的自适应粗糙 K-means 聚类算法 ...........18
3.3 聚类效果指标 .................. 20
第四章 基于相似性度量的高维数据聚类分析改进算法.......25
4.1 高维数据的特征分析 ...... 25
4.2 基于相似性度量函数的改进算法 ............... 26
4.3 基于相似性度量的高维数据聚类分析改进算法 ......... 27
第五章 高维数据聚类算法在食品安全检测中的应用..................34
5.1 食品安全检测分析的现状 .......... 34
5.2 本章实验的高维聚类分析方法 ............ 37
5.3 实验与分析 .................. 38

第五章 高维数据聚类算法在食品安全检测中的应用

5.1 食品安全检测分析的现状

特别是，对儿童成长极为重要的奶制品行业，更不能出现任何的问题，因为儿童是一个国家，一个家庭的未来，如果儿童因为奶制品问题上出现严重的伤害，那我们这个国家未来怎么办？这也是为什么国家这么重视奶粉安全问题的原因。为什么不法商家会把三聚氰胺添加到奶粉中呢？一方面他们是为了牟取暴利，另一方面是降低奶粉的制作成本三聚氰胺能够加入到奶粉中是因为其含氮量 66%，价格便宜，形似蛋白粉，添加到奶粉中不易被发现。当前食品检测过程中普遍采用测定氮含量来计算蛋白质的含量，而不是直接测量蛋白质的含量，所以兑了水的牛奶加入三聚氰胺后，使用氮含量测定的方法也会因蛋白质含量达标而通过检测。传统的安全检测方法的流程如下图 5-1 所示。这些方法中大多数需要进行样品前处理，而样品前处理一般耗费时间长、对仪器的要求较高、而且会一定程度上破坏样品质量，因此不能达到及时、无损、快速检测的要求。目前，急需一种能够不破坏样品质量、检测速度较快并能够实时检测的方法来判定奶粉中是否含有三聚氰胺。

5.2 本章实验的高维聚类分析方法

本章使用的分析算法主要有 BP 神经网络算法和 SIMCA 算法，以及本文第四章提出的 PsimCA 算法。首先，介绍一下 BP 神经网络的相关技术内容。前面已经提到BP神经网络是于1986年由Rumelhart等人组成的科学小组提出的，是一种按误差逆传播算法训练的多层前馈网络。BP神经网络模型拓扑结构包括输入层、隐层和输出层。BP利用一种称为激活函数来描述层与层之间的关联，使得模拟各层神经元之间的交互反应。激活函数必须满足处处可导的条件。那么比较常用的输入函数和输出函数分别如公式(5.1)和(5.2)所示。
......

主要结论与展望

随着互联网技术的不断发展以及移动互联网技术的不断进步，人们积累了大量复杂且高维的数据，而如何收集并分析人们产生的这些复杂且高维的数据，从中发现有价值的信息是当前的研究重点。聚类分析作为一种常用的数据分析技术，在现今这个充斥着复杂数据的时代已经广泛受到人们的重视。鉴于现存的一些聚类分析算法在处理高维数据时往往需要高昂的时空开销并且不一定获得较好的效果，本文重点为改进基于加权距离的聚类算法性能使之在高维数据中高效的执行并能够获得较好的聚类性能，从而提出了一些可行的解决方案。因此，本文从对数据约简的角度出发，以划分算法、基于相似度量函数为基础的技术为手段，来对高维数据聚类分析展开深入研究讨论并进行一些实际应用。总结全文所做的工作，主要的工作成果包括以下几个方面：（1）提出了一种基于加权距离计算的自适应粗糙 K 均值算法，该算法主要是针对现存的粗糙划分算法在处理高维数据表现出高耗时和执行聚类分析效果不理想等因素，提出了一种自适应粗糙 K 均值算法，并将该方法与属性约简相结合，利用改进后算法自适应的确定聚类个数以及划分的聚类结果。在 UCI 数据集上的实验表明，改进后的算法在处理高维数据时有着较理想的聚类分析效果。

.....

参考文献（略）

本文编号：313552