数字技术与应用
基于网格和聚类的流数据孤立点挖掘
任广佛
罗聪
（贵州大学计算机科学与信息学院
贵州贵阳
550025)
·理论操素·
【摘要]在数据挖掘中，对于数据源中的摄立点的研充可以用于网络攻击欧诈检测等领域。而Internet的广泛使用使得大景数据以时序性的流的形式存在，针对传统数据挖播对流数据挥立点挖据应用中所遇到的间题，文中提出了一个基于改进的距离和密度的抵立点挖掘算法。实验证明，该算法能够有效地检测到流数据中的局部孤立点，从面捕提到数据流上的概念漂移，能更好地应用于实际。
【关键词班立点
流数据
[中图分类号]TP311 1引言
概念源移
案类
网格
[文献标识码]A
[文章编号]10079416（2010）070182-01
用别除这可能导致某些重要的隐最信息的
随着高速大规模网络的迅速发展，在高速网络环境下的访间记录数据往往以流的形式出现，我们称这样的数据为流数据。即流数据有着以下特性[1]：在短时间内有大量数据到达，数制或数据的摘要信息必须按照顺序存取且只能被读取一次或有限，不能随机存取，时序性，在应用领域中的数据流往往义是高维的。由于数据流动念的特殊性，对流数带进行迅速处理以获取有用信息就带来了新的机遇和挑战。处理数据流最主要的挑战是使用有限的存储空间和算法的快速运行，即要求算法高效其至是实时的和使用有限的存储空间，显然，传统的数据挖掘算法危以满足这种要求。
在数据挖掘中，经常存在一些数据对它们不符合数据的一般模型。这样的
象，
数据对象被称为差立点。预立点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制2。另外，孤立点也可能是周有的数据变异性的结果，许多数据挖掘算法试图使覆立点的影响最小化，直接在数据预处理中剃除掉数据源中的摄立点，但是由于这些数据可能是噪声的同时也可能隐靠了特定价值的信息，比如网络攻击。
味地采
# 8
A
图1
丢失。在数帮挖播中，对待数据集中的摄立点有两种策略；一种是将它们作为噪声面从数据集中清洗出去，另一种则将它们作为研究对象，称为亮立点探测。由于网络上的大多数数据类型都为流数据，所以本文在流数据上对其摄立点数据进行挖掘
本文提出了一个基于流数锯的改进的距离和密度的延立点挖据算法。本文所做工作：
(1)数据预处理：对于流数据中的高维数据，利用网格技术进行降维处理。
(2)改进基于距离聚类算法：针对现有基于距离的案类挖掘算法，加入了密度探测从而解决了基于距离案类算法中易出现的托立点虚警和摄立点漏报现象。
(3)算法捕获的是局部据立点，有效地避免了流数据的“概念源移"对探测算法的影响。
2基本概念
本文将讨论对流数据进行蕉立点挖据，前面我们讲到了报立点是数据集中的不满足数据集的一般数据模型的数带对象。面这只是给出了一个概念上的定义，具体在实际的应用中我们需要的是一个已
a2 P
基于距离的况立点检测算法的两种错误
表1
Nu
d>=D d 182
基于距离与密度的提立点判定情况
n
错误2：将M归人与其股小的距离函数值的类立点
数字技术与应用万方数据
量化的对象。在文中后面的试验中我们将具体涉及到特定摄立点的定义。
在摄立点的操测过程中，我们需主要考虑一下两个间题：一是孤立点的量化，针对特定的应用环境和数据集而不同。二是证立点的操测算法，即设置对数据业的扫描算法和对摄立点的判定算法，本文中综合考虑了流数据的特点和数据天生的浆类性14]，即算法要考虑实时性、低空间复杂度等要求。分别采用了需动时间窗口和基于距离的密度的案类算法米进行数据集的扫描和摄立点探测。
2.1流数据概要数据结构
概要数据结构(Synopsis Data Structure)）是算法为支持目标计算面在内存中保存的数据流数据的压缩信息。概要数据结构主要的构造方法有抽样技术，小波变换，直方图技术、哈希方法、梗概技术等。
2.2滑动窗口技术
滑动窗口技术是通过在内存中创建滑动窗口来保存最近一段时间内到达的数据流数据集合，以实时地支持连续查询或挖掘。用户事先指定窗口大小。假设窗口的大小为w，在任一时间点n，滑动窗口的时间范围是Aao-)- A,，时间点Aun(9n 1) 之前的数据全部忽略不计。目前的研究成果主要有指数直方图技术、基本窗口技术和链式推样技术。在文中主要用基本窗口技术来维护概要数据结构.即将大小为w 的清动窗口按时间序列划分个等宽的子窗口(w/k个元素)，并且由一个摘要表示其
窗口的特征， 2.3网格
本文假定输入数据是n维的，每个输入的数据都定义在空间P中：
P=P×P×..×P,(其中P是i维方向
的定义空间）
将M归人与其最小的距离函数值的类
借误1；将M作为-个单独的类的质心（亮立点类）
(1)