论文部分内容阅读
许多应用场合会动态实时地产生大量数据,如电子商务网站中的点击流,传感器网络和RFID中的实时读数,称这种数据为数据流。由于受到物理设备精度的限制,网络带宽和能量等的影响,这类数据往往具有不确定性,称这类数据流为不确定数据流或概率数据流。概率数据流具有以下特点:(1)数据量巨大,长度无限;(2)实时性强;(3)只能对数据流中的每个数据进行单遍扫描处理,无法保存全部数据进行反复读取;(4)数据流中的每个数据或数据的属性有误差或不确定性。如何对概率流数据进行分析和挖掘处理是一项具有极大挑战性的任务,利用传统的数据挖掘算法往往得不到正确的结果。本文主要研究概率数据流的聚类技术,研究工作主要包括以下几方面:1、分析了概率数据流模型,为后期的概率数据流聚类算法提供了基础。2、针对聚类对象为概率数据流本身,本文提出了一种基于小波概要的并行不确定数据流的聚类算法,简称U-HWT-kmeans。U-HWT-kmeans算法利用离散小波变换并考虑元组不确定性得到概率数据流的小波概要结构,采用期望距离度量流间的距离。3、针对聚类对象为概率数据流内的数据,本文提出了一种基于密度的概率数据流的聚类算法Pdenstream,以发现任意形状的簇。该算法应用了一种称为概率核心簇的“密集”微簇来捕捉概率数据流中的任意形状,并进一步设计了概率密集簇和候选概率密集簇,用于维护和保存数据流中数据分布的密度信息。4、在第3项内容基础上,本文提出了一种滑动窗口下基于密度的概率数据流的聚类算法PWdenstream,以获取当前数据流的特征。该算法将Pdenstream算法扩展到滑动窗口下,将概率核心簇,概率密集簇和候选概率密集簇以聚类特征指数直方图的形式存储,并以指数直方图技术维护其聚类特征,从而实现滑动窗口下的概率数据流聚类。本文提出的算法是对现有概率数据流的聚类技术的有益补充和改进。理论分析和实验表明本文提出的算法能够有效地解决相应问题,与现有概率数据流聚类算法相比,本文提出的算法在聚类空间开销、聚类速度以及聚类结果准确性上具有一定的优势。