论文部分内容阅读
摘要：本文主要围绕K均值聚类算法进行研究，详细分析了K均值算法的特点，尤其是其不足之处。并针对其现存的几个明显不足，提出了可以优化的思路和基于该思路的改进方法。力求在现基础上更进一步提高K均值算法的准确率和稳定性。
关键词：K均值算法；算法优化；无线传感器网络；植物生长条件
中图分类号：TP18 文献识别码：A 文章编号：1001-828X（2016）002-000-02
在这信息大爆炸的“大数据”时代，全球的信息量每秒都在高速增长。仅据我国的数据统计，2014年全国出版的图书种类就有448431种，期刊9966种，报纸1912种[1]。而数据挖掘（DataMining）技术在这一信息时代显得尤为关键。它是指在大型数据存储库中，自动地发现有用信息的过程[2]。本文着重分析了聚类分析中最为经典的算法——K均值（K-means）聚类算法，它是于1957年由Lloyd首次在文献中提出的[3]，具有简单、高效的特性。但其本身也存在着明显的几个缺陷。比如：聚类数目对K均值聚类算法过于依赖，对聚类结果的影响太大。还有对于初始中心点的选取非常敏感，算法很容易陷入局部最优，而非全局最优等。针对它的几点不足，本文一一进行了分析改进。针对初始中心点的选取问题可以采用增量更新中心法，大大减小了因选取不当带来的误差和影响；对K值的确定可利用数据采样法选择一个最优解。K均值聚类算法通过改进后都有效的改善了它的分类性能，取得了较高的分类准确率和稳定性。并且在其具体应用上得到了验证。
一、K均值聚类算法
K均值算法的具体流程如下：
输入：数据集x={x1， x2， ..xn}，聚类数目k；
输出：k个类簇cj， j=1，2，..k。
[stepl]令I=1，随机选取k个数据点作为k个类簇的初始簇中心，mj（I）， j=1，2，..k；
[step2]计算每一个数据点与这k个簇中心的距离d（xi， mj， （I）），i=1，2，..n，j=1，2，..k，如果满足d（xi， mj， （I））=min{d（xi， mj， （I））， j=1，2，..k}，则xi∈Cj；
[step3]计算k个新的聚类中心mj（I 1）= j=1，2，..k；
[step4]判断：若mj（I 1）≠mj（I）， j=1，2，..k，则I=I 1，返回至step2；否则，算法结束[4]。
由以上步骤可以看出，K均值算法的实现比较简单，并且在一定的数据量下，运行效率是非常高的。然而，K均值算法也存在着一些明显的不足还有待改进：
第一，对于时间复杂性和空间复杂性有要求[5]。K均值聚类算法每次迭代过程都要调整簇中心及重新分配数据点，因此当数据量比较大时并不适用。
第二，聚类数K值需事先给出，聚类效果没有保证。K均值算法的最初步骤就是要确定聚类的个数K[6]，而往往获取K值的代价要比K均值聚类算法的代价大得多。
第三，聚类结果易受噪声和离群点影响。噪声和离群点的存在会严重干扰中心的计算，它们所带来的影响也是不容小觑的。
第四，过度依赖簇中心的选取。K均值算法中首先需要根据初始聚类中心来确定一个初始划分，使得K均值算法对初始簇中心点的严重依赖性。
二、K均值聚类算法的优化
针对以上问题，本文提出了一种新的改进方法。为了避免离群点影响结果，首先应当处理好离群点。但是处理它不代表删掉它。通过预处理，移除具有异乎寻常影响的点，往往可以有效减少对簇中心选择的判断失误。比如，删除过小的聚簇，或者将彼此接近的一些聚簇合并成一个更大的聚簇[7]。
其次，鉴于簇中心的选择相当关键，为了减小由于簇中心选取不当带来的误差，可以在点到簇的每一次指派之后，都适当的增加质心的数量，更新原来的质心。原始的算法规则是所有的点都指派到簇中以后再更新簇中心，这样操作的局限就在于不能够及时的更正由于质心不准确而引起聚类效果不佳的影响。而改进后的算法能够及时调整质心，增量更新，并且可以调整点的相对权值。
通过在以上两方面的优化之后，再利用数据采样方法，从数据集中抽样若干数量的数据样本，用不同的K值来进行K均值算法聚类，然后选取结果最优的K值作为此算法的初始簇数目，最后再针对所有的数据执行最后的K均值算法聚类。这将对聚类的准确率有着明显的帮助。
三、应用
数据挖掘在农业环境监测和植物生长条件完善方面起到非常重要的作用。利用无线传感器网络获取植株的具体信息数据，包括：环境温度，空气湿度，CO2浓度，土壤PH，风速等[8]。收集到的数据再通过k均值算法得到一个聚类结果，从结果中再分析适合植物生长的各方面的条件因素信息，以此来改善植物生长环境和条件。
数据采集整理过后，根据第2节介绍的算法步骤，输入：n个数据对象集合Xi，和指定的聚类数目K。输出：K个聚类中心和K个聚类集合Cj。通过反复迭代，最终用15次迭代运算将所有数据分为4个聚类簇。然后根据人工的经验将不同的簇分为优、良、中、差四等生长环境[9]。其中24%的数据表示优，30%表示良，28%的表示中，18%的表示差。聚类为优的状态可知道，该植物适合温度在白天24-26度，在空气湿度都比较高的时候，空气中的二氧化碳浓度为300微升/升，光照在3万到4万雷克斯，PH值在6-7之间，风速以0.47m/s左右为适合。
下面用本文提出的优化算法再次进行聚类分析，具体步骤如下：
[step1]初始化：选择4个代表样本作为初始聚类中心。
[step2]根据传感器收集的数据类型，计算簇的均值，根据均值将数据分为不同簇。
[step3]重新计算簇中心均值，将数据对象重新分配到最相似的聚类簇中。并在点到簇的每一次指派之后，都适当的增加簇中心的数量，更新原来的簇中心。 [step4]计算新的聚中心：更新簇均值，重复以上步骤2和3，直到聚类不再发生变化，或是达到最大迭代次数，那么就算迭代完成。
此算法在每次循环中，不断修改中心点，每次的循环的中心点记录下来。当本次循环的聚类中心点与下次循环聚类中心点的值相同，就退出。
由上表可知，优化后的算法与前次结果基本一致，但是优化后算法在得到最终结果的过程中只进行了9次迭代，大大减少了原本算法的迭代次数。减少了工作量和时间空间的复杂度，适合农业中大数据量的分析。
四、总结
聚类分析是数据挖掘的重要技术和手段之一，是数据挖掘领域中的研究热点之一。K均值聚类算法作为一个发展最早、并且应用最广的聚类分析算法，因其具有算法思想简单、易于实现等优点已经在众多研究领域得到广泛而成功的应用。但是 K均值聚类算法仍然存在一些不足可以完善的地方。
本文就 K均值聚类算法的四点明显缺陷进行了分析，通过研究分析后提出了优化方法。优化后的K均值算法可以应用到农业领域等各个领域，本来举了一个适用在探究植物生长条件的例子，由聚类结果可以知道一个大致的数据范围对植物生长是比较好的，因此，尽量让那些条件聚集到该条件的变量范围，采取加温，增补二氧化碳浓度，增加光照强度的要求等等，让植物在最佳条件下得到培育。
参考文献：
[1]中华人民共和国国家统计局. 中国统计年鉴—2015[M]. 北京：中国统计出版社，2015.
[2]Pang-Ning Tan，Michael Steinbach，Vipin Kumar. 数据挖掘导论[M]. 北京：人民邮电出版社，2011.
[3]董骐瑞. k-均值聚类算法的改进与实现[D]. 长春：吉林大学，2015.
[4]蒋帅. k-均值聚类算法研究[D]. 西安：陕西师范大学，2010.
[5]邵峰晶，于忠清. 数据挖掘原理与算法[M]. 北京：中国水利水电出版社，2003.
[6]欧陈委. K-均值聚类算法的研究与改进[D]. 长沙：长沙理工大学，2012.
[7]Xindong Wu，Vipin Kumar. 数据挖掘的十大算法[M]. 北京：清华大学出版社，2013.
[8]张辉宜，孙倩文，袁志祥等. 基于无线传感器网络的温湿度监控系统设计[J]. 计算机技术与发展，2014（11）：246-249.
[9]李春辉. 大数据在农业物联网中的应用研究[D]. 齐齐哈尔：齐齐哈尔大学，2015.
作者简介：罗 岚（1993–），女，汉族，湖南邵阳人，西南民族大学计科学院，研究方向：物联网方向。
关键词：K均值算法；算法优化；无线传感器网络；植物生长条件
中图分类号：TP18 文献识别码：A 文章编号：1001-828X（2016）002-000-02
在这信息大爆炸的“大数据”时代，全球的信息量每秒都在高速增长。仅据我国的数据统计，2014年全国出版的图书种类就有448431种，期刊9966种，报纸1912种[1]。而数据挖掘（DataMining）技术在这一信息时代显得尤为关键。它是指在大型数据存储库中，自动地发现有用信息的过程[2]。本文着重分析了聚类分析中最为经典的算法——K均值（K-means）聚类算法，它是于1957年由Lloyd首次在文献中提出的[3]，具有简单、高效的特性。但其本身也存在着明显的几个缺陷。比如：聚类数目对K均值聚类算法过于依赖，对聚类结果的影响太大。还有对于初始中心点的选取非常敏感，算法很容易陷入局部最优，而非全局最优等。针对它的几点不足，本文一一进行了分析改进。针对初始中心点的选取问题可以采用增量更新中心法，大大减小了因选取不当带来的误差和影响；对K值的确定可利用数据采样法选择一个最优解。K均值聚类算法通过改进后都有效的改善了它的分类性能，取得了较高的分类准确率和稳定性。并且在其具体应用上得到了验证。
一、K均值聚类算法
K均值算法的具体流程如下：
输入：数据集x={x1， x2， ..xn}，聚类数目k；
输出：k个类簇cj， j=1，2，..k。
[stepl]令I=1，随机选取k个数据点作为k个类簇的初始簇中心，mj（I）， j=1，2，..k；
[step2]计算每一个数据点与这k个簇中心的距离d（xi， mj， （I）），i=1，2，..n，j=1，2，..k，如果满足d（xi， mj， （I））=min{d（xi， mj， （I））， j=1，2，..k}，则xi∈Cj；
[step3]计算k个新的聚类中心mj（I 1）= j=1，2，..k；
[step4]判断：若mj（I 1）≠mj（I）， j=1，2，..k，则I=I 1，返回至step2；否则，算法结束[4]。
由以上步骤可以看出，K均值算法的实现比较简单，并且在一定的数据量下，运行效率是非常高的。然而，K均值算法也存在着一些明显的不足还有待改进：
第一，对于时间复杂性和空间复杂性有要求[5]。K均值聚类算法每次迭代过程都要调整簇中心及重新分配数据点，因此当数据量比较大时并不适用。
第二，聚类数K值需事先给出，聚类效果没有保证。K均值算法的最初步骤就是要确定聚类的个数K[6]，而往往获取K值的代价要比K均值聚类算法的代价大得多。
第三，聚类结果易受噪声和离群点影响。噪声和离群点的存在会严重干扰中心的计算，它们所带来的影响也是不容小觑的。
第四，过度依赖簇中心的选取。K均值算法中首先需要根据初始聚类中心来确定一个初始划分，使得K均值算法对初始簇中心点的严重依赖性。
二、K均值聚类算法的优化
针对以上问题，本文提出了一种新的改进方法。为了避免离群点影响结果，首先应当处理好离群点。但是处理它不代表删掉它。通过预处理，移除具有异乎寻常影响的点，往往可以有效减少对簇中心选择的判断失误。比如，删除过小的聚簇，或者将彼此接近的一些聚簇合并成一个更大的聚簇[7]。
其次，鉴于簇中心的选择相当关键，为了减小由于簇中心选取不当带来的误差，可以在点到簇的每一次指派之后，都适当的增加质心的数量，更新原来的质心。原始的算法规则是所有的点都指派到簇中以后再更新簇中心，这样操作的局限就在于不能够及时的更正由于质心不准确而引起聚类效果不佳的影响。而改进后的算法能够及时调整质心，增量更新，并且可以调整点的相对权值。
通过在以上两方面的优化之后，再利用数据采样方法，从数据集中抽样若干数量的数据样本，用不同的K值来进行K均值算法聚类，然后选取结果最优的K值作为此算法的初始簇数目，最后再针对所有的数据执行最后的K均值算法聚类。这将对聚类的准确率有着明显的帮助。
三、应用
数据挖掘在农业环境监测和植物生长条件完善方面起到非常重要的作用。利用无线传感器网络获取植株的具体信息数据，包括：环境温度，空气湿度，CO2浓度，土壤PH，风速等[8]。收集到的数据再通过k均值算法得到一个聚类结果，从结果中再分析适合植物生长的各方面的条件因素信息，以此来改善植物生长环境和条件。
数据采集整理过后，根据第2节介绍的算法步骤，输入：n个数据对象集合Xi，和指定的聚类数目K。输出：K个聚类中心和K个聚类集合Cj。通过反复迭代，最终用15次迭代运算将所有数据分为4个聚类簇。然后根据人工的经验将不同的簇分为优、良、中、差四等生长环境[9]。其中24%的数据表示优，30%表示良，28%的表示中，18%的表示差。聚类为优的状态可知道，该植物适合温度在白天24-26度，在空气湿度都比较高的时候，空气中的二氧化碳浓度为300微升/升，光照在3万到4万雷克斯，PH值在6-7之间，风速以0.47m/s左右为适合。
下面用本文提出的优化算法再次进行聚类分析，具体步骤如下：
[step1]初始化：选择4个代表样本作为初始聚类中心。
[step2]根据传感器收集的数据类型，计算簇的均值，根据均值将数据分为不同簇。
[step3]重新计算簇中心均值，将数据对象重新分配到最相似的聚类簇中。并在点到簇的每一次指派之后，都适当的增加簇中心的数量，更新原来的簇中心。 [step4]计算新的聚中心：更新簇均值，重复以上步骤2和3，直到聚类不再发生变化，或是达到最大迭代次数，那么就算迭代完成。
此算法在每次循环中，不断修改中心点，每次的循环的中心点记录下来。当本次循环的聚类中心点与下次循环聚类中心点的值相同，就退出。
由上表可知，优化后的算法与前次结果基本一致，但是优化后算法在得到最终结果的过程中只进行了9次迭代，大大减少了原本算法的迭代次数。减少了工作量和时间空间的复杂度，适合农业中大数据量的分析。
四、总结
聚类分析是数据挖掘的重要技术和手段之一，是数据挖掘领域中的研究热点之一。K均值聚类算法作为一个发展最早、并且应用最广的聚类分析算法，因其具有算法思想简单、易于实现等优点已经在众多研究领域得到广泛而成功的应用。但是 K均值聚类算法仍然存在一些不足可以完善的地方。
本文就 K均值聚类算法的四点明显缺陷进行了分析，通过研究分析后提出了优化方法。优化后的K均值算法可以应用到农业领域等各个领域，本来举了一个适用在探究植物生长条件的例子，由聚类结果可以知道一个大致的数据范围对植物生长是比较好的，因此，尽量让那些条件聚集到该条件的变量范围，采取加温，增补二氧化碳浓度，增加光照强度的要求等等，让植物在最佳条件下得到培育。
参考文献：
[1]中华人民共和国国家统计局. 中国统计年鉴—2015[M]. 北京：中国统计出版社，2015.
[2]Pang-Ning Tan，Michael Steinbach，Vipin Kumar. 数据挖掘导论[M]. 北京：人民邮电出版社，2011.
[3]董骐瑞. k-均值聚类算法的改进与实现[D]. 长春：吉林大学，2015.
[4]蒋帅. k-均值聚类算法研究[D]. 西安：陕西师范大学，2010.
[5]邵峰晶，于忠清. 数据挖掘原理与算法[M]. 北京：中国水利水电出版社，2003.
[6]欧陈委. K-均值聚类算法的研究与改进[D]. 长沙：长沙理工大学，2012.
[7]Xindong Wu，Vipin Kumar. 数据挖掘的十大算法[M]. 北京：清华大学出版社，2013.
[8]张辉宜，孙倩文，袁志祥等. 基于无线传感器网络的温湿度监控系统设计[J]. 计算机技术与发展，2014（11）：246-249.
[9]李春辉. 大数据在农业物联网中的应用研究[D]. 齐齐哈尔：齐齐哈尔大学，2015.
作者简介：罗 岚（1993–），女，汉族，湖南邵阳人，西南民族大学计科学院，研究方向：物联网方向。