On Detecting Event Periodicity in Binary Data Series
Yuan Hu · 2015
Data series is defined as the series of data which present sequentially happening events. Real life has several examples of time-related data series, such as weather conditions of a particular location, stock trading data, transactions in a supermarket, computer network visiting traffic, gene sequencing data, etc. A time-related data series is mostly characterized by repeating cycles. The identification of periodic events or the detection of the periodicity of an event could shed light on the behavior habit and future trends of the case represented by time-related data series, hence leading to more effective decision making. Thus, the job of periodicity detection is a process for finding temporal regularities within the time-related data series, and the goal of analyzing a time series is to find whether and how frequent a periodic pattern(full or partial) is repeated within the series.Let et be the event occurring at timestamp t and S = {e1; e2;...; e|S|} be a time-related data series having |S| events, where et represents the event recorded at time instance i and |S| is the length of data series. In S, each event type can be denoted by a symbol(e.g., a, b, c). In the following we will use x to denote a given event type. Specially, we can see two commonly facts in real world for event x = {Bob goes to gym}: Bob goes to gym once a week (not at any exact weekday.) and Bob likes to go to gym on Tuesdays(not at every week.). Actually, these two facts show some different periodicity of event x. The first addresses the fact that event x is averagely distributed in a week; whereas, the second one means event x will happened at a fixed time point(the distribution of x may not be so good). Different from the traditional research, this study addresses the problem of how to detect these two periodicities for a given event x in data series S: First, we use the binary data series to present the appearances of a given event x in S by defining et =1 if x appears at time position t, 1 ≤ t ≤ |S|. For example, setting x = {a}, we can obtain binary data series BS={ 0011 1000 1001 1000 1000} from data series S = {bbaa abbd abca abbc abcd}. Second, a π(n)-partition method for data series is introduced, which is a complete period-covered partition, and it can divide the data series into length-equal and time-continuous segments. Third, we summarize the periodicity of event x in S into two different types: an event x is said to have distribution periodicity if all the appearances of x in S are averagely distributed; an event x is said to have structure periodicity if x appears at an exact same time point in each period. Finally, we use the cross entropy to measure the feasibility of each partition results for the detection of an event's periodicity. Also, we propose an evaluation method to obtain the periodicity of periodic event. Additionally, we demonstrate some experiment results for event periodicity with two real data sets. The first is the Amazon Access Samples Data Set, which was created and donated by Amazon Corp in 2011(http://archive.ics.uci.edu/ml/datasets/). Another data set is the Lover's Call Data Set collected from two lover's cell phone communications from Nov. 1, 2011 to Dec. 1, 2011. The experiment results show that the method can be used to explore the periodicity of an event in binary data series efficiently. Especially, it works well with very low time consumption. The main contributions of this paper are summarized as follows.(1) This work represents a pioneering effort to distinguish the idea of distribution(time slot) periodicity and structure(point-in-time) periodicity.(2) A simple and complete partition method π(n) is proposed. This method allows both distribution periodicity and structure periodicity for a given event to be detected simultaneously.(3) Based on the minimum cross entropy principle and the property of a periodic function, we present an efficient method to measure and determine the periodicity of an event.