第一章绪论
自进入二十一世纪以来，随着数据获取能力的不断提高和计算机的飞速发展，人们获得的数据信息越来越多，如何寻找这些海量数据信息中潜在的规律，更好地为人类服务，是目前机器学习面临的挑战之一.机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科.机器学习是专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能.机器学习应用十分广泛，如数据挖掘、信息检索、计算机视觉、生物特征识别、DNA序列检测、机器人等学科.聚类作为机器学习的一个重要分支，得到了来自统计学、计算机学科等领域的研究者广泛关注.在过去的几十年里，人们尝试从不同的角度来描述聚类问题，并提出了许多基于不同理论和适用于不同应用的聚类算法.相比提供标签信息的监督聚类，无监督聚类就是在无监督的条件下，将现有的无标签数据进行归类的数据分析过程，其目标就是要挖掘出数据的内在结构.本章内容分为六节.在第1.1节，回顾课题研究背景和意义.在第1.2节，综述了无监督聚类研究现状.第1.3节给出了维数约简的研究现状.第1.4节介绍了聚类中一些相关问题.第1.5节阐述了本论文的研究内容、研究方法与创新点.第1.6节给出了论文的主体结构和内容安排.
1.1课题研究背景及意义
聚类就是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程.由聚类所生成的同类别数据彼此相似，而不同类别之间相异.随着信息科学技术的发展，收集和存储无标签数据样本已相当容易，而获取有标签数据的样本却相当困难.由于标签信息不仅需要专家知识，耗费大量人力物力，而且人为标记难免出现错误.无监督聚类就是在无监督的前提下，对收集到的数据进行归类分析，挖掘数据的内在结构进而获取有用的信息，是当前机器学习的一个难点、也是热点之一.利用聚类方法，把数据划分为不同的类别是非常有用的.由于聚类会将数据分解为几个不同的子集，这些子集比整体数据集具有更显著的同一性，有助于分析和理解数据.在商业活动中，决策人员可以利用聚类算法将消费者划分为不同的群体，从而了解不同群体消费者的心理，以帮助商家做出目标明确的营销策略.在客户关系管理中，聚类模型会将属性相似的公司客户分配到相同的组，为公司提供其客户的自然分组.对这样的分组，公司可做出进一步的决策，如对不同组的客户提供特别的服务和产品等.聚类还可以识别离群点，即那些不同于其他客户的客户，这可能意味着新的市场商机，公司可进一步开发.在文档聚类中，新闻报道可以进一步划分为政治、体育、时尚、艺术等子组.在生物学上，聚类可以对基序(motifs)进行分组，这是蛋白质结构中反复出现的氨基酸序列.基序可能对应于它们所表征的序列内部的结构或功能要素.比方说，如果氨基酸是字母，蛋白质是句子，那么基序就像单词，即具有特殊意义、频繁出现在不同句子中的一串字母.在电子商务中，通过对相似浏览行为的客户进行分组聚类，分析同组客户的共同特征，可以更好地了解自己的客户，进而对网站建设提供方向，给客户提供更合适的服务.
.........
1.2聚类研究现状
聚类既能作为一个单独过程，通过寻找数据样本内在的分布结构，揭示数据样本的内在性质及规律，也可作为分类等其它学习任务的前驱过程，为进一步的数据分析提供基础.一个完整的聚类分析过程主要包括四个阶段[8]：特征选择或特征抽取、设计相似度算法、划分和聚类结果评估.基于不同的设计思想和不同的学习策略，人们设计出不同类型的聚类算法.关于聚类算法的分类和详细描述，可参考[9].划分法也被认为是优化法，其算法的主要思想是首先设定聚类的目标函数，然后通过优化目标函数对数据集合进行划分.K-means算法就是最具代表性的划分法聚类算法.K-means算法的目标就是依据某种给定的距离度量方式，划分数据集，使得所有数据点到其聚类中心的距离之和最小.该算法简单、效率高，时间复杂度与数据样本的大小呈线性关系，具有良好的可扩展性；缺点是算法只能收敛到局部最优解，且对初始中心、噪声样本和独立点敏感.为克服这些缺点，人们提出了多种基于K-means的改进算法.为了能处理分类属性型数据，如性别、家庭住址等属性，K-modes算法[10]采用差异度来代替K-means算法中的距离.K-modes算法中差异度越小，则表示距离越小.一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为1，最后计算1的总和.这个和就是某个样本到某个聚类中心的差异度.该样本属于差异度最小的聚类中心.为解决K-means对初始中心敏感的问题，Bagirov[11]提出一种流形全局K-means算法;雷等[12]提出K-meansSCAN通过构建加权连通图，依据连通图合并子类;Chung等[13]提出一种快速鲁棒的基于对称的K-means算法.Xiong等[14]从数据分布的角度，分析了K-means算法的聚类结果.为了对数值型和属性型混合数据样本进行聚类，Ji等[15]提出一种模糊K-prototype聚类算法.Bachem等[16]于2016年在NIPS上提出K-means改进算法不仅能克服K-means对初始中心的敏感性，而且适用于海量数据聚类.与K-means算法有紧密联系的还有高斯混合模型(Gaussianmixturemodel,GMM)的期望最大化(Expectationmaximization,EM)算法.当GMM的各个分布均为球形分布时，EM算法和K-means算法是等价的[17].
.........
第二章基于矩阵分解的鲁棒无监督特征选择
2.1引言
高维数据普遍存在于研究的各个领域，如图像处理、模式识别和机器学习.数据的高维特性不仅增加了计算的复杂度和算法的存储空间，而且冗余和噪声特征会严重影响算法的性能[139].维数约简方法按照一定规则通过在高维数据中寻找相关低维特征达到降维的目的.维数约简不仅可以节约计算时间，而且能得到更紧凑和易推广的学习模型[79].在本章中，我们提出一种新的无监督特征选择方法，称为基于矩阵分解的鲁棒无监督特征选择算法，该算法明确地保持了数据局部几何结构，在l2,1范数度量下，同时进行鲁棒的判别特征选择和鲁棒的聚类.具体而言，主要通过预测投影数据点的类别中心点而非数据的伪标签来实现特征选择.为此，将目标矩阵分解为两个矩阵：潜在类别中心矩阵和稀疏表示矩阵.此外，潜在类别中心矩阵的正交约束不仅保证其接近真实类别中心，而且能使不同类样本的稀疏表示尽可能相互远离,进而使得特征选择矩阵选择具有判别性的特征.不仅如此，稀疏表示保持原始数据局部结构的同时，流形正则化项保持数据的几何结构.在6个公开数据库上的实验结果表明，与最好的一些特征选择方法相比，我们提出的RUFSM方法在大多数情况下都得到最好的性能.
..........
2.2RUFSM算法目标函数
鲁棒的基于回归的特征选择模型(2.3)已被证明在无监督情况下处理数据噪声或奇异样本点非常有效[80,96].在模型(2.3)中，目标矩阵T对选取判别特征非常重要.现有的许多方法[80,96,102,103]利用伪标签作为目标矩阵T得到非常高的聚类性能.但是，这种目标矩阵T是0-1矩阵，使得优化模型(2.3)是一个NP-难问题[67].具体而言，对长度为1的样本向量xi(i=1,2,···,n)，投影到W之后与0-1向量ti相等是非常困难的.常用的策略是在保持某些性质的前提下，将其松弛到连续值.受矩阵分解在机器学习和数据挖掘[47,97,141,142]中高性能的启发，在模型(2.5)中，三个矩阵需要通过学习得到，即投影数据点WX的聚类中心B、稀疏表示H和列稀疏的投影矩阵W.最小化前两项可处理数据中的噪声和奇异样本，实现鲁棒的特征选择.∥W∥2,1确保投影矩阵W的列具有稀疏性.这样，进行特征选择的时候，我们滤除投影矩阵W零列对应的那些特征.流形正则化项能够保持数据的几何结构.
...........
第三章图正则化低秩因子分解算法.....36
3.1引言....363.2相关工作..........38
3.2.1非负矩阵分解(NMF).........38
3.2.2因子分解(CF).....38
3.2.3局部连续因子分解(LCCF)......39
3.3GLCF目标函数......393.4GLCF多步更新规则....41
3.5GLCF算法收敛性分析..........42
3.6GLCF算法分析......44
3.6.1计算复杂度分析....44
3.6.2与梯度下降法的关系.........44
3.6.3针对负值数据矩阵求解算法.....46
3.7实验结果及分析......48
3.8本章小结..........54
第四章基于子空间聚类的紧凑低秩表示..........56
4.1引言.....56
4.2低秩表示..........57
4.3图正则化紧凑低秩表示GCLRR算法框架........58
4.4图正则化紧凑低秩表示GCLRR算法优化........59
4.5模型分析..........64
4.6实验结果与分析......67
4.7本章小结..........72
五章总结与展望.....79
5.1总结....79
5.2展望及未来工作......80
第四章 基于子空间聚类的紧凑低秩表示
当今社会，许多模式识别与计算机视觉问题需要分析和处理大量的高维数据．然而，高维数据不仅增加了计算复杂度和存储空间，而且由于噪声更会影响算法性能．不仅如此，实际问题中的数据点有可能来自多个子空间的并，而数据点具体来自那一子空间却是未知的．比如，视频中有可能同时包含几个不同的移动物体，为了区分这些不同的目标，就需要求取属于不同物体的不同子空间．子空间聚类就是将来自不同子空间的高维数据分割到各自对应所属的低维子空间．本章在分析现有子空间聚类算法的基础上，提出一种新的子空间聚类方法：图正则化紧凑的低秩表示 (Graph regularized compact low rank representation, G-CLRR). 在 GCLRR 算法中，不仅可以同时进行字典学习和低维低秩表示，而且用于子空间聚类的原始数据的低维表示，利用低秩约束获取全局子空间结构的同时，利用流形正则化保持数据点的局部结构. 此外，为了使得算法对噪声具有鲁棒性，l2,1范数用来度量原始数据与其低秩近似之间的误差. 实验结果表明，与现有最好的几种基于 LRR 算法相比，提出的 GCLRR 算法具有较高的聚类性能.
4.1 引言
基于 LRR 的子空间聚类方法能有效的处理噪声数据，但它们依然有一些不足之处．首先，目前大部分基于 LRR 的子空间聚类方法都选用原始数据作为字典，优化算法涉及到 O(n2) 个变量 [57]，其中 n 为样本个数. 当样本个数 n 增加的时候，算法的复杂度将大幅增加. 此外，原始数据直接被选为字典并不具有表示性，通过学习得到的字典通常能获得更好的性能. 幸运的是，原始数据通常含有噪声能够被进一步紧凑的表示. 其次，大多数子空间聚类算法是通过相互独立的两步完成的，先对给定的原始数据进行学习得到一个相似度矩阵，随后用相应的聚类方法将数据点聚类到相应的子空间. 因此，由于这两步的独立进行，这些方法无法得到全局的优化结果. 2016 年，最新提出的谱聚类引导 LRR (Spectral clustering steeredLRR) [172] 为得到全局优化结果，将 LRR、NCut 和 K-means 三者的目标函数整合到一个目标函数中. 不仅如此，这些方法将低秩和流形正则化约束在相似度矩阵而非低维表示上，用于最终聚类的低维表示并不能很好地获取数据的全局和局部结构.为了解决上述问题，我们提出一种新的基于 LRR 的子空间聚类算法，图正则化紧凑低秩表示 GCLRR. 明确考虑了数据中的全局结构和局部几何信息，在 l2,1范数下同时进行字典学习和低秩表示. 在提出的 GCLRR 模型中，原始数据 X 的线性组合被作为字典 A，即 A = XW，不仅可以保持原始数据的结构，同时可以降低算法的复杂度. 当线性组合系数 W 更新的时候，字典 A 将相应的更新. 用于聚类的低维表示 H 同时获取全局和局部结构，我们将 H 的列向量看成是 Rr中的一个点，利用 K-means 将它们直接聚类到 C 类. 此外，我们验证一些基于 LRR 的算法是我们算法模型的特例. 在不同数据库上的实验结果表明，与最好的一些基于 LRR的算法相比，我们提出的 GCLRR 能得到较好的聚类结果.
..........
总 结
随着信息技术和互联网的飞速发展，各行各业都有大量的高维数据，对这些数据的分析和理解，挖掘数据中潜在的规律是推动社会发展的主要动力之一. 机器学习正是从海量数据中获取规律的重要手段. 面对海量的、无标签、含有噪声的高维数据，人们迫切需要在没有标签信息、剔除噪声样本或奇异样本干扰、且将高维数据样本转化为低维表示的情况下对数据进行分析并挖掘其内在规律. 因此，近年来在机器学习方法中，基于维数约简的鲁棒无监督聚类方法成为一个研究热点，越来越受到研究者的重视并得到快速发展，已经被广泛应用于图像分析、生物信息学、模式识别等重要领域.在第一章中，主要介绍了基于维数约简的无监督聚类背景和研究意义, 对聚类和维数约简的研究现状进行了综述，并概述了本文的主要工作和创新点.在第二章中，以矩阵分解为手段，以回归的鲁棒特征选择方法为基础，提出一种基于矩阵分解的鲁棒特征选择算法 (RUFSM). RUFSM 选用 l2,1范数作为误差度量来消除噪声样本和奇异样本对数据样本本质属性特征的影响，将目标矩阵分解为两个矩阵 (正交类别中心矩阵和低维稀疏表示矩阵) 的乘积使得投影矩阵能更好地选择具有类别辨别性的特征，类别中心的正交性能使异类之间相互远离，而低维表示的稀疏性和流形正则化能同时保持全局结构和局部结构，使得同类低维表示靠近的同时异类互相远离. 算法分析表明，RUFSM 具有一般性. 在 RUFSM 算法中，当正则化参数和部分矩阵特殊取值时，易得一些现有特征选择算法为其特例. 大量实验结果表明本章提出的 RUFSM 算法无论在鲁棒性上还是性能上都超过了相关特征选择算法.
..........
参考文献（略）