Transcript My presentation - Monash University

Visualisation of Cluster Dynamics
and Change Detection in Ubiquitous
Data Stream Mining
Authors
Brett
Gillick, Mohamed Medhat Gaber, Shonali Krishnaswamy, and
Arkady Zaslavsky
 Caulfield School of Information Technology, Monash University, 900
Dandenong Rd, Caulfield East, Victoria, 3145, Australia
Email
[email protected]
Introduction





Power of handheld devices is increasing
Ubiquitous Data Mining (UDM) allows
“anytime, anywhere” analysis [4,5]
UDM data mining algorithms have been
developed [1,3]
Visualisation is useful in traditional DM
Apply visualisation in UDM to assist with, and
speed up, the decision making process for
mobile users
Related work
Kargupta et al [3] have proposed
“MobiMine” a system where the data
mining is conducted on a central server.
 The results are compressed using
Fourier transformation.
 The compressed results are sent to the
mobile device for visualization

Change detection & cluster dynamics
visualisation model

As seen in [2] change
detection algorithm must be
trained
 Lightweight Clustering module


Change Detection module


Incoming data stream is
clustered
Periodically, this algorithm is
run with current statistical
information compared to
stored information in order to
detect changes
Visualisation module

Continuously updates a
visualisation of clusters and
any change detection
information that has been
generated
Visualisation of Cluster Dynamics

Lightweight Clustering (LWC) algorithm
[1]
Threshold-based
 One pass clustering algorithm
 Produces cluster and weight information


Visualise
Cluster positions
 Cluster weights

Cluster dynamics visualisation algorithm
1.
2.
3.
4.
5.
6.
7.
8.
Let m be the number of history sets of clusters stored in memory
Let there be n = { CS1, CS2, …, CSm } sets of clusters resulting
from the clustering algorithm where CS1 is the current set of
clusters and CSm is the oldest stored set of clusters
Let there be CC = { cc1, cc2, …, ccn } cluster centres in each CS
Let C = { c1, c2, …, cm } be a set of colour codes indicating the
cluster set’s time stamp
A colour ci, is assigned to represent a particular cluster set CSj
where i,j=1..m
Let G be the graphical object used in the visualization to
represent a cluster centre and GW be the graphical object
associated with G representing the cluster’s weight
Each CC will be coloured according to its cluster set with colour ci
The size of each cluster’s enclosing object will be equal to the
cluster’s weight
Visualisation of Change Detection
STREAM-DETECT algorithm (presented
earlier) [2]
 Produces notifications of significant
changes in

Cluster domain
 Cluster distribution (uniform, normal)


Visualise

Sets of clusters before & after change
Change detection visualisation algorithm
1.
2.
3.
4.
5.
6.
7.
Let CS1 be the set of clusters before a detected
change
Let CS2 be the set of clusters after a detected change
Let c1 be the colour used to indicate a pre-change set
of clusters
Let c2 be the colour used to indicate a post-change set
of clusters
Let G be the graphical object used in the visualization
to represent a cluster centre and GW be the graphical
object associated with G representing the cluster’s
weight
Each cluster in CS1 will be assigned the colour c1
Each cluster in CS2 will be assigned the colour c2
Implementation

J2ME using the Connected Limited Device
Configuration (CLDC) 1.1 and Mobile
Information Device Profile (MIDP) 2.0
 Mobile 3D Graphics (M3G) library which is an
optional package for J2ME and runs alongside
MIDP
 Emulators from the Mobility Pack for Netbeans
4.1
 Data generator
Implementation
Cluster positions taken from three
numerical attributes
 Positions and weights of clusters are
shown in the display
 Using transparency, sets of previous
clusters are displayed in order to show
cluster dynamics
 User is able to control camera to allow
relative cluster positions to be examined

Implementation

Neutral colour used for normal cluster
information

Active colour used to alert the user
Conclusion
We have proposed our model for the
visualisation of cluster dynamics and
cluster change detection using our
visualisation framework
 The visualisation module is able to
display a 3D view of clusters
 Alerts are given to users about
significant changes using an ‘active’
colour

References
[1] Gaber, M. M., Krishnaswamy, S., Zaslavsky, A.: Cost-Efficient Mining Techniques
for Data Streams, Australasian Workshop on Data Mining and Web Intelligence
(DMWI2004), Dunedin, New Zealand (2004)
[2] Gaber, M. M., Yu P. S.: Classification of Changes in Evolving Data Streams using
Online Clustering Result Deviation, submitted to the 3rd International Workshop
on Knowledge Discovery from Data Streams to be held in conjunction with
ICML'06, June 2006.
[3] Kargupta, H., Park, B., Pittie, S., Liu, L., Kushraj, D., Sarkar, K.: MobiMine:
Monitoring the Stock Market from a PDA. ACM SIGKDD Explorations, Volume 3,
Issue 2. ACM Press (2002) 37-46
[4] Kargupta, H., Bhargava, R., Liu, K., Powers, M., Blair, P., Bushra, S., Dull, J.,
Sarkar, K., Klein, M., Vasa, M., Handy, D.: VEDAS: A Mobile and Distributed Data
Stream Mining System for Real-Time Vehicle Monitoring. Accepted for publication
in the Proceedings of the SIAM International Data Mining Conference, Orlando.
(2004)
[5] Zaki, M. J.: Online, Interactive and Anytime Data Mining, guest editorial for special
issue of SIGKDD Explorations, Volume 3, Issue 2 (2002) i-ii