US 11,748,658 B2Granted

System and method for categorical time-series clustering

AssigneeTata Consultancy Services Limited

InventorsSakyajit Bhattacharya, Avik Ghose

Life of this patent

Estimating the term…

Loading patent…

Abstract

This disclosure relates generally to categorical time-series clustering. In an embodiment, the method for categorical time-series clustering for categorical time-series associated with distinct subjects obtained from sensors. Based on the categorical time-series, the subjects are clustered into clusters by using a Markov chain model. Clustering the subjects include assigning each subject to a cluster. The subjects are assigned to the clusters by determining cluster-specific transition matrices based on a transitional probability of the subject's transitioning between states. A semi-distance function is constructed for each cluster-specific transitional matrix between the states at multiple time instances, which us indicative of a conditional probability of movement of the subject between the states at different time instance. Using an expectation maximization (EM) model, one or more latent variables of each of the cluster-specific transitional matrices are obtained to determine a likelihood of association of the subject to the cluster.

Claims9

Dependent claims

A processor implemented method, comprising:

obtaining, from a plurality of sensors, a plurality of categorical time-series associated with a plurality of subjects, via one or more hardware processors, wherein each categorical time-series from amongst the plurality of categorical time-series associated with a distinct subject from amongst the plurality of subjects;
and
clustering, based on the plurality of categorical time-series, the plurality of subjects into a plurality of clusters in an unsupervised manner by using a Markov chain model to assign the plurality of subjects to the plurality of clusters, via the one or more hardware processors, assigning a subject from amongst the plurality of subjects into a cluster from amongst the plurality of clusters comprises:
determining a plurality of cluster-specific transition matrices (Mh) based on a transitional probability of the subject's transitioning from a first state to a second state, the plurality of cluster-specific transition matrices (Mh) associated with the Markov Chain Model and obtained from the plurality of categorical time-series;
constructing, for each of the plurality of cluster-specific transitional matrices, a semi-distance function between the first state and the second state at multiple time instances, the semi-distance function indicative of a conditional probability of movement of the subject from the first state at a first time instant to the second state at a second time instant;
and
obtaining, by using an expectation maximization (EM) model, one or more latent variables of each of the cluster-specific transitional matrices to determine an association of the subject to the cluster;
wherein the one or more latent variables comprises a logarithmic function as shown below:
Log
⁢
L
=
∑
i
=
1
n
[
y
i
(
log
⁢
L
i
M
2
+
∑
j
=
1
k
l
j
i
⁢
log
⁢
s
j
)
+
(
1
-
y
i
)
⁢
(
log
⁢
L
i
M
1
+
∑
j
=
1
k
l
j
i
⁢
log
⁡
(
1
-
s
j
)
]
where,
LiM1=Πj,k(mjk1)Ni,jk and LiM2=Πj,k(mjk2)Ni,jk
Wherein, the one or more latent variables are Yi=1 if yi is generated by M2 and Yi=0 otherwise for i=1, 2, . . . ,n,
Wherein, the logarithmic function Log L is a summation of cluster-specific transitional matrices based on the transitional probability of the subject's transitioning from the first state LiM1 to the second state LiM2 associated with the Markov Chain Model,
Where, mjk1 is an off-diagonal element of M1, mjk2 is an off-diagonal element of M2, Ni,jk is a cardinality of transitions from state j to state k observed in time series i and sj is a jth diagonal element in a diagonal matrix with a state j of the Markov Chain Model.

78 more elements

A system (300) comprising:

one or more memories (304);
and
one or more first hardware processors (302), the one or more first memories (304) coupled to the one or more first hardware processors (302), wherein the one or more first hardware processors (302) are configured to execute programmed instructions stored in the one or more first memories (304), to:
obtain, from a plurality of sensors, a plurality of categorical time-series associated with a plurality of subjects, each categorical time-series from amongst the plurality of categorical time-series associated with a distinct subject from amongst the plurality of subjects;
and
cluster, based on the plurality of categorical time-series, the plurality of subjects into a plurality of clusters in an unsupervised manner by using a Markov chain model to assign the plurality of subjects to the plurality of clusters, wherein to assign a subject from amongst the plurality of subjects into a cluster from amongst the plurality of clusters, the one or more hardware processors are configured by the instructions comprises:
determine a plurality of cluster-specific transition matrices (Mh) based on a transitional probability of the subject's transitioning from a first state to a second state, the plurality of cluster-specific transition matrices (Mh) associated with the Markov Chain Model and obtained from the plurality of categorical time-series;
construct, for each of the plurality of cluster-specific transitional matrices, a semi-distance function between the first state and the second state at multiple time instances, the semi-distance function indicative of a conditional probability of movement of the subject from the first state at a first time instant to the second state at a second time instant;
and
obtain, by using an expectation maximization (EM) model, one or more latent variables of each of the cluster-specific transitional matrices to determine an association of the subject to the cluster,
wherein the one or more latent variables comprises a logarithmic function as shown below:
Log
⁢
L
=
∑
i
=
1
n
[
y
i
(
log
⁢
L
i
M
2
+
∑
j
=
1
k
l
j
i
⁢
log
⁢
s
j
)
+
(
1
-
y
i
)
⁢
(
log
⁢
L
i
M
1
+
∑
j
=
1
k
l
j
i
⁢
log
⁡
(
1
-
s
j
)
]
where,
LiM1=Πj,k(mjk1)Ni,jk and LiM2=Πj,k(mjk2)Ni,jk
wherein, the one or more latent variables are Yi=1 if y;
is generated by M2 and Yi=0 otherwise for i=1, 2, . . . ,n,
wherein, the logarithmic function Log L is a summation of cluster-specific transitional matrices based on the transitional probability of the subject's transitioning from the first state LiM1 to the second state LiM2 associated with the Markov Chain Model,
where, mjk1 is an off-diagonal element of M1, mjk2 is an off-diagonal element of M2, Ni,jk is a cardinality of transitions from state j to state k observed in time series i and sj is a jth diagonal element in a diagonal matrix with a state j of the Markov Chain Model.

82 more elements

One or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors cause:

obtaining, from a plurality of sensors, a plurality of categorical time-series associated with a plurality of subjects, via one or more hardware processors, wherein each categorical time-series from amongst the plurality of categorical time-series associated with a distinct subject from amongst the plurality of subjects;
and
clustering, based on the plurality of categorical time-series, the plurality of subjects into a plurality of clusters in an unsupervised manner by using a Markov chain model to assign the plurality of subjects to the plurality of clusters, via the one or more hardware processors, assigning a subject from amongst the plurality of subjects into a cluster from amongst the plurality of clusters comprises:
determining a plurality of cluster-specific transition matrices (Mh) based on a transitional probability of the subject's transitioning from a first state to a second state, the plurality of cluster-specific transition matrices (Mh) associated with the Markov Chain Model and obtained from the plurality of categorical time-series;
constructing, for each of the plurality of cluster-specific transitional matrices, a semi-distance function between the first state and the second state at multiple time instances, the semi-distance function indicative of a conditional probability of movement of the subject from the first state at a first time instant to the second state at a second time instant;
and
obtaining, by using an expectation maximization (EM) model, one or more latent variables of each of the cluster-specific transitional matrices to determine an association of the subject to the cluster,
wherein the one or more latent variables comprises a logarithmic function as shown below:
Log
⁢
L
=
∑
i
=
1
n
[
y
i
(
log
⁢
L
i
M
2
+
∑
j
=
1
k
l
j
i
⁢
log
⁢
s
j
)
+
(
1
-
y
i
)
⁢
(
log
⁢
L
i
M
1
+
∑
j
=
1
k
l
j
i
⁢
log
⁡
(
1
-
s
j
)
]
where,
LiM1=Πj,k(mjk1)Ni,jk and LiM2=Πj,k(mjk2)Ni,jk
wherein, the one or more latent variables are Yi=1 if yi is generated by M2 and Yi=0 otherwise for i=1, 2, . . . ,n,
wherein, the logarithmic function Log L is a summation of cluster-specific transitional matrices based on the transitional probability of the subject's transitioning from the first state LiM1 to the second state LiM2 associated with the Markov Chain Model,
where, mjk1 is an off-diagonal element of M1, mjk2 is an off-diagonal element of M2, Ni,jk is a cardinality of transitions from state j to state k observed in time series i and sj is a jth diagonal element in a diagonal matrix with a state j of the Markov Chain Model.

78 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/025,137Filed 18 Sep 2020
Priority: IN 20192103765218 Sep 2019
Published: US 2021/0081844 A118 Mar 2021
Granted: 5 Sep 2023
Term ends: Not estimatedThe source records don’t support an estimate.

Classification13 codes

G06N 20/00
Machine learning
G16Y 40/20
IoT characterised by the purpose of the information processing: analytics; Diagnosis
G06F 16/285
Relational databases: clustering or classification
G06Q 10/04
Administration; Management: forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or…