# US 2021/0081844 A1 · System and method for categorical time-series clustering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0081844 A1
- Document ID: US20210081844A1
- Status: Published application
- Kind: A1
- Application number: 17/025,137
- Filed: 2020-09-18
- Published: 2021-03-18
- Earliest claimed: 2019-09-18
- Assignees: Tata Consultancy Services Limited
- Applicants: Tata Consultancy Services Limited
- Inventors: Sakyajit BHATTACHARYA; Avik GHOSE
- Web page: https://patentgrep.com/patent/US20210081844A1

## CPC

- G06N 20/00: Machine learning
- G16Y 40/20: Analytics; Diagnosis
- G06F 16/285: {Clustering or classification}
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06Q 10/1091: Recording time for administrative or management purposes
- G06Q 50/22: Social work or social welfare, e.g. community support activities or counselling services
- G16Y 10/50: Finance; Insurance
- G16Y 10/55: Education
- G16Y 10/60: Healthcare; Welfare
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G16Y: INFORMATION AND COMMUNICATION TECHNOLOGY SPECIALLY ADAPTED FOR THE INTERNET OF THINGS [IoT]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The processor implemented method of claim 1, wherein the plurality of categorical time-series are obtained based on a monitoring of movements of the plurality of subjects over a period of time by the plurality of sensors.

### Claim 3 (depends on 2)

The processor implemented method of claim 2, wherein the plurality of sensors comprises passive unobtrusive sensors.

### Claim 4 (depends on 1)

The processor implemented method of claim 1, wherein each of the plurality of categorical time-series comprises categorical parameters comprising qualitative variables associated with the plurality of subjects.

### Claim 5

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.

### Claim 6 (depends on 5)

The system of claim 5, wherein the one or more hardware processors are configured to obtain the plurality of categorical time-series based on a monitoring of movements of the plurality of subjects over a period of time by the plurality of sensors.

### Claim 7 (depends on 6)

The system of claim 6, wherein the plurality of sensors comprises passive unobtrusive sensors.

### Claim 8 (depends on 6)

The system of claim 6, wherein each of the plurality of categorical time-series comprises categorical parameters comprising qualitative variables associated with the plurality of subjects.

### Claim 9

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.
