# US 10,482,158 B2 · User-level KQI anomaly detection using markov chain model

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

- Number: US 10,482,158 B2
- Document ID: US10482158B2
- Status: Granted
- Kind: B2
- Application number: 15/476,584
- Filed: 2017-03-31
- Published: 2018-10-04
- Granted: 2019-11-19
- Earliest claimed: 2017-03-31
- Assignees: Futurewei Technologies, Inc.
- Applicants: Futurewei Technologies, Inc.
- Inventors: Kai Yang; Yanjia Sun; Ruilin Liu; Deti Liu; Jin Yang
- Web page: https://patentgrep.com/patent/US10482158B2

## CPC

- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 5/045: Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- H04W 24/02: Arrangements for optimising operational condition
- H04W 24/04: Arrangements for maintaining operational condition
- H04W 36/0044: {of quality context information}
- G06N 5/025: Extracting rules from data
- H04W 24/08: Testing, {supervising or monitoring} using real traffic
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Techniques are provided for monitoring the performance of a user device in a communication network. The techniques include detecting an anomaly in a performance measurement such as a key quality indicator (KQI) of the user device. The techniques include obtaining historical measurements of the KQI for user devices. The historical measurements are assigned to states to reflect whether the performance is good or bad, or somewhere in between. The states can be defined differently for different hours in the day so that the states represent the relative performance for that time of day. For each user device, a Markov model is provided indicating probabilities of transitions between the states. Additional measurements are obtained of the KQI for a selected user device, and the Markov model of the selected user device is used to detect an anomaly in the additional measurements.

## Claims

### Claim 1

A device, comprising:
a non-transitory memory storage comprising instructions; and
one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:
obtain historical measurements of a key quality indicator for a set of user devices including a selected user device in a communication network;
assign the historical measurements to a plurality of states, one state per historical measurement;
determine stationary probabilities and transition probabilities of the plurality of states for the set of user devices;
obtain additional measurements of the key quality indicator for the selected user device;
assign the additional measurements to the plurality of states, one state per additional measurement, to provide a sequence of states; and
for each window of multiple windows applied to the sequence of states, determine a probability of a sequence of multiple states in the window based on the stationary probabilities and the transition probabilities of the plurality of states for the set of user devices and determine whether the probability of the sequence of multiple states is consistent with an anomaly;
determine that, among the additional measurements, an additional measurement is an anomaly based on whether the probabilities of the sequences of multiple states are consistent with the anomaly; and
generate an indication of the anomaly.

### Claim 2 (depends on 1)

The device of claim 1, wherein:
the transition probabilities are determined using a Markov model.

### Claim 3 (depends on 1)

The device of claim 1, wherein the one or more processors execute the instructions to:
determine the stationary probabilities of each state of the plurality of states based on a number of times the historical measurements for the selected user device are assigned to the state relative to a number of the historical measurements for the selected user device.

### Claim 4 (depends on 1)

The device of claim 1, wherein:
the additional measurements are obtained over a time period which is less than a time period over which the historical measurements are obtained.

### Claim 5 (depends on 1)

The device of claim 1, wherein:
the plurality of states represent different quality levels, ranging from a lowest state which represents a lowest quality level to a highest state which represents a highest quality level.

### Claim 6 (depends on 1)

The device of claim 1, wherein the historical measurements are for a plurality of user devices in the communication network, and the one or more processors execute the instructions to:
associate the historical measurements with different times of day, such that each historical measurement is associated with one time of day;
form clusters of times with similar historical measurements; and
for each cluster, determine a range of the historical measurements and define the plurality of states based on the range, wherein the historical measurements of each cluster are assigned to the plurality of states which are defined for the cluster.

### Claim 7 (depends on 6)

The device of claim 6, wherein the one or more processors execute the instructions to:
for each cluster, divide the range of the historical measurements into unequal increments and define the plurality of states based on the unequal increments.

### Claim 8 (depends on 1)

The device of claim 1, wherein:
the windows are overlapping.

### Claim 9 (depends on 1)

The device of claim 1, wherein:
for each window, one of the stationary probabilities is for an initial state of the sequence of states, one or more of the transition probabilities are for reaching one or more subsequent states in the sequence of multiple states in the window, and the probability of the sequence of multiple states in the window is based on the one of the stationary probabilities and the one or more of the transition probabilities.

### Claim 10 (depends on 1)

The device of claim 1, wherein:
for each window, the probability of the sequence of multiple states in the window is based on stationary probabilities of an initial state of the sequence of states and of one or more subsequent states in the sequence of multiple states in the window.

### Claim 11 (depends on 1)

The device of claim 1, wherein:
for each window, the probability of the sequence of multiple states in the window is based on a geometric mean of probabilities of each state of the sequence of multiple states in the window.

### Claim 12

A method for processing data, comprising:
obtaining historical measurements of a key quality indicator for a set of user devices in a communication network;
assigning the historical measurements to a plurality of states, one state per measurement;
determining stationary probabilities and transition probabilities of the plurality of states for the set of user devices;
obtaining additional measurements of the key quality indicator for a selected user device;
assigning the additional measurements to the plurality of states, one state per measurement, to provide a sequence of multiple states;
determining a probability of the sequence of multiple states based on the stationary probabilities and the transition probabilities of the plurality of states for the set of user devices;
determining whether the probability of the sequence of multiple states is consistent with an anomaly and
labelling the additional measurements to indicate which of the additional measurements are consistent with the anomaly.

### Claim 13 (depends on 12)

The method of claim 12, wherein:
the probability of the sequence of multiple states is based on a stationary probability of an initial state of the sequence of multiple states and a transition probability for reaching a subsequent state of the sequence of multiple states.

### Claim 14 (depends on 12)

The method of claim 12, wherein the sequence of multiple states comprises an initial state and a subsequent state, the method further comprising:
in response to determining that a stationary probability of the subsequent state is less than a threshold, the determining the probability of the sequence of multiple states is based on stationary probabilities of the initial state and the subsequent state.

### Claim 15 (depends on 12)

The method of claim 12, wherein the sequence of multiple states comprises an initial state and a subsequent state, the method further comprising:
in response to determining that a stationary probability of the subsequent state is greater than a threshold, the determining the probability of the sequence of multiple states is based on a stationary probability of the initial state and a transition probability for reaching the subsequent state.

### Claim 16 (depends on 12)

The method of claim 12, wherein the sequence of multiple states comprises a windowed portion of a sequence of states to which the historical measurements are assigned.

### Claim 17

A non-transitory computer-readable medium storing computer instructions for accessing data, that when executed by one or more processors, cause the one or more processors to perform the steps of:
obtaining measurements of a key quality indicator for a selected user device in a communication network;
assigning the measurements to a plurality of states, one state per measurement, to provide a plurality of overlapping sequences of states, wherein the plurality of states are defined based on historical measurements of the key quality indicator for a plurality of user devices in the communication network;
determining a probability of each sequence of states;
classify the probabilities in anomaly and no-anomaly clusters; and
for each sequence of states, determining whether the measurements of the key quality indicator for the selected user device represent an anomalous condition based on whether the probability for the sequence of states is classified into the anomaly or no-anomaly cluster.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein:
the probability of the sequence of states is based on stationary probability of an initial state of the sequence of states and a transition probability for reaching a subsequent state of the sequence of states.

### Claim 19 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein:
the probability of the sequence of states is based on stationary probabilities of an initial state of the sequence of states and of a subsequent state of the sequence of states.

### Claim 20 (depends on 1)

The device of claim 1, wherein:
for each window of multiple windows applied to the sequence of states, the probability is consistent with the anomaly when the probability is relatively low and is not consistent with the anomaly when the probability is relatively high.