Clustering mechanism for identifying and grouping of classes in manufacturing process behavior

• US 5,764,824 A
• Filed: 08/25/1995
• Issued: 06/09/1998
• Est. Priority Date: 08/25/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levanoni, Menachem, Kurtzberg, Jerome M.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/519,229
• Time in Patent Office: 1,019 Days
• Field of Search: 395/20, 395/11, 395/27, 382/159, 382/130, 382/37, 382/281, 382/9, 382/10, 634/419.19, 364/807, 364/468.26, 327/355, 324/306, 342/94
• US Class Current: 706/50
• CPC Class Codes: 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

Abstract

A clustering technique groups manufacturing data in clusters of similar parametric behavior. Each cluster groups data points which satisfy a given criterion of process behavior similarity. These data may be widely separated in time and thus need not form time ordered clusters. The technique operates in multi-dimensional parameter space and can represent process data that is characterized with multiple performance measures. The technique produces a partition of the data into the minimum number of clusters which satisfy the criterion that all data in the grouping are within a given threshold distance from a cluster nucleus. In addition, the clustering mechanism according the invention is computationally rapid.

Claims

1. A computer implemented method for clustering data which represents process behavior to enable identification and grouping of classes of similar process behavior in a manufacturing process comprising the steps of:

(a) monitoring a manufacturing process with one or more sensors and selecting therefrom n data points Zi, I=1, . . . ,n representative of process behavior;

(b) forming an n×

m relationship matrix C, where C(i,j)=1 if Zi and Zj are within a distance r of one another and 0 otherwise, where r is a measure of closeness of data points;

(c) selecting all unmarked rows of the relationship matrix which contain unmarked columns with single 1s in them, these columns being termed "singleton" columns, and marking all singleton columns and all selected rows;

(d) selecting for further nuclei of clusters an unmarked row with a maximum number of unmarked columns and marking the selected row and marking all columns which contain is in the selected row;

(e) if any columns remain unmarked, repeating steps (c) and (d);

(f) when all columns are marked, deleting all columns corresponding to selected rows in the relationship matrix which are nuclei of clusters;

(g) for a selected row, appending to the nucleus, as cluster members, all data points corresponding to 1s in the existing columns of the selected row and deleting the columns associated with the selected cluster members for that row; and

(h) repeating step (g) until all selected rows representing cluster nuclei are treated so that all columns in the relationship matrix are deleted.

3. The computer implemented method in claim 1 further comprising the step of:

(i) displaying a representation of clustered said data points.

2. A computer apparatus for monitoring a manufacturing process and clustering data which represents process behavior to enable identification and grouping of classes of similar process behavior in the manufacturing process comprising:

input means for receiving data from one or more manufacturing process sensors, said data corresponding to n data points Zi, I=1, . . . ,n, which are to be clustered;

a central processing unit connected to said input means for receiving said data;

said central processing unit forming an n×

m relationship matrix C, where C(i,j)=1 if Zi and Zj are within a distance r of one another and 0 otherwise, where r is a measure of closeness of data points, said central processing unit selecting all unmarked rows of the relationship matrix which contain unmarked columns with single 1s in them, these columns being termed "singleton" columns, and marking all singleton columns and all selected rows, said central processing unit selecting for further nuclei of clusters an unmarked row with a maximum number of unmarked columns and marking the selected row and marking all columns which contain is in the selected row, and when all columns are marked, said central processing unit deleting all columns corresponding to selected rows in the relationship matrix which are nuclei of clusters;

said central processing unit further, for a selected row, appending to the nucleus, as cluster members, all data points corresponding to 1s in the existing columns of the selected row and deleting the columns associated with the selected cluster members for that row until all selected rows representing cluster nuclei are treated so that all columns in the relationship matrix are deleted; and

display means connected co said central processing unit for displaying data points representing the data received from the manufacturing process;

said display means being further responsive to said central processing unit for displaying grouped data points as clusters.