Adaptive Estimation of Weight Coefficient in a Time-weighted Incremental EM-algorithm for Data Streams
Application of data stream clustering is quite general. Applications of data streams include mining data generated by sensor networks, meteorological analysis, stock market analysis, computer network traffic monitoring, long-term population-based, cognitive, real-time sociological studies etc. These applications involve datasets that are far too large to fit in main memory and are typically stored in a secondary storage device. Real-time processing of large volumes of data requires efficient, fast algorithms and data compression. Moreover, recently obtained objects are often more important than the old ones, so several clustering algorithms implement a damped window model with a user-defined decay coefficient. This coefficient is not obvious. An important task in the development of machine learning algorithms is to reduce the number of algorithm parameters (user-defined parameter) through the development of adaptive mechanisms. Such a mechanism for determining the decay coefficient proposed in this paper. A Gaussian mixture data stream algorithm is constructed with damped window model. Decay coefficient for the object according damped window is w=w(At) where At is time since object arrived from the stream into cluster, weight of the cluster W(t) is sum of all its objects. Recent objects receive higher weight than older ones, and the weights of the objects decrease with time. It is usually to assume w(At)=e<sup>-aAt</sup> (a>0), with following properties: 1) when arrives, the object weight is equal to one: w(0)=1; 2) over time object weight monotonic decreases to zero: lim w(At) = 0; At 3) if weight of object w(A^) after At! units of time is known, then after more At<sub>2</sub> it can be easily recalculates as w(Ati+At<sub>2</sub>) = w(Atj)w(At<sub>2</sub>); 4) if weight of cluster W(t) for the instant in time t is known, and during the next time period At there was no new objects arrived in this cluster, then weight of this cluster can be recalculates as W(t+At) = W(t)w(At). Let at initial instant in time we have a set of K Gaussian clusters C<sub>k</sub> that described by their means ц and correlation matrixes X<sub>k</sub>. Weight W<sub>k</sub> at initial time defined as a number of objects in cluster C<sub>k</sub>. Let {x<sub>1</sub>, x<sub>2</sub>,.,.}eR<sup>d</sup> is data stream, i.e. set of objects with timestamps t<sub>1</sub>, t<sub>2</sub>,.... When a new object x with timestamp t arrives to the cluster C<sub>k</sub>, the following algorithm executes. Input: new object x, cluster parameters: mean correlation matrix X, weight W<sub>k</sub> (k=1,2,...K), time period since last object arrives At. 1. Recalculate weights W<sub>k</sub> = e<sup>-aAt</sup>W<sub>k</sub> (k=1,2,...,K). W<sub>k</sub> 9<sub>k</sub> ( x\ ц<sub>k</sub>, Z <sub>K</sub> ) 2. Calculate probabilities of belonging x to the k-th cluster щ =--~i~\-. Put x into the most probable cluster. ZmWФ* (( Mi'' Z ) 3. For this cluster (in with x is, index of cluster is dropped) recalculate mean ц, correlation matrix X and weight W: W+ W (|~- x)<sup>2</sup> ^ 2~+- W=W+1, w+1 i+ = <sub>T</sub> ~ ; 2+ = w+1 w+1 where indexes - and + corresponds to the values before and after recalculation. Note that weight function depends on a>0, that may be defined individually for each C<sub>k</sub>. We propose the following algorithm to recalculate a separately for each cluster at the time the object arrives into cluster. Input: xi, x<sub>2</sub>,...,x<sub>N</sub> - last N objects putted into cluster, t<sub>1</sub>,t<sub>N</sub> - their timestamps, |<sub>0</sub> - cluster mean Z<sub>0</sub> - cluster correlation matrix. 1. At initial instance of time t<sub>0</sub> adopt a=0, i.e. we assume that cluster is not moving. 2. When object x<sub>i</sub> with timestamp t<sub>i</sub> (i<N) arrives into the cluster, accumulate variables | = (x<sub>1</sub> + x<sub>2</sub> +...+ x<sub>N</sub>)/Nand ft-t<sub>0</sub>). v = <sup>N</sup> (|<sup>-</sup>|0) _ 3. If i=N calculate ^n <sub>( )</sub> using accumulated variables. Calculate a = -| v |ln e/r, where r is Euclidean distance be- 2 i=1<sup>(t</sup>i <sup>t</sup>0<sup>)</sup> tween |<sub>0</sub> and confidence ellipse boundary (confidence probability p = 1 - e) in direction of v vector. Set t<sub>0</sub>=t<sub>N</sub>, assign |<sub>0</sub> and Z<sub>0</sub> a corresponding values of cluster at the time t<sub>N</sub> and return to step 1. We perform an experiment using an imitation model of Gaussian mixture clusters with moving centroids. Some results are shown in this article. Proposed algorithm is undemanding to resources (time, memory) and therefore is suitable for real-time monitoring in large dynamic systems, such as computer systems and networks. Quality of decay coefficient adaptation is acceptable as follows from the experimental data.