论文部分内容阅读
在现实生活中，人们经常遇到海量的、快速产生的数据，称为数据流。为了对数据流进行有效的处理，人们提出适合数据流聚类的新模型。面向数据流的聚类问题已成为当前国内外聚类研究的一个重要方向。
本文以网络访问日志流为研究对象，结合网络访问日志流的特点，提出基于网格和密度的改进数据流聚类算法。改进算法分为在线和离线聚类两部分。算法通过引入网格方法提高在线聚类的速度，并使用基于密度聚类思想实现任意形状的数据聚类。
针对网络访问日志流特征存在冗余的特点，提出一种无监督环境下的带启发式的二阶段聚类特征选择算法获取有效特征。该算法通过对每个原始特征按其聚类重要性排序作为启发式策略以进行特征选择。算法分为三步：第一步是将所有原始特征都按照聚类重要性进行排序；第二步是通过二阶段聚类算法(Two-Steps)选择合适的特征子集；第三步对已选的特征子集计算任意两个特征的相关系数，去除相关系数大的特征，选出合理的特征。接着本文对该特征选择算法的结果进行实验分析，表明带启发式的二阶段聚类特征选择算法获取的特征是有效的。
数据流聚类算法的一个难点在于实时处理速度，因此本文的改进数据流聚类算法引入网格划分方法实现数据快速处理。虽然网格划分能在一定程度加快数据处理，但是网格划分的单元数随着数据维数的增加成指数增长，使得在高维数据聚类时增加了查找网格的时间消耗。为此，本文提出二次网格划分方法。它是在初次网格划分的基础上再划分出较大的网格块，然后通过哈希表实现数据点的直接定位，减少查找网格的时间消耗。数据流聚类算法的另外一个困难之处是算法使用的内存空间有限。由于本文的改进数据流聚类算法引入网格划分，随着数据流的不断到达，存储在内存中的网格信息将不断增多。为避免内存不足，本文使用网格合并、抛弃方法节省内存空间的消耗，并使用切割方法提高合并后网格的精度。改进数据流聚类算法的在线部分就是结合二次划分以及合并、切割等方法实现对网络访问日志流快速有效聚类。算法的离线部分是对在线处理的中间结果做进一步的聚类分析。
最后通过实验比较改进数据流算法与CluStream算法在聚类质量、时间和空间上的差异。结果表明改进数据流聚类算法对网络访问日志流聚类能取得很好效果。