ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (8): 1683-1696.doi: 10.7544/issn1000-1239.2020.20200432

所属专题: 2020数据挖掘与知识发现专题

• 人工智能 • 上一篇    下一篇

基于随机投影的高维数据流聚类

朱颖雯1,2,3,陈松灿1,2   

  1. 1(南京航空航天大学计算机科学与技术学院 南京 211106);2(模式分析与机器智能工业和信息化部重点实验室(南京航空航天大学) 南京 211106);3(三江学院计算机科学与工程学院 南京 210012) (yingwen.zhu@nuaa.edu.cn)
  • 出版日期: 2020-08-01
  • 基金资助: 
    国家自然科学基金重点项目(61732006)

High Dimensional Data Stream Clustering Algorithm Based on Random Projection

Zhu Yingwen1,2,3, Chen Songcan1,2   

  1. 1(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106);2(MIIT Key Laboratory of Pattern Analysis and Machine Intelligence (Nanjing University of Aeronautics and Astronautics), Nanjing 211106);3(College of Computer Science and Engineering, Sanjiang University, Nanjing 210012)
  • Online: 2020-08-01
  • Supported by: 
    This work was supported by the Key Program of National Natural Science Foundation of China (61732006).

摘要: 高维数据流在许多现实应用中广泛存在,例如网络监控.不同于传统的静态数据聚类问题,数据流聚类面临有限内存、单遍扫描、实时响应和概念漂移等问题.然而现有许多数据流聚类算法在处理高维数据时,常常因产生维数灾难而导致高计算复杂度和较差的性能.为了解决此问题,基于随机投影和自适应谐振理论(adaptive resonance theory, ART)提出了一种针对高维数据流的高效聚类算法RPFART.该算法具有线性计算复杂度,仅包含1个超参数,并对参数设置鲁棒.详细分析了随机投影对ART的主要影响,尽管该算法仅简单地将随机投影与ART方法进行了结合,但在多个数据集上的实验结果表明:即使将原始尺寸压缩到10%,该方法仍可以达到与RPGStream算法相当的性能.对于ACT1数据集,其维数从67500减少到6750.

关键词: 高维数据, 数据流聚类, 随机投影, 自适应谐振理论, 聚类

Abstract: High dimensional data streams emerge ubiquitously in many real-world applications such as network monitoring. Clustering such data streams differs from traditional data clustering algorithm where the given datasets are generally static and can be read and processed repeatedly, thus facing more challenges due to having to satisfy such constraints as bounded memory, single-pass, real-time response and concept-drift detection. Recently many methods of such type have been proposed. However, when dealing with high dimensional data, they often result in high computational cost and poor performance due to the curse of dimensionality. To address the above problem, in this paper we present a new clustering algorithm for data streams, called RPFART, by combining the random projection method with the adaptive resonance theory (ART) model that has linear computational complexity, uses a single parameter, i.e., the vigilance parameter to identify data clusters, and is robust to modest parameters setting. To gain insights into the performance improvement obtained by our algorithm, we analyze and identify the major influence of random projection on ART. Although our method is embarrassingly simple just by incorporating the random projection into ART, the experimental results on variety of benchmark datasets indicate that our method can still achieve comparable or even better performance than RPGStream algorithm even if the raw dimension is compressed up to 10% of the original one. For ACT1 dataset, its dimension is reduced from 67500 to 6750.

Key words: high dimensional data, data stream clustering, random projection, adaptive resonance theory, clustering

中图分类号: