随着Internet的大规模普及、信息处理技术和数据处理技术的发展及企业信息化程度的提高，各种网络资源以爆炸式速度迅猛增长，现存的网络资源以数据库存储的形式为主，数据的形式以半结构化和结构化的形式存储。但是在网络技术迅猛发达的今天，数据库中的数据量更是以惊人的速度发展，就形成了数据量很大而对于有用的信息的发掘和利用成为一大难题的现象，也成为现在研究的热点问题。

如何从激增的数据背后找到有价值的信息，并从中提取出知识己经成为目前数据挖掘和知识管理等研究领域的重要课题。而数据挖掘技术正是解决这一课题的重要方法。其中聚类(clustering)是数据挖掘三大领域(关联规则，聚类，分类)之一，是分析数据并从中发现有用信息的一种手段。它将数据对象的集合分组成为由类似的对象组成的多个簇。同一个簇中的对象彼此相似，不同簇中的对象彼此相异。对象间相似度是根据描述对象的属性来进行计算的。距离是经常采用的度量方式，从机器学习的角度来看，聚类属于无指导学习，与分类不同，聚类和无指导学习不依赖于预先定义的类和带标号的类的训练实例。

聚类分析具有广泛的应用价值，如市场分割、模式识别、生物学研究、空间数据分析、web文档分类。除此之外，聚类分析还可以作为独立的数据挖掘工具，来了解数据发布，或者作为其他数据挖掘算法的预处理步骤。

聚类已经被广泛地研究了许多年，迄今为止，研究人员己经提出了许多聚类算法，大体上这些算法可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。其中，K-means属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数作为聚类准则。主要优点是算法简单、快速而且能有效地处理大数据集。

1.2 国内外研究现状

现有的聚类算法虽然众多，但它们都或多或少地存在着一些缺陷和不足。迄今为止没有任何一种聚类算法可以对于任何一类数据集，针对任何一种应用要求都能够达到高质量的聚类效果。目前对聚类算法的探讨和改进是国内外专家、学者的热门话题。聚类过程的本质是一个优化的过程，通过一种迭代运算使得系统的目标函数达到一个最优解。

K-均值算法是聚类分析中基于划分方法的一种经典算法，思想简单，效率高，应用领域相当广泛，比如文档聚类、图象分割等应用。K-means算法从提出到现在也经历了一个很长的发展阶段，由于其经典性、可应用性强、快速和简单等特点，人们进行了大量的研究。K-means算法的应用主要体现在一下几个方面：

·K-means算法在高维数据中的应用；

·K-means算法在流式数据中的应用；

·K-means算法在部分信息数据中的应用；

·K-means算法在有偏数据中的应用。

1997年，Mitchell就如何以混合模型算法的形式，对基于平方欧几里德距离的K—均值算法进行了研究分析。2000年，Steinbach，Karypis和Kumar提出了二分K—均值算法，该算法进行对整个数据集进行划分，知道用户设定类的个数，该算法聚类效果和计算效率都比较好，还一定程度解决了原k-means算法选取初始点方法所产生的问题。2002年，Dhillon，Guan和Kogan提出了局部搜索策略“first variation”，改进了基于余弦相似度的K-均值算法。2003年，Dhillon等提出了辅助文本分类的文本属性聚类方法和基于信息理论的联合聚类方法，他是从信息理论的角度对基于KL散度的K-均值算法进行研究。由于k-means算法对孤立点很敏感，初始点的选择该算法的影响比较大，因此人们近些来在这些方面也做了大量的研究。

k-means算法在经过长期的发展过程中，虽然得到了很多的改进，对其缺点和优点人们也进行了大量的研究，本文将重点介绍K-means算法，并分析其存在的优缺点，最后提出了一种改进的K-means算法。

2.1 聚类分析概述

数据挖掘技术出现的时间不长，相应聚类方面的研究时间也不长，但是其发展非常迅速，在工程中的应用，特别是在搜索引擎中的应用非常广泛，聚类的理论和技术迅速增加。各种经典聚类算法相应出现，在聚类过程中，每种聚类算法表现出一定的缺点和局限性，针对这些问题，人们不断的对聚类算法的再改进，同时提出相应的理论作为改进的基础。比如提出孤立点的问题，计算样本间距离的不同计算方法，聚类结果质量的评定等。

K-means算法作为一种基于划分的经典算法，开始只是提出了一种聚类过程的思想，当然存在很多缺点和局限性。从提出到现在的整个发展过程中，人们针对它存在的问题，在原k_means算法的基础上提出了大量的改进算法。所有的改进算法，大部分都是把其他的聚类方法，比如，基于层次方法、基于密度方法等，应用到K-means的算法步骤当中，而改进之后，也只是解决某一方面的问题。

现在随着网络用户的快速增加，数据信息的膨胀速度更是惊人，那么在聚类过程中对大数据量的聚类效果和时间也成为聚类研究非常关心的问题，人们也提出了一些解决办法，但是真正解决还需时间。针对K-means算法，改进之后会出现用户输入参数增加，聚类数据形状要求严格等问题现在一直没有得到很好的解决。而最关键的用户输入参数直接影响聚类的效果，如何解决这一问题，还需要进一步研究。

聚类分析是数据挖掘的一个重要领域，而聚类算法是研究的核心。聚类是将没有类别标记的对象，根据其特征，将其划分为不同的数据类。目的是使得属于同一类别的个体之间的距离尽可能的小(很高的相似度)，而不同类别上的个体间的距离尽可能的大(相似度尽可能的小)。聚类方法包括统计、机器学习方法、神经网络方法和面向数据库的方法。

 

 传统K-means聚类算法概述

 

根据K-means算法的基本流程，这里将对传统的K-means算法做简单的仿真，这里，仿真所使用的数据为一组空间坐标点，其坐标点的分布如下图所示：

图3.2 初始化产生的数据分布1

这里，初始化的数据由预先设置的三组数据组成，即初始化的数据集聚类如下图所示：

图3.3 初始化产生的数据分布2

然后，我们将这组数据输入到K-means算法进行聚类分析，得到的分类结果如下所示：

图3.4 聚类分析之后的数据集

    从图3.4的仿真结果可知，初始的随机数基本能够正确的分成了3类，和初始化输入的数据种类相似。每一类的识别率达到了80%左右。

一般而言，K-均值聚类算法存在的主要问题有以下几个方面：

·K-均值聚类算法中聚类个数k需要被预先给定。聚类个数k值的选定是很难估计的，很多的时候，我们事先并不知道给定的数据集应该分成多少类才最合适。

图3.5 K值不确定时的错误聚类

    如图3.5所示，假设有三类数据，但是当K值无法确定的时候，假设取K值为2，那么其聚类结果则如图3.5右图一样，显然，这种聚类结果并不是最佳的聚类结果，因此K值的确定，对聚类结果有着较大的影响。

·算法对初始值的选取依赖性极大以及算法常陷入局部极小解。K-均值算法首先随机地选取k个点作为初始聚类中心，再利用迭代的重定位技术寻找最优聚类中心直到算法收敛。因此，初始值的不同可能导致算法聚类效果的不稳定。

(a).初始聚类中心点1

(b).初始聚类中心点2

图3.6 不同初始聚类中心点的聚类分析结果

    如图3.6所示，对于不同的聚类中心点的选取，会导致最后的聚类结果的不同。

·将簇的质心作为聚类中心进行新一轮聚类计算，将导致远离数据密集区的孤立点和噪声点会导致聚类中心偏离真正的数据密集区，所以K-均值算法对噪声点和孤立点非常敏感。

图3.7 孤点对聚类中心的影响

  从图3.7的仿真结果可知，如果存在孤点的时候，会对实际的聚类中心点有较大的影响，如上图红色数据的中心点。

·对于大数据量，算法的开销非常大。从K-均值聚类算法流程可以看出，该算法需要不断地进行样本分类迭代调整，不断地计算调整后的新的聚类中心。因此，当数据集的数量非常大时，算法的时间开销也是相当惊人的的。所以需要对算法的时间复杂度进行分析，改进，

以提高算法的应用范围。

    根据前一章提出的改进办法，本章将重点使用改进后的算法数据进行仿真并对比改进前后的K-means算法的聚类结果。

人为模拟产生3类混合数据源作为测试源，测试结果如下所示：

图3.8 去孤点仿真

    从图3.8可知，通过改进后的K-means算法，可以有效去除一些比较明显的孤点，从而大大增加了聚类中心值。

图3.9 未设定K=3，软件自动识别最佳类别为3

图3.9可知，在没有预先设定K的情况下，通过改进后的K-means算法，可以自动识别到最佳的类别数为3，在MATLAB的命令窗口可以看到具体的运行结果：

人为模拟产生4类混合数据源作为测试源，测试结果如下所示：

图3.10 去孤点仿真

图3.11 未设定K=4，软件自动识别最佳类别为4

图3.11可知，在没有预先设定K的情况下，通过改进后的K-means算法，可以自动识别到最佳的类别数为4，在MATLAB的命令窗口可以看到具体的运行结果：

人为模拟产生5类混合数据源作为测试源，测试结果如下所示：

图3.12 去孤点仿真

图3.13 未设定K=5，软件自动识别最佳类别为5

图3.13可知，在没有预先设定K的情况下，通过改进后的K-means算法，可以自动识别到最佳的类别数为5，在MATLAB的命令窗口可以看到具体的运行结果：

第四章 基于K-means算法的网络数据的聚类分析

    本章，我们将应用第三章的研究成果，使用改进后的K-means算法对网络用户数据信息进行聚类分析，本课题，重点对网络数据中的用户工作地点等相关数据进行提取和聚类分析，进而将分析出哪些客户在哪些区域工作或者经常在哪些区域活动。

4.1 网络数据的获得与分析

这里，从网站“http://reality.media.mit.edu/download.php”下载“the Reality Mining project”的数据库，用作本课题的实际的测试数据，使用MATLAB进行价值，可以看到如下的数据信息：

 

图4.1 网络数据列表

    根据本课题的要求，我们需要通过该数据库进行分析，从而提供各种网络数据服务，比如用户工作的地点的分析，用户登入时间的分析，用户使用电脑设备类别，用户发送短信信息等等。

    这里我们将重点根据数据库中的地址信息来分析不同用户的实际工作地点或者活动地点。

4.2 测试样本的提取

本文，将针对用户工作地点的相关信息进行聚类分析，获得用户的工作地址聚类结果。下面将对数据进行提取，获得初始的测试数据集。

4.2.1 测试样本的选择

通常情况下，我们可以根据每个人的生活特点，将一个人的特性归纳为如下几点：

表4.1 用户特性分类表

分类	说明	评价
按使用行为细分	按用户使用量高低区隔隔优势；	方法简单、固定，容易进行定量分析；
按人口统计学/地理学细分	按用户社会等级区隔； 按用户性别、年龄、职业区隔 按城区、乡镇等区隔	方法简单、固定，容易进行定量分析；

测试数据子集合的选取，根据课题的研究需要，我们选择数据库中的locs，all_locs，loc_id作为测试样本数据。此外，选择my_office，my_group作为用户工作地点的聚类分析数据源，最后选择my_mac作为用户使用电脑的MAC物理地址的聚类分析数据源。

通过上面的选择，我们可以通过聚类分析获得如下的聚类结果：

 

 

图4.2 数据选择图

最后，从提取的数据中可以知，my_mac，my_office，my_group等三组数据其具有唯一性和可分辨性，即通过数值本身即可得知该用户的相关信息，因此，这里不需要进行进一步的聚类分析，所以，最后我们只对locs，all_locs，loc_id等三组数据进行数据 提取和异常处理。

locs中的数据的含义为：通信时间，地区标号.通信小区标号；

All_locs中的数据的含义为：地区标号.通信小区标号；

Loc_ids中的数据的含义为：locs数据的中索引值，即基站ID号；

因此，在本质，我们所用到的数据为通信时间，基站ID号，地区标号，通信小区标号，所以，最后只需要将这四组数据进行提取分析。

4.2.2 数据的提取和异常数据的排除

在为每一个用户生成所有的变量后，必须对数据进行清洗，检查所有变量的缺失值、未知值、无效值或有效值。

缺失值：一条记录（观测）的某个字段（变量）没有值，为空；

未知值：一条记录（观测）的某个字段（变量）有值，但不知道其意义；

无效值：一条记录（观测）的某个字段（变量）值是无效的，但其意义是已知的；

有效值：一条记录（观测）的某个字段（变量）值是有效的，这是正常的情况。

数据清洗的过程就是把缺失值、未知值或无效值用有效值替代的过程。经过检查本研究数据有大量缺失值的发生，因为某些客户在某些特定的产品没有进行交易，因此在不同的表关联到一起的时候有缺失的情况发生，对这部分记录全用0代替。没有未知值和无效值的情况发生。

    此外，对于数据的异常值，本文采取的措施是删除，最后，为了提高聚类的效果，需要去掉相关性较高的变量，主成分分析可以生成原始变量线性组合的主成分，这些主成分既保留了原始变量的大部分信息，而且相互独立，可以提高聚类的效果。本研究对相关性较高的变量提取主成分，这些主成分和与任何变量都不相关的变量一起作为聚类的输入变量。

    通过上面的操作之后，将所需要的数据单独保存为*.mat格式，这样可以方便的为后面的操作使用。

 

在MATLAB中，运行“data_catch.m“代码执行数据提取和保存。此时，我们将所用到的数据信息通信时间，基站ID号，地区标号，通信小区标号保存到了其他数据库中：

最后考虑数据的唯一性，即为了对不同区域的用户进行聚类分析，那么不考虑时间因素，这样可以只保存每个用户出现过的活动区域，从而方便最终的聚类分析。

这样，在后期的处理的时候，可以大大提高数据处理效率。

4.3 基于K-means算法的样本聚类分析

4.3.1 将测试样本数据应用到K-means算法之中

用K-Means算法进行聚类分析，最重要的两个参数是最大类的个数K以及K个初始凝聚点的选择。本文所设计的K-means算法将对K值进行自动搜索，获得最佳的K值，而初始化聚类中心，则采用随机设置的办法进行。

在数据输入到K-means算法之前，为了便于观察分类的结果，将数据中的areaID作为实际测试数据的X轴坐标，将cellID作为实际测试数据的Y轴坐标，那么如果两个测试点重合，这说明两个用户处于同一地点，如果X轴相同，而Y不相同，那么说明两个用户在同一地点，但是出于不同的通信小区，如果X轴不同，而Y轴值相同，那么说明两个用户在不同的地区，但是在相同的小区。

由于，网路数据库的数据量非常大，无法直接进行处理，这里，我们采取的措施为选择每个用户出现最多的几个区域area和小区cell作为处理样本进行聚类分析。这样做的优势在于，在数据量非常大的时候，通过选取出现概率最大的几组数据作为代表性数据，能够最大程度上反映数据的实际特征。

这里，考虑实际情况，选取出现概率最多的六组数据作为测试数据。

通过MATLAB仿真，测试数据可以表现出如下的结果，即每个用户的大致分布。

图4.3每组出现最多的一组AreaID分布图

图4.4每组出现最多的二组AreaID分布图

    从图4.4可知，用户的区域ID主要集中在两个区域，这类似于实际中的工作地点和家庭住址，而其余比较散的点对应着其余较少活动的场所。

    从上面的仿真可知，由于用户分布具有较大的随机性，且对于各个用户而言，其基本会出现经常去的地方，或者是很少去的地方，那么对于这些较少出现的区域，可以认为是采样数据中孤点进行处理。

4.3.2 将测试样本数据应用到K-means算法之中

    我们将测试样本输入到改进后的K-means算中，进行仿真。

图4.5每组出现最多的一组AreaID的聚类分析结果

图4.6每组出现最多的二组AreaID的聚类分析结果

    从上面的聚类仿真结果可知，系统自动将用户所在的区域聚类成两大类，这个和前面所考虑的两类场所的实际情况向吻合。