Clustering technique for cyclic phenomena

• US 20050144148A1
• Filed: 12/31/2003
• Published: 06/30/2005
• Est. Priority Date: 12/31/2003
• Status: Active Grant

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Inventors: Kumpulainen, Pekka, Vehvilainen, Pekko, Hatonen, Kimmo
• Granted Patent: US 7,461,037 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 18/10 Pre-processing; Data cleansing
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/088 Non-supervised learning, e.g. competitive learning
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods

Abstract

A data processing system processes data arrays that collectively describe cyclic behavior of at least one variable in several entities in a physical process. Each cycle comprises several time slots. An input routine (2-4) receives multiple data arrays, each data array containing multiple data items, each of which describes a variable of an entity in one time slot. A magnitude-determination routine (2-6) determines a specific magnitude parameter, such as average, volume or peak, for each of the several entities. A scaling routine (2-8) scales the data arrays between entities such that the specific magnitude parameters are suppressed and only their shape is maintained. A training routine (2-10) trains a clustering system with a first plurality of the scaled data arrays, to determine a set of cluster centers. After training, a clustering routine (2-12) applies a second plurality of the scaled data arrays to the trained clustering system.

Claims

1. A method for processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a physical process;

the method comprising;

determining a first cycle in the cyclic behavior and dividing the first cycle into multiple time slots;

determining multiple data arrays, each data array containing multiple data items such that each data item describes a variable of an entity in one time slot;

for each of the several entities, determining a specific magnitude parameter;

scaling the data arrays between entities such that the specific magnitude parameters are suppressed;

training a clustering system with a first plurality of the scaled data arrays to determine a set of cluster centers; and

using the trained clustering system to cluster a second plurality of the scaled data arrays.

2. A method according to claim 1, wherein the specific magnitude parameters are determined separately for each first cycle.

3. A method according to claim 1, further comprising determining a second cycle that is a multiple of the first cycle and re-clustering the clustered data arrays in respect of the second cycle.

4. A method according to claim 1, further comprising processing the suppressed specific magnitude parameter separately from the clustering system.

5. A method according to claim 1, wherein the clustering system is an unsupervised clustering system.

6. A method according to claim 5, further comprising initializing the unsupervised clustering system with a-priori seed values prior to said training.

7. A method according to claim 1, further comprising:

associating predetermined confidence interval with the cluster centers;

for each clustered data array of the second plurality, determining a best-matching cluster center and checking if the clustered data array is within said predetermined confidence interval of the best-matching cluster center;

if yes, archiving an indicator of the best-matching cluster center and discarding the data array in question;

or

if not, archiving data items of the data array for those time slots in which the clustered data array is not said within said predetermined confidence interval.

8. A method according to claim 7, wherein the confidence interval narrows progressively with increasing magnitude parameter of the variable described.

9. A method according to claim 1, further comprising using the clustered second plurality of the scaled data arrays to detect anomalous situations.

10. A method according to claim 1, further comprising using the clustered second plurality of the scaled data arrays to determine a pricing strategy.

11. A method according to claim 1, wherein the scaled data arrays represent usage of services by various subscribers, and the method further comprises using the clustered second plurality of the scaled data arrays to select candidate subscribers for service advertising.

12. A method according to claim 1, wherein said several entities are network resources and the method further comprises:

using the scaled data arrays to determine a set of optimized operating parameters for a network resource; and

copying the optimized operating parameters to another network resource.

13. A data processing system for processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a physical process, wherein the cyclic behavior exhibits at least a repeating first cycle and each first cycle comprises multiple time slots;

the data processing system comprising;

an input routine for receiving multiple data arrays, each data array containing multiple data items such that each data item describes a variable of an entity in one time slot;

a magnitude-determination routine for determining a specific magnitude parameter for each of the several entities;

a scaling routine for scaling the data arrays between entities such that the specific magnitude parameters are suppressed;

a training routine for training a clustering system with a first plurality of the scaled data arrays, to determine a set of cluster centers; and

a clustering routine for clustering a second plurality of the scaled data arrays with the trained clustering system.

14. A data processing system according to claim 13, wherein the magnitude-determination routine is operable to determine the specific magnitude parameters separately for each first cycle.

15. A data processing system according to claim 13, further comprising a routine for processing the suppressed specific magnitude parameter separately from the clustering system.

16. A data processing system according to claim 13, further comprising an archival routine operable:

to associate a predetermined confidence interval with the cluster centers;

for each clustered data array of the second plurality, to determine a best-matching cluster center and to check if the clustered data array is within said predetermined confidence interval of the best-matching cluster center;

if yes, to archive an indicator of the best-matching cluster center and to discard the data array in question;

or

if not, to archive data items of the data array for those time slots in which the clustered data array is not said within said predetermined confidence interval.