JP2001283184A - Clustering device - Google Patents

Abstract

(57) [Problem] To provide a clustering device capable of responding to a dynamic change of data in clustering with a simple configuration and a simple procedure. SOLUTION: In a clustering apparatus for classifying input data using clusters, a cluster creation apparatus 1 for creating a cluster, and a clustering execution apparatus for executing clustering of input data using clusters created by the cluster creation apparatus 2, a clustering result monitoring device 3 that monitors the clustering result of the clustering execution device and identifies input data that has been incorrectly classified;
A storage means for storing misclassified input data, wherein when a predetermined number or more of data is stored in the storage means, the cluster creating apparatus creates a new cluster based on the data; are doing. The cluster can be corrected in response to the dynamic change of the input data, and erroneous classification can be suppressed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a clustering apparatus for classifying a large number of data into classes based on their similarity, and more particularly to a clustering apparatus capable of appropriately coping with dynamic changes in input data.

[0002]

2. Description of the Related Art Conventionally, various clustering methods have been proposed. FIG. 6 shows an example of the most common clustering device.

Here, 100 denotes a prototype data group for learning, 102 and 103 denote clusters A and B, each of which is regarded as an initial cluster, and 104 denotes a cluster A102. Cluster B10
105 indicates the distance to cluster 105, and clusters A102 and B103
Is shown in the cluster C. 200 indicates a cluster result created from the prototype data, and 201 and 202 indicate the finally created cluster Y and cluster Z. 30
0 indicates a clustering device using a cluster, and 301
Denotes a cluster Y exactly the same as 201, 302 denotes a cluster Z exactly the same as 202, 303 denotes an input X to be clustered, and 304 denotes a point of the input X303 in the space where the cluster exists.

In this device, first, a cluster required for a clustering device is created. This is determined by the following work.

[0005] If the closest cluster is searched from the prototype data group 100 for learning, and the cluster A 102 and the cluster B 103 are selected as a result, this cluster 2
The two are integrated into cluster C105, and clusters A and B are deleted. At this time, the cluster C105 has both the values of the cluster A102 and the cluster B103. Next, similarly, a series of operations of searching for the closest cluster from the prototype data group 100 and integrating them are repeated. At this time, when the number of all clusters becomes 1, or when the distance between the closest clusters is larger than a certain value, the operation is terminated.

[0006] By this series of operations, a cluster result 200 created from the prototype data is obtained, and finally the integrated cluster is a cluster Y201 and a cluster Z202.
Becomes

The clustering device 300 using the clusters performs the actual clustering using the finally integrated clusters. When the input X303 is input to the clustering apparatus 300 using this cluster, when the input X303 is included in the cluster Y301, the input X303
Is clustered into the cluster Y301.

Further, a self-organizing map (SOM: Self-Oraganization Map, more specifically, T. Koho
nen, "Self-Oraganization and Associate Memory", T
hirdEdition, Springer-Verlag, Berlin, 1989. ) Is also known (Japanese Patent Laid-Open No. 7-234853).
In this method, prototype data is input to the SOM, the neurons forming the SOM are learned, and the learned neurons are classified into clusters. When input data is given to the SOM after the cluster is formed, a neuron having a value close to the input is determined, and the input data is clustered.

[0009]

However, in the clustering method as described above, since clusters are formed using prototype data, clusters are formed only in prototype data. Therefore, there is a problem that when actual data is clustered using these clusters, it is not possible to cope with dynamic changes in input data.

In other words, when data to belong to a new class occurs with the passage of time, the conventional method cannot deal with the data at all and is erroneously classified into one of the clusters.

In order to prevent this erroneous classification, in the conventional method, it is necessary to perform clustering again using all data including the prototype data, and a large work load is imposed. A method of correcting a cluster when data is newly added is disclosed in Japanese Patent Application Laid-Open No. H5-205058. However, it is necessary that it is known that new data is added, It is necessary to notify that the cluster is to be modified by adding data, and it is not possible to automatically collect additional data or modify the cluster automatically.

An object of the present invention is to solve such a conventional problem, and an object of the present invention is to provide a clustering apparatus capable of responding to a dynamic change of data in clustering with a simple configuration and procedure.

[0013]

Therefore, according to the present invention, in a clustering apparatus for classifying input data using clusters, a cluster creating apparatus for creating clusters and a cluster created by the cluster creating apparatus are used. A clustering execution device that performs clustering of input data, a clustering result monitoring device that monitors a clustering result of the clustering execution device to identify misclassified input data, and a storage unit that accumulates misclassified input data. When a certain number or more of data is accumulated in the accumulation means, the cluster creating apparatus creates a new cluster based on the data.

Therefore, it is possible to correct the cluster in response to the dynamic change of the input data, thereby suppressing erroneous classification.

[0015]

Embodiments of the present invention will be described below with reference to the drawings. The present invention is not limited to these embodiments at all, and can be implemented in various modes without departing from the gist thereof.

(First Embodiment) As shown in FIG. 1, a clustering apparatus according to a first embodiment includes a prototype data DB 4 for managing prototype data, and a cluster creating apparatus for creating a cluster 5 using the prototype data. 1 and input data 6 using the created cluster 5
, A clustering result monitoring device 3 that monitors a clustering result 7 of the clustering execution device 2, and a misclassification input data DB8 that manages data determined to be misclassified by the clustering result monitoring device 3. Have.

In this apparatus, the cluster creating apparatus 1 generates a cluster 5 using the prototype data DB 4. The clustering execution device 2 uses the generated cluster 5 to cluster the input data 6 that has been input, and outputs a clustering result 7. The clustering result monitoring device 3 monitors the output clustering result 7 and, when it determines that the error included in the clustering result 7 of the input data 6 is a certain value or more and is clearly misclassified, The input data 6 is added to the misclassified input data DB8, and the number of data accumulated in the misclassified input data DB8 is counted. This misclassified input data D
When the data in B8 exceeds a certain number, the cluster creation device 1 is instructed to create a cluster using the misclassified input data DB8.

The operation of each device will be described in more detail. First, the cluster creation device 1 operates when the cluster 5 is not created and when the clustering result monitoring device 3 instructs creation of a cluster.

When the cluster 5 has not been created, the individual data of the prototype data group in the prototype data DB 4 is regarded as the initial cluster, and the closest cluster is searched therefrom. This distance is obtained by Expression 1 in FIG. The two clusters obtained at this time are integrated to form a new cluster. The merged cluster is deleted, and the newly created cluster has all the values of the cluster deleted by the merge. Similarly, a series of operations of searching for the closest cluster from the prototype data DB and integrating them are repeated. At this time, when the number of all clusters becomes 1, or when the distance between the closest clusters is larger than a certain value, the operation is terminated.

Through this series of operations, a cluster 5 created from the prototype data 4 is created.

Next, when an instruction to create a cluster is received from the clustering result monitoring device 3, the misclassified input data D
Using B8, a cluster is created in the same operation as creating cluster 5. At this time, the created cluster in which the number of values included in the cluster is equal to or more than a certain value is added to the cluster 5 as a new cluster. Finally, the misclassification input data DB is cleared.

Next, the operation of the clustering execution device 2 will be described. Using the cluster 5 created by the cluster creation device 1, the cluster with the closest distance to the input data 6 is selected. The calculation of this distance is obtained by Expression 1 in FIG. At this time, the selected cluster and the calculated distance representing the error are output as the clustering result 7.

The clustering result monitoring device 3 adds the input data 6 to the misclassified input data DB 8 when the error included in the output clustering result 7, that is, the calculated distance is a certain value or more. The number is counted, and when the data in the misclassified input data DB8 exceeds a certain number, the cluster creation device 1 is instructed to create a cluster using the misclassified input data DB8.

As described above, the clustering apparatus of this embodiment can automatically create clusters during operation, and can automatically create clusters in response to dynamic changes in input data. . Therefore, the occurrence of misclassification due to a dynamic change in input data can be quickly suppressed. Further, in this device, since the cluster is re-created using only the data automatically collected as the misclassified data in the process of clustering the actual data, the cluster can be corrected with a small burden.

(Second Embodiment) The clustering apparatus of the second embodiment creates a cluster using a self-organizing map (hereinafter, referred to as SOM).

As shown in FIG. 2, this apparatus comprises a prototype data DB4, a cluster creation apparatus 1, a clustering execution apparatus 2, a clustering result monitoring apparatus 3, and a misclassification input data DB8, as in the first embodiment.
The cluster creation device 1 includes a data input unit 11 for inputting prototype data, an SOM creation unit 12 for creating an SOM 9, and a cluster creation unit 13 for creating a cluster using the SOM 9, and a clustering result monitoring device 3. Has a clustering result monitoring means 31 for monitoring the clustering result 7 of the clustering execution device 2 and an SOM correction means 32 for creating the SOM 10 using the data of the misclassified input data DB8.

In this apparatus, the data input means 11 of the cluster creation apparatus 1 inputs data from the prototype data DB 4, and the SOM creation means 12 uses this data to
9 and the cluster generating means 13 generates the cluster 5 using the SOM 9. The clustering execution device 2
Input data 6 input using the generated cluster 5
Are clustered, and a clustering result 7 is output. When the clustering result monitoring means 31 of the clustering result monitoring device 3 determines that the error included in the output clustering result 7 is a certain value or more and is clearly misclassified, the misclassification input data DB 8 , And counts the number.

When the data in the misclassified input data DB8 exceeds a certain number, the SOM correcting means 32 creates a new SOM10 by using the data of the misclassified input data DB8 as an input, and stores the SOM10 in the cluster creating means 13. Instruct the creation of the used cluster. In response to this, the cluster creating means 13
A cluster is created using the SOM 10 and added to the already created cluster 5.

Next, the operation of each section will be described in more detail. First, the operation of the SOM creating means 12 will be described.

As shown in FIG. 4, the SOM is formed from neurons 402 arranged two-dimensionally, and each neuron has a vector called the reference vector 403 and having the same dimension as the input.

The SOM creating means 12 creates an SOM according to the procedure shown in the flowchart of FIG. Step A1: The number of learning times T is set to 0. Step A2: A neuron arranged two-dimensionally as shown in FIG. 4 is created, and a reference vector of the same dimension as the input is given to each neuron by random numbers.

Step A3: The data input means 11 takes out one piece of data at random from the prototype data DB4.

Step A4: For this data, FIG.
A neuron C having a reference vector satisfying the expression (2) is determined.

Step A5: The reference vector of the neuron located near the neuron C is updated according to the equation (3) in FIG.

Step A6: When the number of learning times T reaches the specified number, step A8: ends.

In step A6, if the number of times of learning T has not reached the specified number of times, step A7: the value of the number of times of learning T is increased by one, and the process returns to step A2.

Next, the cluster generation means 13 generates the cluster 5
This operation is performed when is not created and when an instruction to create a cluster is received from the SOM correcting unit 32.

First, when the cluster 5 has not been created,
The cluster 5 is created using the SOM 9. For each neuron of SOM9, a neuron having a reference vector satisfying equation (4) in FIG. 5 is selected, and the selected neuron is regarded as an initial cluster. From among them, the closest cluster is searched. This distance is obtained by equation (1) in FIG. The two clusters obtained at this time are integrated to form a new cluster. The merged cluster is deleted, and the newly created cluster has all the values of the cluster deleted by the merge. Similarly, a series of operations of searching for the closest clusters and integrating them are repeated. At this time, when the number of all clusters becomes 1, or when the distance between the closest clusters is larger than a certain value, the operation is terminated.

Similarly, when a cluster creation message is received from the SOM correction means 32, a cluster is created using the SOM 10 and added to the cluster 5.

The clustering execution device 2 clusters the input data 6 using the cluster 5 and outputs a clustering result 7 as in the first embodiment. The clustering result monitoring means 31 determines that the error included in the output clustering result 7 is a value equal to or more than a certain value,
When it is determined that the classification is misclassified, the input data 6 is added to the misclassification input data DB 8 and the number thereof is counted.

When the data in the misclassified input data DB8 exceeds a certain number, the SOM correcting means 32 takes the data of the misclassified input data DB8 as an input and sets the size of the map to SOM9 according to the flowchart of FIG. Create a small SOM10 equal to the number of vertical or horizontal neurons. Then, the erroneous classification input data DB 8 is cleared, and the cluster creation means 13 is instructed to create a cluster. The cluster creating means 13 creates a cluster using the SOM 10 and adds it to the created cluster 5 as described above.

As described above, in the clustering apparatus of this embodiment, since the clustering is performed using the SOM, the existing SOM can be applied as it is, and when a new cluster is created, the cluster is very small. Since the SOM is used, the processing speed is high, and the practical effect is great. In addition, since this new cluster is created using data automatically collected as misclassified data in the process of clustering actual data, this new cluster can be used to respond to dynamic changes in input data. can do.

[0043]

As is clear from the above description, the clustering apparatus of the present invention can quickly create a new cluster in response to a dynamic change of input data, It is possible to suppress the occurrence of misclassification due to a significant change.

Further, the creation of this new cluster is performed using only data automatically collected as misclassified data when the clustering is performed, so that the creation burden is reduced.

In an apparatus having means for directly creating a cluster from misclassified data, it is possible to automatically create a cluster even while the apparatus is operating, and it is possible to quickly respond to dynamic changes in input data. The advantageous effect described above can be obtained.

In an apparatus that performs clustering using SOM, an existing SOM can be applied as it is, and when a new cluster is created, an extremely small SOM is used, so that the processing speed is high. The effect is obtained.

As a result, the present invention can be effectively applied to an apparatus for clustering data whose input data changes with time. For example, the learning result of a student who changes with time can be used as input data. This is extremely effective when used in a clustering device of a learning system for classifying students, or a clustering device for examining the taste of viewers accessing an Internet homepage.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of a clustering device according to a first embodiment of the present invention;

FIG. 2 is a block diagram showing a configuration of a clustering device according to a second embodiment of the present invention;

FIG. 3 is a flowchart illustrating a procedure for creating an SOM according to the second embodiment;

FIG. 4 is a diagram showing SOM visually.

FIG. 5 is a diagram showing mathematical formulas;

FIG. 6 is a diagram illustrating an example of a conventional clustering device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Cluster creation apparatus 2 Clustering execution apparatus 3 Clustering result monitoring apparatus 4 Prototype data DB 5 Cluster 6 Input data 7 Clustering result 8 Misclassification input data DB 9, 10 SOM 11 Data input means 12 SOM creation means 13 Cluster generation means 31 Clustering result Monitoring means 32 SOM correction means 100 Prototype data group 102 Cluster A 103 Cluster B 104 Distance 105 Cluster C 200 Cluster result created from prototype data 201 Cluster Y 202 Cluster Z 300 Clustering device using cluster 301 Cluster Y 302 Cluster Z 303 Input X 304 Input X point 401 SOM 402 Neuron 403 Reference vector

Claims (5)

[Claims] 1. A clustering apparatus for classifying input data by using a cluster, comprising: a cluster creation apparatus for creating the cluster; and clustering of the input data using the cluster created by the cluster creation apparatus. A clustering execution device, a clustering result monitoring device that monitors a clustering result of the clustering execution device to identify misclassified input data, and a storage unit that accumulates the misclassified input data. A clustering apparatus, wherein when a predetermined number or more of data is accumulated in the means, the cluster creating apparatus creates a new cluster based on the data. 2. The method according to claim 1, wherein when a predetermined number or more of data is stored in the storage unit, the cluster generating apparatus automatically generates a new cluster using the data and adds the new cluster to the already generated cluster. The clustering device according to claim 1, wherein: 3. The clustering apparatus according to claim 1, wherein the clustering result includes clustering error data. 4. A self-organizing map generating means for generating a self-organizing map by using prototype data as input, and a cluster forming means for partitioning the generated self-organizing map to form a cluster. The clustering apparatus according to claim 1, further comprising: 5. A clustering result monitoring device, comprising: a clustering result monitoring unit for monitoring a clustering result; and when a predetermined number or more of data is accumulated in the accumulation unit, a self-organizing map is generated by using the data as an input. The self-organizing map modifying means, wherein the cluster forming means of the cluster creating apparatus creates a cluster by dividing the self-organizing map when the self-organizing map modifying means generates the self-organizing map. The clustering apparatus according to claim 4, wherein the clustering apparatus adds the cluster to an already created cluster.