The invention relates generally to the field of data mining. More particularly, the invention relates to the field of data mining for sequential data that represents event sequences.
Most data mining research has concentrated on set-oriented tabular data. There are, however, important types of data that do not fit within this framework. One such form of data is event sequences that occur in many application areas. An event sequence is an ordered collection of events from a finite set of event types, with each event of the sequence having an occurrence time.
One example of an event sequence is the event or error log from a process such as telecommunications network management. Here the event types are the possible error messages, and the events are actual occurrences of errors at certain times. Also a web access log from a single session of a user can be viewed as an event sequence. In this case, the event types are the web pages, and an individual event is a request for a particular page at a particular time. Other examples of application areas in which event sequences occur are user interface design (event types are different user commands), criminology (types of crime), biostatistics (different symptoms), etc. In each of these applications, the data consists of one or several event sequences. Note that an event sequence is different from a time series in that a time series describes a variable with a continuous value over time, whereas an event sequence consists of discrete events happening in more or less random fashion.
One interesting aspect of event sequences is the degree of similarity between two event types. The definition of similarity may vary depending on the application. For example, if the application is web browsing behavior, two web pages may be considered similar if they convey the same type of information. If the example is computer user interface design, two commands may be similar if they accomplish the same function. Such similarity information is useful in itself, as it provides insight into the data. The similarity of web pages may be used to determine where links may be appropriate. The similarity of computer user commands may be used to select alternative commands to be suggested to the computer user. Moreover, similarities between event types can be used in various ways to make querying the data set more useful.
Because of the increasing difficulty and expense of determining similarity between event types in large sets of event sequences, it is desirable to provide a method of determining similarity between event types by merely scanning and interpreting the data in the database. Such a method would do away with the need to compare the content of event types to determine their similarity.
Determining a degree of relative similarity between event types in event sequences by examining the context of the event types facilitates similarity analysis of large sets of event sequences.
An event sequence may be defined as an ordered collection of events from a finite set of event types, with each event of the sequence having an occurrence time. An event may be defined as a tuple containing two elements, an event type and an occurrence time.
The present invention determines the similarity between a plurality of event types in at least one event sequence. The invention may be implemented in the form of program modules or computer-executable instructions stored on a computer readable medium or in the form of an apparatus having means to process data stored on a database.
In one exemplary embodiment of the invention, an event sequence is examined, and a context for each of a plurality of event types is compiled. These contexts are then compared to determine a degree of similarity between the corresponding event types.
A context set is compiled by recording the events which occur within a predetermined time period of each occurrence of the event type. The context set may include event types which occur during the time period before each occurrence of the event type or event types both before and after the event type.
To compare the contexts, the context sets are transformed into vector representations and then the distance between the vectors is calculated. The context sets may be transformed into vectors having the same number of dimensions as the finite set of event types has elements, with each dimension corresponding to an event type and the value of each dimension being based on the number of times the corresponding event type occurs in the context set. The context sets may be transformed into centroid vectors.
Conventional distance calculations may be employed for determining the distance between vectors, such as the Euclidean distance formula.