基于自然邻的在线数据流聚类算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘 要 大数据时代数据的重要性越来越高，实时数据采集技术的发展使各个领域在 应用过程中都可以获取数据流。气象预测、电子商务、网络安全、视频监控等领 域都会产生大量的数据流。在这些领域，对数据流以及相关技术的研究显得至关 重要。 因数据流总量的无限性，数据流聚类只能对一段连续有限数据集进行挖掘。 数据流算法一般是采用滑动窗口、界标窗口和衰减窗口来选定需要挖掘的数据集， 采用概要数据结构来维护数据的统计信息，使得挖掘任务可以顺利进行下去。数 据流算法也可以被划分为一下四种方法，分别是基于密度的算法、基于网格的算 法、基于划分的算法和基于层次的算法。数据流聚类算法存在着参数过多，参数 值难以确定的问题。以 CluStream 算法为代表的两阶段聚类处理算法，无法实时 产生聚类结果，后来提出了完全在线处理的 CEDAS 算法解决了这一问题，但该 算法无法自动获取微簇阈值与搜索半径。 针对上述数据流存在的问题，本文引入自然邻居算法，自然邻居算法不同于 k 自然邻算法无需人工输入参数，可以自适应迭代出数据集自然特征值，且考虑 了数据的分布情况，在自然邻居算法里，数据分布密集区域的邻居点个数较多， 稀疏区域的邻居个数较少。本文通过大量的实验，找到了如何通过自然邻算法的 自然特征值确定密度阈值与邻域半径的公式，同时根据观察得到的数据集自然分 布的规律，对本文算法微簇中心点搜索半径进行加权处理。通过将自然邻算法引 入CEDAS ，本文提出了NaN-CEDAS 算法。 为了验证 NaN-CEDAS 算法的有效性，本文分别在人工数据集与真实数据流 集上对算法的有效性进行了验证。首先采用几组常用的聚类数据集验证了通过自 然邻居算法得出的阈值与邻域半径的正确性，实验证明了本文算法根据自然邻算 法得出的阈值与邻域半径能正确的将数据集聚类。然后通过两个人工数据流集证 明本文算法拥有良好的微簇合并、微簇分离以及快速发现新微簇的能力。最后通 过 KDDCUP 99 网络攻击数据集和英特尔伯克利研究实验室传感器数据流两个真 实数据集验证了本文算法应用于实际场景的效果。同 CEDAS 、DenStream 、 CluStream 算法的对比实验表明，该算法有很好的实验结果。 关键词：数据流；聚类；自然邻算法；NaN-CEDAS I 重庆大学硕士学位论文 英文摘要 Abstract The importance of data in the era of big data is getting higher and higher, and the development of real-time data acquisition technology enables data streams to be acquired in various fields during application. A large number of data streams are generated in the fields of weather forecasting, e-commerce, network security, and video surveillance. In these areas, research on data streams and related technologies is critical. Compared with static data, data streams are characterized by time series, infinite data volume, volatility and low value density. The above characteristics of data stream pose a new challenge to cluster mining on data streams: