Clustering technique for cyclic phenomena

• US 7,461,037 B2
• Filed: 12/31/2003
• Issued: 12/02/2008
• 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: Vehvilainen, Pekko, Hatonen, Kimmo, Kumpulainen, Pekka
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US10/748,673
• Publication Number:
  US 20050144148A1
• Time in Patent Office: 1,798 Days
• Field of Search: 706/12, 706 16- 20
• US Class Current: 706/18
• 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 computer-implemented method for producing a trained clustering system, the method comprising:

processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a telecommunication network;

wherein said processing of the data arrays comprises

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; and

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

wherein the method further comprises training a clustering system with a first plurality of the scaled data arrays to determine a set of cluster centers, thereby producing the trained clustering system operable to cluster a second plurality of the scaled data arrays, whereby the second plurality of the scaled data arrays clustered by the trained clustering system may differ in magnitude from the first plurality of the scaled data arrays used for training the clustering system.

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

3. The 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. The method according to claim 1, further comprising processing the suppressed specific magnitude parameter separately from the clustering system.

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

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

7. The 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 the clustered data array is within said predetermined confidence interval of the best-matching cluster center, archiving an indicator of the best-matching cluster center and discarding the data array in question;

or

if the clustered data array is within said predetermined confidence interval of the best-matching cluster center, 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. The method according to claim 7, wherein the confidence interval narrows progressively with increasing magnitude parameter of the variable described.

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

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

11. The 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. The 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.

19. The method of claim 1, wherein at least some of the entities in the telecommunication network are resources of the telecommunication network.

20. The method of claim 19, further comprising using the scaled data arrays to determine a set of optimized operating parameters for a first resource of a telecommunication network and copying the optimized operating parameters to one or more second resources, wherein the first and second resources have different magnitude parameters.

21. The method of claim 1, wherein the at least one variable includes a performance indicator which indicates a performance of the telecommunication network.

22. The method of claim 1, further comprising detecting an anomalous situation in the telecommunication network by the trained clustering system.

23. The method of claim 1, further comprising determining a pricing strategy in the telecommunication network by the trained clustering system.

24. The method of claim 1, further comprising selecting candidate subscribers for service advertising in the telecommunication network by the trained clustering system.

25. The method of claim 1, further comprising storing the second plurality of the scaled data arrays into a computer storage.

13. A computer program product embodied on a computer readable medium, the computer program product comprising program code for controlling a processor to execute a method, the method comprising:

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;

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

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

clustering a second plurality of the scaled data arrays with the trained clustering systems,

wherein the method further comprises processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a telecommunication network to obtain the second plurality of the scaled data arrays, and using the second plurality of the scaled data arrays to determine at least one condition, wherein the cyclic behavior exhibits at least a repeating first cycle and each first cycle comprises multiple time slots.

14. The computer program product according to claim 13, wherein a magnitude-determination routine is operable to determine the specific magnitude parameters separately for each first cycle.

15. The computer program product according to claim 13, further comprising processing the suppressed specific magnitude parameter separately from the clustering system.

16. The computer program product 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 the clustered data array is within said predetermined confidence interval of the best-matching cluster center, to archive an indicator of the best-matching cluster center and to discard the data array in question;

or

if the clustered data array is within said predetermined confidence interval of the best-matching cluster center, 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.

17. An apparatus comprising:

a determining unit configured to determine a first cycle in the cyclic behavior and dividing the first cycle into multiple time slots;

a unit configured to determine 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, a unit configured to determine a specific magnitude parameter;

a scaling unit configured to scale the data arrays between entities such that the specific magnitude parameters are suppressed;

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

a unit configured to use the trained clustering system to cluster a second plurality of the scaled data arrays,

wherein the apparatus is used for processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a telecommunication network to obtain the second plurality of the scaled data arrays, and using the second plurality of the scaled data arrays to determine at least one condition.

18. An apparatus comprising:

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

determining means for 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 means for determining a specific magnitude parameter;

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

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

means for using the trained clustering system to cluster a second plurality of the scaled data arrays,

wherein the apparatus is used for processing data arrays that collectively describe cyclic behavior of at least one variable in several entities in a telecommunication network to obtain the second plurality of the scaled data arrays, and using the second plurality of the scaled data arrays to determine at least one condition.