Fully online clustering of evolving data streams into arbitrarily shaped clusters
Fully online clustering of evolving data streams into arbitrarily shaped clusters
复制标题
DOI：
10.1016/j.ins.2016.12.004
复制
发表时间：
2017-03-01
影响因子：
8.1
通讯作者：
MacKenzie, A. R.
中科院分区：
文献类型：
--
作者：
Hyde, Richard;Angelov, Plamen;MacKenzie, A. R.
近年来，连续数据流中的数据可用性不断增加，对这些数据进行聚类在数据分析中具有许多优势。通常的情况是，这些数据流不是固定的，而是随时间演变的，并且集群不是规则形状，而是在数据空间中形成任意形状。以前用于聚集这种数据流的技术要么是混合的在线/离线方法，要么是开窗口的离线方法，或者只找到超椭圆集群。在本文中，我们提出了一种完全在线的技术，用于将不断演变的数据流聚类成任意形状的簇。它是一种两阶段技术，它准确、对噪声具有健壮性、计算和存储效率高，并且随着数据维度的增加而具有较低的时间损失。该技术的第一阶段产生微簇，第二阶段将这些微簇组合成宏簇。通过使用超球形微团簇保持计算的简单性和最小化，实现了尺寸稳定性和高速。通过维护一种图结构，其中微簇是节点，边是它与相交的微簇的对，我们最小化了宏簇维护所需的计算量。微团簇本身的描述方式使得不需要计算核心区和壳区，也不需要单独定义外部微团簇。我们演示了所提出的技术在宏聚类以完全在线的方式发展时加入和分离宏聚类的能力。据作者所知，没有其他完全在线的技术，因此我们将该技术与流行的在线/离线混合替代技术在准确性、纯度和速度方面进行了比较。然后将该技术应用于真实的大气科学数据流，并用于发现短期、长期和季节性漂移及其对异常检测的影响。除了具有良好的计算特性外，该技术还可以通过使用欧几里得或分形形状因子来表征星团超形状，从而增加超椭圆方法的分析价值。由于该技术将宏聚类记录为图形，因此随着时间的推移，表征聚类图的顺序、程度和完备性将产生进一步的分析价值。(C)2016 Elsevier Inc.保留所有权利。
In recent times there has been an increase in data availability in continuous data streams and clustering of this data has many advantages in data analysis. It is often the case that these data streams are not stationary, but evolve over time, and also that the clusters are not regular shapes but form arbitrary shapes in the data space. Previous techniques for clustering such data streams are either hybrid online / offline methods, windowed offline methods, or find only hyper-elliptical clusters. In this paper we present a fully online technique for clustering evolving data streams into arbitrary shaped clusters. It is a two stage technique that is accurate, robust to noise, computationally and memory efficient, with a low time penalty as the number of data dimensions increases. The first stage of the technique produces micro-clusters and the second stage combines these micro-clusters into macro-clusters. Dimensional stability and high speed is achieved through keeping the calculations both simple and minimal using hyper-spherical micro-clusters. By maintaining a graph structure, where the micro-clusters are the nodes and the edges are its pairs with intersecting micro-clusters, we minimise the calculations required for macro-cluster maintenance. The micro-clusters themselves are described in such a way that there is no calculation required for the core and shell regions and no separate definition of outer micro clusters necessary. We demonstrate the ability of the proposed technique to join and separate macro-clusters as they evolve in a fully online manner. There are no other fully online techniques that the authors are aware of and so we compare the technique with popular online / offline hybrid alternatives for accuracy, purity and speed. The technique is then applied to real atmospheric science data streams and used to discover short term, long term and seasonal drift and their effects on anomaly detection. As well as having favourable computational characteristics, the technique can add analytic value over hyper-elliptical methods by characterising the cluster hyper-shape using Euclidean or fractal shape factors. Because the technique records macro-clusters as graphs, further analytic value accrues from characterising the order, degree, and completeness of the cluster-graphs as they evolve over time. (C) 2016 Elsevier Inc. All rights reserved.