Cooperation with Tel-Aviv University

Enhanced situation space mining for data streams

Y Mirsky, T Halpern, R Upadhyay, S Toledo, Y Elovici

SAC '17 Proceedings of the Symposium on Applied Computing Pages 842-849 Marrakech, Morocco — April 03 - 07, 2017

Data streams can capture the situation which an actor is experiencing. Knowledge of the present situation is highly beneficial for a wide range of applications. An algorithm called pcStream can be used to extract situations from a numerical data stream in an unsupervised manner. Although pcStream outperforms other stream clustering algorithms at this task, pcStream has two major flaws. The first is its complexity due to continuously performing principal component analysis (PCA). The second is its difficulty in detecting emerging situations whose distributions overlap in the same feature space.

In this paper we introduce pcStream2, a variant of pcStream which employs windowing and persistence in order to distinguish between emerging overlapping concepts. We also propose the use of incremental PCA (IPCA) to reduce the overall complexity and memory requirements of the algorithm. Although any IPCA algorithm can be used, we use a novel IPCA algorithm called Just-In-Time PCA which is better suited for processing streams. JIT-PCA makes intelligent ‘short cuts’ in order to reduce computations. We provide experimental results on real-world datasets that demonstrates how the proposed improvements make pcStream2 a more accurate and practical tool for situation space mining.