基于K-Means聚类算法的上网监测数据分析方法研究_开题报告

随着互联网技术的飞速发展，特别是机器人、人工智能的应用，人们能够获取的信息呈现了爆炸式的增长。几年前我们觉得一个亿的数据量已经很大了，但现在几十亿、几百亿的数据量都很常见。面对互联网时代的海量信息，如何从中提取出我们需要的有价值的数据，如何对这些庞杂的数据进行分类，并找出其中的异常信息等等。国内外很多大公司都投入大量的人力物力研发机器学习算法，以期能够从“堆积如山”的信息中找出“金子”。

机器学习概述

机器学习很火，我们日常生活中经常看到机器学习的应用，例如机场中使用人脸识别系统进行身份验证、百度的无人驾驶汽车、网上商店的个性化营销推广(网上浏览了某件商品但没买，过几天打开不同网站将看到那件商品的推荐广告)等等。

什么是机器学习？机器学习是一个计算机程序，针对某个特定的任务，从经验中学习，并且越做越好。 机器学习一般可以分为两类：

无监督学习(unsupervised learning)：对不带任何标签的数据特征进行建模，通常被看成是一种“让数据自己介绍自己”的过程。这类模型包括聚类（clustering）任务和降维（dimensionality reduction）任务。聚类算法可以将数据分成不同的组别，而降维算法追求用更简洁的方式表现数据。

聚类算法概述

聚类（clustering）是指将数据集划分成组的任务，这些组叫作簇（cluster），其目标是划分数据，使得一个族内的数据点非常相似且不同簇内的数据点非常不同。聚类算法为每个数据点分配（或预测）一个数字，表示这个点属于哪个簇。

因此人类天生具有这种归纳总结能力，能够把相似的事物放到一起作为一类事物进行认识，它们之间可以有彼此的不同，这个不同是有一个“限度”，只要在这个限度内，特征稍有区别无关大碍，它们仍然是这一类事物。当然在这一类事物的内部，同样有这种现象，一部分个体之间比较相似，而另一部分个体之间比较相似，这两部分个体彼此之间能够被明显认知到差异，那么这个部分的事物又会在大类别的内部重新划分成两个不同的部分进行认知。例如从鱼的生活环境可以分为淡水鱼和海水鱼，其中淡水鱼又可以分为鲤鱼草鱼等等。

K-Means聚类算法概述

聚类算法有很多种，K-Means算法是其中一种，它被广泛应用到各个领域。

K-Means聚类算法也称为快速聚类法，它是典型的基于距离的非层次聚类算法，在最小化误差函数的基础上将数据划分为预定的类数K，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。

K-Means算法以 k为参数，把 n个对象分成 k个簇，使簇内具有较高的相似度，而簇间的相似较低。

其处理过程如下：

1. 从N个样本数据中随机选取K个对象作为初始的聚类中心；

2. 分别计算每个样本到各个聚类中心的距离，将对象分配到距离最近的聚类中；

3. 所有对象分配完成后，重新计算K个聚类的中心；

4. 与前一次计算得到的K个聚类中心比较，如果聚类中心发生变化，转过程2，否则转过程5；

5. 当质心不发生变化时停止并输出聚类结果。

聚类的结果可能依赖于初始聚类中心的随机选择，可能使得结果严重偏离全局最优分类。在实践中，为了得到较好的结果，通常选择不同的初始聚类中心，多次运行K-Means算法。

K-Means 聚类算法是由 Steinhaus 1955年、Lloyd 1957年、Ball &Hall 1965年、McQueen 1967年分别在各自的不同的科学研究领域独立的提出。K-Means聚类算法被提出后，在不同的学科领域被广泛研究应用，并发展出大量不同的改进算法。例如针对K-Means算法通常会在获取一个局部最优值时终止，且只适合于数据型数据的聚类问题，Kaufman和Rousseeuw分别提出了K中心点算法PAM和CLARA；Huang也针对K-Means算法存在的不足之处进行改进，提出了一种适合于分类属性数据的K-Modes算法，等等。

国内对K-Means聚类算法也有很深入的研究，孔锐、张国宣等人通过将核学习思想应用到K-Means聚类算法中，提出了一种核K-Means聚类算法，进而提高了K-Means算法的运算速度；徐义峰、陈春明等人针对K-Means聚类算法中有关随机选择初始聚类中心的缺陷，提出了一种新的基于数据样本分布选取初始聚类算法中心的方法，进而提高了K-Means算法的聚类准确度。杨博、刘大有等人对复杂网络的结构进行分析，将聚类算法应用到复杂网络的特殊结构，实现对复杂网络的聚类分析；姚清耘、刘功申等人基于向量空间模型提出的针对于文本数据的聚类分析算法。

虽然K-Means算法被提出已经超过50年了，但因其容易实施、简单、高效、成功的应用案例和经验，目前仍然是应用最广泛的划分聚类算法之一。

研究方向

本文主要应用K-Means聚类算法，分析某个市的所有网吧在半个月时间内的上网记录数据，从中找出一些规律，为上级领导部门制定政策提供参考依据。例如分析哪个年龄段最喜欢上网？80后、90后、还是00后？这些年龄段的人上网有什么特点，比如是上网频繁高但每次上网时间短？还是上网次数少但每次上网时间长？分析一天时间每个时间点每个网吧的上网人员次数，与经纬度度结合，制作成地图热力，用来显示一天之内，上网人员的迁徙情况，如果发现某个时点某个地区的人员特别多，是不是出现了大量人群聚集的情况？针对大量人群聚集，是否需要上级领导部门多安排警力预防发生某些群体性事件？等等

^范文提纲

一、机器学习与聚类

（一）、机器学习概述

（二）、聚类算法概述

（三）、聚类算法分类

二、K-Means概述

（一）、K-Means含义

（二）、K-Means国内外现状

（三）、K-Means算法的实现

三、K-Means在上网监测数据分析中的应用

（一）、上网监测数据说明

（二）、最佳上网时间

（三）、上网时长调查

（四）、最爱上网个人评选

（五）、最佳网吧评选

四、降维及数据预测

（一）、降维概述

（二）、爱上网的XX后

（三）、不同人群上网时长研究

（四）、上网人员迁徙情况

（五）、数据预测

五、致谢

参考文献

[1]高扬,卫峥.白话大数据与机器学习[M].北京:机械工业出版社,2016:105-110

[2]何宇健.Python与机器学习实战[M].北京:电子工业出版社,2017

[3]Jake VanderPlas. Python数据科学手册[M].北京:人民邮电出版社,2018

[4]Sarah Guido. Python机器学习基础教程[M].北京: 人民邮电出版社,2018

[5]黄永昌.scikit-learn机器学习:常用算法原理及编程实战[M]. 北京:机械工业出版社,2018

[6]Alexander T.Combs.Python机器学习实践指南[M].北京:人民邮电出版社,2017

[7]周志华.机器学习[M]北京:清华大学出版社,2016

[8]范淼.Python机器学习及实践—从零开始通往Kaggle竞赛之路北京:清华大学出版社,2016

[9]杉山将.图解机器学习[M].北京:人民邮电出版社,2015

[10]张良均,王路.Python数据分析与挖掘实战[M].北京:机械工业出版社,2015

[11]Anil K J. Data clustering:50years beyond K-Means[M].Pattern Recognition Letters , 2010, 31

[12]孔锐,张国宣,施泽生,郭立:基于核的K-均值聚类[J]计算机工程,Vol.30,No.11,June 2014

[13] 徐义峰,陈春明,徐云青:一种改进的K-均值聚类算法[J]Computer Applications and Software,Vol.25,No.3,Mar. 2008

[14] Leonard Kaufman, Peter J. Rousseeuw. Clustering Large Applications(Program CLARA)[J]Published Online,Chapter 3, 2008

[15]Huang Z., Ng, MKP. A Fuzzy k-modes Algorithm for Clustering Categorical Data. [J]IEEE Transactions on Fuzzy Systems, 1999， 446-452

[16]杨博，刘大有等:复杂网络聚类方法[J]Journal of Software, Vol.20, No.1, January 2009

[17]姚清耘，刘功申，李翔:基于向量空间模型的文本聚类算法[J]Computer Engineering, Vol.34, No.18, September 2008