1 绪论
1.1 研究背景和意义
我们生活在数据时代。每天,科学、社会、商业和医学、工业以及我们日常生活中方方面面都会产生大量的数据。这些数兆字节或者数千兆字节的数据像洪流一样注入计算机网络、万维网和各类数据存储设备。数据的爆炸式增长、普遍可用和庞大的数目使我们所处的时代成为真正的数据时代。要想从这些海量数据中发现可利用的信息,迫切需要功能强大并且通用的工具来将这些数据转化成有组织的知识。正是在这种需求下,数据挖掘诞生了。数据挖掘是从海量数据中发现有趣的模式和知识的过程。聚类分析是其中一种重要的数据挖掘方法。 聚类分析,可以简称为聚类。它是一个把数据对象集划分成多个组或者簇的过程。在这个过程中,簇中对象尽可能的彼此相似,但与其他簇中的对象尽可能不相似。由聚类分析所产生的簇的集合称为一个聚类。聚类的划分不是通过人,而是通过聚类方法所进行的。由于可能发现数据内先前并不知道的群组,所以聚类分析是有用的。聚类分析已经在许多应用领域得到了普遍的应用,其中包括商务智能、web 搜索、图像模式识别、信息安全和生物学等。聚类可以按照数据的相似性来把大型数据集合进行分割成组。因此,在某一些应用中,聚类又被称为数据分割。聚类还可以用来进行离群点检测,其应用包括电子商务中的犯罪活动监控和信用卡的欺诈检测。由于具备数据挖掘功能,聚类分析也可以作为一种独立的工具,可以用来观察数据的分布,研究每个簇的特点从而将进一步的分析锁定在某个特定的簇集合上。因为数据库中有数目庞杂的数据需要处理,聚类分析已经成为数据挖掘研究领域中一个特别活跃的研究课题。目前已经出现了大量的聚类算法。基本的聚类算法主要有基于划分的聚类算法,基于层次的聚类算法,基于密度的聚类算法,以及基于网格的聚类算法。这些聚类方法经常被用来解决单视角聚类问题。
..........
1.2 多视角聚类国内外研究现状
多视角聚类问题已经越来越引起人们的重视,由此出现了很多关于多视角聚类研究方面的文章。国内外很多科研人员在这个领域付出了大量心血,做了很多理论以及应用方面的研究,使得多视角聚类的方法更加饱满成熟,并将研究成果应用于日常生活的方方面面。这些研究也为研究人员以后在多视角领域的进一步探索做出了铺垫。 由于单视角聚类方法不能识别多源数据中隐含的聚类结构,多视角聚类的提出最初只是为了合并来自多个视角信息,如今已经在许多领域演变为一种用来提高聚类性能或者聚类精度的有效方法。许多聚类算法,例如文献[1]提出的多视角 K-means 聚类算法,文献[2]提出的多视角期望最大化的算法,分别对经典的 K-means 聚类算法和 EM 聚类算法做了延伸。最近,一些用来解决多视角聚类问题的新算法被提出,如文献[3]和文献[4]。这些算法考虑到来自多重数据集的信息,与只利用单视角的数据单独执行经典聚类相比,拥有更好的结果。 谱聚类是用于多视角聚类最广泛的数据聚类方法之一。它首先通过计算特征向量的规范化的拉普拉斯矩阵,找到一个低维嵌入矩阵 U,然后在矩阵 U 的转置上执行 k-means 算法,最后得到最终的聚类结果。在理想的情况下,TUU 应该是斜对角块并且是稀疏矩阵。为了解决计算非凸 SSC 模型的问题,文献[5]提出了一种新的基于固定排序投影矩阵凸包的凸松弛 SSC。这种凸 SSC 模型可以有效地被交替方向方法的乘数解决。并在 SSC 模型上进一步扩展,形成了成对的 SSC 模型,该模型利用多视角信息数据,提高了聚类性能。 传统多视角聚类的结果取决于在独立视角上学习过程的好坏。在执行多视角聚类任务时,将每个视角独立对待,分别进行聚类。最后采取相应的集成策略对每个视角聚类的结果进行集成,从而得到最终的聚类结果。这种聚类算法认为的对视角数据进行分割,可能会导致全局划分结果较差。协同聚类算法,例贝叶斯协同聚类、基于协同聚类的高斯算法等,还有很多其他的算法,已经在诸多文献中被提出来,目的在于在聚类过程中同时学习所有视角特征。这些算法已经在文本聚类,基因表达分析,图像处理等不同的应用领域中显示出良好的聚类效果。
.........
2 相关研究概述
2.1 几种经典的聚类算法介绍
聚类分析方法的发展经历着跨学科的努力。分类学家、社会学家、心理学家、生物学家、统计学家、数学家、计算机科学家、医学研究人员以及其他收集和处理真实数据的研究人员都对聚类分析方法做出了一定贡献。1954 年,一篇处理人类学数据的文章初次提到数据聚类,之后聚类又在不同的应用领域被人们所熟知。 正如本文之前提到的,许多不同的学科文献已经提出来了成千上万的聚类算法。要将所有这些算法一一罗列确实有些困难。然而,聚类方法的不同在于目标函数、概率生成模型和启发式的选择。因此可将聚类算法大致分为以下四类:基于划分的聚类算法是将一个包含 n 个对象的数据集划分成 k 个簇,每个区域至少包含一个数据对象,并且每个区域称为一个簇,每个数据对象有且仅有一个簇与之对应。基于划分的聚类算法大多数是以距离为划分标准的,把距离相近的对象尽可能划分到同一个簇中,使得同一个簇中的对象尽可能“相近”,不同簇中的对象尽可能“相斥”。 基于划分的聚类算法思路是:先根据设定聚类数目 k 把原始数据集分为 k个簇,接着进行迭代计算,从而使每个数据对象划分到其最“合适”的区域内,终止迭代过程。虽然我们已经将数据划分到对应的区域内,但是该区域并不一定是该数据在原始数据集中所对应的簇。为了实现高质量的聚类效果,需要其根据相应的需求作一定的改进和扩充,以突破其在数据集形状上的限制。
.........
2.2 面向大规模数据的单视角聚类
如今,数据挖掘领域内有很多研究是为大规模数据集的高效聚类分析寻求解决方法。这样做的目的就是为了提升传统聚类算法的可伸缩性。大多传统的聚类算法仅在规模较小的数据集上聚类效果较好,执行效率较高。但相对包含的上百万个数据对象的大规模数据集来说,利用传统聚类算法直接进行聚类往往不能同时保证聚类效率以及聚类结果的质量[15]。人们先后提出了很多解决方案来处理这个难题。其中既包括对传统聚类算法的升级改进,如基于约束信息的半监督聚类算法等。又包括对数据的处理,如基于抽样的方法、基于聚类特征选择的方法以及并行运算等等。 数据挖掘是一个快速发展的领域,其目的是从大规模数据集中发掘出有价值的模式和规则。随着数据规模的不断增大,数据挖掘的发展也需要适应大规模数据集的处理。大规模数据集的聚类分析需要较大的存储空间,因此不能一次性将数据全部读入内存。基于抽样的聚类算法首先对原始数据集进行抽样得到样本子集,利用所得样本集代表原数据集,从而缩小参考范围。然后对样本数据集进行分析,根据样本结果推测分析出总体数据集的相关信息。抽样可分为概率抽样和非概率抽样。概率抽样是一种从总体中按某种概率统计获取样本的方法。概率抽样的优点是能够保证样本的代表性,从而避免人为的干扰和偏差。抽样在聚类分析中的应用主要在两个方面:形成初始簇和数据约简。聚类分析中最经典的划分方法是 k-means 和 k-medoids 方法,该类划分方法首先通过抽样选取 k 个对象作为初始簇的中心,然后根据相应算法迭代计算,调整中心直到不再发生改变为止,因此抽样在形成初始簇的过程中尤为重要。抽样在聚类分析中也要进行数据约简,典型的基于中心点划分的 PAM 算法对小规模数据集比较有效,但对于大规模数据集效果不佳。对此可采用 CLARA[16]算法,该算法的主要思想是不考虑整个数据集,首先利用抽样技术从原始数据集中选择一小部分作为样本数据集,然后利用 PAM 算法从样本中选择中心点[17]。只要样本数据的选取足够随机化,那么它就越具有代表性,从样本数据集中选取的中心点就会与从原始数据集中选取的中心点更相似。此外,CLARA 算法通过对原始数据集进行多次抽样,然后利用 PAM 算法对得到的每个样本集进行聚类分析,从而得到效果最佳的聚类结果。
...........
3 LKMC 多视角聚类算法 ............. 18
3.1 背景介绍 ....... 18
3.2 机器学习中的范数正则化介绍 ...... 19
3.3 算法相关公式 ........ 23
3.4 算法描述 ....... 26
3.4.1 面向大规模数据的多视角 K-means 聚类算法(LKMC) .......... 30
3.4.2 RMKMC 算法 ............ 32
3.5 算法收敛性分析 ............. 33
3.6 本章小结 ....... 33
4 实验结果及分析 ......... 34
4.1 实验环境的建立 ............. 34
4.2 实验设计 ....... 34
4.3 算法时间复杂度分析 .... 43
4.4 参数讨论 ....... 43
4.5 本章小结 ....... 43
5 总结与展望 ......... 45
5.1 总结 ...... 45
5.2 展望 ...... 45
4 实验结果及分析
4.1 &