第一章 绪论
1.1 研究背景和意义
自进入 21 世纪以来，信息时代的发展和进步导致数据呈指数形式增长，尤其在近年，大数据的迅猛发展使得人们可以轻轻松松获得大量的信息，但这些数据包含的信息越来越丰富，使得挖掘有价值信息的工作难度迅速上升，而传统的数据库技术不能达到发现数据中潜在的规律和模式的要求，所以新技术的提出显得尤为迫切。如何对这些复杂的海量数据进行快速有效的处理？如何从大数据中发掘潜在的模式和规律？如何快速找出其中的有用信息？这些都成为人们获取有用信息的关键前提。而作为大数据处理及信息挖掘的重要手段，数据挖掘能够从大量的数据中检测到其中潜在的规律和模式等，所以其研究是必须且必要的。
第三章 基于全局融合的多核概念分解模型求解算法 . . . . . . . . . . . . . . . 19
3.1 基于全局融合的多核概念分解模型 . . . . . . . . . . . . . . . . . . . . . 19
3.2 基于全局融合的多核概念分解模型求解算法 . . . . . . . . . . . . . . . . 19
第四章 基于局部判别分析全局集成的多核概念分解算法 . . . . . . . . . . . . . 29
4.1 基于局部判别分析全局集成的多核概念分解模型 . . . . . . . . . . . . . 29
4.1.1 多核概念分解 . . . . . . . . . . . . 29
4.1.2 局部判别正则化 . . . . . . . . . . . . . 30
第五章 总结与展望 . . . . . . . . . . . . . . . . . . 49
5.1 总结 . . . . . . . . . . . . . . . 49
5.2 展望 . . . . . . . . . . . . . . . . 49
第四章 基于局部判别分析全局集成的多核概念分解算法
4.1 基于局部判别分析全局集成的多核概念分解模型
4.1.1 多核概念分解
..........................
第五章 总结与展望
5.1 总结
非负矩阵分解在聚类分析领域的意义非常重大，概念分解把矩阵分解模型推广到了单个非线性核空间，从而提升了矩阵分解的学习能力和普适性[106]。不同的核函数获得的概念分解结果是不相同的。由于缺少标签信息，实际应用中如何针对特定的任务或数据集设计合适的核函数是非常困难的。针对概念分解在核函数选择方面的困难[96]，本文参考国内外相关工作并取得了以下两个成果：#p#分页标题#e#
提出基于全局融合的多核概念分解算法 (GMKCF)[96]。在概念分解的基础上，通过全局线性加权的方法在无监督的多核学习框架中从多个初始给定的核函数里学习聚类质量更高、稳定性更好的核函数。在没有引入额外超参数的前提下，提出了基于全局融合的多核概念分解模型，一方面借助融合后的高质量核函数提升概念分解质量，另一方面借助概念分解发现数据集上的本征结构并用于指导多核融合参数的学习。推导并设计了可保证收敛的迭代式优化求解算法。多个基准数据集的聚类结果表明，本文所提出的 GMKCF 算法在多个指标上优于常见单核聚类算法以及常见的多核聚类基准方法。
提出基于局部判别分析全局集成的多核概念分解算法 (DMKCF)。为了进一步在多核概念分解的框架中充分考虑多核意义下的局部几何结构，我们进一步提出基于单核局部判别式分析而诱导的全局多核融合的正则化方法，它充分考虑了多核意义下数据的潜在局部几何结构，解决了一致核矩阵迭代过程中因离散邻域发生变化引起的算法的单调收敛性[28]被破坏的问题。且设计了一种有效的迭代策略，利用乘法更新规则获得最优的唯一解，并进行了严格的收敛性和正确性分析。在基准数据集上的实验结果表明，该算法在多个聚类评价指标上优于许多先进的多核算法。
综上，本文围绕概念分解中核函数设计的问题，探索了概念分解中新的核函数生成算法，即基于全局融合的多核概念分解算法和基于局部判别分析全局集成的多核概念分解算法, 并将这两种算法应用于聚类分析中并获得良好的实验效果。
参考文献（略）
1.1 研究背景和意义
自进入 21 世纪以来，信息时代的发展和进步导致数据呈指数形式增长，尤其在近年，大数据的迅猛发展使得人们可以轻轻松松获得大量的信息，但这些数据包含的信息越来越丰富，使得挖掘有价值信息的工作难度迅速上升，而传统的数据库技术不能达到发现数据中潜在的规律和模式的要求，所以新技术的提出显得尤为迫切。如何对这些复杂的海量数据进行快速有效的处理？如何从大数据中发掘潜在的模式和规律？如何快速找出其中的有用信息？这些都成为人们获取有用信息的关键前提。而作为大数据处理及信息挖掘的重要手段，数据挖掘能够从大量的数据中检测到其中潜在的规律和模式等，所以其研究是必须且必要的。
数据挖掘作为一个跨多个学科的计算机科学分支，自上世纪下半叶被提出到现在，经历了各种挑战，同时也有着迅猛的发展。聚类分析作为数据挖掘研究的一项重要方法，在数据挖掘研究中占有重要地位，它的目标是来自不同簇之间样本点的距离应尽可能的大，而来自同一个簇间的样本点的距离应尽可能的小。在很多领域中，聚类分析的理论应用是非常广泛的，比如多个数据对象之间的相似度衡量、潜在结构的发现等。在实际应用中，从电商领域发现用户群体特征[1]，到新媒体领域热点事件挖掘[2]，再到生物医学领域蛋白质网络结构模块的识别[3]，无一不体现聚类分析的重要意义。研究人员经过几十年的研究，现已有上千种不同的聚类算法被提出，但实际的应用场景各种各样，所以没有任何一种算法适用于所有的数据集。因为聚类算法对应聚类结果是很难预测的，但实际的应用场景多种多样的，所以须按照样本数据本身的特点来判断哪种聚类算法更合适，从而获得最好的聚类效果。传统的聚类算法大致分为：基于层次的、基于图论的、基于网格或基于密度的等。
矩阵分解算法是机器学习中的研究热点，作为非线性维数约简方法，目标是把一个高维矩阵分解成两个或多个矩阵乘积的形式。它被广泛应用于获得低维表示，这种方法通过更加紧凑和准确的表示，可以大大提高聚类学习任务的性能。Lee 和 Seung在 1999 年《Nature》上提出了一种新的矩阵分解的思路，该方法为非负矩阵分解，即 Non-negative Matrix Factorization，缩写为 NMF[4]。因 NMF 会使得多维数据更容易被描述，所以 NMF 自提出起已逐渐成为计算机视觉[5]、信号处理[6]等众多领域中很常见且非常受欢迎的一种工具，也被广泛应用在聚类分析中。
.............................
1.2 国内外研究现状
(1) 聚类方法研究现状
数据挖掘是一种能够在大量各种类型的数据里检测到其中潜在规律和模式的方法。其领域中的聚类分析是一种重要的数据分析手段，它可以用来探索数据的固有结构，所以自提出起就是一项应用广泛且发展迅速的技术手段。例如，在电商领域，通过聚类技术能够发现不同的客户群体的潜在特征，能够为不同的客户群体提供更合适的推荐服务[1]；在新媒体领域，通过聚类分析技术对某个时间段内的媒体文本数据进行聚类分析，该时间段内的热点事件可以被发现[2]；在生物学领域，通过对蛋白质网络结构数据进行聚类分析，用于发现蛋白质网络结构模块等[3]。
(1) 聚类方法研究现状
数据挖掘是一种能够在大量各种类型的数据里检测到其中潜在规律和模式的方法。其领域中的聚类分析是一种重要的数据分析手段，它可以用来探索数据的固有结构，所以自提出起就是一项应用广泛且发展迅速的技术手段。例如，在电商领域，通过聚类技术能够发现不同的客户群体的潜在特征，能够为不同的客户群体提供更合适的推荐服务[1]；在新媒体领域，通过聚类分析技术对某个时间段内的媒体文本数据进行聚类分析，该时间段内的热点事件可以被发现[2]；在生物学领域，通过对蛋白质网络结构数据进行聚类分析，用于发现蛋白质网络结构模块等[3]。
聚类算法发展十分迅速，截至现在已有了许多经典聚类算法思路，本文中将这些经典的聚类算法进行分类，可以有下述几种。层次聚类算法，包括自顶向下和自底向上两种思路，分别称作分解层次聚类及聚合层次聚类[9]，例如 DIANA 和 AGNES[10]。划分式聚类算法，需要预先设置好合适的类簇的个数，以及初始的各类簇的中心点位置，通过不断迭代优化使算法收敛达到最优结果，例如经典的 K-means（适用于数值型数据）和 K-modes（可处理分类型数据）[11]。基于密度的聚类算法（如 DBScan[12]）和基于网格的聚类算法（如 STING[13]）在处理时空数据、发现任意形状类簇、检测奇异值效果较好，且这类算法对噪声的敏感程度很低，对于处理大型的高维数据适合采用此类算法，还有两者相结合的聚类算法，如 CLIQUE[14]。基于图论的聚类算法，该算法首先构造最小生成树，在逐步对最小生成树的最长边进行剪枝而构成类簇[15]，从图论中演化而来的谱聚类[16]采用图结构将样本和样本连接起来，每个样本作为一个点，对所有点构成的图进行切分，根据子图内和子图间的权重分配进行聚类。
........................
第二章 基础知识
2.1 聚类分析相关理论
2.1.1 聚类分析的概念
聚类分析在数据挖掘相关研究领域中的重要性十分显著，其目标是把无标签样本划分到各类簇中，使得同一类簇中的样本距离尽量小，而不同簇中的样本距离尽量大[67]。聚类分析非常有助于对数据潜在结构进行挖掘，现已广泛应用于电子商务[1]、文本信息挖掘[2]、生物医学[3]等领域。
聚类问题来源于分类问题，但和分类问题又有很大的区别。分类问题中需要划分的类簇是预知的，而聚类的数据对象是没有标签的，因此我们可以说聚类是一个比分类更加困难的问题[68]。
........................
........................
第二章 基础知识
2.1 聚类分析相关理论
2.1.1 聚类分析的概念
聚类分析在数据挖掘相关研究领域中的重要性十分显著，其目标是把无标签样本划分到各类簇中，使得同一类簇中的样本距离尽量小，而不同簇中的样本距离尽量大[67]。聚类分析非常有助于对数据潜在结构进行挖掘，现已广泛应用于电子商务[1]、文本信息挖掘[2]、生物医学[3]等领域。
聚类问题来源于分类问题，但和分类问题又有很大的区别。分类问题中需要划分的类簇是预知的，而聚类的数据对象是没有标签的，因此我们可以说聚类是一个比分类更加困难的问题[68]。
........................
2.2 非负矩阵分解相关理论
2.2.1 非负矩阵分解研究背景
在计算机很多领域 (比如计算机视觉[5]、信号处理[6]) 的研究中，我们往往可以采集到高维度的特征对样本进行刻画。一般来讲，将高维数据变换为低维数据至少可以带来两方面的好处：(1) 变化后低维数据的存储和计算开销会降低；(2) 数据的内在结构更容易被发现。
研究人员提出许多面向矩阵数据的分解方法可以用于对高维数据进行降维分析，其中包括、线性判别分析 (LDA)[71]、投影寻踪 (PP)[72]、主成分分析 (PCA)[73]、因子分析 (FA)[74]、独立分量分析 (ICA)。这些方法的建模分析目标各有不同，且相关约束条件和求解方法也各不相同，但是，这些方法有两个共有的特点：(1) 分解量中允许有负数（允许有减性的描述）；(2) 维数约减呈线性[75]。
2.2.1 非负矩阵分解研究背景
在计算机很多领域 (比如计算机视觉[5]、信号处理[6]) 的研究中，我们往往可以采集到高维度的特征对样本进行刻画。一般来讲，将高维数据变换为低维数据至少可以带来两方面的好处：(1) 变化后低维数据的存储和计算开销会降低；(2) 数据的内在结构更容易被发现。
研究人员提出许多面向矩阵数据的分解方法可以用于对高维数据进行降维分析，其中包括、线性判别分析 (LDA)[71]、投影寻踪 (PP)[72]、主成分分析 (PCA)[73]、因子分析 (FA)[74]、独立分量分析 (ICA)。这些方法的建模分析目标各有不同，且相关约束条件和求解方法也各不相同，但是，这些方法有两个共有的特点：(1) 分解量中允许有负数（允许有减性的描述）；(2) 维数约减呈线性[75]。
Lee 和 Seung 提出针对非负数据的分析方法 NMF[4]，并将其应用于人脸的局部特征表示和文本语义特征的抽取。NMF 使得分解后的矩阵不存在负的分量。NMF 在心理学上和生理学这一角度来看，可以更加直观地描述：各个部分构成了整体 (Part-based representation)，如人脸是由眼睛、耳朵、鼻子和嘴等器官组成，从局部各部分的感知构成了对整体的感知[76]。因此，NMF 可以被认为是对数据的本质做了一种全新的描述。
NMF 的稀疏性和纯加性 (only additive，not subtractive) 使得对高维数据的描述更加清晰 (原始高维数据通过用低维的方式呈现显得更简单) 且合适 (很多有具体意义的数据本不应该存在负数)。此外，部分外界变化对原始矩阵的特征的影响在某种程度上是可以被 NMF 方法得到的矩阵稀疏抑制的[77]，NMF 自提出起已逐渐成为计算机视觉[5]、信号处理[6]等众多领域中很常见且非常受欢迎的一种工具。具体来看，NMF 已经被用到图像还原[78]、短文本聚类[79]、人脸识别[80]等众多领域之中。
.............................
NMF 的稀疏性和纯加性 (only additive，not subtractive) 使得对高维数据的描述更加清晰 (原始高维数据通过用低维的方式呈现显得更简单) 且合适 (很多有具体意义的数据本不应该存在负数)。此外，部分外界变化对原始矩阵的特征的影响在某种程度上是可以被 NMF 方法得到的矩阵稀疏抑制的[77]，NMF 自提出起已逐渐成为计算机视觉[5]、信号处理[6]等众多领域中很常见且非常受欢迎的一种工具。具体来看，NMF 已经被用到图像还原[78]、短文本聚类[79]、人脸识别[80]等众多领域之中。
.............................
第三章 基于全局融合的多核概念分解模型求解算法 . . . . . . . . . . . . . . . 19
3.1 基于全局融合的多核概念分解模型 . . . . . . . . . . . . . . . . . . . . . 19
3.2 基于全局融合的多核概念分解模型求解算法 . . . . . . . . . . . . . . . . 19
第四章 基于局部判别分析全局集成的多核概念分解算法 . . . . . . . . . . . . . 29
4.1 基于局部判别分析全局集成的多核概念分解模型 . . . . . . . . . . . . . 29
4.1.1 多核概念分解 . . . . . . . . . . . . 29
4.1.2 局部判别正则化 . . . . . . . . . . . . . 30
第五章 总结与展望 . . . . . . . . . . . . . . . . . . 49
5.1 总结 . . . . . . . . . . . . . . . 49
5.2 展望 . . . . . . . . . . . . . . . . 49
第四章 基于局部判别分析全局集成的多核概念分解算法
4.1 基于局部判别分析全局集成的多核概念分解模型
4.1.1 多核概念分解
..........................
第五章 总结与展望
5.1 总结
非负矩阵分解在聚类分析领域的意义非常重大，概念分解把矩阵分解模型推广到了单个非线性核空间，从而提升了矩阵分解的学习能力和普适性[106]。不同的核函数获得的概念分解结果是不相同的。由于缺少标签信息，实际应用中如何针对特定的任务或数据集设计合适的核函数是非常困难的。针对概念分解在核函数选择方面的困难[96]，本文参考国内外相关工作并取得了以下两个成果：#p#分页标题#e#
提出基于全局融合的多核概念分解算法 (GMKCF)[96]。在概念分解的基础上，通过全局线性加权的方法在无监督的多核学习框架中从多个初始给定的核函数里学习聚类质量更高、稳定性更好的核函数。在没有引入额外超参数的前提下，提出了基于全局融合的多核概念分解模型，一方面借助融合后的高质量核函数提升概念分解质量，另一方面借助概念分解发现数据集上的本征结构并用于指导多核融合参数的学习。推导并设计了可保证收敛的迭代式优化求解算法。多个基准数据集的聚类结果表明，本文所提出的 GMKCF 算法在多个指标上优于常见单核聚类算法以及常见的多核聚类基准方法。
提出基于局部判别分析全局集成的多核概念分解算法 (DMKCF)。为了进一步在多核概念分解的框架中充分考虑多核意义下的局部几何结构，我们进一步提出基于单核局部判别式分析而诱导的全局多核融合的正则化方法，它充分考虑了多核意义下数据的潜在局部几何结构，解决了一致核矩阵迭代过程中因离散邻域发生变化引起的算法的单调收敛性[28]被破坏的问题。且设计了一种有效的迭代策略，利用乘法更新规则获得最优的唯一解，并进行了严格的收敛性和正确性分析。在基准数据集上的实验结果表明，该算法在多个聚类评价指标上优于许多先进的多核算法。
综上，本文围绕概念分解中核函数设计的问题，探索了概念分解中新的核函数生成算法，即基于全局融合的多核概念分解算法和基于局部判别分析全局集成的多核概念分解算法, 并将这两种算法应用于聚类分析中并获得良好的实验效果。
参考文献（略）
