首页 >  硕士论文 > 软件工程硕士论文 >   正文

软件工程硕士论文:面向大规模数据的多视角K-means聚类算法的研究

添加时间:2017-11-22 18:57:15   浏览:次   作者: www.dxlwwang.com
专业论文资料, 搜索论文发表论文代写论文网为你解忧愁!详情请咨询我们客服。
获取免费的论文资料? 欢迎您,提交你的论文要求,获取免费的帮助

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   n;并且每个区域称为一个簇,每个数据对象有且仅有一个簇与之对应。基于划分的聚类算法大多数是以距离为划分标准的,把距离相近的对象尽可能划分到同一个簇中,使得同一个簇中的对象尽可能“相近”,不同簇中的对象尽可能“相斥”。基于划分的聚类算法思路是:先根据设定聚类数目 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.2.1 L1 范数..... 20
3.2.2 L2 范数..... 21
3.2.3 L1 范数与 L2 范数的差异........... 22
3.3 算法相关公式......... 23
3.4 算法描述 ......... 26
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 实验环境的建立
实验环境:CPU 为 Intel(R)Core(TM)i5-2450M,2.50Hz,16G 内存,Win7 旗舰版 64 位操作系统。编码环境:MATLAB R2014a。在这一节,我们将在表 4.1 中的五个数据集上进行试验,来验证提出的LKMC 聚类算法的有效性,并采用三种聚类评价指标来评测算法的性能。我们将使用提出的 LKMC 的多视角聚类性能与相应的单视角聚类性能作比较。此外,我们还与几个基础的算法做了比较,如原始的多视角 K-means 算法(NKMC)和自相似传播算法(AP)。在我们的算法中,如果忽略每个视角特征的权重学习,算法就退化成了一个简单的版本,可以简称为 SLKMC。为了显示权重学习的重要性,我们也与这个简单版本的算法作比较。在进行聚类算法之前,对于每种类型的特征数据要首先进行标准化,使所有的值在[-1,1]的范围内。当执行 NKMC 算法时,我们用预处理后的标准化特征作为经典的 K-means 算法的输入。Caltech101 数据集:这是一个包含 8677 幅图像,101 类的对象识别数据集。我们选择常用的 7 个类,人脸、摩托车、美元钞票、加菲猫、史努比、停车标志和温莎椅。根据文献[54]对数据进行取样,共有 441 幅图像。为了能得到不同的视角,我们从每幅图像中提取 6 个视角特征,包括 256 维度的 LBP 特征,100 维度的 HOG 特征,512 维度的 GIST 特征,48 维度的 CMT 特征,1302 维度的 CENTRIST 特征,以及 128 维度的 DOG-SIF 特征。手写体数据集:该数据集包含 2000 个数据点,包含 0 到 9 这十个数字类,也就是说每个数字类有二百个数据点。我们用已发布的 6 个特征进行多视角聚类。这六个特征分别是 FOU 特征视角:包含 76 个字符形状的傅里叶系数;FAC 特征视角:包含 216 个相关轮廓;KAR 特征视角:包含 64 个 Karhunen-Love 系数;PIX 特征视角:平均的窗口包含 240 个像素点;ZER 特征视角:包含 47 个 Zemike 矩;MOR 特征视角:包含 6 个形态变量。
..........
 
总结
 
使用多视角数据来描述数据特征已经运用在众多领域之中。只考虑一个视角进行聚类导致很多信息缺失。而随着数据的爆炸式增长,大规模的多视角数据信息等待我们去挖掘利用。本文讨论了在 K-means 聚类算法处理大规模数据的基础上,结合2,1  范数以及分块处理技术提出了面向大规模数据的多视角K-means 聚类算法。本文所做的主要工作包括:首先介绍了大规模多视角聚类的研究背景和研究意义,并介绍了近几年国内外最新的研究方向和进展。然后介绍了经典的聚类算法和几种常见的大规模数据聚类算法并详细描述了三种多视角学习模型。本文从 K-means 聚类算法常常用来解决大规模数据问题这个角度出发,提出使用多视角 K-means 聚类算法来处理大规模多视角数据的想法。又考虑到算法的稳定性,将常用的 L1 范数改进为2,1  范数,又融入了处理大规模数据的分块思想,从而提出了面向大规模数据的多视角 K-means 聚类算法,并通过人工数据集和几个真实数据集验证了所提出的算法的有效性。本文提出的 LKMC 算法能够在内存有限的情况下对大规模数据进行多视角聚类,并采用了均匀的分块策略,尽可能的保证了聚类精度,适用于大规模多视角聚类问题。该算法利用统一的聚类指标,找到一个共识模型在多个特征视角之间进行聚类。通过在目标函数上使用结构化稀疏诱导范数,使我们的算法在处理噪声值时的稳定性得到提高。本文提出的算法能够自适应地学习各个视角的权重,对目标函数进行优化迭代且有效地解决了非光滑的问题并证明了其收敛性。本文在五个数据集上与几个相关算法做出对比实验,实验结果表明了 LKMC 算法的有效性。
..........
参考文献(略)

提供海量毕业论文,论文格式,论文格式范文,留学生论文,商务报告相关资料检索服务。
本论文由代写论文网整理提供 http://www.dxlwwang.com/
需要专业的学术论文资料,请联系我们客服
本文地址:http://www.dxlwwang.com/ruanjian/6288.html
论文关键字:软件工程硕士论文 大规模数据 K-means 聚类算法