胡文瑜等:数据挖掘取样方法研究51

-2-1

样且只需Elog(D)内存,其用于滑动窗口模型的算法是基于变异的链式取样方法.

º在流上挖掘分位点:令集合大小为N,参数<I(0,1),分位点元素就是数据集排序之后第<N位置的元素.分位点是数据集合的一个重要统计量.获得分位点有助于优化查询计划,提高数据库系统的性能.流上挖掘分位点的应用实例见Manku

-1

2

[46]

3 取样算法面临的挑战和研究展望

通过研究可以发现,传统取样技术在数据挖掘领域得到了深远的发展,有了新的内涵和生命力.取样技术在数据库的查询优化和近似处理、数据挖掘算法的数据预处理、流频繁元素挖掘和流分位点挖掘等方面的研究是比较充分和成熟的,但是取样技术的研究空间和研究挑战性仍然很大,尤其体现在数据流管理领域,具体包括:1)如何在尽可能小的样本集上获取尽可能精确的结果,即在一定的空间局限下和一定的精确性要求下,如何确定合适的样本大小(也称为取样复杂性问题);2)相对而言,适用于界标模型的取样技术比较成熟,而应用于滑动窗口模型的取样技术近年来虽有不少研究,但存在着内存上界不确定、附加成本较高和滑动窗口较小等诸多限制;3)目前的算法大多局限于处理只插入或少量删除的情形,需要进一步研究能处理带任意顺序的插入和删除操作或存在频繁增删情况的数据取样问题,这也是数据流概要动态维护问题;4)目前一些诸如IP流量监测这样的应用依靠或取决于逆向分布挖掘技术的发展,研究能在数据流中进行动态逆向取样和概要维护的算法也是有待充分研究的一个分支方向;5)当数据分布是严重偏斜或流查询中选择性很低时,将均匀取样方法应用于流聚类或流聚集查询中会出现不良结果,解决的办法是偏倚取样,如何设计好的偏倚取样算法,尤其是基于密度的偏倚取样算法仍是未来的研究方向之一.

文献[55]的数据流特征保持取样法和文献[56]的关联规则挖掘取样误差量化模型和快速估计算法是对问题1)的研究成果.文献[57]是问题2)的突破,能将一些原先无法用于滑动窗口模型的取样技

-53]术[52拓展到滑动窗口模型.文献[14,36]对3)的问题均有研究,但文献[36]应用背景局限于空间几

,空

间需求是O(Elog(EN)),能保证误差范围,但不支持删除操作.

4)数据流偏倚取样技术的应用

Palmer等人提出了保持原数据密度的加权偏倚取样方法,单遍扫描数据集能用于流数据聚类,与CongressSampling方法相反,它是组越小取样率越高,确保不会漏失小的聚类,适合于离群点分析.但其采用的输入点与组尺寸的映射方法是Hash方法,Hash冲突有可能降低取样质量,另外一个缺点是不能有效区分噪声和小尺寸聚类.文献[47]是基于偏倚取样算法的流挖掘频繁元素应用,空间需

-1

求是O(E),能保证误差范围,但不支持删除操作.文献[48]的偏倚取样方法可应用于演化数据流的查询评估和分类中,采取在水库取样的基础上添加时间偏倚函数来提高动态概要结构的时间相关性.文献[49]在高维数据流的在线相关性分析中利用了偏倚取样技术.

2.4 取样方法在数据挖掘中的应用发展

目前,不断创新的取样技术在数据挖掘领域的新应用持续呈现.Brown等人[20]提出的均匀取样算法是一个能并行处理经划分后的数据流并最终进行取样合并的近似查询算法.该算法不能处理带任意顺序的插入和删除.Jermaine等人[50]讨论了在线维护基于磁盘存储的随机取样方法,提出了一种样本文件存储方式,克服了无法在内存中维护大尺寸取样集的局限,并着重于解决高效存储、读取问题,可操作性强.Dash等人[51]提出了一个适用于大数据集和含噪声数据环境的单遍扫描算法,类似于StickSampling和LossyCounting算法,但应用范围可扩展到关联规则挖掘、分类和聚类,算法不足之处在于要求数据离散格式化.

取样技术的拓展应用包括在数据流环境中处理图形问题.任意顺序的流元素代表了图形的边,常见的问题有图形流中三角形数的评估.文献[52]是这类应用的代表.

近来,熵对网络监测应用的重要性得到了认识[53].网络流量分布熵的计算可用于网络流量的聚类、分类和异常侦测,Chakrabarti等人[54]提出了一[24]

何数据流,且空间有效性偏低,计算成本大,降低了

实用性.文献[10]对4)作了研究并提出了一种在逆向分布数据流中进行动态逆向取样的方法.文献[58]的流挖掘取样算法能应对在进化数据集中增量维护有界均匀取样集的挑战,无需昂贵的基数据存取,解决了3)4)的问题.但应该看出,应对这些挑战的研究不够充分和成熟,应用领域局限,留下了研究空间.人们期待更多新的取样技术能作出更多的突.