US 5,809,490 AGrant

Apparatus and Method for Selecting a Working Data Set for Model Development

Issue Date:1998-09-15

•33 Claims

•7 Drawing Sheets

Abstract

The present invention provides a data selection apparatus which augments a set of training examples with the desired output data. The resulting augmented data set is normalized such that the augmented data values range between -1 and +1 and such that the mean of the augmented data set is zero. The data selection apparatus then groups the augmented and normalized data set into related clusters using a clusterizer. Preferably, the clusterizer is a neural network such as a Kohonen self-organizing map (SOM). The data selection apparatus further applies an extractor to cull a working set of data from the clusterized data set. The present invention thus picks, or filters, a set of data which is more nearly uniformly distributed across the portion of the input space of interest to minimize the maximum absolute error over the entire input space. The output of the data selection apparatus is provided to train the analyzer with important sub-sets of the training data rather than with all available training data. A smaller training data set significantly reduces the complexity of the model building or analyzer construction process.

Metadata

Assignee

Aspen Technology Inc.

Inventors

John P. Guiver
Casimir C. Klimasauskas

Application Information

Application Number:US 6427790

Filing Date:1996-05-03

Priority Date:1996-05-03

Art Unit:274

Classifications

IPC:

G06F 1518

Field of Search:

39511;24;22;23

Patent Drawings (7 sheets)

Description

Field of the Invention

The invention relates to an apparatus and a method for selecting data, and more specifically, to an apparatus and a method for selecting working data from a full data set for model development.

Background of the Invention

In a number of system modeling applications where first principles, analytical, or expert knowledge about the actual structure of the system to be modeled is lacking or inadequate, data driven analyzers may be applied in place of conventional analyzers. These data driven analyzers may incorporate a number of models such as parametric statistical models, non-parametric statistical models, clustering models, nearest neighbor models, regression methods, and engineered (artificial) neural networks. Typical applications include handwriting recognition, speech recognition, image recognition, financial modeling, financial forecasting, target marketing and process control in various manufacturing facilities such as power plants, chemical plants and refineries, among others.

Prior to operation, data driven analyzers or models need to be built using one or more training sessions. The data used to build the analyzer or model in these sessions are typically referred to as training data. As data driven analyzers are developed by examining only training examples, the selection of the training data can significantly affect the accuracy and the learning speed of the data driven analyzer. One approach used heretofore generates a separate data set referred to as a test set for training purposes. The test set is used to avoid overfitting the model or analyzer to the training data. Overfitting refers to the situation where the analyzer has memorized the training data so well that it fails to fit or categorize unseen data. Overfitting is a common problem in data driven analyzers or models.

Typically, during the construction of the analyzer or model, the analyzer's performance is tested against the test set. The selection of the analyzer or model parameters is performed iteratively until the performance of the analyzer in classifying the test set reaches an optimal point. At this point, the training process is completed. An alternative to using an independent training and test set is to use a methodology called cross-validation. Cross-validation can be used to determine parameter values for a parametric analyzer or model for a non-parametric analyzer. In cross-validation, a single training data set is selected. Next, a number of different analyzers or models are built by presenting different parts of the training data as test sets to the analyzers in an iterative process. The parameter or model structure is then determined on the basis of the combined performance of all models or analyzers. Under the cross-validation approach, the analyzer or model is typically retrained with data using the determined optimal model structure.

The quality of the above-mentioned analyzers or models is critically dependent on the selection of training data or test sets. In many cases, a large amount of data is collected and is available for building the model or constructing the analyzer. Ideally, the training data should cover the entire region where new data may be fitted into. However, for practical reasons, limitations may exist on the quality of data available for training the analyzer.

These limitations may exist where the data may be inherently rare, or may be expensive to collect, or may simply have been drowned out by populated data clusters which do not significantly affect the decisions of the analyzer. For example, in many industrial processes, steady state conditions can exist for a very long duration. In contrast, disturbance conditions occurs on a much more infrequent basis. As data collected during the steady state conditions are not as interesting as data collected during the disturbance condition, it is important that these rare but critical events be included in the training set. Further, it is important that the data associated with the steady state condition mentioned above be pruned out so that the rarer, more important data during the disturbance condition can be focused on during training to improve the accuracy and the training speed.

Summary of the Invention

By augmenting and subsequently clustering the input vector with the target outputs for the model to be developed, the data selection apparatus of the present invention picks a set of data which is more nearly uniformly distributed across the portion of the input space of interest. The present invention effectively filters out data in portions of the data space with a heavy distribution of data or examples in favor of those with fewer data or examples. Thus, these models effectively minimize the maximum absolute error over the entire space. For modeling techniques which minimize sum squared error or more generally r-Minkowski error measures, the data selection apparatus of the present invention results in models which perform better over the entire space.

The analyzer is subsequently trained with important sub-sets of the training data rather than with all available training data. A smaller data set significantly reduces the model building or analyzer construction process. This in turn increases the scope of the training to allow for further optimization of model types and structures for the analyzer.

Brief Description of the Drawings

A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:

FIG. 1 is a block diagram of a computer system functioning as the data selector according to the present invention;

FIG. 2 is a flow chart illustrating the process of selecting data using the data selector of FIG. 1;

FIG. 3 is a flow chart illustrating the process of building the data set in FIG. 2;

FIG. 4 is a flow chart illustrating an alternative process in the data set building step in FIG. 2;

FIG. 5 is a block diagram illustrating the clusterizer of FIG. 2;

FIG. 6 is a flow chart illustrating the process of training the clusterizer of FIG. 5; and

FIG. 7 is a chart comparing results achieved using the data selector of FIGS. 1 and 2 with results using the prior art technique.

Description of the Preferred Embodiment

Turning now to the drawings, FIG. 1 is a representative computer system S which provides the processing capability for the data selection apparatus of the present invention. Although the computer system S is shown as a high performance IBM compatible personal computer, any other suitable processing environments may be used, including workstations, minicomputers, mainframes, or supercomputers.

In FIG. 1, the system S has a CPU or a processor 100 connected to a level two (L2) cache 104. The L2 cache 104 provides additional caching capabilities to the processor's on-chip cache to improve performance. Both the processor 100 and the L2 cache 104 are connected to a high speed local bus 105. The processor 100 of the preferred embodiment is a Pentium microprocessor manufactured by Intel Corporation of Santa Clara, Calif. In the preferred embodiment, the processor operates with a standard IBM-PC compatible operating system, such as MS-DOS or Windows, available from Microsoft Corporation of Redmond, Wash.

In addition to the CPU 100 and cache 104, a number of memory interface and memory devices are connected between the local bus 105 and a PCI bus 106. These devices include a memory to PCI cache controller (MPC) 101 and a dynamic random access memory (DRAM) array 102. The MPC 101 is connected to the DRAM array 102 to collectively form a high performance memory system for the computer system S. A display 108 is also connected to the PCI bus 106.

A plurality of PCI slots 124 and 126 are provided to accept PCI expansion cards and to interface these cards into the PCI bus 106. The expansion card may support a number of data collection instruments. The data collected varies according to the type of product being produced. For illustrative purposes, FIG. 1 shows the architecture of the computer supporting various process control data collection devices such as various sensors and output drivers in a representative plant.

In the embodiment disclosed here, the representative plant is a refinery or a chemical processing plant having a number of process variables such as temperature and flow rate variables. These variables are sensed by various instruments. As shown in FIG. 1, in the event that the computer system is operating in a chemical plant, the collected data may include various disturbance variables such as a feed stream flow rate as measured by a flow meter 32, a feed stream temperature as measured by a temperature sensor 38, component feed concentrations as determined by an analyzer 30, and a reflux stream temperature in a pipe as measured by a temperature sensor 71. The collected data can also include controlled process variables such as the concentration of produced materials, as measured by analyzers 48 and 66. The collected data further may include manipulated variables such as the reflux flow rate as set by a valve 80 and determined by a flow meter 78, a reboil steam flow rate as set by a valve 60 and measured by a flow meter 58 and the pressure in a tank as controlled by a valve 86.

It is to be understood that the description of data to be collected such as the reflux flow rate and the reboil steam flow rate are associated with the operations of the chemical plant and has only been provided as examples of the types of variables to be collected. The techniques and processes according to the present invention can be utilized in a wide range of technological arts, such as speech recognition, image recognition, financial modeling, target marketing, and various process control applications in oil refineries, chemical plants, power plants and industrial manufacturing plants, among others. Thus, the present invention is not to be construed as limited to the description of specific embodiments. As noted above, the present invention is adapted to be practiced within the full range of technological arts.

The PCI bus 106 is also connected to a system controller 112. The system controller 112 is a PCI to ISA bus bridge. Preferably the system controller 112 provides a PCI bus master and slave controller, an ISA bus controller, DMA devices, and an IDE disk interface. The system controller 112 is also connected to an IDE interface port 114 for driving one or more hard disk drives, preferably a CD-ROM player 117 and a disk drive 119.

The system controller 112 is connected to an Input/Output (I/O) chip 120. The I/O chip 120 is connected to a flash ROM 122 which contains boot-up information for the computer system S. Additionally, the I/O device 120 provides a parallel port, a serial port, a keyboard interface and a mouse interface, among others, for the computer system S.

Turning now to FIG. 2, the operation of the data selection apparatus of the present invention is shown. The data selection apparatus of FIG. 2 selects a working set of data from a full set of data for developing models. The product generated by the data selection apparatus of the present invention may be used by a suitable data driven analyzer such as that discussed in a co-pending patent application having application Ser. No. 08/642,725, entitled "HYBRID LINEAR-NEURAL NETWORK PROCESS CONTROL" and commonly assigned to the assignee of the present invention, hereby incorporated by reference. It is to be noted that when the computer of FIG. 1 is operating under the control of the routine shown in FIG. 2, the computer of FIG. 1 is a new and improved data selection apparatus which improves the training of data driven analyzers.

In FIG. 2, the data selection apparatus acquires input data in step 220. The input data is further selected such that the data used in the modeling process may only be a sub-set of the potential data available. Next, the data selection apparatus of the invention augments the input data with the target output in step 222. In step 222, the output variables are preferably appended to the input variables to form the data space prior to the normalization step 224. The output variables represent outcomes of the model and as such it is important that the training set include data that is representative of the output space. The importance of certain output variables can be increased by adding more weight to their contribution to the distance function used in the clusterizer of step 226, as discussed below. In the asymptotic case, only output variables are used during the clustering step 226. Further, the present invention contemplates that the data may be selected such that only a portion of the potential data available as well as a portion of the outputs will be used.

In step 224, the routine normalizes the augmented data. Preferably, the variables are normalized so that they are mean zero, and have values between -1 and +1. The normalization is accomplished by subtracting the mean and dividing by a number which is preferably selected from a range of two to three times the standard deviation of the variables.

The data selection apparatus then separates the augmented, normalized data into related groups using a clusterizer in step 226. Optionally, the individual input or output variables can be transformed using non-linear functions known to those skilled in the art to have a distribution that is closer to being uniform or normal or to some other desired distribution. The optional univariate non-linear transformations can enhance the effectiveness of the clusterizer by spreading out the data to span the boundaries of the data space.

In step 226, the number of clusters is typically determined as a fraction of the total data. Alternatively, the number of clusters may be determined experimentally by iteration. In the preferred embodiment, a self organizing map (SOM) clusterizer is initially driven to perform an equi-probable clustering. The equi-probable clustering is relaxed as the iterative nature of the clustering algorithm proceeds so that the resulting clusters are distributed at representative points around the augmented data space. Although equi-probable clusterizers are used, the clusterizer may also use a weighted clustering methods which are not based on the equi-probable clustering approach.

Additionally, in another embodiment, after the clustering process has been performed, each example or data in the training set is matched to a cluster based only on the input portion of the data. An analyzer or model is built for each individual data cluster. Afterward, the composite model assigns the new data input to a cluster before it uses the model associated with the cluster to create an output.

The data selection apparatus then builds one or more working data sets from the clusters formed in step 226 using a data extractor in step 228. In the data extractor of the preferred embodiment, a cut-off level K is selected as some fraction of the average number of examples per cluster such as 70%. In a round robin fashion, data is picked at random from each cluster until there is no more data associated with the cluster, or the desired number of examples have been selected from the cluster. Alternatively, K data examples can be picked from each cluster at random starting with the first cluster and proceeding to the next. If the cluster has fewer than K values, all of the data examples are selected. After performing step 228, the routine simply exits.

The analyzer is subsequently trained with the thus selected sub-sets of the training data rather than with all available training data. A smaller data set significantly reduces the model building or analyzer construction process. This in turn increases the scope of the training to allow for further optimization of model types and structures for the analyzer.

For modeling techniques which minimize sum squared error (or more generally r-Minkowski error) measures, the data selection apparatus of the present invention results in models which perform better over the entire space as these models effectively minimizes the maximum absolute error over the entire space. The data selection apparatus of the present invention thus works well with any modeling technique based on data which optimizes a single composite measure over all of the data used to estimate the model, but the final solution must predict equally well over all the known examples. The model to be developed using this working set may be of any data-derived form of model: linear, neural, polynomial, rational polynomial.

Turning to FIG. 3, one embodiment of the data extractor for selectively moving data from its respective cluster in step 228 is shown in more detail. In FIG. 3, the routine selects a first cluster to work on in step 250. It also computes a cutoff level K in step 252. As previously indicated, the cut-off level K is selected as some fraction of the average number of examples per cluster such as 70%. Additionally, the present invention also contemplates that an iterative approach can be used to determine K. Using this approach, the clusterized data is used to create one analyzer or model while a sub-set of the data, preferably a subset with a new cut-off level K, is picked and used to create a second analyzer or model. This process can be performed in many iterations. The cut-off level K which results in the best performing analyzer or model is used to create the final analyzer or model.

In step 254, the routine selects data from the cluster in a randomized manner. In step 256, the routine moves a selected group of data into the working data set. Next, in step 258, the routine tests to see if the quantity of data moved into the model data set has reached the cut-off level K in step 258. If not, the routine then checks to see if there is any data remaining in the cluster to be moved in step 260. If additional data needs to be moved in step 260, the routine loops back to step 254 to continue clustering the data. Alternatively, from step 258, if the data move has reached the cutoff level K, or alternatively, from step 260, no data exists to be moved in the cluster, the routine moves to step 262. In step 262, the routine checks to see if additional clusters need to be worked on. If so, the routine selects the next cluster to work on in step 264 before it loops back to step 254 to continue clustering the data. Alternatively, if no clusters remain to be worked on in step 262, the routine exits.

FIG. 4 is an alternative embodiment of the extractor for selectively moving data from its respective cluster in step 228. In FIG. 4, the routine identifies the cutoff level K in step 280. In contrast to the embodiment of FIG. 3 which selects the cut-off level K as some fraction of the average number of examples per cluster, step 280 uses a predetermined constant value for K.

Next, the routine selects the first cluster to work on in step 282. In step 284, the routine checks to see of the cluster has more than K elements of data in it. If so, the routine selects the starting index into the cluster on a random basis in step 286. Then, in step 288, the routine copies a number of K data elements, starting from the index point of the cluster, to the working data set.

Alternatively, from step 284, if the cluster does not have more than K data points, the routine simply selects all data elements from the current cluster in step 290. It then moves all data elements from the cluster to the working data set in step 292.

From either step 288 or step 292, the routine determines whether or not additional clusters need to be worked on in step 294. If so, the routine selects the next cluster to work on in step 296 and jumps to step 284 to continue the model building process. Alternatively, if all clusters have been worked on, the routine exits.

Turning now to the clusterizer of step 226, the clusterizer is preferably a neural network known by those skilled in the art as a Kohonen self organizing map (SOM), shown in more detail in FIG. 5. The Kohonen SOM is an unsupervised learning network which transforms a P dimensional input pattern to a Q dimensional discrete map in a topologically ordered fashion. Typically, Q is a one or two dimensional discrete map. In the Kohonen SOM, input points that are close in the P dimension are mapped close together on the Q dimension lattice. Each lattice cell is represented by a neuron associated with a P dimensional adaptable weight vector. The match between each weight factor is computed with every input. The best matching weight factor and some of its topological neighbors are then adjusted to better match the input points. The Kohonen SOM offers the desirable property of topology preservation where nearby input patterns activate nearby output units on the map. Such networks have been used for generating semantic maps, graph partitioning and clustering where high dimensional, complex information is compressed into an ordered fashion by reducing the dimensionality of the information without loss of knowledge about interrelationship of data.

Referring now to FIG. 5, the Kohonen SOM is organized as a two-dimensional grid or array of neurons having an input layer 139 and an output layer 149. The input layer 139 has a plurality of input neurons 140, 142 and 144. Similarly, the output layer 149 has a plurality of individual output neurons 150 through 179. Each of the neurons 140 through 144 of the input layer 139 is fully connected to each of the neurons 150 through 179 of the output layer 149.

Additionally, each of the neurons in the output layer 149 is associated with a spatial neighborhood. As shown in FIG. 5, the spatial neighborhood 163 encompasses neurons 154, 162, 164 and 166, among others. The spatial neighborhood 163 allows a winning neuron, preferably a Euclidean-based winning neuron as defined below, to prohibit neurons outside of the neighborhood 163 from acting and to excite only the neurons in its immediate neighborhood 163 or those physically closest to the neuron. Thus, only the winner and its neighbors within the neighborhood 163 can learn and adjust their weights. Once the winning neuron is chosen, the weight of the winning neuron must be adjusted and all units within its neighborhood are also adjusted.

The shape of the spatial neighborhood 163 is preferably square, rectangular, or circular. The initial neighborhood size of the SOM is preferably set from 1/2 to 2/3 of the SOM network size. This neighborhood size is shrunk over time according to a schedule, preferably one with an exponentially decreasing function, as discussed below.

Prior to using the Kohonen SOM clusterizer, the SOM needs to be trained. FIG. 6 shows the routine to train the Kohonen SOM of FIG. 5 in more detail. In FIG. 6, the input data x is loaded in step 182. Next, the weights of the SOM network is initialized in step 184. The initial weights of the SOM network may be chosen using a number of strategies. Preferably, the initial weights are selected using a random number generator.

In step 188, the routine determines the winning neuron for the particular input data by selecting the unit at location (i,j) in the two-dimensional output layer 149 (FIG. 5) with the minimum output. Preferably, the input data X, which for the current invention includes the target outputs, has M values and is denoted by:

Further, each Kohonen SOM neuron i will also have M weight values which are denoted by:

The use of i and j denotes the n-dimensional vector associated with the units at location (i,j) of the two dimensional output layer 149 (FIG. 5).

Each neuron computes the Euclidean distance between the input vector X and the store weight vector W. Now the Euclidean distance D.sub.i is computed for each of the N Kohonen neurons. ##EQU1##

The neuron with the lowest value of D.sub.i is selected as the winner. Additionally, in the event that the influence of the output variables is to be increased for the purpose of cluster creation, the output variables can be magnified by giving more weight to their contributions to the distance function shown above. Once the neuron with the smallest adjusted distance has been determined, the routine then determines the remaining neurons whose weights need to be adjusted. The neurons to be adjusted is determined using a neighborhood function, as discussed below.

Next, the conscience mechanism of step 189 minimizes the risk that a few neurons can end up representing too much of the input data. This situation could arise due to the initial randomization of the Kohonen neuron weights. In this case one neuron might end up representing all the data and little information about the clusters in the input data would be found in the Kohonen SOM's output layer. The conscience mechanism depends on keeping a record of how often each Kohonen neuron wins and this information is then used during training to bias the distance measurement.

If a neuron has won more than 1/N fraction of the time (where N is the number of Kohonen neurons) then its distance is adjusted upward to decrease its chance of winning--in fact, the adjustment is proportional to how much more frequency than average the neuron has won. Also if a neuron has won less than 1/N fraction of the time, then its distance is decreased to make it more likely to win.

In step 189, the routine also biases the distance measurements to encourage neurons that are not winning with an average frequency and, of course, to discourage neurons that are winning at an above average frequency. The conscience mechanism helps develop a uniform data representation in the SOM layer.

The adjusted distance D.sub.i ' simply is the distance minus a bias. The bias, denoted by B.sub.i is computed using the following formula:

where F.sub.i is the frequency with which the neuron i has historically won, and N is the number of neurons in the SOM layer.

At initialization, ##EQU2##

Once B.sub.i and D.sub.i have been computed, the adjusted distance, D.sub.i ' can be computed as:

Thus, when ##EQU3## is decreased so that the neuron i's chance of winning is increased. Alternatively, when F.sub.i >1/N, D.sub.i ' is increased so that the respective neuron i's chance of winning is decreased.

The conscience mechanism helps the Kohonen layer achieve another benefit: the neurons naturally represent approximately equal information about the input data. Where the input space has sparse data, the representative Kohonen neurons compact the space. Where the input space has high density, the representative Kohonen neurons spread out to allow finer discrimination.

In step 190, the neighborhood is preferably square, circular or diamond shaped and may alternate between different shapes. Further, the size of the neighborhood may be changed as the learning process proceeds. Preferably, a large neighborhood size is initially specified. This neighborhood size is reduced during the learning process to arrive at a single neuron. In step 190, the routine updates weights of all neurons in the neighborhood of the winning neuron according to the following learning rule: ##EQU4##

In the above equations, N.sub.cicj (t) is the neighborhood of the unit located at (i,j) at time t, and .alpha.(t) is the learning rate at time t.

In step 192, it is necessary to keep track of the winning frequency of each neuron. This frequency is updated after the winning neuron is selected. For purposes of convenience, the following formulas are used to calculate F.sub.i and only approximate the true winning frequency. Thus, for the winning neuron, or the neuron with the lowest adjusted distance:

For the remaining Kohonen neurons:

After weights of the neighboring neurons have been adjusted, the learning coefficient .alpha. is maintained or decreased over each iteration in step 194. For instance, .alpha. may start at a value such as 0.4 and decrease over time to 0.1 or lower. Similarly, the neighborhood N.sub.cicj (t) is either maintained or shrunk in step 196.

Next, the routine determines whether the change in the weight values is less than a predetermined threshold in step 198. If not, the routine further determines whether a predetermined maximum iteration limit has been reached in step 200. If the iteration threshold has not been reached, the routine loops back to step 188 to continue the training process. Alternatively, if the change in weight values is less than the determined threshold in step 198, or if the maximum iteration limit has been reached in step 200, the routine exits.

During training, the Kohonen neuron with the smallest distance adjusts its weight to be closer to the values of the input data. The neighbors of the winning neuron also adjust their weights to be closer to the same input data vector. The adjustment of neighboring neurons is instrumental in preserving the order of the input space in the SOM. Statistical methods are used so that the range of inputs converges to a single output. Because the correct output is unknown, the Kohonen SOM assumes that if all the data converges to a particular point, that point must be significant. In each pass through the network, the node with a minimum distance between the input and its weight vector is considered the winner. Every node in the neighborhood is updated so that their weight vectors move toward the winner's vectors. After a series of passes through the network, all inputs tend to converge to a single output.

In this manner, the Kohonen SOM of the preferred embodiment looks for regularities or trends and makes adaptations according to the function of the network while providing a graphical representation of its findings after the SOM has been trained. Advantageously, the two-dimensional vector maintains the order of the multi-dimensional input data. Thus, information is compressed when the Kohonen SOM forms reduced representations of the most relevant facts without loss of knowledge about the interrelationships.

During the recall phase, the Kohonen SOM of the preferred embodiment acts as a two-dimensional map that can, from a random starting point, find the natural relationships among patterns without any external guidance. The Kohonen layer neurons each measure the Euclidean distance of its weights to the incoming input values. The Kohonen neuron with the minimum distance is called the winner and has an output of 1.0, while the other Kohonen neurons have an output of 0.0. A variation of this competitive output has more than one neurons with small Euclidean distance generating a positive output.

During the recall phase, the same Euclidean distance used during training is used to measure distance. In the recall phase, each neuron computes the Euclidean distance between the input vector X and the store weight vector W. Thus, the Euclidean distance D.sub.i is computed for each of the N Kohonen neurons as follows: ##EQU5##

The neuron with the lowest value of D.sub.i is selected as the winner during the recall phase. In the preferred embodiment, each neuron in the output layer 149 represents one data cluster mapping of the input data.

The winning neuron is, in a measurable way, the closest to the input value and thus represents the input value. The ability of the Kohonen SOM clusterizer of the present invention to perform an order-preserving projection of the input space onto the two-dimensional Kohonen output layer allows the Kohonen SOM clusterizer of the present invention to provide a set of data which is more nearly uniformly distributed across the portion of the input space of interest. Further, by filtering out data in portions of the data space with a heavy distribution of data in favor of those with few examples, the present invention supports models which perform better over the entire space as these models effectively minimizes the maximum absolute error over the entire space.

Although the preferred embodiment uses a Kohonen SOM as the clusterizer, the present invention contemplates that other suitable clusterizers can be used, including a k-means clusterizer or a learning vector quantization (LVQ) clusterizer. For instance, as is known by those skilled in the art, the standard euclidean k-means clusterizer finds a set of k cluster centers which represent a local minimum of the total squared euclidean distances E between the k cluster points x.sub..alpha. and N exemplars (training vectors) x.sub.i : ##EQU6## where M.sub..alpha.i is the cluster membership function, which is a k.times.N matrix of 0's and 1's with exactly one 1 per column. The positions of the cluster points x.sub..alpha. are varied to minimize E. The cluster membership function is redetermined in an iterative fashion after each minimization of E such that each exemplar point belongs to the nearest cluster point's cluster. The cycle of E minimization and M redetermination is iterated until E and M reaches a steady state which represents the local minimum for E.

An adaptive formulation of k-means requires no storage of past exemplars x.sub.i or the cluster membership function M.sub..alpha.i. This formulation, suitable for real-time applications or analog implementation, uses only the current exemplar x(t) as a training signal to modify the nearest cluster vector x.sub.closest according to: ##EQU7## where n is a learning rate. The determination of which of the x.sub..alpha. is x.sub.closest can be accomplished in log k time on a serial computer, constant time on a parallel computer, or approximately constant time in an analog system via a winner-take-all circuit. The learning rate n can be set initially large and then gradually reduced toward zero according to an annealing schedule as is known in the art.

Although the present invention has discussed Kohonen SOM clusterizers and k-means clusters, the invention also contemplates that alternative neural networks can be used to perform the clustering process, including a learning vector quantization (LVQ) network, as discussed by T. Kohonen, J. Kangas, and K. Torkkola in "LVQ.sub.-- PAK: A program package for the correct application of Learning Vector Quantization algorithms" IEEE International Joint Conference on Neural Networks, Baltimore, Md., pp. I725-730 (Jun. 7-11, 1992).

By sub-sampling the data and minimizing the sum squared error on the sub-sampled data, the present invention minimizes the maximum absolute error over the training set. The benefits of the present invention is illustrated in the results contained in Table 1 and the graphical illustration of FIG. 7. Table 1 and the corresponding graphical illustration of FIG. 7 show that the analyzer trained on selected portions of the data is more accurate than the analyzer trained on all data.

Turning now to FIG. 7, the desired result is contrasted with the outputs of the analyzers as trained by all data or by a sub-set of data, as is done by the present invention, is shown. In FIG. 7, a representative data set Y is plotted against a corresponding X data set in the top line of FIG. 7. The results of an indiscriminate application of all data to an analyzer or model during training is shown in the second line of FIG. 7. Further, the results of applying only a selected portion of the training data, as determined by the SOM clusterizer of the present invention, to the analyzer is shown in the third line of FIG. 7. Finally, the fourth line of FIG. 7 illustrates the data selected by the present invention.

The first line of FIG. 7 shows two impulses 300 and 320. Ideally, the analyzer or model should be able to pick up the impulses and reflect the impulses on its respective line in FIG. 7. In the second line of FIG. 7 which corresponds to the column labeled "All" of Table 1, the deficiency of training the analyzer with all data points is shown. Although the analyzer of the second line has picked up the impulse 320 from the original Y data in an impulse 322, the analyzer or model of the second line is not able to pick up the spike 300. In fact, this analyzer behaves poorly in response to the spike 300 with an exponential decay rather than a spike.

Turning now to the third line of FIG. 7 which represents the output generated by the present invention, the third line shows a modulated spike 304 and a spike 324 which correspond to spikes 300 and 320 of the input data. In the fourth line, a number of vertical bars are plotted across the bottom of FIG. 7. Further, under both spikes 300 and 320, there were examples selected by the SOM algorithm of the present invention. Additionally, other points were selected fairly sparsely and uniformly across the more constant parts of the fourth line. The uniform selection of the other points is desirable as representative points from both X and Y data should be included in the training data.

Table 1 shows the data supporting the lines of FIG. 7. In Table 1, the first two columns constitute the data X and Y from which the Y versus X plot of line 1 of FIG. 7 is generated. The analyzer is subsequently trained with all data, or with a subset of the data. These results are illustrated in the third and fourth columns.

The third column of Table labeled "All" is the output of the analyzer which has been trained on all data points. For comparison purposes, the fourth column labeled "SOM" shows the results of the analyzer or model built on training data subselected from the total data using the invention.

Turning now to column 5 of Table 1, various flag values are shown. In Table 1, three types of flags are shown: AWT.sub.-- V which corresponds to data that the SOM clusterizer of the present invention has chosen to be training data; AW.sub.-- SV which corresponds to data that the invention has determined to be test data, while A.sub.-- V indicates that the data is validation data such that the data is not used during the building of the model building. Thus, the data selector of the present invention sub-samples the total data efficiently and sparsely. Further, the present invention picked out important points from the total data set. Thus, by augmenting and subsequently clustering the input vector with the target outputs for the model to be developed, the data selection apparatus of the present invention picks a set of data which is more nearly uniformly distributed across the portion of the input space of interest. Thus, the present invention filters out data in portions of the data space with a heavy distribution of data or examples in favor of those with fewer data or examples.

For modeling techniques which minimize sum squared error (or more generally r-Minkowski error) measures, the data selection apparatus of the present invention results in models which perform better over the entire space as these models effectively minimize the maximum absolute error over the entire space. The data selection apparatus of the present invention thus works well with any modeling technique based on data which optimizes a single composite measure over all of the data used to estimate the model, but the final solution must predict equally well over all the known examples.

The data selection apparatus of the present invention works well with any modeling technique based on data which optimizes a single composite measure over all of the data used to estimate the model, but the final solution must predict equally well over all the known examples. Analyzers or models which can benefit from the working set generated by the present invention include linear models, polynomial models, rational polynomial models, neural networks and other types of data-derived models.

It is to be further understood that the description of data to be collected such as the reflux flow rate and the reboil steam flow rate are associated with the operations of the chemical plant and has only been provided as examples of the types of variables to be collected. The techniques and processes according to the present invention can be utilized in a wide range of technological arts, such as in many other process control environments, particularly multi-variable and more particularly non-linear environment present in a number of plants such as oil refineries, chemical plants, power plants and industrial manufacturing plants, among others. Thus, the present invention is not limited to the description of specific variables collected during the operation of the illustrative plant environment. Additionally, the description of various types of data driven analyzers have only been provided as examples of the types of pattern recognizers that can benefit from the data selection apparatus of the present invention.

Further, the representative applications mentioned such as speech recognition, image recognition, and process control have been provided as examples. Hence, the techniques and processes according to the present invention can be utilized in a wide range of technological arts, such as in many other process control environments such as oil refineries, chemical plants, power plants and industrial manufacturing plants, among others. Thus, the present invention is not limited to the description of specific operating environments.

The foregoing disclosure and description of the invention are illustrative and explanatory thereof, and various changes in the size, shape, materials, components, circuit elements, wiring connections and contacts, as well as in the details of the illustrated circuitry and construction and method of operation may be made without departing from the spirit of the invention.

Claims

We claim:

1. A method for generating a working set of data from a full set of data in a computer for building an analyzer, said analyzer having target outputs, said method comprising the steps of: augmenting said full set of data with the target outputs; normalizing said augmented data; clustering said augmented and normalized data; and selecting one or more members of said clusterized data as said working set of data.

2. The method of claim 1, wherein said clustering step further comprises the step of selecting a subset of said augmented and normalized data.

3. The method of claim 1, wherein said augmenting step further comprises the step of selecting a portion of said full set of data and a portion of said target outputs.

4. The method of claim 1, further comprising the step of applying univariate, non-linear transformations to said augmented and normalized data prior to said clustering step.

5. The method of claim 1, wherein said clustering step uses a weighted distribution.

6. The method of claim 1, wherein said clustering step uses an equi-probable distribution.

7. The method of claim 1, wherein said clustering step further comprises the step of emphasizing said outputs.

8. The method of claim 1, wherein said clustering step uses a statistical technique.

9. The method of the claim 8, wherein said statistical technique is a K-means technique.

10. The method of claim 1, wherein said clustering step is performed by a neural network.

11. The method of claim 10, wherein said neural network is a learning vector quantization neural network.

12. The method of claim 10, wherein said neural network is a self organizing map.

13. The method of claim 1, wherein said normalizing step further comprises the step of detecting and removing outliers in the data.

14. The method of claim 1, further comprising the step of building an analyzer using said working set of data.

15. The method of claim 1, further comprising the step of iteratively selecting data to create one or more analyzers.

16. The method of claim 15, further comprising the step of completing said iterating step when a cutoff level is reached.

17. The method of claim 1, further comprising the step of: matching each example in a training set to a cluster based on said full set of data; uniquely associating an analyzer with a cluster; assigning a recall data to a cluster; and applying said analyzer associated with said cluster to said recall data to provide an output.

18. An apparatus for generating a working set of data from a full set of data in a computer for building an analyzer, said analyzer having target outputs, said apparatus comprising: a cumulator for augmenting said full set of data with the target outputs; an adjuster coupled to said cumulator for normalizing said augmented data; a clusterizer coupled to said adjuster for clustering said augmented and normalized data; and a selector coupled to said clusterizer for picking one or more members of said clusterized data as said working set of data.

19. The apparatus of claim 18, wherein said adjuster further comprises a sub-sampler for selecting a subset of said augmented and normalized data.

20. The apparatus of claim 18, wherein said cumulator further comprises a sub-sampler for selecting a portion of said full set of data and a portion of said target outputs.

21. The apparatus of claim 18, further comprising a transformer coupled between said adjuster and said clusterizer for performing univariate, non-linear transformations to said augmented and normalized data.

22. The apparatus of claim 18, wherein said clusterizer uses a weighted distribution.

23. The apparatus of claim 18, wherein said clusterizer uses an equi-probable distribution.

24. The apparatus of claim 18, wherein said outputs are emphasized by said clusterizer.

25. The apparatus of claim 18, wherein said clusterizer uses a statistical technique.

26. The apparatus of the claim 25, wherein said statistical technique is a K-means technique.

27. The apparatus of claim 18, wherein said clusterizer is a neural network.

28. The apparatus of claim 27, wherein said neural network is a learning vector quantization neural network.

29. The apparatus of claim 27, wherein said neural network is a self organizing map.

30. The apparatus of claim 18, wherein said adjuster further comprises: a non-parametric outlier detector; and a scaler coupled to said non-parametric outlier detector.

31. The apparatus of claim 18, further comprising an analyzer formed from said working set of data.

32. The apparatus of claim 31, further comprising an analyzer generator, said model generator iteratively picking said working set of data to create one or more of analyzers until an optimal analyzer is found.

33. A program storage device having a computer readable program code embodied therein for generating a working set of data from a full set of data to build an analyzer, said analyzer having target outputs, said program storage device comprising: a cumulator code for augmenting said full set of data with the target outputs; an adjuster code coupled to said cumulator code for normalizing said augmented data; a clusterizer code coupled to said adjuster code for clustering said augmented and normalized data; and a selector code coupled to said clusterizer code for picking one or more members of said clusterized data as said working set of data.

Patent Citations (12)

Patent	Date	Inventor
US5111531	1992-05-01	Grayson et al.
US5142612	1992-08-01	Skeirik
US5159660	1992-10-01	Lu et al.
US5263120	1993-11-01	Bickel
US5276771	1994-01-01	Manukian et al.
US5335291	1994-08-01	Kramer et al.
US5353207	1994-10-01	Keeler et al.
US5386373	1995-01-01	Keeler et al.
US5428644	1995-06-01	Kohonen
US5465320	1995-11-01	Enbutsu et al.
US5477444	1995-12-01	Bhat et al.
US5479576	1995-12-01	Watanabe et al.

Non-Patent Literature (33)

Geladi, Paul, et al., "Partial Least-Squares Regression: A Tutorial", Analytica Chimica Acta, 185 (1986) pp. 1-17.
Serth, R.W., et al., "Gross Error Detection and Data Reconciliation in Steam-Metering Systems", A.I.Ch.E. Journal, May 1986, vol. 32, No. 5, pp. 733-742.
Serth, R.W., et al., "Detection of Gross Errors in Nonlinearly Constrained Data: A Cast Study", Chem. Eng. Comm. 1987, vol. 51, pp. 89-104.
Moody, J., et al., "Learning with Localized Receptive Fields", Yale University of Dept. of Computer Science, Sep. 1988, pp. 1-11.
Wold, Svante, et al., "Nonlinear PLS Modeling", Chemometrics and Intelligent Laboratory Systems, 7 (1989), pp. 53-65.
Kramer, et al., "Diagnosis Using Backpropagation Neural Networks--Analysis and Criticism", Computers Chem. Engng., vol. 14, No. 2, 1990, pp. 1323-1338.
Helland, Kristian, et al., "Recursive algorithm for partial least squares regression", Chemometrics and Intelligent Laboratory Systems, 14 (1991), pp. 129-137.
Puskorius, G.V., et al., "Decoupled Extended Kalman Filter Training of Feedforward Layered Networks", IEEE, 1991, pp. I-771-I-777.
Kohonen, Teuvo, et al., LVQ.sub.-- PAK: A program package for the correct application of Learning Vector Quantization algorithms, IEEE, 1992, pp. I-725-I-730.
Plutowski, et al., "Selecting concise training sets from clean data", Feb. 1992, pp. 1-45.
Qin, S.J., et al., "Nonlinear PLS Modeling Using Neural Networks", Computers Chem. Engng., vol. 16, No. 4, 1992, pp. 379-391.
Su, Hong-Te, et al., "Integrating Neural Networks with First Principles Models of Dynamic Modeling", IFAC Symp. on DYCOR+, 1992, pp. 77-82.
Kramer, Mark A., et al., "Embedding Theoretical Models in Neural Networks", 1992, ACC/WA14, pp. 475-479.
Kramer, M.A., "Autoassociative Neural Networks", Computers Chem. Engng., vol. 16, No. 4, 1992, pp. 313-328.
deJong, Sijmen, "SIMPLS: an alternative approach to partial least squares regression", Chemometrics and Intelligent Laboratory Systems, 18 (1993), pp. 251-263.
Klimasauskas, C., "Developing a Multiple MACD Market Timing System," Advanced Technology for Developers, vol. 2, Special Issue, 4 Qtr. 1993, pp. 1-47.
Thompson, Michael L., et al., "Modeling Chemical Processes Using Prior Knowledge and Neural Networks", A.I.Ch.E. Journal, Aug. 1994, vol. 40, No. 8, pp. 1328-1340.
Haykin, Simon, "Neural Networks Expand SP's Horizons", IEEE Signal Processing Magazine, Mar. 1996, pp. 24-49.
Mulgrew, Bernard, "Applying Radial Basis Functions", IEEE Signal Processing Magazine, Mar. 1996, pp. 50-65.
Jain, Anik K., et al., Artificial Neural Networks: A Tutorial, Computer, Mar. 1996, vol. 29, No. 3, pp. 31-44.
Shang, Yi and Wah, Benjamin, "Global Optimization for Neural Network Training", Computer, Mar. 1996, vol. 29, No. 3, pp. 45-54.
Serbedzija, Nikola B., "Simulating Artificial Neural Networks on Parallel Architecture", Computer, Mar. 1996, vol. 29, No. 3, pp. 57-63.
Tan, Chew Lim, et al., "An Aritificial Neural Network that Models Human Decision Making", Computer, Mar. 1996, vol. 29, No. 3, pp. 64-70.
Setiono, Rudy, et al., "Symbolic Representation of Neural Networks", Computer, Mar. 1996, vol. 29, No. 3, pp. 71-77.
Zhao, Hong, et al., "Modeling of Activated Sewage Wastewater Treatment Processes Using Integrated Neural Networks and a First Principle Model", IFAC, 13th World Congress, 1996, pp. 1-5.
Westinghouse Electric Corporation, Descriptive Bulletin 21-161, WDPFII System Overview, pp. 1-5.
Westinghouse Electric Corporation, Descriptive Bulletin 21-196, WDPFII WEStation Historian, pp. 1-4.
Westinghouse Electric Corporation, Descriptive Bulletin 21-188, WDPFII Distributed Processing Unit--Series 32, pp. 1-4.
Westinghouse Electric Corporation, Descriptive Bulletin 21-195, WEStation OpCon, pp. 1-4.
Westinghouse Electric Corporation, Descriptive Bulletin DB21-206, Standard Algorithms, pp. 1-8.
Westinghouse Electric Corporation, Descriptive Bulletin 21-189, WDPFII Westnet II Plus Data Highway, pp. 1-2.
Westinghouse Electric Corporation, Descriptive Bulletin 21-177, WDPFII Q-Line Process I/O, pp. 1-2.
White, David A., and Sofge, Donald A. (Ed.), Handbook of Intelligent Control, (pp. 283-356).

Abstract

Description