# US 6,731,990 B1 · Predicting values of a series of data

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

- Number: US 6,731,990 B1
- Document ID: US6731990B1
- Status: Granted
- Kind: B1
- Application number: 09/493,167
- Filed: 2000-01-27
- Granted: 2004-05-04
- Earliest claimed: 2000-01-27
- Assignees: Nortel Networks Limited
- Inventors: Malcolm Edward Carter; Otakar Fojt; Michael Maurice Dodson; Jason Levesley; Christopher Hobbs
- Web page: https://patentgrep.com/patent/US6731990B1

## CPC

- G05B 13/026: {using a predictor}
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)

## Abstract

Communications data such as traffic levels in a communications network is analysed using techniques adapted from the study of chaos. Future values of a series of communications data are predicted and an attractor structure is determined from the communications data. This enables the communications processes to be monitored, controlled and analysed. Action can be taken to modify the communications process using the results from the prediction and attractor structure to reduce costs and improve performance and efficiency. These methods may also be used for product data from manufacturing processes. An algorithm bank is compiled containing prediction algorithms suitable for different types of data series, including those exhibiting deterministic behaviour and those exhibiting stochastic behaviour. Recent past values of a data series are taken and assessed or audited in order to determine which of the algorithms in the bank would provide the optimal prediction. The selected algorithm is then used to predict future values of the data series. The assessment or auditing process is carried out in real time and a prediction algorithm selected using a “smart switch” such that different algorithms are used for different stages in a given series as required. This enables good prediction of data series which change in nature over time to be obtained.

## Claims

### Claim 1

A method of predicting a future value of a series of communications data comprising at least some data measured at irregular time intervals comprising the steps of:
(i) forming a set of vectors wherein each vector comprises a number of successive values of the series of data;
(ii) identifying from said set of vectors, a current vector which comprises a most recent value of the series of data;
(iii) identifying at least one nearest neighbour vector from said set of vectors, wherein for each nearest neighbour vector a measure of similarity between that nearest neighbour vector and the current vector is less than a threshold value;
(iv) for each nearest neighbour vector, determining a corresponding vector, each corresponding vector comprising values of the series of data that are a specified number of data values ahead of the data values of the nearest neighbour vector in said series of data; and
(v) calculating the predicted future value on the basis of at least some of the corresponding vector(s).

### Claim 2 (depends on 1)

A method as claimed in claim 1 wherein said step (i) of forming a set of vectors further comprises determining an interval value, said interval value being an integer.

### Claim 3 (depends on 2)

A method as claimed in claim 2 wherein said interval value is determined on the basis of a local minimum in a graph of autocorrelation function.

### Claim 4 (depends on 2)

A method as claimed in claim 2 wherein said interval value is determined on the basis of a local minimum in a graph of average mutual information.

### Claim 5 (depends on 2)

A method as claimed in claim 2 wherein said interval value is determined on the basis of a phase portrait.

### Claim 6 (depends on 2)

A method as claimed in claim 2 wherein each vector in said set of vectors comprises values that occur at a position in the series that is a fixed number of values along in said series from the values of one other vector of the set, and wherein said fixed number of values is said interval value.

### Claim 7 (depends on 1)

A method as claimed in claim 1 wherein said step (i) of forming a set of vectors further comprises determining how many vectors are required for said set of vectors.

### Claim 8 (depends on 7)

A method as claimed in claim 7 wherein said number of required vectors is determined using a method of principal component analysis.

### Claim 9 (depends on 7)

A method as claimed in claim 7 wherein said number of required vectors is determined using a method of saturation of system invariants.

### Claim 10 (depends on 7)

A method as claimed in claim 7 wherein said number of required vectors is determined on the basis of false nearest neighbour vectors.

### Claim 11 (depends on 7)

A method as claimed in claim 7 wherein said number of required vectors is determined on the basis of true vector fields.

### Claim 12 (depends on 1)

A method as claimed in claim 1 wherein two or more corresponding vectors are determined and said step (v) of calculating the predicted future value comprises calculating an average of said corresponding vectors.

### Claim 13 (depends on 12)

A method as claimed in claim 12 wherein said average is a weighted average.

### Claim 14 (depends on 1)

A method as claimed in claim 1 wherein said step (v) of calculating the predicted future value further comprises the steps of:
a) for each nearest neighbour vector, determining a second corresponding vector, each second corresponding vector comprising values of the series of data that are said specified number of data values behind the data values of the nearest neighbour vector in said series of data; and
b) determining a set of second corresponding vectors for which a measure of similarity between each second corresponding vector and a particular vector is less than a threshold value; and
c) calculating the predicted future value only on the basis of corresponding vectors for which the nearest neighbour vector has a second corresponding vector that is a member of said set of second corresponding vectors.

### Claim 15 (depends on 1)

A method as claimed in claim 1 wherein said series of data comprise a number of measured values of a single parameter.

### Claim 16 (depends on 1)

A method as claimed in claim 1 wherein said series of data comprise values that were measured over time.

### Claim 17 (depends on 1)

A method as claimed in claim 1 wherein said measure of similarity comprises a distance.

### Claim 18 (depends on 1)

A method as claimed in claim 1 wherein said predicted future value of the series of values is between 1 and 50 values ahead in the series.

### Claim 19 (depends on 1)

A method as claimed in claim 1 wherein said predicted future value of the series of values is between 1 and 15 values ahead in the series.

### Claim 20 (depends on 1)

A method as claimed in claim 1 wherein said step (v) of calculating the predicted future value further comprises obtaining an actual value corresponding to the predicted value and comparing said actual value with said predicted value.

### Claim 21

A computer program stored on a computer readable medium, said computer program being arranged to control a computer system for predicting one or more future values of a series of data, said computer program being arranged to control said computer system such that:
(i) a plurality of past values of said series of data is accepted;
(ii) an assessment of the level of deterministic behaviour of said series of data is made on the basis of said selected plurality of past values;
(iii) a store of predictive algorithms is accessed and one of said predictive algorithms selected on the basis of said assessment of the level of deterministic behaviour of the series of data; and
(iv) one or more future values of the series of data are obtained by using said selected predictive algorithm.

### Claim 22

A computer system for predicting a future value of a series of communications data comprising at least some data measured at irregular time intervals comprising:
(i) a processor arranged to form a set of vectors wherein each vector comprises a number of successive values of the series of data;
(ii) an identifier arranged to identify from said set of vectors, a current vector which comprises a most recent value of the series of data;
(iii) a second identifier arranged to identify at least one nearest neighbour vector from said set of vectors, wherein for each nearest neighbour vector a measure of similarity between that nearest neighbour vector and the current vector is less than a threshold value;
(iv) a determiner arranged to determine, for each nearest neighbour vector, a corresponding vector, each corresponding vector comprising values of the series of data that are a specified number of data values ahead of the data values of the nearest neighbour vector in said series of data; and
(v) a calculator arranged to calculate the predicted future value on the basis of at least some of the corresponding vector(s).

### Claim 23

An apparatus for controlling a communications process comprising:
(i) one or more inputs arranged to receive a series of communications data measured at irregular time intervals and associated with the communications process; and
(ii) a computer system for predicting at least one future value of said series of data said computer system comprising:
a processor arranged to form a set of vectors wherein each vector comprises a number of successive values of the series of data;
an identifier arranged to identify from said set of vectors, a current vector which comprises a most recent value of the series of data;
a second identifier arranged to identify at least one nearest neighbour vector from said set of vectors, wherein for each nearest neighbour vector a measure of similarity between that nearest neighbour vector and the current vector is less than a threshold value.

### Claim 24

A computer system for predicting one or more future values of a series of data, said computer system comprising:
(i) an input arranged to accept a plurality of past values of said series of data;
(ii) a processor arranged to assess the level of deterministic behaviour of said series of data on the basis of said selected plurality of past values;
(iii) an input arranged to access a store of predictive algorithms and wherein said processor is further arranged to select one of said predictive algorithms on the basis of said assessment of the level of deterministic behaviour of the series of data; and
(iv) an output arranged to provided one or more future values of the series of data obtained by using said selected predictive algorithm.

### Claim 25 (depends on 24)

A communications network comprising a computer system as claimed in claim 24.

### Claim 26

A method of assessing a level of deterministic behaviour of a series of communications data comprising at least some data measured at irregular time intervals comprising the steps of:
(i) using a predictive algorithm to predict a value of said data series which corresponds to a past value of said data series, said prediction being made on the basis of a subset of said past values;
(ii) repeating said step (i) immediately above a plurality of times using the same predictive algorithm and wherein said subset of said past values is larger for successive repetitions of said step (i); and
(iii) assessing the effect of the size of said subset of past values on the performance of said predictive algorithm.

### Claim 27

A computer system for assessing a level of deterministic behaviour of a series of communications data comprising at least some data measured at irregular time intervals said computer system comprising:
(i) a processor arranged to use a predictive algorithm to predict a value of said data series which corresponds to a past value of said data series, said prediction being made on the basis of a subset of said past values; and
(ii) wherein said processor is further arranged to repeat said step (i) immediately above a plurality of times using the same predictive algorithm and where said subset of said past values is larger for successive repetitions of said step (i); and
(iii) wherein said processor is further arranged to assess the effect of the size of said subset of past values on the performance of said predictive algorithm.

### Claim 28

A method of predicting one or more future values of a series of data, said method comprising the steps of:
(i) selecting a plurality of past values of said series of data;
(ii) assessing the level of deterministic behaviour of said series of data on the basis of said selected plurality of past values;
(iii) selecting a predictive algorithm from a store of predictive algorithms on the basis of said assessment of the level of deterministic behaviour of the series of data; and
(iv) using said selected predictive algorithm to predict said one or more future values of the series of data.

### Claim 29 (depends on 28)

A method as claimed in claim 28 wherein said step (ii) of assessing the level of deterministic behaviour of the series of data comprises substantially determining an attractor structure from said past values.

### Claim 30 (depends on 29)

A method as claimed in claim 29 wherein said step (ii) of assessing the level of deterministic behaviour of the series of data further comprises inputting details about said determined attractor structure to a neural network.

### Claim 31 (depends on 28)

A method as claimed in claim 28 wherein said step (ii) of assessing the level of deterministic behaviour of the series of data further comprises, applying one of the predictive algorithms from said store to a plurality of the past values to determine predicted values which correspond to others of the past values, and determining a measure of the accuracy of said predicted values.

### Claim 32 (depends on 31)

A method as claimed in claim 31 wherein said measure of the accuracy of said predicted values comprises a co-efficient of determination.

### Claim 33 (depends on 28)

A method as claimed in claim 28 wherein said step of assessing the level of deterministic behaviour comprises:
(i) Using a predictive algorithm from said store to predict a value of said data series which corresponds to a past value of said data series, said prediction being made on the basis of a subset of said past values; and
(ii) Repeating said step (i) immediately above a plurality of times using the same predictive algorithm and wherein said subset of said past values is larger for successive repetitions of said step (i).

### Claim 34 (depends on 33)

A method as claimed in claim 33 which further comprises the step of calculating the differences between said predicted values and said corresponding past values and plotting a graph of said differences against an indication of the size of said subset of past values.

### Claim 35 (depends on 34)

A method as claimed in claim 34 which further comprises the step of determining the location of a first local minimum of said graph.

### Claim 36 (depends on 33)

A method as claimed in claim 33 wherein said prediction algorithm is suitable for data series which exhibit deterministic behaviour.

### Claim 37 (depends on 33)

A method as claimed in claim 33 wherein said prediction algorithm comprises the steps of:
(i) forming a set of vectors wherein each vector comprises a plurality of successive past values of the series of data;
(ii) identifying from said set of vectors, a current vector which comprises a most recent value of the series of data within said vectors;
(iii) identifying at least one nearest neighbour vector from said set of vectors, wherein for each nearest neighbour vector a measure of similarity between that nearest neighbour vector and the current vector is less than a threshold value;
(iv) for each nearest neighbour vector, determining a corresponding vector, each corresponding vector comprising values of the series of data that are a specified number of data values ahead of the data values of the nearest neighbour vector in said series of data; and
(v) calculating a predicted value on the basis of at least some of the corresponding vector(s).

### Claim 38 (depends on 28)

A method as claimed in claim 28 wherein said store of predictive algorithms comprises at least one auto regressive integrated moving average (ARIMA) algorithm.

### Claim 39 (depends on 28)

A method as claimed in claim 28 wherein said step (ii) of assessing the level of deterministic behaviour of said series of data on the basis of said selected plurality of past values is carried out in real time.

### Claim 40 (depends on 28)

A method as claimed in claim 28 wherein said step (iii) of selecting a predictive algorithm from a store of predictive algorithms on the basis of said assessment of the level of deterministic behaviour of the series of data is carried out in real time.

### Claim 41 (depends on 28)

A method as claimed in claim 28 which further comprises the step of repeating said steps (i) of selecting past values and said step (ii) of assessing the level of deterministic behaviour, and, if the results of said assessment differ substantially from the results of the previous assessment, then repeating said steps (iii) and (iv).

### Claim 42 (depends on 28)

A method as claimed in claim 28 wherein said series of data comprises values observed at irregular time intervals.

### Claim 43 (depends on 28)

A method of controlling a product manufacturing process comprising
(i) obtaining a series of product data values from products produced in said manufacturing process;
(ii) predicting one or more future values of said series of product data values using the method claimed in claim 28;
(iii) adjusting said product manufacturing process on the basis of said one or more predicted future values.

### Claim 44 (depends on 28)

A method of managing a communications network comprising the steps of:
(i) obtaining a series of communications data values from said communications network;
(ii) predicting one or more future values of said series of communications data values using the method claimed in claim 28; and
(iii) managing said communications network on the basis of said one or more predicted future values.
