基于改进的K-means算法的异常检测
摘 要：聚类算法通常用于数据的聚类。除此，它还可以用于异常数据的检测。首先介绍了基于划分的聚类算法K-means ，然后给出改进算法I-K-means的算法描述，最后通过实例进行异常分析。 关键词：异常检测；聚类分析；K-means；I-K-means 0 引言
在进行数据挖掘的原始数据中，往往包含一些这样的数据对象,它们与数据的一般行为或模型不一致, 这些数据对象被称为异常数据(或称孤立点)。对于异常的定义很多，目前较多采用的是著名统计学家Douglas Hawkins给出的定义：异常点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。大部分数据挖掘方法对异常数据的处理是在数据清洗阶段，其目的是清除这些有可能对研究带来影响的数据。然而在另一些挖掘过程中，罕见事件（异常数据）的检测比正常事件的检测更有意义，如金融欺诈识别、网络入侵检测、违规交易检测、恶劣天气预报等。本文主要讨论应用基于划分的I-K-means算法进行异常数据的检测。 1 聚类分析
聚类是一个将数据集划分为若干组或类的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。 (1)聚类算法。目前聚类算法较多，这些算法大致可分为五类：
层次方法、划分方法、密度方法、网格方法、模型方法。
层次聚类方法是对给定的数据集进行层次分解，直到满足某种条件为止。如BIRCH、CURE算法。划分方法的主要思想是给定一个有n个对象的数据集，划分算法构造K个划分，每一个划分就代表一个簇，k≤n。最终达到同一簇中的对象是“相似的”，不同簇中的对象是“相异的”。如k-means算法。基于密度的聚类思想是，只要一个点的密度大于某个阈值，就把它加到与之相近的簇中去。如DBSCAN、OPTICS。基于网格聚类方法先将空间量化为有限数目的单元，然后在这个量化空间上进行聚类操作。典型算法如STING。基于模型的聚类方法就是试图对给定数据与某个数学模型达成最佳拟合。这类方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两类：统计学方法和神经网络方法。针对具体问题，算法的选择主要取决于数据的类型及聚类的目的和应用。
(2)K-means算法。k-means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。
k-means 算法接受输入量 k ，然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
聚类相似度的计算是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行的。 算法描述：
算法：k-means
输入：簇的数目k和包含n个对象的数据库 输出：k个簇，使平方误差准则最小。
方法：①任意选择k个对象作为初始的簇中心；②repeat；③ 根据簇中对象的平均值，将每个对象（重新）赋给最类似的簇；④更新簇的平均值，即计算每个簇中对象的平均值；⑤Until不再发生变化。 算法工作过程：
首先，随机地从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数，具体定义如下: E=∑
k
i=1
∑
p∈C
i
|p-m
i|
2
其中E为数据库中所有对象的均方差之和；p为代表对象的空间中的一个点，表示给定的数据对象。 m
i为聚类C
i的平均值。这个准则函数试图使生成的结果簇尽
可能地紧凑和独立。显然，若E值越大，说明误差越大，聚类结果越不好。因此，我们应该寻求使E最小的聚类结果，即在误差平方和准则下的最优结果。判断：若|E(I+1)-E(I)|<ε则算法结束，否则I=I+1，返回继续执行（2）步。在算法的每次迭代过程中，把每一个数据对象分到离它最近的聚类中心所在的簇。这种聚类通常称为最小方差划
基于改进的K-means算法的异常检测
