FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: TIME SERIES ANALYTICS
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY
SERVICES LIMITED
Indian Nirmal Building, 9th Floor,
Nariman Point,
Mumbai - 400021, Maharashtra
India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.
1
2
TECHNICAL FIELD
[0001] The present subject matter relates, in general, to time series analytics and,
particularly but not exclusively, to identifying frequently occurring waveform patterns in time
series.
5 BACKGROUND
[0002] Data recording devices which include sensors, are widely deployed in several
industries, such as automotive industry, stock market industry, electrical industry, and electromechanical
industry. Such devices typically record data pertaining to an activity or an
operation at uniform intervals of time. For example, in stock markets in financial sectors, the
10 data recording device may be deployed for recording the value of a stock through the course
of a day. Data recorded by such data recording devices is generally represented in the form of
a time series. A time series may be understood as a sequence of values measured typically at
successive points in time spaced at uniform time intervals. Further, the data may be subjected
to several data analytics techniques for analysis and diagnostic purposes.
15 BRIEF DESCRIPTION OF DRAWINGS
[0003] The detailed description is described with reference to the accompanying figures.
In the figures, the left-most digit(s) of a reference number identifies the figure in which the
reference number first appears. The same numbers are used throughout the drawings to
reference like features and components.
20 [0004] Figure 1 illustrates a network environment implementing time series analytics, in
accordance with an implementation of the present subject matter.
[0005] Figure 2 illustrates a method for identifying frequently occurring waveform
patterns in time series, in accordance with an implementation of the present subject matter.
DETAILED DESCRIPTION
25 [0006] Sensors generally sense and record data pertaining to an operation or a system at
uniform intervals of time. Such data measured at successive points in time spaced at uniform
time intervals, may be represented as a time series, and is referred to as time series data.
3
Typically, a time series represents data pertaining to a single run of the operation or the
system and as may be understood, several such time series may be recorded by the sensor
during different runs of the operation or the system. For example, a sensor may be deployed
for recording data pertaining to different runs of a vehicle in a vehicle testing facility. The
time series data recorded by such sensors can be used for further analysis 5 using analytics
techniques, such as rule mining, classification, and anomaly detection.
[0007] Certain analytics techniques make use of frequently occurring waveform patterns,
also referred to as cluster of subsequences or time-series motif, present in a time series for
analyzing time series data. A waveform pattern, also known as motif, may be understood as a
10 sequence of values corresponding to a particular state of the operation. For example, a
waveform pattern may correspond to or represent different temperature states, such as high
temperature and low temperature of a thermostat. Generally, in order to identify frequent
motifs present in a time series, time series data pertaining to the time series is initially
segmented into a plurality of subsequences. Each of the subsequence in the plurality of
15 subsequences is of a predetermined length. The predetermined length typically corresponds to
time duration of an operation or an event for which the frequent motifs are to be identified.
The plurality of subsequence is then analyzed for identifying the motifs.
[0008] In one conventional method for identifying motifs, each of the plurality of
subsequences is compared with the remaining subsequences in the plurality of subsequences.
20 In a case where the subsequence matches any of the remaining subsequences, both the
subsequences are paired together. As an outcome of the aforementioned method, pairs of
similar or equal subsequences are obtained. For a given set of subsequences comprising n
subsequences, the number of operations required to determine all pairs of similar
subsequences is of order n2. Further, as the number of subsequences in the set of
25 subsequences increases, the number of operations required for determining pairs of similar
subsequences also increase. Thus, for larger time series from which large number of
subsequences are obtained, identification of such pairs becomes a computationally intensive
task. Further, the conventional method is limited to identification of pairs only. As a result,
further analysis involving time consuming complex computations may need to be performed
30 for identification of a group of similar subsequences from the identified pairs of
subsequences.
4
[0009] In another technique, the plurality of subsequences is clustered into one or more
clusters using various clustering mechanisms. Such clustering mechanisms are typically
dependent on size and shape of clusters for clustering the subsequences. In said technique,
clusters of similar or matching subsequences are ascertained. Two subsequences are deemed
to be similar in a case where a distance between the two subsequences 5 is less than a
predetermined distance pertaining to the cluster. As the number of subsequences getting
clustered into the cluster increases, the predetermined distance pertaining to the cluster also
increases. As a result, a large number of non-similar subsequences may get clustered into the
cluster. Thus, said technique may result in generation of clusters of poor quality which in turn
10 may affect the outcome of further analytics being performed using such clusters.
[0010] The present subject matter describes a method and a system for identifying
frequently occurring waveform patterns in time series. According to an implementation, a
plurality of subsequences pertaining to time series data of the time series is clustered into one
or more spherical clusters of predetermined diameter. The predetermined diameter of a
15 spherical cluster is obtained by fixing a radius, say R, of the spherical cluster. As a result of
fixing the radius, a maximum distance between any two subsequences in the spherical cluster
is at most equal to the diameter of the spherical cluster. Fixing of the radius averts the
probability of the predetermined diameter increasing with the increase in number of the
subsequence being clustered into the cluster. Thus, clustering of subsequences into spherical
20 clusters of predetermined diameter, also referred to as bounded spherical clusters, reduces the
probability of a non-similar subsequence getting clustered into spherical cluster.
[0011] In an implementation, frequently occurring waveform patterns pertaining to one or
more time series are identified. Initially, each time series is segmented to obtain a plurality of
subsequences corresponding to the time series. In one example, the time series may be
25 segmented using a moving window of length w such that each subsequence obtained as a
result of the segmentation is of length w. For instance, a thousand seconds long time series
may be segmented using a moving window of length ten seconds to obtain nine hundred and
ninety one subsequences of length ten seconds each. Thereafter, a subsequence matrix
comprising the subsequences is generated. The subsequence matrix includes a subsequence in
30 every row and the number of rows in the subsequence matrix is equal to a number of
subsequences. For example, in the previous instance where the thousand second long time
5
series was segmented, the subsequence matrix may include nine hundred and ninety one rows,
where each row comprises a subsequence.
[0012] The subsequences included in the subsequence matrix may then be filtered and
normalized. In one example, the subsequences may be filtered using an indicator function
(f()). As would be understood, the indicator function may be 5 defined based on a
predetermined filtering condition and may be deployed for identifying subsequences
satisfying the predetermined filtering condition. The subsequences satisfying the filtering
condition are retained for further processing. On the other hand, all subsequences failing to
satisfy the predetermined filtering condition are filtered out and are not considered for further
10 processing. For instance, for a time series pertaining to a temperature sensor, motifs indicating
a temperature change of less than thirty degree Celsius between any two points in the
subsequence may be filtered out. For the purpose, an indicator function may be suitably
defined for filtering out the subsequences failing to meet the aforementioned condition. As
may be understood, the indictor function may be suitably defined and deployed depending
15 upon the implementation where the indication function is being deployed. The filtered
subsequences, i.e., the subsequences satisfying the predetermined filtering condition may then
be normalized for obtaining a plurality of normalized subsequences.
[0013] In order to normalize a filtered subsequence, initially a local mean of the filtered
subsequence may be computed. Thereafter, the local mean may be subtracted from the filtered
20 subsequence for obtaining a normalized subsequence. Similarly, each of the plurality of
filtered subsequences may be normalized in a similar manner for obtaining the plurality of
normalized subsequences. As may be understood, as a result of normalization, a waveform
occurring at different levels of magnitude throughout the plurality of filtered subsequences
may be collated at a single level of magnitude. For example, a waveform pattern may be
25 representative of two different temp states, say 20oF and 120oF, and thus may occur at two
different level of magnitude. Upon normalization, the waveform is normalized to a level
where a distance measure between the two waveform patterns will result in identification of
the two waveforms as similar.
[0014] The plurality of normalized subsequences may then be further processed for
30 removing trivially matching subsequences. In one implementation, trivially matching
6
subsequences may be removed using a technique of symbolic aggregate approximation (SAX)
representation. Initially, in order to identify trivially matching subsequences, each element of
a subsequence may be discretized into a symbol using SAX representation. As a result, a
symbolic depiction of the subsequence may be obtained. The subsequence may then be
compared with its adjacent subsequences to determine whether the symbolic 5 depiction of the
subsequence is equal to any of the adjacent subsequences. In a case where the symbolic
depiction of the subsequence is equal to its adjacent subsequences, the subsequence and the
adjacent subsequence are removed and are not considered for further processing. As a result
of trivially matching subsequence removal, a plurality of potentially non-trivially matching
10 subsequences, hereinafter referred to as non-trivial subsequences, is obtained. The non-trivial
subsequences may then be clustered into one or more spherical clusters, where each cluster is
of a predetermined radius (R).
[0015] Upon completion of clustering, spherical clusters with similar subsequences are
obtained. In one implementation, each cluster for which a number of subsequences, included
15 in the cluster, is less than a predefined threshold number is not considered for further
processing. In an example, the predetermined threshold may be equal to the number of timeseries
which are being analyzed. While, the clusters for which a number of subsequences
included in the cluster is greater than the predefined threshold number, are further processed
for identifying motifs. Such clusters may also be referred to as high support clusters.
20 [0016] In one implementation, the high support clusters may be analyzed for identifying
the frequently occurring waveform patterns. In order to identify the frequently occurring
waveform pattern, shifted clusters from among the high support clusters are initially identified
and removed. As will be understood, two clusters, say a first cluster (C1) and a second cluster
(C2), are ascertained to be shifted clusters when p% of the subsequences included in the C1
25 match trivially with the subsequences of the C2. Upon identification of such shifted clusters
from amongst the high support clusters, the shifted clusters are removed. Thereafter, trivially
matching subsequences from each of the remaining high support clusters may be identified. In
one example, the trivially matching subsequences may be identified using a two pointer
algorithm. Upon identification of the trivially matching subsequences, the trivially matching
30 subsequences are removed. The clusters of subsequences obtained after aforementioned
processes are referred to as group-motifs.
7
[0017] Upon obtaining the group-motifs, level splitting of each of the group motif may be
performed. In one example, for level splitting a group motif, a mean of each subsequence
present in the group motif is computed. Subsequently, the group motif may be split using one
dimensional clustering. For example, DBSCAN clustering may be used for splitting the group
motif based on the mean of each subsequence present in the group motif. 5 Thereafter, group
motifs for which the number of subsequences present in the group motif is higher than
predefined threshold number are ascertained to be the frequent motifs. The subsequences
included in the frequent motifs depict the frequently occurring waveform pattern.
[0018] In one implementation, the frequent motifs may be ranked based on a rank of each
10 frequent motif. In one example, the rank of a motif may be based on at least one of deviation,
level, and non-trivial match count. Ranking of the final motifs enables identification of top-k
frequent motifs, where k is an integer.
[0019] Thus, the present subject matter facilitates identification of frequently occurring
waveform patterns in time series in an efficient manner. As a result of fixing the diameter, the
15 diameter does not increase with increase in the number of subsequences getting clustered in a
cluster. Thus, the predetermined distance, pertaining to the cluster, with which a distance
between two subsequences is compared with for determination of similarity for clustering
remains constant and does not increase. As a result, the possibility of non-similar
subsequences getting clustered into a same cluster is reduced. Further, as will be clear from
20 the foregoing description, some of the duplicate subsequences and trivially matching
subsequences are removed at the outset, thereby improving the accuracy and computational
speed of the overall process for identification of the frequent occurring waveform patterns.
Furthermore, ranking of the final motifs enables identification of top final motifs, i.e., the
final motifs may be obtained in a particular arrangement based on their ranks.
25 [0020] These and other advantages of the present subject matter would be described in
greater detail in conjunction with the following figures. While aspects of described systems
and methods for optimizing application resources can be implemented in any number of
different computing systems, environments, and/or configurations, the embodiments are
described in the context of the following device(s).
8
[0021] Figure. 1 illustrates a network environment 100 implementing time series
analytics, according to an embodiment of the present subject matter. The network
environment 100 includes a plurality of computing devices 102-1, 102-2, 102-3,..., 102-N,
hereinafter collectively referred to as computing devices 102 and individually referred to as a
computing device 102, in communication with each other through 5 a network 104.
Communication links between the computing devices 102 are enabled through a desired form
of communication, for example, via dial-up modem connections, cable links, digital
subscriber lines (DSL), wireless or satellite links, or any other suitable form of
communication.
10 [0022] In one implementation, the computing devices 102 may be implemented as one or
more computing systems, such as personal computers, laptops, desktops, servers, and the like.
The network 104 may be a wireless network, a wired network, or a combination thereof. The
network 104 can also be an individual network or a collection of many such individual
networks, interconnected with each other and functioning as a single large network, e.g., the
15 Internet or an intranet. The network 104 can be implemented as one of the different types of
networks, such as intranet, local area network (LAN), wide area network (WAN), the internet,
and such. Further, the network 104 may include network devices that may interact with the
computing devices 102 through communication links.
[0023] In one implementation, the computing device 102 may include one or more
20 processor(s) 106, I/O interfaces 108, and a memory 110 coupled to the processor 106. The
processor 106 can be a single processing unit or a number of units, all of which could include
multiple computing units. The processor 106 may be implemented as one or more
microprocessors, microcomputers, microcontrollers, digital signal processors, central
processing units, state machines, logic circuitries, and/or any devices that manipulate signals
25 based on operational instructions. Among other capabilities, the processor 106 is configured
to fetch and execute computer-readable instructions and data stored in the memory 110.
[0024] The I/O interfaces 108 may include a variety of software and hardware interfaces,
for example, interfaces for peripheral device(s), such as a keyboard, a mouse, a display unit,
an external memory, and a printer. Further, the I/O interfaces 108 may enable the computing
30 device 102 to communicate with other devices, such as web servers and external databases.
9
The I/O interfaces 108 can facilitate multiple communications within a wide variety of
networks and protocol types, including wired networks, for example, local area network
(LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or
satellite. For the purpose, the I/O interfaces 108 include one or more ports for connecting a
number of computing systems with one another 5 or to a network.
[0025] The memory 110 may include any non-transitory computer-readable medium
known in the art including, for example, volatile memory, such as static random access
memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile
memory, such as read only memory (ROM), erasable programmable ROM, flash memories,
10 hard disks, optical disks, and magnetic tapes. In one implementation, the computing device
102 also includes module(s) 112 and data 114.
[0026] The module(s) 112, amongst other things, include routines, programs, objects,
components, data structures, etc., which perform particular tasks or implement data types. The
module(s) 112 may also be implemented as, signal processor(s), state machine(s), logic
15 circuitries, and/or any other device or component that manipulate signals based on operational
instructions.
[0027] Further, the module(s) 112 can be implemented in hardware, instructions executed
by a processing unit, or by a combination thereof. The processing unit can comprise a
computer, a processor, such as the processor 106, a state machine, a logic array or any other
20 suitable devices capable of processing instructions. The processing unit can be a generalpurpose
processor which executes instructions to cause the general-purpose processor to
perform the required tasks or, the processing unit can be dedicated to perform the required
functions.
[0028] In another aspect of the present subject matter, the module(s) 112 may be
25 machine-readable instructions (software) which, when executed by a processor/processing
unit, perform any of the described functionalities. The machine-readable instructions may be
stored on an electronic memory device, hard disk, optical disk or other machine-readable
storage medium or non-transitory medium. In one implementation, the machine-readable
instructions can be also be downloaded to the storage medium via a network connection.
10
[0029] In one implementation, the module(s) 112 further includes a pre-processing
module 116, a clustering module 118, a post-processing module 120, a ranking module 122,
and other module(s) 124. The other modules 124 may include programs or coded instructions
that supplement applications and functions of the computing device 102.
[0030] The data 114 serves, amongst other things, as a repository 5 for storing data
processed, received, and generated by one or more of the modules 112. The data 114 includes
processing data 126, clustering data 128, and other data 130. The other data 130 includes data
generated as a result of the execution of one or more modules in the modules 112.
[0031] In an embodiment, the computing device 102 may be implemented for performing
10 time series analytics. The time series analytics may be understood as analysis of time series
data pertaining to a time series. For instance, the computing device 102 may be deployed for
identifying frequently occurring waveform patterns pertaining to one or more time series.
Although the following description is with reference to plurality of time series, the principles
of the present subject matter may be applicable in case of analytics of a single time series.
15 [0032] In one implementation, the pre-processing module 116 may segment each of the
one or more time series into a plurality of subsequences. A subsequence may be understood as
a segment pertaining to time series data corresponding to the time series. In one example, the
pre-processing module 116 may segment the time series into subsequences of predetermined
length (w) using a moving window technique. Upon segmenting the time series, the pre20
processing module 116 may generate a subsequence matrix based on the one or more time
series. The subsequence matrix may include the plurality of subsequences corresponding to
each of the one or more time series. The pre-processing module 116 may further process the
subsequence matrix for filtering and normalizing the plurality of subsequences included in the
subsequence matrix.
25 [0033] In one implementation, the pre-processing module 116 may filter the subsequences
using an indicator function (f()) for obtaining a plurality of filtered subsequences. As will be
understood, the indicator function may be based on a predetermined filtering condition. For
instance, subsequences depicting waveform patterns having a slope of more than thirty
degrees at any point in the subsequence may be filtered by suitably defining the indicator
30 function. In said implementation, the pre-processing module 116 may apply the indicator
11
function to each of the plurality of subsequence included in the subsequence matrix.
Thereafter, the pre-processing 116 may obtain the subsequences, also referred to as filtered
subsequences, satisfying the predetermined condition. Upon obtaining the filtered
subsequences, the pre-processing module 116 may normalize the filtered subsequences for
obtaining a plurality of normalized subsequences. In order to normalize 5 a filtered
subsequence, the pre-processing module 116 may initially reduce the predetermined length
(w) of the subsequence to a reduced length (d) by piecewise averaging based on the filtered
subsequence. For instance, the pre-processing module 116 may normalize the filtered
subsequence using the following equation:
Si = _
_
Σ __
_
_
_
_
_
_
_____ _
10 (1)
where Si is a filtered subsequence, d is the reduced length, w is the predetermined length, and
value of i varies from one to d. Thereafter, the pre-processing module 116 may subtract a
local mean of the filtered subsequence from the filtered subsequence for obtaining a
normalized subsequence having zero mean. The local mean may be obtained as an average of
15 the values in a sub-sequence.
[0034] Subsequently, the pre-processing module 116 may further process the plurality of
normalized subsequences for removing trivially matching subsequences. As may be
understood, two subsequences are deemed to be trivially matching in a case where the two
subsequences have at least one time-stamp in common. Further, in another case, the two
20 subsequences may be deemed to be trivially matching if there is no other subsequence
between the two subsequences, in temporal order, such that at-least one subsequence in the
middle is significantly different from the two subsequences. In one example, the preprocessing
module 116 may use a known technique of SAX representation for removal of
trivially matching subsequences. A trivial subsequence may be understood as a subsequence
25 whose SAX symbolic depiction is same an SAX symbolic depiction of at least one of its
adjacent subsequences. The pre-processing module 116 may initially discretize each element
pertaining to the normalized subsequence into a symbol, using the technique of SAX
representation, for obtaining a symbolic depiction of the normalized subsequence. The preprocessing
module 116 may then compare the symbolic depiction of the normalized
12
subsequence with its adjacent normalized subsequences. In a case the symbolic depiction
matches with a symbolic depiction of at least one of the adjacent normalized subsequences,
the pre-processing module 116 may remove the adjacent subsequences. Upon removing the
adjacent subsequences, the pre-processing module 116 may obtain a plurality of potentially
non-trivial subsequences. The non-trivial subsequences may be understood 5 as a subsequence
whose symbolic depiction does not match with an adjacent normalized subsequence. The preprocessing
module 116 may store the plurality of non-trivial subsequences as a candidate
subsequence matrix in the processing data 126. The candidate subsequence matrix may be
further processed for clustering the non-trivial subsequences.
10 [0035] In one implementation, the clustering module 118 may cluster the plurality of nontrivial
subsequence into a plurality of spherical clusters of predetermined diameter based on a
fixed radius (R). For clustering a non-trivial subsequence, the clustering module 118 may
initially identify a target spherical cluster for the non-trivial subsequence. For identifying the
target spherical cluster, the clustering module 118 may initially identify a candidate cluster
15 set. The candidate cluster set may be understood as a set of one or more spherical clusters in
vicinity of the non-trivial subsequence. As will be understood, the candidate cluster set
includes the target spherical cluster of the non-trivial subsequence. In one example, the
clustering module 118 may use a clustering technique for identifying the candidate cluster set.
Examples of the clustering techniques include, but are not limited to, a binary search tree
20 (BST) acceleration, a local-sensitive hashing (LSH) acceleration, and a balanced iterative
reducing and clustering using hierarchies (BIRCH) acceleration. Thereafter, the clustering
module 118 may compute a cluster distance for each of the spherical clusters present in the
candidate cluster set. The cluster distance may be understood as a distance between a
subsequence which is to be clustered and a centroid of a cluster included in a candidate cluster
25 set of the subsequence. Upon computing the candidate cluster for each of the spherical
clusters present in the candidate cluster set, the clustering module 118 may identify a vicinity
cluster based on the cluster distance. The vicinity cluster may be understood as a spherical
cluster having the lowest candidate cluster distance from among the candidate cluster set.
Thereafter, the clustering module 118 may compare the cluster distance of the vicinity cluster
30 with the predetermined radius. In a case where the cluster distance of the vicinity cluster is
less than the predetermined radius, the clustering module 118 ascertains the vicinity cluster to
13
be the target spherical cluster. Thereafter, the clustering module 118 may cluster the nontrivial
subsequence in the target spherical cluster. Further, the clustering module 118 may
update the centroid of the target spherical cluster. In a case where the cluster distance of the
vicinity cluster is more than the predetermined radius, the clustering module 118 may create a
new cluster and cluster the non-trivial subsequence in the new cluster. The 5 clustering module
118 may store the plurality of spherical clusters in the clustering data 128.
[0036] Upon clustering of the non-trivial subsequences into the spherical clusters, the
spherical clusters may be further processed for obtaining the frequently occurring waveform
patterns. In one implementation, the post-processing module 120 may obtain the spherical
10 clusters stored in the clustering data 128 for further processing. The post processing module
120 may initially identify one or more high support clusters from the plurality of spherical
clusters. The high support cluster may understood as a spherical cluster for which a number of
non-trivial subsequences included in the spherical cluster is more than or equal to a
predefined threshold number. In an example, the predefined threshold number may be equal
15 to a number of the time series which are being analyzed. Thereafter, the post processing
module 120 may identify one or more pairs of shifted clusters from amongst the high support
clusters. As will be understood, two high support clusters, say a first high support cluster (C1)
and a second high support cluster (C2), are ascertained to be as shifted clusters in a case
where a predetermined percentage of a number of non-trivial subsequences of C1 overlap
20 with a number of non-trivial subsequences of the C2. In such a case, the post processing
module 120 may remove the high support cluster with the lower number of subsequences
from amongst the C1 and the C2. Thereafter, the post processing module 120 may process the
remaining high support clusters for removing the trivially matching subsequences present in
the high support clusters for obtaining one or more spherical clusters, also referred to as group
25 motifs. As described, the one or more group motifs do not include any shifted clusters and
trivially matching subsequences.
[0037] The post processing module 120 may then further process each of the one or more
spherical clusters for obtaining the frequently occurring waveform patterns. In one
implementation, the post processing module 120 may initially compute a mean for each non30
trivial subsequence present in the spherical cluster. The computed mean may also be referred
14
to as level. For instance, the post processing module 120 may compute the mean using the
following equation:
L(Si) = _
_
Σ S_
_ _
___ (2)
where L is the mean, Si is the non-trivial subsequence, and w is the predetermined length.
5 [0038] Thereafter, the post processing module 120 may use a one-dimensional clustering
technique for clustering the subsequences present in the spherical cluster into a plurality of
sub-clusters. In one example, the post processing module 120 may use DBSCAN clustering
for obtaining the sub-clusters from the spherical clusters.
[0039] Upon obtaining the sub-clusters, the post processing module 120 may ascertain
10 one or more frequent waveform clusters from amongst the one or more spherical clusters. In
one example, the post processing module 120 may ascertain the frequent waveform clusters
based on a number of subsequences in each of the sub-clusters included in the spherical
clusters. In said example, in a case where the number of subsequences included in a subcluster
of the spherical cluster is more than or equal to the predefined threshold number, the
15 post processing module 120 may ascertain the sub-cluster of the spherical cluster to be a
frequent waveform cluster. In another case, where the number of subsequences included in a
sub-cluster of the spherical cluster is less than the predefined threshold number, the post
processing module 120 may discard the sub-cluster of the spherical cluster. The post
processing module 120 may then store the frequent waveform clusters in the processing data
20 126. The frequent waveform cluster obtained depicts frequently occurring waveform patterns.
[0040] The frequent waveform clusters obtained may be ranked for identifying top-k
clusters, where k is an integer. In one implementation, the ranking module 122 may rank the
frequent waveform clusters using a predetermined ranking function. In one example, the
ranking function may be based on based on at least one of a deviation (Δ) of the frequent
25 waveform cluster, a level (l) of the frequent waveform cluster, and a non-trivial match count
(|Mi|) of the frequent waveform cluster. The deviation may be understood as an average
deviation of the non-trivial subsequences pertaining to the frequent waveform cluster. The
level of the frequent waveform cluster may be understood as an average of the means of each
of the non-trivial subsequence pertaining to the frequent waveform cluster. Further, the non15
trivial match count may be understood as a number of the non-trivial subsequences present in
the frequent waveform cluster.
[0041] Upon computing the rank for the frequent waveform clusters, the post processing
module 120 may arrange the frequent waveform clusters based on their respective ranks. For
instance, the post processing module 120 may arrange the frequent waveform 5 cluster in an
increasing order or a decreasing order based on the ranks of the frequent waveform clusters.
[0042] Figure 2 illustrates a method 200 for identifying frequently occurring waveform
patterns in time series, according to an embodiment of the present subject matter. The method
200 may be implemented in a variety of computing systems in several different ways. For
10 example, the method 200, described herein, may be implemented using the computing device
102, as described above.
[0043] The method 200, completely or partially, may be described in the general context
of computer executable instructions. Generally, computer executable instructions can include
routines, programs, objects, components, data structures, procedures, modules, functions, etc.,
15 that perform particular functions or implement particular abstract data types. A person skilled
in the art will readily recognize that steps of the method can be performed by programmed
computers. Herein, some embodiments are also intended to cover program storage devices,
e.g., digital data storage media, which are machine or computer readable and encode machineexecutable
or computer-executable programs of instructions, wherein said instructions
20 perform some or all of the steps of the described method 200.
[0044] The order in which the method 200 is described is not intended to be construed as
a limitation, and any number of the described method blocks can be combined in any order to
implement the method, or an alternative method. Additionally, individual blocks may be
deleted from the method without departing from the spirit and scope of the subject matter
25 described herein. Furthermore, the methods can be implemented in any suitable hardware,
software, firmware, or combination thereof. It will be understood that even though the method
200 is described with reference to the computing device 102, the description may be extended
to other systems as well.
16
[0045] With reference to the description of Figure 2, for the sake of brevity, the details of
the components of the computing device 102 are not discussed here. Such details can be
understood as provided in the description provided with reference to Figure 1.
[0046] At block 202, each of one or more time series are segmented into a plurality of
subsequences. In one implementation, each time series may be segmented into 5 a plurality of
subsequences using a moving window of predetermined length. A subsequence may be
understood as a segment of predetermined length pertaining to time series data corresponding
to the time series. In one example, the pre-processing module 116 may segment the time
series into the plurality of subsequences.
10 [0047] At block 204, a subsequence matrix comprising the plurality of subsequences is
generated. In one implementation, the pre-processing module 116 may generate the
subsequence matrix based on the segmentation. The subsequence matrix may comprise the
plurality of subsequence corresponding to each of the time series.
[0048] At block 206, the subsequence matrix may be processed to obtain a candidate
15 subsequence matrix. Upon generating the subsequence matrix, the plurality of subsequences
in the subsequence matrix may initially be filtered using an indicator function for obtaining a
plurality of filtered subsequences. Thereafter, the filtered subsequences may be normalized
for obtaining a plurality of normalized subsequences. Subsequently, trivially matching
subsequences may be removed from the normalized subsequences using a known technique of
20 SAX representation for obtaining a plurality of non-trivial subsequences.
[0049] At block 208, the plurality of non-trivial subsequences is clustered into a plurality
of spherical clusters having a predetermined diameter. In one implementation, the non-trivial
subsequences may be clustered into spherical clusters having a predetermined diameter which
in turn is based on a fixed radius (R). Initially a candidate cluster set may be indentified for
25 the non-trivial subsequence using a clustering technique, for example, BST acceleration, LSH
acceleration, and BIRCH acceleration. Thereafter, a vicinity spherical cluster may be
identified from the candidate cluster set. In a case where a cluster distance of the vicinity
spherical cluster is less than the predetermined radius, the non-trivial subsequence may be
clustered into the vicinity spherical cluster. In a case where the cluster distance of the vicinity
30 spherical cluster is more than the predetermined radius, the non-trivial subsequence may be
17
clustered in a new spherical cluster. In one example, the clustering module 118 may cluster
the non-trivial subsequences in the spherical clusters.
[0050] At block 210, a plurality of sub-clusters for one or more spherical clusters, from
among the plurality of spherical clusters, are obtained. In one example, the spherical clusters
may be further processed for identifying one or more high support clusters. Thereafter, 5 shifted
clusters from among the high support clusters may be identified and removed. Upon removal
of the shifted clusters, trivially matching subsequences from the remaining high support
clusters may be removed for obtaining the one or more spherical clusters. Thereafter, each of
the one or more spherical clusters may be further processed. For example, the spherical
10 cluster may be further clustered based on a mean of each of the non-trivial subsequences in
the spherical cluster. In one example, one dimensional clustering technique, such as DBSCAN
clustering, may be used. As a result of clustering, the plurality of sub-clusters is obtained. In
one implementation, the post processing module 120 may obtain the plurality of sub-clusters
for each of the one or more spherical clusters.
15 [0051] At block 212, one or more frequent waveform clusters are ascertained from the
one or more spherical clusters. In one example, the frequent waveform clusters may be
ascertained based on a number of subsequences in each of the sub-clusters of the spherical
cluster. In a case where the number of subsequence in a sub-cluster of the spherical cluster is
more than a predefined threshold number, the sub-cluster is ascertained to be a frequent
20 waveform cluster. In another case, where the number of subsequence in a sub-cluster of the
spherical cluster is less than the predefined threshold number, the sub-cluster may be
discarded. In an example, the predefined threshold number may be equal to a number of the
time series being analyzed. The ascertained frequent waveform clusters depicts frequently
occurring waveform patterns.
25 [0052] The frequent waveform clusters obtained may be further ranked using a ranking
function. In one example, the ranking function may be based on at least one of a deviation of
the frequent waveform cluster, a level of the frequent waveform cluster, and a non-trivial
match count of the frequent waveform cluster. The ranking of the frequent waveform cluster
facilitates in identifying top frequently occurring waveform pattern.
18
[0053] Although implementations for methods and systems for identifying frequently
occurring waveform patterns are described, it is to be understood that the present subject
matter is not necessarily limited to the specific features or methods described. Rather, the
specific features and methods are disclosed as implementations for identifying frequently
occurring 5 waveform patterns.
19
I/We claim:
1. A method for identifying frequently occurring waveform patterns in time series, the
method comprising:
segmenting each of one or more time series into a plurality of subsequences,
wherein each of the plurality of subsequences is a segment of a predetermined 5 length
pertaining to time series data corresponding to the time series;
obtaining a candidate subsequence matrix, comprising a plurality of non-trivial
subsequences, wherein each of the non-trivial subsequence is a subsequence having
unique symbolic aggregate approximation (SAX) symbolic representation in
10 comparison to adjacent non-trivial subsequences;
clustering the plurality of non-trivial subsequences into a plurality of spherical
clusters, wherein each of the plurality of spherical clusters is of a predetermined
diameter;
obtaining a plurality of sub-clusters for each of one or more spherical clusters,
15 from among the plurality of spherical clusters, based on a mean of each of the plurality
of non-trivial subsequences present in the spherical cluster, wherein each of the
plurality of sub-clusters includes one or more non-trivial subsequences from amongst
the plurality of non-trivial subsequences; and
ascertaining, one or more frequent waveform clusters, from each of the one or
20 more spherical clusters based on a number of non-trivial subsequences present in each
of the plurality of sub-clusters of the spherical cluster, wherein a frequent waveform
cluster has a number of non-trivial subsequences greater than a predefined threshold
number, and wherein the non-trivial subsequences depict frequently occurring
waveform patterns.
25 2. The method as claimed in claim 1, wherein the obtaining further comprises:
generating a subsequence matrix based on the segmenting, wherein the
subsequence matrix comprises each of the plurality of subsequences; and
processing the subsequence matrix to obtain the candidate subsequence matrix.
3. The method as claimed in claim 2, wherein the processing further comprises:
30 filtering the plurality of subsequences using an indicator function for obtaining
a plurality of filtered subsequences, wherein each of the plurality of filtered
20
subsequences satisfies a predetermined filtering condition depicted by the indicator
function;
reducing the predetermined length of each of the plurality of filtered
subsequences to a reduced length using piecewise averaging of the filtered
5 subsequences;
computing a local mean for each of the plurality of filtered subsequences of
reduced length; and
subtracting, for each of the plurality of filtered subsequences of reduced length,
the local mean from the filtered subsequence to obtain a plurality of normalized
10 subsequences, wherein a normalized subsequence is a subsequence having a zero
mean;
discretizing, for each of the plurality of normalized subsequences, each element
pertaining to the normalized subsequence into a symbol using the SAX representation
for obtaining a symbolic depiction of the normalized subsequence; and
15 identifying, from among the discretized plurality of normalized subsequences,
at least one non-trivial subsequence, wherein the non-trivial subsequence is a
subsequence whose symbolic depiction does not match with a symbolic depiction of
an adjacent subsequence.
4. The method as claimed in claim 1, wherein the clustering further comprises:
20 ascertaining, for each of the plurality of non-trivial subsequences, a candidate
cluster set based on a clustering technique, wherein the candidate cluster set comprises
one or more spherical clusters in vicinity of the non-trivial subsequence and wherein
the clustering technique is one of a binary search tree (BST) acceleration, a localsensitive
hashing (LSH) acceleration, and a balanced iterative reducing and clustering
25 using hierarchies (BIRCH) acceleration;
computing a cluster distance for each of the one or more spherical clusters
pertaining to the candidate cluster set, wherein the cluster distance is a distance
between the non-trivial subsequence and a centroid of the spherical cluster;
identifying a vicinity spherical cluster, from among the one or more spherical
30 clusters, wherein the vicinity spherical cluster is a cluster having lowest value of
cluster distance; and
21
comparing the cluster distance of the vicinity spherical cluster with a
predetermined threshold distance, wherein the predetermined threshold distance is
equal to the predetermined radius.
5. The method as claimed in claim 4 wherein the clustering further comprises:
ascertaining, for the cluster distance of the vicinity spherical 5 cluster being less
than the predetermined threshold distance, the vicinity spherical cluster as a target
spherical cluster; and
including the non-trivial subsequence in the target spherical cluster.
6. The method as claimed in claim 4, wherein the clustering further comprises:
10 creating, for the cluster distance of the vicinity spherical cluster being more
than the predetermined threshold, a new cluster; and
including the non-trivial subsequence in the new cluster.
7. The method as claimed in claim 4, wherein the candidate cluster set is ascertained
based on at least one of a binary search tree (BST) acceleration technique, a locally
15 sensitive hashing (LSH) acceleration technique, and a BIRCH acceleration technique.
8. The method as claimed in claim 1, wherein each of the plurality of non-trivial
subsequences present in the spherical cluster are clustered into sub-clusters using onedimensional
clustering techniques.
9. The method as claimed in claim 1, wherein the method further comprises:
20 identifying, from amongst the plurality of spherical clusters, one or more high
support spherical clusters, wherein each of the one or more high support spherical
clusters is a spherical cluster having a number of subsequences greater than the
predefined threshold number;
identifying one or more pairs of shifted spherical clusters from among the
25 identified high support clusters, wherein a predetermined percentage of non-trivial
subsequences of a first high support spherical cluster present in a pair of shifted
spherical clusters is similar to the non-trivial subsequences of a second high support
spherical cluster present in the pair of shifted spherical cluster, and wherein the
number of non-trivial subsequence in the first high support cluster is less than the
30 number of non-trivial subsequences in the second high support cluster; and
22
obtaining the second high support clusters from the one or more pairs of shifted
clusters; and
processing each of the high support clusters to remove trivial match
subsequences present in the high support cluster for obtaining the one or more
spherical clusters pertaining to the plurality of spherical 5 clusters.
10. The method as claimed in claim 1, wherein the method further comprises:
computing a rank for each of the one or more frequent waveform clusters using
a ranking function, wherein the ranking function is based on at least one of a deviation
of the frequent waveform cluster, a level of the frequent waveform cluster, and a non10
trivial match count pertaining to the frequent waveform cluster, wherein the deviation
is a an average deviation of the non-trivial subsequences pertaining to the frequent
waveform cluster, the level of the frequent waveform cluster is an average of the
means of each of the non-trivial subsequence pertaining to the frequent waveform
cluster, and the non-trivial match count is a number of the non-trivial subsequences
15 present in the frequent waveform cluster; and
arranging the one or more frequent waveform clusters based on the rank of each
of the one or more frequent waveform clusters.
11. A computing device (102) comprising:
a processor (106);
20 a pre-processing module (116) coupled to the processor (106) to,
segments each of one or more time series into a plurality of
subsequences, wherein each of the plurality of subsequences is a segment of a
predetermined length pertaining to time series data corresponding to the time
series;
25 obtains a candidate subsequence matrix, wherein the candidate
subsequence matrix comprises a plurality of non-trivial subsequences, wherein
each of the non-trivial subsequence is a subsequence having unique symbolic
aggregate approximation (SAX) symbolic representation in comparison to
adjacent non-trivial subsequences;
30 a clustering module (118) coupled to the processor (106) to, cluster the plurality
of non-trivial subsequences into a plurality of spherical clusters, wherein each of the
23
plurality of spherical clusters is of a predetermined diameter, and wherein a maximum
distance between a first non-trivial subsequence and a second non-trivial subsequence
present in the spherical cluster is less than or equal to the predetermined diameter; and
a post-processing module (120) coupled to the processor (106) to,
obtain a plurality of sub-clusters for one or more spherical 5 clusters from
among the plurality of spherical clusters based on a mean of each of the
plurality of non-trivial subsequences present in the spherical cluster, wherein
each of the plurality of sub-clusters includes one or more non-trivial
subsequences from amongst the plurality of non-trivial subsequences; and
10 ascertain, one or more frequent waveform clusters, from each of the one
or more spherical clusters based on a number of non-trivial subsequences
present in each of the plurality of sub-clusters of the spherical cluster, wherein a
frequent waveform cluster has a number of non-trivial subsequences greater
than a predefined threshold number, and wherein the non-trivial subsequences
15 depict frequently occurring waveform patterns.
12. The computing device (102) as claimed in claim 11, wherein the pre-processing
module (116) further,
generates a subsequence matrix based on the segmenting, wherein the
subsequence matrix comprises each of the plurality of subsequences;
20 filters the plurality of using an indicator function for obtaining a plurality of
filtered subsequences, wherein each of the plurality of filtered subsequences satisfies a
predetermined filtering condition depicted by the indicator function;
reduces the predetermined length of each of the plurality of filtered
subsequences to a reduced length using piecewise averaging of the filtered
25 subsequences;
computes a local mean for each of the plurality of filtered subsequences of
reduced length; and
subtracts, for each of the plurality of filtered subsequences of reduced length,
the local mean from the filtered subsequence to obtain a plurality of normalized
30 subsequences, wherein a normalized subsequence is a subsequence having a zero
mean;
24
discretizes, for each of the plurality of normalized subsequences, each element
pertaining to the normalized subsequence into a symbol using the SAX representation
for obtaining a symbolic depiction of the normalized subsequence; and
identifies, from among the discretized plurality of normalized subsequences, at
least one non-trivial subsequence, wherein the non-trivial 5 subsequence is a
subsequence whose symbolic depiction does not match with a symbolic depiction of
an adjacent subsequence.
13. The computing device (102) as claimed in claim 11, wherein the clustering module
(118) further,
10 ascertains, for each of the plurality of non-trivial subsequences, a candidate
cluster set using a clustering technique, wherein the candidate cluster set comprises
one or more spherical clusters in vicinity of the non-trivial subsequence;
computes a cluster distance for each of the one or more spherical clusters
pertaining to the candidate cluster set, wherein the cluster distance is a distance
15 between the non-trivial subsequence and a centroid of the spherical cluster;
identifies a vicinity spherical cluster, from among the one or more spherical
clusters, wherein the vicinity spherical cluster is a cluster having lowest value of
cluster distance; and
compares the cluster distance of the vicinity spherical cluster with a
20 predetermined threshold distance, wherein the predetermined threshold distance is
equal to the predetermined radius.
14. The computing device (102) as claimed in claim 13, wherein the clustering module
(118) further,
ascertains, for the cluster distance of the vicinity spherical cluster being less
25 than the predetermined threshold distance, the vicinity spherical cluster as a target
spherical cluster; and
clusters the non-trivial subsequence in the target spherical cluster.
15. The computing device (102) as claimed in claim 13, wherein the clustering module
(118) further,
30 creates, for the cluster distance of the vicinity spherical cluster being more than
the predetermined threshold, a new cluster; and
25
clusters the non-trivial subsequence in the new cluster.
16. The computing device (102) as claimed in claim 11, wherein the post processing
module (120) further,
identifies, from amongst the plurality of spherical clusters, one or more high
support spherical clusters, wherein each of the one or more high 5 support spherical
clusters is a spherical cluster whose number of subsequences is greater than a number
of the one or more time series;
identifies one or more pairs of shifted spherical clusters from among the
identified high support clusters, wherein a predetermined percentage of non-trivial
10 subsequences of a first high support spherical cluster present in a pair of shifted
spherical clusters is similar to the non-trivial subsequences of a second high support
spherical cluster present in the pair of shifted spherical cluster, and wherein the
number of non-trivial subsequence in the first high support cluster is less than the
number of non-trivial subsequences in the second high support cluster; and
15 obtains the second high support clusters from the one or more pairs of shifted
clusters; and
processes each of the high support clusters to remove trivial match
subsequences present in the high support cluster for obtaining the one or more
spherical clusters pertaining to the plurality of spherical clusters.
20 17. The computing device (102) as claimed in claim 11, wherein the computing device
(102) further comprises a ranking module (122) coupled to the processor (106) to,
computes a rank for each of the one or more frequent waveform clusters using a
ranking function, wherein the ranking function is based on at least one of a deviation
of the frequent waveform cluster, a level of the frequent waveform cluster, and a non25
trivial match count pertaining to the frequent waveform cluster, wherein the deviation
is a an average deviation of the non-trivial subsequences pertaining to the frequent
waveform cluster, the level of the frequent waveform cluster is an average of the
means of each of the non-trivial subsequence pertaining to the frequent waveform
cluster, and the non-trivial match count is a number of the non-trivial subsequences
30 present in the frequent waveform cluster; and
26
arranges the one or more frequent waveform clusters based on the rank of each
of the one or more frequent waveform clusters.
18. A non-transitory computer-readable medium having embodied thereon a computer
program for executing a method comprising:
segmenting each of one or more time series into a plurality 5 of subsequences,
wherein each of the plurality of subsequences is a segment of a predetermined length
pertaining to time series data corresponding to the time series;
obtaining a candidate subsequence matrix, wherein the candidate subsequence
matrix comprises a plurality of non-trivial subsequences, wherein each of the non10
trivial subsequence is a subsequence having unique symbolic aggregate approximation
(SAX) symbolic representation in comparison to adjacent non-trivial subsequences;
clustering the plurality of non-trivial subsequences into a plurality of spherical
clusters, wherein each of the plurality of spherical clusters is of a predetermined
diameter;
15 obtaining a plurality of sub-clusters for one or more spherical clusters from
among the plurality of spherical clusters based on a mean of each of the plurality of
non-trivial subsequences present in the spherical cluster, wherein each of the plurality
of sub-clusters includes one or more non-trivial subsequences from amongst the
plurality of non-trivial subsequences; and
20 ascertaining, one or more frequent waveform clusters, from each of the one or
more spherical clusters based on a number of non-trivial subsequences present in each
of the plurality of sub-clusters of the spherical cluster, wherein a frequent waveform
cluster has a number of non-trivial subsequences greater than a predefined threshold
number, and wherein the non-trivial subsequences depict frequently occurring
waveform patterns.