第３３卷第４期 计算机应用研究 Ｖ０１．３３ Ｎｏ．４ ２０１６年４月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ａｐｒ．２０１６ 大数据下的快速ＫＮＮ分类算法 苏毅娟 ，邓振云 ，程德波 ，宗鸣 （１．广西师范学院计算机与信息工程学院，南宁５３００２３；２．广西师范大学广西多源信息挖掘与安全重点实验 室和广西区域多源信息集成与智能处理协同创新中心，广西桂林５４１００４） 摘要：针对Ｋ最近邻算法测试复杂度至少为线性，导致其在大数据样本情况下的效率很低的问题，提出了一 种应用于大数据下的快速ＫＮＮ分类算法。该算法创新性地在Ｋ最近邻算法中引入训练过程，即通过线性复杂 度聚类方法对大数据样本进行分块，然后在测试过程中找出与待测样本距离最近的块，并将其作为新的训练样 本进行Ｋ最近邻分类。这样的过程大幅度地减少了Ｋ最近邻算法的测试开销，使其能在大数据集中得以应用。 实验表明，该算法在与经典ＫＮＮ分类准确率保持近似的情况下，分类的速度明显快于经典ＫＮＮ算法。 关键词：Ｋ最近邻；测试复杂度；大数据；分块；聚类中心 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１６）０４．１００３—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１６．０４．００９ Ｆａｓｔ ＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｂｉｇ ｄａｔａ Ｓｕ Ｙｉｊｕａｎ ，Ｄｅｎｇ Ｚｈｅｎｙｕｎ２ ，Ｃｈｅｎｇ Ｄｅｂｏ ，Ｚｏｎｇ Ｍｉｎｇ２ （１．Ｃｏｌｌｅｇｅ ｏｆＣｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｘｉ Ｔｅａｃｈｅｒｓ Ｅｄｕｃａｔｉｏｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ ５３００２３，Ｃｈｉｎａ；２．Ｇｕａｎｇｘｉ Ｋｅｙ Ｌａｂｏｒａ— ｔｏｒｙ ｏｆＭｕｌｔｉ·ｓｏｕｒｃｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｍｉｎｉｎｇ＆Ｓｅｃｕｒｉｔｙ ａｎｄ Ｇｕａｎｇｘｉ Ｃｏｌｌａｂｏｒａｔｉｅｖ Ｉｎｎｏｖａｔｏｉｎ Ｃｅｎｔｅｒ ｏｆＭｕｌｔｉ—Ｓｏｕｒｃｅ Ｉｎｆｏｒｍａｔｏｉｎ Ｉｎｔｅｒａｔｉｏｎ＆Ｉｎｔｅｌｌｉ— ｇｅｎｔ Ｐｒｏｃｅｓｓｉｎｇ，Ｇｎａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｅｖｒｓｉｔｙ，Ｇｕｉｌｉｎ Ｇｎａｎｇｘｉ ５４１００４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｔｈｅ Ｋ—ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ａｌｇｏｒｉｔｈｍ，ｔｅｓｔｉｎｇ ｃｏｍｐｌｅｘ ｉｓ ｌｉｎｅａｒ ａｔ ｌｅａｓｔ，ａｎｄ ｌｅａｄ ｔｏ ｔｈｅ ａｃ— ｃｕｒａｃｙ ｉｓ ｌｏｗ ｗｈｅｎ ｔｈｅ ｓａｍｐｌｅｓ ａｒｅ ｌａｒｇｅ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｆａｓｔ ＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆａｓｔｅｒ ｔｈａｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＫＮＮ ｄｉｄ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｎｎｏｖａｔｉｖｅｌｙ ｉｎｔｒｏｄｕｃｅｄ ｔｈｅ ｔｒａｉｎｉｎｇ ｐｒｏｃｅｓｓ ｄｕｒｉｎｇ ｔｈｅ ＫＮＮ ｍｅｔｈｏｄ，ｉ．ｅ．，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂｌｏｃｋｅｄ ｔｈｅ ｂｉｇ ｄａｔａ ｂｙ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅｎ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｓｅｌｅｃｔｅｄ ｔｈｅ ｎｅａｒｅｓｔ ｃｌｕｓｔｅｒ ａｓ ｎｅｗ ｔｒａｉｎｉｎｇ ｓａｍｐｌｅｓ ａｎｄ ｅｓｔａｂｌｉｓｈｅｄ ａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍｏｄｅ１．Ｔｈｉｓ ｐｒｏｃｅｓｓ ｒｅｄｕｃｅｄ ｔｈｅ ＫＮＮ ａｌｇｏｒｉｔｈｍ ｔｅｓｔｉｎｇ ｏｖｅｒｈｅａｄ，ｗｈｉｃｈ ｍａｄｅ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌ— ｇｏｒｉｔｈｍ ｃｏｕｌｄ ｂｅ ａｐｐｌｉｅｄ ｔｏ ｂｉｇ ｄａｔａ．Ｅｘｐｅｒｉｍｅｎｔｓ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｉｓ ｓｉｍｉｌａｒｉ— ｔｙ ｔｈａｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＫＮＮ，ｂｕｔ ｔｈｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｓｐｅｅｄ ｈａｓ ｂｅｅｎ ｓｉｇｎｉｉｆｃａｎｔｌｙ ｉｍｐｒｏｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：Ｋ－ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ（ＫＮＮ）；ｔｅｓｔｉｎｇ ｃｏｍｐｌｅｘ；ｂｉｇ ｄａｔａ；ｂｌｏｃｋ；ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ 一种基于密度的训练样本裁剪方法，使样本分布密度趋于平 ０引言 均，降低了ＫＮＮ的计算量。文献［４］提出了一种基于利用中 随着互联网的迅猛发展，大数据不断地产生，分类作为当 心文档代替原始样本建立分类模型的方法，减少了ＫＮＮ算法 需要进行相似计算的样本数，从而达到提高分类速度的目的。 前数据挖掘中最实用的技术之一，已得到广泛的应用。目前常 用的分类方法有决策树、人工神经网络、ＳＶＭ、Ｂａｙｅｓ、ＫＮＮ等。 文献［５］提出了减少大量计算的排类算法和归类算法，在不影 响原有准确率的情况下，构建了一种基于ＫＮＮ的快速分类算 ＫＮＮ算法因其简单和有效在分类算法中得到了广泛的应用， 法，提高了分类的速度。这些算法主要是通过快速搜索算法、 其基本思想是：在训练样本中找到待测样本的ｋ个最近邻样 降维 或通过一定的优化策略直接减少需要进行相关性计 本，然后根据这ｋ个最近邻样本的类进行投票，以此来决定测 算的样本数，从而提高分类的效率。但当面临大数据和高维样 试样本的类别。但是ＫＮＮ在寻找最近邻样本的过程中，需要 本时，这些分类方法的效率将会大幅度降低 “ 。 逐个计算测试样本与每个训练样本的距离（或相似度），当训 针对ＫＮＮ算法无训练过程的特点 ”Ｊ，本文创新性地对 练样本为大数据时，将会产生很高的计算开销，如果大数据集 其引入一个训练过程，即首先采用线性复杂度聚类方法对大数 是保存在内存（或硬盘）中，这种逐个扫描的方式几乎不可行。 据进行分块。而在测试过程，对于每一个测试样本，首先找出 目前提出了许多对于ＫＮＮ的改进算法，文献［１，２］提出 与待测样本距离最近的聚类中心所在的簇作为新的训练样本 一种从所有已知样本中选取测试样本的 个最近邻，然后建立 集，然后对新训练集建立分类模型进行分类。由于聚类后簇内 分类器进行分类的方法，提高了分类的性能。文献［３］提出了 样本的相似度高，所以该算法能达到既减少计算量，又能保持 收稿日期：２０１４·ｎ－３０；修回日期：２０１５—０１—２３ 基金项目：国家自然科学基金资助项目（６１４５０００１，６１２６３０３５，６１５７３２７０）；国家“８６３”计 划资助项目（２０１２ＡＡ０１１００５）；国家“９７３”计划资助项目（２０１３ＣＢ３２９４０４）；广西自然科学基金资助项目（２０１２ＧｘＮｓＦＧＡ０６００ｏ４，２０１４ｊｊＡＡ７０１７５． ２Ｏ１５ＧｘＮｓＦＡＡ１３９３０６，２０ｌ５ＧｘＮｓＦＣＢ１３９０１）；广西八桂创新团队、广西百人计划和广西高校科学技术研究重点项目（２０１３ＺＤ０４） 作者简介：苏毅娟（１９７６一），女，广西桂林人，副教授，主要研究方向为机器学习和数据挖掘；邓振云（１９９１．），男（通信作者），江西南昌人，硕士， 主要研究方向为机器学习和数据挖掘（５９７２７７２８７＠ｑｑ．ｃｏｒｎ）；程德波（１９９０一），男，江西丰城人，硕士，主要研究方向为数据挖掘和机器学习；宗鸣 （１９９０－），男，江苏泰州人，硕士，主要研究方向为机器学习和数据挖掘． 计算机应用研究 较高分类准确率的目的。 第３３卷 复杂度的算法非常适合在大数据方面的应用。最后，给出ＬＳＣ 算法的具体步骤，如下所示： １ 基于聚类的ＫＮＮ改进算法 本文算法包括两个过程，即训练过程和测试过程。训练过 程主要选取适用的聚类算法对大数据样本进行分类；测试过程 算法Ｉ ＬＳＣ算法 输入：ｎ个数据点 ， ：，…， 输出：ｋ个子簇。 通过Ｋ—ｍｅａｎｓ选取Ｐ个界标点； 根据式（１）投影原始数据Ｘ到界标矩阵，得到原始矩阵的表示ｌＺＥＲｐ ； 根据矩阵Ｚ，计算ＺＺｒ的前ｋ个特征向量 ； 根据式（４）计算特征向量８； 运用Ｋ·ｍｅａｎｓ对特征向量８进行最终的聚类，并输出ｋ个子簇。 Ｒ 以及聚类个数ｋ。 主要是对测试样本在它最近的簇运行ＫＮＮ算法。 １．１ 训练过程 聚类是数据分析中最基本的一种技术，它在数据挖掘、机 器学习、模式识别方面都得到广泛应用。所谓聚类就是将数据 １．２测试过程 对象分组成多个类和簇的过程。其中，聚类所生成的簇包含簇 内样本相似性高和簇之间差异性大两个性质。 目前的聚类方法有很多，如基于划分的Ｋ—ｍｅａｎｓ算法、基 于层次的ＢＩＲＣＨ算法 和基于密度的ＤＢＳＣＡＮ算法Ｈ 等。 但是面临高维大样本数据时，常见的聚类算法将在时间复杂度 本文在采用ＬＳＣ算法得到ｋ个子簇并求出ｋ个聚类中心 后，找出距离待测样本最近的聚类中心所在的子簇，将其作为 新的训练样本。由于通过ＬＳＣ聚类得到的子簇中的样本都是 彼此相似的，所以在选定的子簇中进行ＫＮＮ分类可以充分保 证分类的准确率。最后，给出基于ＬＳＣ聚类的ＫＮＮ改进算法 的具体步骤，如下所示： 算法２ ＬＣ—ＫＮＮ算法 方面受到极大挑战。因此，对高维大样本数据进行聚类需要满 足一些条件：复杂度低，最好是线性的，如文献［１６，１７］。为 此，本文采用了文献［１８］提出的聚类算法，即基于界标的谱聚 类（１ａｎｄｍａｒｋ．ｂａｓｅｄ ｓｐｅｃｔｒａｌ ｅ￣ｕｓｔｅｒ／ｎｇ，ＬＳＣ）算法，该算法主要是 输人：数据集。 输出：待测样本类标签的预测值。 使用ＬＳＣ聚类方法对训练样本进行聚类，得到ｍ个聚类中心Ｃ ， Ｃ２，Ｃ３，…，Ｃ ； 选取Ｐ（Ｐ＜＜ｎ）个具有代表性的点作为界标点，并将这Ｐ个界 标点进行线性组合以替代原始数据。常见的谱聚类算法 通 常用所有样本表达每个数据，这种方法大大降低了相似矩阵的 复杂度，即从二次降到了一次，从而也顺带把特征根求解的复 杂度降低到了线性 。 计算待测样本ｙ与所有聚类中心的距离Ｄ（Ｙ，Ｃ ），将与之距离最 近的聚类中心所在的簇作为新的训练样本，即ＮｅｗＸｉ＝ｍｉｎ｛Ｄ（Ｙ，ｃ ）｝ ｉ：１，２，·一，ｍ； ＬＳＣ算法通过“压缩”原始数据找出一组基向量去代表每 在新训练样本ＮｅｗＸ 中对待测样本进行ＫＮＮ分类，得到待测样本 Ｙ的ｋ个最近邻，并通过投票确定其类标签的预测值ｃｌａｓｓ 。 个数据点，即找出Ｐ个具有代表的界标点。常见的选取界标点 的方法有随机选取法和Ｋ－ｍｅａｎｓ聚类。随机选取法即随机选 通过算法２可知，当聚类的个数较多，即ｍ较大时，新的 训练样本ＮｅｗＸ 的样本数将远小于原始样本数，可以很容易 取界标点；而Ｋ－ｍｅａｎｓ聚类算法通过简单重复算法几次（通常 低于１０次），把得到的聚类中心作为界标点。本文重复Ｋ— 达到大幅度减少ＫＮＮ的计算量 ０ 、提高分类速度的目的。 但是随着ｍ的增大，聚类的开销也会同时增加，且新训练样本 ＮｅｗＸ 中的样本数将会逐渐减小，这很有可能会导致分类准确 率的下降。为了避免这种情况，聚类的个数ｍ需要设置在一 个比较合理的数值。 极端情况下，假定令ｍ为样本个数时，则为１ＮＮ算法，该 ｍｅａｎｓ聚类算法１０次，把得到的聚类中心作为界标点。 把每个界标点当做一个向量组成界标矩阵Ｕ，ＬＳＣ算法用 得到的Ｐ个界标点表示所有的原始数据点ｘ＝［ Ｒ ，即找出Ｘ在界标矩阵上的投影Ｚｃ Ｋｈ（ ，ｕｉ） ．．． （ ） ”， ］ … （ Ｊ 算法分类的效率较高，但当训练样本分布比较集中时，则很有 可能导致分类准确率降低；而令ｍ＝１时，则为经典的ＫＮＮ算 法。因此，常见Ｋ最近邻算法是本文算法的一种特例。通过 以上分析可知，聚类的簇的个数ｍ越大，ＫＮＮ分类需要扫描的 样本数也就越少，运行速度越快。但是考虑到样本集为大数 其中： ，是矩阵Ｕ的第 个列向量，Ｕ， ）是ｃａ 。的ｒ个最近邻界 标组成的Ｕ的子矩阵。易知，矩阵Ｚ的运行时间为０（ｐｍｎ）。 接着对其进行谱聚类分析，首先构造图矩阵Ｗｏ Ｗ： ＾ （２） 据，如果ｍ较小，簇中样本数依然很大，不能在内存（数据空 间）中运行。因此，假设程序运行占用的总内存为Ｍ，计算机 其中：Ｚ＝ＤＩ１ Ｚ，Ｄ是Ｚ中行向量的和，则矩阵Ｗ即为一个单 ＾ 系统内存为眠，样本集中最小类样本的个数为 ，那么ｍ的 取值范围可表示为ｒＭ／Ｍｏ＜ｍ＜ 。 在确定新训练样本ＮｅｗＸ 、对测试样本选取ｋ个最近邻过 程中， 值是非常重要的参数之一。文献［２４］建议ｋ＝ （ｎ＞ １００），ｎ是测试样本的个数，但这种取法通常不能得到满意的 结果，并且该想法也没有理论保证。 由于本文提出的基于ＬＳＣ 方法得到的子簇ＮｅｗＸ 中样本之间都是相关的，考虑到在大 数据中需要减少ＫＮＮ的计算量，所以ｋ值的选取不宜过大，在 保持较高分类准确率的情况下，ｋ值的选取应尽可能小。通过 实验发现，当 ＝１、２时，分类的结果较优。 位矩阵『ｏ当得到单位图矩阵ｗ后，通过奇异值分解计算Ｚ的 特征向量如下： ２＝Ａ 日Ｔ＾ ＾＾ （３） 易知，左奇异向量Ａ：［。 ．－，０ ］∈ 为矩阵ｚＺｒ前ｋ ＾ ＾ 个特征向量，右奇异向量８＝［ｂ ，…，ｂ ］ｅ Ｒ 为矩阵 Ｚ的 ＾ ＾ 特征向量。ｃａ于矩阵Ｗ＝ Ｚ为Ｐ×Ｐ维，可知向量Ａ的计算 时间为０（Ｐ ），而特征向量８的计算时间则可通过下式得出： ：２－１ｆｌｌＴ （４） 特征向量Ｂ的总时间为Ｏ（ｐ ＋ｐ２ｎ）［ｚｌＩ。由于Ｐ＜＜ｎ，所 １．３图例说明 以当选取特征向量Ｂ进行Ｋ－ｍｅａｎｓ聚类时，算法运行的总时间 则由０（．ｒｔ。）降为Ｏ（ｐ ），算法的效率得到明显的提高。这种低 ＫＮＮ分类算法虽然简单、有效且准确率高，但是缺点也很 明显，其时间复杂度几乎与样本数成正比。这是因为ＫＮＮ算法 第４期 苏毅娟，等：大数据下的快速ＫＮＮ分类算法 ·１００５· 是一种懒惰的基于实例的学习方法，每次在寻找待测样本的ｋ 表３两种算法在ｍｎｉｓｔ数据集上的对比 个最近邻时，都需要计算其与所有训练样本的距离，当训练样本 较大时，分类的时间也成正比增加。考虑到目前ＫＮＮ分类都是 在数据空间中进行，在样本为大数据晴况下要扫描数据集（或者 从磁盘／内存中读取）一遍几乎不可能。为了解决这个问题，本 文将样本集分成多个较小的块（保证每个块都能够在内存中运 行），并将具有代表性的块作为新的训练样本进行ＫＮＮ分类。 如图１所示，对样本集进行聚类得到三个聚类中心，分别计算测 试样本与三个聚类中心的距离。可知测试样本１距离簇１的聚 类中心最近，因此本算法将簇１作为样本１的新的训练样本；而 对于测试样本２，其最近邻样本中虽然包含簇２、簇３的样本，但 是距离最近的聚类中心为簇３，所以将簇３作为新的测试集。考 虑到仅将簇３作为新的训练样本可能会影响分类准确率，但通 表４两种算法在ｇｉｓｅｔｔｅ数据集上的对比 过ＬＳＣ算法得到的簇内样本之间具有较高的相似性，簇簇之间 样本差异性大，所以将簇３作为新的训练样本集进行ＫＮＮ分类 时，依旧能够保持较高的分类准确率。 辩荔熬 １ １ ／ Ｒ１． 翳１ ２ ２ ２ ３－ ３￣ 图１改进算法中测试样本选择训练样本集的过程 ２实验设计 为了验证算法的有效性，本文通过ＭＡＴＬＡＢ编程实现本 表５两种算法在ｌｅｔｔｅｒ数据集上的对比 文算法，并在Ｗｉｎ７系统下的ＭＡＴＬＡＢ ７．１软件上进行实验。 本文以分类准确率和时间作为评价指标，对随机分块ＫＮＮ算 法、基于ＬＳＣ的ＫＮＮ改进算法以及经典ＫＮＮ算法进行对比。 实验所用数据来源于ＬＩＢＳＶＭ和ＵＣＩ数据集，数据集的基本信 息如表１所示。 表１数据集基本信息 Ｎｏ数据集样本数属性数类数 Ｎｏ数据集样本数属性数类数 １ ｕｓｐｓ ９ ２９８ ２５６ １０ ４ ｌｅｔｔｅｒ ２Ｏ ０（）ｏ ｌ６ ２６ ２ ｍｎｉｓｔ ７０ ０００ ７８０ １０ ５ ｐｅｎｄｉｇｉｔｓ １０ ９９２ １６ １０ ３ ｇｉｓｅｔｔｅ ７ ０００ ５ ０００ ２ ６ ｓａｔｉｍａｇｅ ６ ４３５ ３６ ６ ２．１分簇数ｍ的确定 改进算法中ｍ是非常重要的参数之一。为了确定参数 表６两种算法在ｐｅｎｄｉｇｉｔｓ数据集上的对比 ｍ，本文对随机分块ＫＮＮ算法和本文改进算法在六个数据集 上分别重复１０次，实验结果不但报告每次实验的结果而且报 告１０次结果的均值和方差。实验结果如表２～７所示。 表２两种算法在ｕｓｐｓ数据集上的对比 通过表２—７可知，随着分块数ｍ的增加，两种算法的分 类速度逐渐变快，但相应的分类准确率却逐渐下降。考虑到两 种算法都属于近似算法，如果分类的准确率明显低于经典 ＫＮＮ算法，那么在大数据分类中将会出现很大的误分率，这显 ·１００６· 计算机应用研究 第３３卷 然是不可取的。此外，从表２—７可知，在分类时间相近的情况 Ｏ ０ Ｏ ｋ值的选取应尽可能小。根据图２所示，本文算法在ｓａｔｉｍａｇｅ 料髂 下，基于ＬＳＣ的ＫＮＮ算法的分类准确率明显高于随机分块的 ＫＮＮ算法，且从表８中可以发现，其分类准确率更加接近经典 数据集上ｋ＝３时可以取到０．８９８６，高于ｋ＝１时的准确率，但 是在ｋ＝１时，本文算法的实验结果已经优于ＫＮＮ。因此，本 ＫＮＮ算法。 表７两种算法在ｓａｔｉｍａｇｅ数据集上的对比 依据上文分析可知，聚类分簇的个数ｍ的大小同样应该 是在保证所有子簇都能在内存中运行的情况下，尽可能小。这 样既减小了聚类的时间，又提高了分类的速度，并且能保证具 有较高的分类准确率。根据表２～７的实验结果显示，在ｍ＝ １０的情况下，分类的结果更优。 ２．２ ｋ值的确定 在算法２确定新的训练样本ＮｅｗＸ 后，需利用ＫＮＮ算法 对测试样本在ＮｅｗＸ 中建立分类模型，其中对于ｋ值的选取是 非常重要的步骤之一。考虑到经ＬＳＣ聚类后簇内的样本已具 有很高的相似性，所以ｋ值的选择无须太大。为了确定ｋ的取 值，分别对表１中数据集进行了如下实验，结果如图２所示。 为了保证实验的准确性，实验结果中每个点都是１０次结果的 均值。 ０ ０ 槲０ 褂０ 器０ ．曙 ０ ０ ；Ｉ《｝《 ０ ０ ０ Ｏ ０ ０ 篓 蒙 。 ０ Ｏ Ｏ 瞄 膛 （ｅ）ｐｅｎｄｉｇｉｔｓ ｄａｔａｓｅｔ （ｆ）ｓａｔｉｍａｇｅ ｄａｔａｓｅｔ 图２六个数据集分别在不同 值时的分类准确率 从图２中曲线可知，随着ｋ值增加，分类准确率总体呈下 降趋势，这是因为簇内样本已经具有了很高的相似性，如果ｋ 值选取得过大，且待分类样本又属于训练集中包含数较少的 类，那么在选择 个最近邻时，实际上并不相似的数据就会被 包含进来，从而造成噪声导致分类效果降低，同时也增加了 ＫＮＮ算法的计算量。因此，在分类准确率保持较高的情况下， 文统一选取 ：１。 ２．３三种算法的·眭能比较 本次实验在分块（簇）数ｍ＝１０、ｋ＝１的情况下，以准确率 和时间为评价指标，对三种算法进行对比实验，实验结果如表 ８所示。 表８三种算法的性能比较 由于改进算法为近似算法，通过表８可以看出，该算法分 类准确率低于经典ＫＮＮ算法１％一２．４％，但是样本数据足够 大时，分类的速度接近于经典ＫＮＮ算法的７—９倍（接近分块 数）。而随机分块算法虽然分类速度略高于本文算法，但分类 准确率较低。通过上述实验可知，使用基于ＬＳＣ的ＫＮＮ改进 算法，能在保持分类准确率较高的情况下，大幅度提高分类的 速度，使其能够在大数据中得到应用。 ３结束语 本文针对经典ＫＮＮ算法难以在大数据样本中应用的问 题，提出了一种基于ＬＳＣ的ＫＮＮ改进算法。该算法针对ＫＮＮ 没有训练过程的特点，创新地引入了一个训练过程，即通过聚 类技术找出了远小于原始样本集的新的训练样本集，极大地减 少了ＫＮＮ算法的计算量，使其能够在大数据空间（内存）中运 行，并且该算法能够保持较高的分类准确率。但是本文算法仍 有一些地方需要改进，如新的训练集用于ＫＮＮ分类时，其分类 准确率的高低依赖于聚类的效果，如果聚类的效果较好，那么 改进算法的分类准确率将完全有可能超过经典算法。 参考文献： ［１］ｚｈａＩＩｇ Ｓｈｉｃｈａｏ．ＫＮＮ－ＣＦ ａｐｐｒｏａｃｈ：ｉｎｃｏｒｐｏｒａｔｉｎｇ ｃｅｒｔａｉｎｔｙ ｆａｃｔｏｒ ｔｏ ＫＮＮ ｃｌａｓｓｉｉｆｃａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｃｓ Ｂｕｌｌｅｔｉｎ，２０１０， １１（１）：２４—３３． ［２］ｚｈａＩＩｇ Ｓｈｉｃｈａｏ，Ｚｈａｎｇ Ｃｈｅｎｇｑｉ，Ｙａｎ Ｘｉａｏｗｅｉ．Ｐｏｓｔ—ｍｉｎｉｎｇ：ｍａｉｎｔｅ－ ｎａｎｃｅ ｏｆ ａｓｓｏｃｉａｔｉｏｎ ｒｏｌｅｓ ｂｙ ｗｅｉｇｈｔｉｎｇ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２００３，２８（７）：６９１—７０７． ［３］李荣陆，胡运发．基于密度的ＫＮＮ文本分类器训练样本裁剪方法 ［Ｊ］．计算机研究与发展，２００４，４１（４）：５３９—５４５． ［４］张孝飞，黄河燕．一种采用聚类技术改进的ＫＮＮ文本分类方法 ［Ｊ］．模式识别与人工智能，２００９，２２（６）：９３６—９４０． ［５］李杨，曾海泉，刘庆华，等．基于ＫＮＮ的快速Ｗｅｂ文档分类［Ｊ］． 小型微型计算机系统，２００４，２５（４）：７２５—７２８． ［６］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｈｕａｎｇ Ｚｉ，Ｙａｎｇ Ｙａｎｇ，ｅｔ ａ１．Ｓｅｌｆ－ｔａｕｇｈｔ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｏｎ ｔｈｅ ｈｉｇｈ—ｄｉｍｅｎｓｉｏｎａｌ ｓｍａｌｌ—ｓｉｚｅｄ ｄａｔａ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏ－ ｇｎｉｔｉｏｎ，２０１３，４６（１）：２１５－２２９． ［７］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｈｕａｎｇ Ｚｉ，Ｃｕｉ Ｊｉａｎｇｔａｏ，ｅｔ ａ１．Ｖｉｄｅｏ－ｔｏ—ｓｈｏｔ ｔａｇ ｐｒｏｐａ— ｇａｔｉｏｎ ｂｙ ｇｒａｐｈ ｓｐａｒｓｅ ｇｒｏｕｐ Ｌａｓｓｏ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｍｕｌｔｉｍｅｄｉａ， ２０１３，１５（３）：６３３—６４６． （下转第１０２３页） 第４期 蔡国永，等：基于用户评论的信任预测方法研究 ·１０２３· 验证了该方法的有效性和可行性。本文的社会网络信任关系 预测方法对推荐及可视化等具有一定的应用价值，未来将进一 步挖掘用户的潜在属性特征从而丰富该模型。 参考文献： ［１］Ｌｉｕ Ｇｕａｎｆｅｎｇ，Ｙａｎ Ｗａｎｇ，Ｏｒｇｕｎ Ｍ Ａ．Ｓｏｃｉａｌ ｃｏｎｔｅｘｔ－ａｗａｒｅ ｔｒｕｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２０１１：１１００—１１０８． ［１０］Ｇｕｈａ Ｒ Ｖ，Ｋｕｍａｒ Ｒ，Ｒａｇｈａｖａｎ Ｐ，ｅｔ ａ１．Ｐｒｏｐａｇａｔｉｏｎ ｏｆ ｔｕｓｒｔ ａｎｄ ｄｉｓｔｒｕｓｔ『Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １３ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ。２００４：４０３—４１２． ［１ １］Ｂｏｒｚｙｍｅｋ Ｐ，Ｓｙｄｏｗ Ｍ，Ｗｉｅｒｚｂｉｃｋｉ Ａ．Ｅｎｒｉｃｈｉｎｇ ｔｒｕｓｔ ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅｌ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｗｉｔｈ ｕｓｅｒ ｒａｔｉｎｇ ｓｉｍｉｌａｒｉｔｙ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ａｓｐｅｃｔｓ ｏｆ Ｓｏｃｉａｌ Ｎｅｔ— ｗｏｒｋｓ．２００９：４０—４７． ｎｅｔｗｏｒｋ ｄｉｓｃｏｖｅｒｙ ｉｎ ｃｏｍｐｌｅｘ ｃｏｎｔｅｘｔｕａｌ ｓｏｃｉｌａ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｅ ｏｆ Ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．２０１２：１０１—１０７． ［２］Ｋａｍｖａｒ Ｓ Ｄ，Ｓｃｈｌｏｓｓｅｒ Ｍ Ｔ，Ｇａｅｒｉａ—Ｍｏｌｉｎａ Ｈ．Ｔｈｅ ｅｉｇｅｎｔｒｕｓｔ ａｌｇｏ－ ｒｉｔｈｍ ｆｏｒ ｒｅｐｕｔａｔｉｏｎ ｍａｎａｇｅｍｅｎｔ ｉｎ Ｐ２Ｐ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｃｏ ｏｆ ｔｈｅ １２ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００３：６４０－６５１． ［１２］Ｘｉａｎｇ Ｒｏｎｇｊｉｎｇ，Ｎｅｖｉｌｌｅ Ｊ，Ｒｏｇａｔｉ Ｍ．Ｍｏｄｅｈｎｇ ｒｅｌａｔｉｏｎｓｈｉｐ ｓｔｒｅｎｇｔｈ ｉｎ ｏｎｌｉｎｅ ｓｏｃｉｌａ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｅｅ ｏｆ ｔｈｅ １９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅ— ｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄ６ Ｗｅｂ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２Ｏ１０：９８１．９９０： ［３］Ｕｇｕｒ Ｋ，Ｇｏｌｂｅｃｋ Ｊ．Ｓｕｎｎｙ：ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｒｕｓｔ ｉｎｆｅｒｅｎｃｅ ｉｎ ｓｏ— ｃｉａｌ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｃｏｎｆｉｄｅｎｃｅ ｍｏｄｅｌｓ［Ｃ］／／Ｐｒｏｃ ｏｆ Ｎａ－ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｏｉｌ ＡｒｉｆｔｉＣｉｌ Ｉａｎｔｅｌｌｉｇｅｎｃｅ．２００７：１３７７—１３８２． ［１３］Ｔａｎｇ Ｊｉｌｉｎｇ，ＧａａＤ Ｈｕｉｊｉ，Ｈｕ Ｘｉａ，ｅｔ ａ１．Ｅｘｐｌｏｉｔｉｎｇ ｈｏｍｏｐｈｉｌｙ ｅｆｆｅｃｔ ｆｏｒ ｔｒｕｓｔ ｐｒｅｄｉｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ６ｔｈ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅ． ｒｅｎｃｅ ｏｎ Ｗｅｂ Ｓｅａｒｃｈ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ。２０１３： ５３．６２． ［４］Ｎｉｋｏｌａｙ Ｋ，Ｔｈｅｍｅ Ａ．Ｔｒｕｓｔ ｐｒｅｄｉｃｔｉｏｎ ｆｒｏｍ ｕｓｅｒ—ｉｔｅｍ ｒａｔｉｎｇｓ［Ｊ］． Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋ Ａｎａｌｙｓｉｓ ａｎｄ Ｍｉｎｉｎｇ，２０１３，３（３）：７４９·７５９． ［１４］Ｚｈａｎｇ Ｙｕ，Ｔｏｎｇ Ｙｕ．Ｍｉｎｉｎｇ ｔｒｕｓｔ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｆｒｏｍ ｏｌｎｉｎｅ ｓｏｃｉｌａ ｎｅｔ． ｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，２０１２， ２７（３）：４９２—５０５． ［５］Ｗａｎｉｔａ Ｓ，Ｎｅｐａｌ Ｓ，Ｐａｒｉｓ Ｃ．Ａ ｓｕｒｖｅｙ ｏｆｔｒｕｓｔ ｉｎ ｓｏｃｉｌａ ｎｅｔｗｏｒｋｓ［Ｊ］． ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２０１３，４５（４）：Ａｒｔｉｃｌｅ ４７． ［６］Ｏｈ Ｈ Ｋ，Ｋｉｍ Ｊ Ｗ，Ｋｉｍ Ｓ Ｗ．Ａ ｐｒｏｂａｂｉｌｉｔｙ－ｂａｓｅｄ ｔｒｕｓｔ ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅｌ ｕｓｉｎｇ ｔｒｕｓｔ—ｍｅｓｓａｇｅ ｐａｓｓｉｎｇ［Ｃ］／／Ｐｍｃ ｏｆ ｔｈｅ ２２ｎｄ Ｉｎｔｅｒｎａｔｉｏ— ｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｍｐａｎｉｏｎ．２０１３：１６１—１６２． ［１５］Ｃａｉ Ｇｕｏｙｏｎｇ，Ｌｙｕ Ｒｕｉ，Ｔａｎｇ Ｊｉｌｉａｎｇ，ｅｔ ａ１．Ｔｅｍｐｏｒｌａ ｄｙｎａｍｉｃｓ ｉｎ ｓｏｃｉｌａ ｔｒｕｓｔ ｐｒｅｄｉｃｔｉｏｎ［Ｊ］．Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ Ｊｏｕｒｎａｌ ｏｆ Ｎａｔｕｒｅ Ｓｃｉｅｎｃｅ，２０１４，１９（５）：３６９－３７８． ［７］Ｌｉｕ Ｈａｉｆｅｎｇ，Ｌｉｍ Ｅ Ｐ，Ｌａｕｗ Ｈ Ｗ，ｅｔ ａ１．Ｐｒｅｄｉｃｔｉｎｇ ｔｒｕｓｔｓ ａｍｏｎｇ ［１６］Ｘｉｎ Ｐａｎ，Ｄｅｎｇ Ｇｕｉｓｈｉ，Ｌｊｕ Ｊｉｎｇｕａｏ．Ｗｅｉｈｔｓｅｄ ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｎｄａ ｐｅｒｓｏｎａｌｉｚｅｄ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｊ］．Ｐｈｙｓｉｃｓ Ｐｒｏｃｅｄｉａ，２０１０，３（５）： １８６７—１８７６． ｕｓｅｒ８ ｏｆ ｏｎｌｉｎｅ ｃｏｍｍｕｎｉｔｉｅｓ：ａｎ ｅｐｉｎｉｏｎｓ ｃａｓｅ ｓｔｕｄｙ［Ｃ］／／Ｐｒｃ ｏｏｆ ｔｈｅ ９ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｏｎｉｃ Ｃｏｍｍｅｒｃｅ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００８：３１０—３１９． ［１７］Ｌｉｕ Ｊｉｎｇｕｏ，Ｚｈｏｕ ＴａＤ，Ｃｈｅ Ｈａａｎｇ’ａｎ，ｅｔ ａ１．Ｅｆｆｅｃｔｓ ｏｆ ｈｉｇｈ－ｏｒｄｅｒ ｃｏｒｒｅｌａｔｉｏｎｓ ｏｎ ｐｅｒｓｏｎａｌｉｚｅｄ ｒｅｃｏｍｍｅｎｄａｔｉｏｎｓ ｆｏｒ ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋｓ ［８］Ｋｉｙｎａａ Ｚ，Ａｓｈａｌｅ Ａ．Ｍｉｎｉｎｇ ｔｒｕｓｔ ａｎｄ ｄｉｓｔｕｒｓｔ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｉｎ ｓｏｃｉａｌ Ｗｅｂ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／Ｐｒｃｏ ｏｆ ＩＥＥＥ Ｉｎｔｅｎａｒｔｉｏｎａｌ Ｃｏｆｎｅｒｅｎｃｅ Ｏｉｌ Ｉｎ— ｔｅｌｌｉｇｅｎｔ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｐｒｏｃｅｓｓｉｎｇ．［Ｓ．１．］：ＩＥＥＥ Ｐｒｅｓｓ，２０１０：７３—７８． ［Ｊ］．Ｐｈｙｓｉｃａ Ａ：Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０，３８９（４）：８８１—８８６． ［１８］Ｚｈｕ Ｙｕｘｉａｏ，Ｌｙｕ Ｌｉｎｙｕａｎ．Ｅｖａｌｕａｔｉｏｎ ｍｅｔｉｒｃｓ ｆｏｒ ｒｅｃｏｍｍｅｎｄｅｒ ｓｙｓ－ ［９］Ｗａｎｇ Ｄａｓｈｕｎ，Ｐｅｄｒｅｓｃｈｉ Ｄ，Ｓｏｎｇ Ｃｈａｏｍｉｎｇ，ｅｔ ａ１．Ｈｕｍａｎ ｍｏｂｉｌｉｔｙ， ｔｅｍｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｕｎｉｖｅｒｓｉｙｔ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈ－ ｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ，２０１２，４１（２）：１６３－ｔ７５． ｓｏｃｉｌａ ｔｉｅｓ，ａｎｄ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １７ｔｈ ＡＣＭ ＳＩＧＫＤＤ （上接第１００６页） ［１６］Ｎｇ Ａ Ｙ，Ｊｏｒｄａｎ Ｍ Ｉ，Ｗｅｉｓｓ Ｙ．Ｏｎ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｉｒｎｇ：ａｎａｌｙｓｉｓ ａｎｄ ａｎ ａｌｇｏｉｒｔｈｍ［Ｍ］／／Ａｄｖａｎｃｅ ｉｎ Ｎｅｕｒａｌ Ｉｆｎｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓ— ｔｅｒｎｓ．Ｃａｍｂｒｉｄｇｅ：ＭＩＴ Ｐｒｅｓｓ；２００２． ［８］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｈｕａｎｇ Ｚｉ，Ｃｈｅｎｇ Ｈｏｎｇ，ｅｔ ａ１．Ｓｐａｒｓｅ ｈａｓｈｉｎｇ ｏｆｒ ｆａｓｔ ｍｕｌｔｉｍｅｄｉａ ｓｅａｒｃｈ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ，２０１３， ３１（２）：９． ［１７］Ｆｉｌｉｐｐｏｎｅ Ｍ，Ｃａｍａｓｔｒａ Ｆ，Ｍａｓｕｌｌｉ Ｆ，ｅｔ ａ１．Ａ ｓｕｒｖｅｙ ｏｆ ｋｅｒｎｅｌ ａｎｄ ［９］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｈｕａｎｇ Ｚｉ，Ｓｈｅｎ Ｈｅｎｇｔａｏ，ｅｔ ａ１．Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃ— ｓｐｅｃｔｒａｌ ｍｅｈｔｏｄｓ ｆｏｒ ｃｌｕｓｔｅｉｒｎｇ［Ｊ］．Ｐａｔｌｅｍ Ｒｅｃｏｇｎｉｔｉｏｎ，２００７，４１ （１）：１７６—１９０． ｔｉｏｎ ｂｙ ｍｉｘｅｄ ｋｅｒｎｅｌ ｃａｎｏｎｉｃａｌ ｃｏｒｅｌａｔｉｏｎ ａｎａｌｙｓｉｓ［Ｊ］．Ｐａｎｅｍ Ｒｅ－ ｃｏｇｎｉｔｉｏｎ，２０１２，４５（８）：３００３—３０１６． ［１８］Ｃｈｅｎ Ｘｉｎｌｅｉ，Ｃａｉ Ｄｅｎｇ．Ｌａｒｇｅ ｓｃａｌｅ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｉｒｎｇ ｗｉｔｈ ｌａｎｄ— ｍａｒｋ－ｂａｓｅｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ［Ｃ］／／Ｐｒｃ ｏｆ ｔｏｈｅ ２５ｔｈ ＡＡＡＩ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｉｆｃｉｌａ Ｉｎｔｅｌｌｉｇｅｎｃｅ．［Ｓ。１．］：ＡＡＡＩ，２０１１：３１３—３１８． ［１０］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｚｈａｎｇ Ｓｈｉｃｈａｏ，Ｊｉｎ Ｚｈｉ，ｅｔ ａ１．Ｍｉｓｓｉｎｇ ｖａｌｕｅ ｅｓｔｉｍａ— ｔｉｏｎ ｏｆｒ ｍｉｘｅｄ—ａｔｔｉｒｂｕｔｅ ｄａｔａ ｓｅｔｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，２３（１）：１１０－１２１． ［１ １］ Ｚｈａｏ Ｙａｎｅｈａｎｇ， Ｚｈａｎｇ Ｓｈｉｃｈａｏ． Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｍｅｎｓｉｏｎ·ｒｅｄｕｃｔｉｏｎ ｆｒａｍｅｗｏｒｋ ｏｒ ｆｅｃｅｎｔ．ｒｂｉａｓｅｄ ｔｉｍｅ ｓｅｒｉｅｓ ａｎａｌｙｓｉｓ『Ｊ １．ＩＥＥＥ Ｔｒａｎｓ ｏｎ ［１９］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｚｈａｎｇ Ｌｅｉ，Ｈｕａｎｇ Ｚｉ．Ａ ｓｐａｒｓｅ ｅｍｂｅｄｄｉｎｇ ａｎｄ ｌｅｓａｔ ｖａｒｉｎｃａｅ ｅｎｃｏｄｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｈａｓｈｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，２０１４，２３（９）：３７３７－３７５０． Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，１８（２）：２３１—２４４． ［２０］Ｚｈｕ Ｘｉａｏｆｅｎｇ，Ｓｕｋ Ｈｅｕｎｇ·ＩＩ，Ｓｈｅｎ Ｄｉｎｇｇｎｇ．Ａ ｎｏａｖｅｌ ｍａｔｉｒｘ—ｓｉｍｉ— ｌａｒｉｔｙ ｂａｓｅｄ ｌｏｓｓ ｆｕｎｃｔｉｏｎ ｆｏｒ ｊｏｉｎｔ ｒｅｇｒｅｓｓｉｏｎ ａｎｄ ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｉｎ ＡＤ ［１２］Ｑｉｎ Ｙｏｎｇｓｏｎｇ，Ｚｈａｎｇ Ｓｈｉｃｈａｏ，Ｚｈｕ Ｘｉａｏｆｅｎｇ，ｅｔ ａ１．Ｓｅｍｉ—ｐａｒａｍｅｔｒｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆｒ ｍｉｓｓｉｎｇ ｄａｔａ ｉｍｐｕｔａｔｉｏｎ［Ｊ］．Ａｐｐｌｉｅｄ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００７，２７（１）：７９—８８． ｄｉａｇｎｏｓｉｓ［Ｊ］．Ｎｅｕｒｏｌｍａｇｅ，２０１４，１００（１Ｏ）：９１－１０５． ［２１］Ｌｉｕ Ｗｅｉ，Ｈｅ Ｊｕｎｆｅｎｇ，Ｃｈａｎｇ Ｓｈｉｈｆｕ．Ｌａｒｇｅ ｇｒａｐｈ ｃｏｎｓｔｕｃｔｒｉｏｎ ｆｏｒ ｓｃａｌａｂｌｅ ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ［Ｃ］／／Ｐｒｃ ｏｆ ｏｈｅ ２７ｔｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ．２０１０． ［１３］Ｗｕ Ｘｉｎｄｏｎｇ，Ｚｈａｎｇ Ｓｈｉｃａｏ．Ｓｙｎｔｈｅｓｉｚｉｎｇ ｈｉｇｈ—ｒｆｅｑｕｅｎｃｙ ｒｕｌｅｓ ｆｒｏｍ ｄｉｆｅｒｅｎｔ ｄａｔａ ｓｏｕｒｃｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔｅ Ｅｎｇｉｎｅｅｒｉｎｇ，２００３，１５（２）：３５３－３６７． ［２２］Ｗｕ Ｘｉｎｄｏｎｇ，Ｚｈａｎｇ Ｃｈｅｎｇｑｉ，Ｚｈａｎｇ Ｓｈｉｃｈａｏ．Ｅｆｉｃｆｉｅｎｔ ｍｉｎｉｎｇ ｏｆ ｂｏｔｈ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｉｎ－ ｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ，２００４，２２（３）：３８１—４０５． ［１４］Ｚｈａｎｇ Ｔｉｎ，Ｒａｍａｋａｒｉｓｈｎａｎ Ｒ，Ｌｉｖｎｙ Ｍ．ＢＩＲＣＨ：ａｎ ｅｆｉｆｃｉｅｎｔ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｏｆｒ ｖｅｙｒ ｌｒａｇｅ ｄａｔｂａａｓｅｓ［Ｊ］．ＡＣＭ ＳＩＧＭＯＤ Ｒｅ－ ｃｏｒｄ，１９９９，２５（２）：１０３·１１４． ［２３］Ｚｈａｎｇ Ｓｈｉｃｈａｏ，Ｑｉｎ Ｚｈｅｎｘｉｎｇ，Ｌｉｎｇ Ｃ Ｘ。ｅｔ ａ１．Ｍｉｓｓｉｎｇ ｉｓ ｕｓｅｆｕｌ： ｍｉｓｓｉｎｇ ｖａｌｕｅｓ ｉｎ ｃ０ｓｔ—ｓｅｎｓｉｔｉｖｅ ｄｅｃｉｓｉｏｎ ｔｉ ｓ［Ｊ］．１ＥＥＥ Ｔｒａｎｓ ｏｎ ＫｎｏｗＩｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｎｎｇ，２ｏ０５，１７（１２）：１６８９—１６９３． ［１５］Ｅｓｔｅｒ Ｍ，Ｋｒｉｅｇｅｌ Ｈ Ｐ，Ｓａｎｄｅｒ Ｊ，ｅｔ ａ１．Ａ ｄｅｎｓｉ￣一ｂａｓｅｄ ｌａｇｏｒｉｔｈｍ ｆｏｒ ｄｉｓｃｏｖｅｉｒｎｇ ｃｌｕｓｔｅｍ ｉｎ ｌｒａｇｅ ｓｐａｔｉａｌ ｄａｔａｂａｓｅｓ ｗｉｔｈ ｎｏｉｓｅ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌａｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．１９９６：２７４－２８７． ［２４］ ｌ ｕ，ｓｈａｎｎａ Ａ．Ａ ｎｅａｒｅ８ｔ ｎｅｉｇｈｂｏｒ ｂｏ０ｔｓｔ糟ｐ ｆ０ｒ ｒｅ８ａｒｎｐｌｉｎｇ ｈｙｄｒｏ－ ｌ０ｇｉｃ ｔｉｍｅ ｓｅｒｉｅｓ［Ｊ］．Ｗａｔｅｒ Ｒｅｓｏｕｒｃｅ Ｒｅｓｅａｒｃｈ，１９９６，３２（３）： ６７９．６９３．