Data classifier using learning-formed and clustered map

[0001] 1. Field of the Invention

[0002] The present invention relates to a data classifier for classifying various data, such as sensory data including image and voice information.

[0003] 2. Description of the Related Art

[0004] In recent years, the amount of information people receive has rapidly increased with the spread and advancement of information devices. In this environment, in order to facilitate selection of desired information, there is a strong demand for techniques for recognizing and classifying information without any human intervention.

[0005] To address this demand, there is a known clustering method wherein data to be classified are compared and similar data are classified into groups of data. For the determination of similarity, various methods are known such as, for example, a maximum likelihood method, a K-means method, a merge method, and an MDS (Multi-Dimensional Scaling) method. These clustering methods all require human execution of processes such as parameter setting.

[0006] On the other hand, as a method for performing the clustering process relatively autonomously, a method is known wherein input image data is classified and sorted on a lattice space map. For this classification and sorting, for example, a self-organizing feature mapping (hereinafter abbreviated simply as SOM) is used (T. Kohonen, Self-organizing formation of topologically correct feature maps, Biological Cybernetics, 1982). The SOM is a network having two layers of an input layer in which data is input and a competitive layer of a lattice space map. The input is weighted and input to each lattice. A group of weights for the input components is called a weight vector.

[0007] At first, the weight vector is initialized through the following process. As described in the Kohonen reference described above, a number of input vectors are selected at random from among a plurality of input vectors (corresponding to a feature set at this point) which is a target for learning, the number being identical to a number of prototypes, and the weight vectors for the lattices are initialized. Also according to Kohonen, it is also possible to randomly set initial values for the weight vectors.

[0008] Next, a learning process is performed for the weight vectors. During the learning steps, a feature set for learning is generated and a predetermined measured value (for example, Euclid distance) is calculated from the learning feature set and the weight vectors of lattices in the lattice space. From among the lattices, a lattice having the maximum correlation (minimum measure) is found (this lattice is called a winning node). For lattices located in the neighborhood of this lattice (winning node) in the lattice space, the weight vector of each of these lattices is adjusted such that the measured value between the learning feature set and the lattice is reduced. After repeating the learning process while adjusting the weight vectors in such a manner, lattices having minimum values with respect to a feature set made of features that are similar to each other become concentrated in a particular area, so that a condition can be obtained which can be applied for data classification. In this process, the selection of lattices in which the weight vectors are to be adjusted is made depending on the distance on the map from the winning node. It is preferable that the amount of adjustment be variable depending on the distance from the winning node c and the magnitude of the amount of adjustment also be changeable. In general, the weight vector w is adjusted based on the following equation (1) so that the vector becomes more similar to the weight vector I of a neighborhood node:

[0009] Equation (1)

[0010] wherein $\begin{array}{cc}{h}_{\mathrm{cj}}=\left(t\right)\exp \left[\frac{{r_c-r_j}^2}{2{\left(\left(t\right)\right)}^2}\right]& \left[\mathrm{Equation}2\right]\end{array}$

[0011] in which (t) represents a parameter known as a learning coefficient which controls the magnitude of the amount of adjustment and (t) represents a function referred to as a neighborhood function which determines the variation in the range for adjusting the weight vectors, both of which monotonically decreases with respect to time t. Adjustment according to equation (1) is performed for all lattices that belong in a range of an inter-node distance of Rmax on the map from the winning node wherein

[0012] Equation 3

[0013] With repetition of learning, the value of Rmax decreases as a result of influence of the neighborhood function (t). As the neighborhood function (t), a function such as a triangular type function, a rectangular (quadrangular) type function, and a Mexican hat type function can be used. It is also known that the selection of the neighborhood function (t) also influences the learning results. The parameter t represents time step and is incremented every time a feature set is input. The factor rcrj represents a norm (distance) between the winning node and the node in which the weight vector is to be adjusted.

[0014] Simple application of the above technique, however, does not allow immediate execution of autonomous data classification. In order to realize autonomous data classification, the appropriateness of the lattice space map must be determined after completion of the learning process. In other words, (1) a method for obtaining an optimum lattice space map is required. In addition, when data is to be classified using the lattice space map after the learning process, it is appropriate to create, in the lattice space, boundaries which form the basis for classification and to classify data given as the classification target based on where the lattice having the minimum measure with respect to the feature set corresponding to the data is located relative to the boundaries (regions in the lattice space separated by the boundaries will be referred to simply as clusters hereinafter). That is, (2) a method for determining the boundaries of clusters is also required.

[0015] Among these required methods, as (1) a method for obtaining an optimum lattice space map, Kohonen proposes a method for selecting a map in which the average quantization error is minimum. That is, from among a plurality of lattice space maps formed using different learning conditions, a map having the minimum average quantization error is selected and is used as an approximated optimum lattice space map. In this method, the topology of the space of the input feature set is not reflected in the topology of the map. In other words, the degree of preservation of topology is low. This may lead to erroneous classification depending on the method for clustering.

[0016] As a method which takes into consideration the preservation of topology, a technique for forming an appropriate map by monitoring a predetermined indication called a topological function (topographic function) to control the learning conditions (Auto-SOM) has also been developed. However, the calculation of the topographic function itself is a heavily loaded process, and therefore, there is a problem in that the learning time increases.

[0017] As (2) a method for autonomously determining the boundaries of clusters, a method known as a U-matrix method (Unified Distance Matrix Method) and a method known as a potential method are both under development. The U-matrix method is described in detail in A. Ultsch et al., Know edge Extraction from Artificial Neural Networks and Applications, Proc. Transputer Anwender Treffen/World Transputer Congress TAT/WTC 93 Aachen, Springer 1993. In the U-matrix method, a sum of the absolute values of differences between the corresponding components of the weight vectors of the two lattices or the root-mean square of the differences is defined as the distance between two adjacent lattices on a map. With such a definition, the distance between adjacent lattices that are each strongly associated (that is, these lattices have weight vectors which are close to the feature set; these lattices will hereinafter be described as prototyped to the feature set) with feature sets having a high similarity, that is, the distance between adjacent lattices that are prototyped to two feature sets having a high similarity, is small. In contrast, the distance between adjacent lattices that are each prototyped to two feature sets having a low similarity is large. Considering a three-dimensional surface with the height representing the magnitude of the distance, the height of a surface corresponding to a distance between lattices each prototyped to feature sets having a high similarity will be low and a valley is formed, whereas the height of a surface corresponding to a distance between lattices prototyped to feature sets having a low similarity will be high and a hill is formed. Therefore, by forming the boundaries along the hills, it is possible to define a group (cluster) of lattices that are prototyped to feature sets having a high similarity. The U-matrix method can be considered as a method for compensating a disadvantage of the self-organizing map that the distance in the input space is not preserved.

[0018] The U-matrix method, however, suffers a problem in that although it is possible to define the boundaries when the height differences between the hills and valleys are significant, in many actual information processes, the height differences between the hills and valleys are not as significant as desired, and the height of the three-dimensional surface varies rather gradually. In such cases, manual setting of the boundaries is necessary. Therefore, the U-matrix method in some cases does not allow autonomous determination of boundaries.

[0019] The potential method is disclosed in D. Coomans, D. L. Massart, Anal. Chem. Acta., 5-3, 225-239 (1981). In the potential method, a probability density function of a population which approximately represents input data is estimated using a predetermined potential function and by superposing a value of a function corresponding to input data, and the regions where the amount of superposition is small are determined as the boundaries. As the potential function, a Gaussian type function is commonly used. More specifically, for a group of input data made of N input vectors each having K dimensions, average potentials received by first input data from the other input data (contribution of the first input on the overall input group) ₁ is defined using the following equations (2) and (3). $\begin{array}{cc}\left[\mathrm{Equation}4\right]{}_l=N^{-1}\underset{g=1}{\overset{N}{}}{}_{l,g}& \left(2\right)\\ \begin{array}{c}{}_{l,g}={\left[{\left(2\right)}^{K/2}{}^K\right]}^{-1}\exp \left[-{\left(2{}^2\right)}^{-1}\underset{k=1}{\overset{K}{}}{\left(x_{kl}^l-x_{\mathrm{kg}}^l\right)}^2\right]\\ \mathrm{wherein}\end{array}{x}_{kl}^l=\frac{\left(x_{\mathrm{kl}}-{\stackrel{\_}{x}}_k\right)}{{}_k},{\stackrel{\_}{x}}_k=N^{-1}\underset{l=1}{\overset{N}{}}{x}_{\mathrm{kl}},{}_k={\left[\underset{l=1}{\overset{N}{}}{\left(x_{\mathrm{kl}}-{\stackrel{\_}{x}}_k\right)}^2\left(N-1\right)\right]}^{1/2}& \left(3\right)\end{array}$

[0020] In these equations, x_k1 represents a k-th component of the first input and represents a smoothing parameter which affects the number of clusters to be classified. Therefore, in the potential method, optimization of distribution function for which the distribution shape is to be assumed and optimization of various parameters are required for each input vector group, that is, knowledge concerning the characteristics of the data to be classification is required in advance, and manual adjustment is therefore required. In addition, in the potential method, as the dimension of the feature set obtained from the input data becomes higher, more samples will be required for determining the appropriate probability density distribution, and therefore the potential method suffers from a problem in that it is difficult to apply the method to a map having only a small number of lattices. In other words, the potential method also does not always ensure autonomous determination of boundaries.

[0021] To solve the above-described problems, various techniques have been studied, such as the techniques disclosed in Japanese Patent Laid-Open Publication No. Hei 7-234854, Japanese Patent Laid-Open Publication No. Hei 8-36557, and Unsupervised Cluster Classification using Data Density Histogram on Self-organizing Feature Map, papers of the Institute of Electronics, Information, and Communication Engineers, D-II Vol. J79 -DII No. 7, pp. 1280-1290, July, 1996. However, each of these techniques presumes that the features to be used for the classification are prototyped to lattices with sufficient distance either in the structure of the input data or in the mapping results. When there is variation in a difference between or an overlapping of distribution shapes for each feature to be classified or in the distance between center of masses of the positions on the map of lattices which are prototyped to the feature, which are common to image data classification, for example, the boundaries of clusters become mingled in a complicated manner on the map and appropriate clustering process cannot be performed.

[0022] In addition, in the related art methods, the number of lattices on the map is determined through research and experience in, and there has been no consideration regarding selection of an appropriate number of lattices suitable for actual usage. However, when the number of lattices is less than an appropriate number, there are some cases where the lattices in the section of the cluster boundaries become strongly associated with a feature set which should belong to another cluster, in which case classification error tends to occur more frequently. For this purpose, a technique for increasing or decreasing the number of lattices such that the average quantization error becomes lower than a predetermined number is disclosed in James S. Kirk et al., A Self-Organized Map with Dynamic Architecture for Efficient Color Quantization, IJCNN'01, 2128-2132. In this technique, however, lattices that image data distribution in the space of a feature set corresponding to the input data are added and the like, and there is no consideration for increasing, for example, the number of lattices in the neighborhood of the cluster boundaries, which is important in data classification. As such, it is also possible to increase the number of lattices from the beginning of the process, but this configuration inevitably leads to an increase in calculation time, and therefore, is not practical.

[0023] An advantage of the present invention is that a data classifier is provided which operates autonomously and which takes into consideration the number of prototypes on a map.

[0024] According to one aspect of the present invention, there is provided a data classifier for classifying input data by using a result of a learning process based on the input data and using a self-organizing map, the classifier comprising means for forming, through learning, a plurality of self-organizing maps corresponding to a plurality of learning parameters, and means for evaluating each of the plurality of learning-formed self-organizing maps and adjusting the learning parameters based on the result of the evaluation, wherein a learning formation process of a self-organizing map is repeated using the adjusted learning parameters.

[0025] According to another aspect of the present invention, there is provided a data classifier comprising mapping means for adjusting coupling weights between a plurality of prototypes in a map space using a plurality of input data and forming a prototype map through learning; and clustering means for calculating a predetermined measure (using calculations to obtain a defined measured value) defined between each prototype and classifying the prototypes into a plurality of clusters based on the measure, wherein the prototype map classified into clusters is supplied for a data classification process. According to another aspect of the present invention, it is preferable that, in the data classifier, the measure is calculated as a value of a function which rapidly and asymptotically approaches 0 from a predetermined differential value as the degree of similarity between prototypes decreases, and the cluster to which the observatory prototype belongs is determined using the measure obtained as the value of the function.

[0026] According to another aspect of the present invention, it is preferable that, in the data classifier, the clustering means provisionally determines clusters to which each prototype belongs; the clustering means calculates, for each cluster, a measure between at least one prototype belonging to the cluster and an observatory prototype to be classified into a cluster, and the clustering means determines the cluster to which the observatory prototype belongs based on the calculated measure.

[0027] According to another aspect of the present invention, it is preferable that, in the data classifier, (a) the clustering means provisionally determines clusters to which the prototypes belong; (b) the clustering means sequentially selects each prototype as an observatory prototype to be classified into a cluster; (c) the clustering means calculates, for each cluster, a measure between at least one prototype belonging to the cluster and the observatory prototype; (d) the clustering means changes, as necessary, the cluster to which the observatory prototype belongs based on the calculated measure, and the processes of (b), (c), and (d) are repeated until there is no change in the cluster to which each prototype belongs so that each prototype is classified into a cluster. According to another aspect of the present invention, it is preferable that, in the data classifier, a parameter used for the measure calculation is determined based on a distribution of an occurrence frequency of a degree of similarity between prototypes.

[0028] According to another aspect of the present invention, it is preferable that, in the data classifier, the learning formation of prototype map is achieved through a self-organizing mapping. According to another aspect of the present invention, it is preferable that the data classifier further comprises means for forming, through learning, a plurality of self-organizing maps corresponding to a plurality of learning parameters, and means for evaluating each of the plurality of learning-formed self-organizing maps and adjusting the learning parameters based on the result of the evaluation, wherein a learning formation of a self-organizing map is again performed with the adjusted learning parameters. According to another aspect of the present invention, it is preferable that, in the data classifier, the evaluation of the self-organizing maps is performed based on a phase relationship between a feature space for input data and a prototype map space and on an average quantization error of the prototype map.

[0029] According to another aspect of the present invention, it is preferable that, in the data classifier, a self-organizing map comprises a plurality of prototypes and the classifier further comprises means for forming, after each prototype is classified into a cluster, at least one new prototype in the boundary section of clusters. Here, a further classification process for the new prototype into a cluster may be executed. According to another aspect of the present invention, it is preferable that, in the data classifier, when the new prototype is formed, an additional learning process is executed for the new prototype. According to another aspect of the present invention, it is preferable that, in the data classifier, the new prototype is formed based on a statistical calculation for prototypes present in the neighborhood of the boundaries. According to another aspect of the present invention, it is preferable that, in the data classifier, the new prototype is formed in portions wherein a density of input data referred to by the prototypes is lower than a predetermined threshold value. According to another aspect of the present invention, it is preferable that, in the data classifier, the new prototype is formed in a boundary section of clusters and in portions wherein a density of input data referred to by the prototypes present in that section is lower than a predetermined threshold value.

[0030] According to another aspect of the present invention, there is provided a method for classifying data by executing a learning process based on input data using a self-organizing map and classifying data using the learning result, the method comprising the steps of forming, through learning, a plurality of self-organizing maps corresponding to a plurality of learning parameters; and evaluating each of the plurality of learning-formed self-organizing maps and adjusting the learning parameters based on the evaluation result, wherein a self-organizing map is again formed through learning with the adjusted learning parameters.

[0031] According to another aspect of the present invention, there is provided a method for classifying data, comprising the steps of a mapping step for forming, through learning, a prototype map by adjusting coupling weights between a plurality of prototypes in a map space according to a plurality of data inputs, and a clustering step for calculating a predetermined measure defined between each prototype and classifying the prototypes into a plurality of clusters based on the measure, wherein the prototype map classified into clusters is supplied for a data classification process.

[0032] According to another aspect of the present invention, it is preferable that the method for classifying data further comprises the step of forming, after each prototype is classified into a cluster, at least one new prototype in the boundaries of the clusters. According to another aspect of the present invention, it is preferable that, in the method for classifying data, in the mapping step, a plurality of learning parameters are used for the learning formation of a plurality of prototype maps corresponding to the learning parameters, each of the plurality of learning-formed prototype maps is evaluated, the learning parameters are adjusted based on the evaluation result, and the learning formation of a prototype map is again performed with the adjusted learning parameters. According to another aspect of the present invention, it is preferable that, in the method for classifying data, the evaluation of maps is executed based on a phase relationship between a feature space for the input data and a prototype map space and on an average quantization error of the prototype map.

[0033] According to another aspect of the present invention, there is provided a data classifying program which instructs a computer to execute a process to perform learning based on input data using a self-organizing map and to classify data using the results of the learning, the program instructing a computer to execute the steps of forming, through learning, a plurality of self-organizing maps corresponding to a plurality of learning parameters; and evaluating each of the plurality of learning-formed self-organizing maps and adjusting the learning parameters based on the evaluation results, wherein a learning formation process for a self-organizing map is again performed with the adjusted learning parameters.

[0034] According to another aspect of the present invention, there is provided a data classifying program which instructs a computer to execute the steps of a mapping procedure for adjusting coupling weights between a plurality of prototypes in a map space using a plurality of input data and for forming a prototype map through learning, and of a clustering procedure for calculating a predetermined measure defined between each prototype and for classifying the prototypes into a plurality of clusters based on the measure, wherein the prototype map classified into clusters is supplied for a data classification process.

[0035] According to another aspect of the present invention, it is preferable that the data classifying program further instructs a computer to execute the step of a procedure for forming, after each prototype is classified into a cluster, at least one new prototype in the boundaries of clusters. According to another aspect of the present invention, it is preferable that, in the data classifying program, in the mapping procedure, a plurality of learning parameters are used to form, through learning, a plurality of prototype maps each corresponding to each learning parameter, each of the plurality of learning-formed prototype maps is evaluated, the learning parameters are adjusted based on the result of evaluation, and the learning formation of a prototype map is again performed with the adjusted learning parameters. According to another aspect of the present invention, it is preferable that, in the data classifying program, the map evaluation is performed based on a phase relationship between a feature space for input data and a prototype map space and on an average quantization error of the prototype map.

[0036] FIG. 1 is a block diagram showing a structure of a data classifier according to a preferred embodiment of the present invention.

[0037] FIG. 2 is a block diagram showing a structure within a data classifier according to the preferred embodiment of the present invention.

[0038] FIG. 3 is a flowchart showing a clustering process.

[0039] FIG. 4 is an explanatory diagram showing an example detection of histogram of distance between prototypes.

[0040] FIG. 5 is a flowchart showing an example update process in the clustering process.

[0041] FIG. 6 is an explanatory diagram showing an example operation of the clustering process.

[0042] FIG. 7 is an explanatory diagram showing an example result of clustering in a prototype map.

[0043] FIG. 8 is an explanatory diagram showing an example prototype addition process and example results of clustering after addition of prototypes.

[0044] A preferred embodiment of the present invention will now be described with reference to the drawings. In the following description, the embodiment is illustrated using an example wherein image data is classified, but the present invention is not limited to image data classification and can also be applied to classification of data from other sensory organs, such as taste data, or to measurement data such as experimental results.

[0045] As shown in FIG. 1, a data classifier according to the preferred embodiment of the present invention comprises a CPU 11, a RAM 12, a ROM 13, a hard disk drive 14, an interface 15 for image input, a display 16, and an external storage 17 which are connected to each other via a bus. In other words, the data classifier 1 according to the embodiment is realized as a software classifier operating on commonly used personal computers. This software can be stored and distributed in storage media such as CD-ROMs and DVD-ROMs, or, alternatively, may be downloaded through a network (a connection interface for the network is not shown). When the software is distributed on the storage media, the software is read at the external storage 17 and stored in the hard disk drive 14 through a predetermined installation procedure. When the software is downloaded through a network, the software is installed to the hard disk drive 14 in a similar manner.

[0046] CPU 11 operates according to a program stored in the hard disk drive 14 and generally executes a data classification program or the like for realizing the data classifier 1 of the embodiment under a control of an operating system such as Microsoft Windows (trademark). More specifically, a data classification program according to the embodiment comprises a map generator 21 and a cluster boundary determiner 22. The map generator 21 comprises an SOM learner 31, a map selector 32, a learning condition setter 33, and a prototype adder 34. Here, each component is realized as a software module, but each component may alternatively be realized as a hardware such as a logical circuit. The processes at the CPU 11 will be described in more detail later.

[0047] The RAM 12 is utilized as a work memory for the CPU 11 and stores various parameters and data while the CPU 11 is in operation. The ROM 13 primarily stores programs required for activating the data classifier, such as a program for reading process of the operating system. These activation programs are well known in the art and will not described in detail.

[0048] On the hard disk drive 14, the main portion of the operating system and various programs are installed. In the embodiment, as described above, the data classification program is also installed to the hard disk drive 14. Although embodiment is described exemplifying a case wherein the data classification program is installed on the hard disk drive, it is also possible for the data classification program to be installed on an SRAM (Static Random Access Memory) or a nonvolatile memory such as EEPROM. In addition, the program need not be installed in the same casing as the CPU 11, and may be installed to another computer which is connected via a network interface (not shown).

[0049] An image inputting device such as a scanner is connected to the image input interface 15. The image input interface 15 receives image data input from the image inputting device and outputs the image data to the CPU 11. The display 16 displays an image according to instructions from the CPU 11.

[0050] Details of Process

[0051] Details of the data classification program to be executed by the CPU 11 will now be described with reference to FIG. 2. The map generator 21 creates a prototype map, for example, through a self-organizing mapping (SOM) as described above and outputs information on the created prototype map to the cluster boundary determiner 22. The cluster boundary determiner 22 operates on the prototype map input from the map generator 21 and classifies prototypes into clusters. Each of these components will now be described separately and in detail.

[0052] Map Generation

[0053] The SOM learner 31 of the map generator 21 first generates a plurality of (for example, M wherein M is an integer greater than or equal to 2) candidates for a prototype map corresponding to each of M sets of learning conditions input from the learning condition setter 33. Each map candidate is prepared by associating, to information specifying each prototype, information on relative weighting of the prototype and each of the components of a feature set. In the embodiment, the prototypes composing the map need not necessarily be arranged as lattice points (in this case, the information specifying a prototype may include coordinate information of the prototype on the map), although in the following description, the prototypes are described as being arranged as lattice points in order to simplify the description.

[0054] The map selector 32 calculates a quantization error (hereinafter abbreviated as QE) and topological product (hereinafter abbreviated as TP) for each map candidate and selects a map suitable for cluster determination as a champion map based on these parameters. The quantization error is calculated according to the following equation (4). $\begin{array}{cc}\left[\mathrm{Equation}5\right]Q{E}_i=\frac{1}{P}\underset{j=1}{\overset{P}{}}{E}_j-W_{\mathrm{cl}}& \left(4\right)\end{array}$

[0055] In the equation (4), P represents the number of feature sets used for map learning (that is, the number of learning patterns), Ej represents a j-th vector of the feature set, Wc represents the weight vector of the winning node for the j-th vector of the feature set. The quantization error is well known, for example, from Kohonen, and will not be described in detail.

[0056] TP is calculated according to the following equation (5). $\begin{array}{cc}\left[\mathrm{Equation}6\right]\mathrm{TP}=\frac{1}{N\left(N-1\right)}\underset{j=1}{\overset{N}{}}\underset{k=1}{\overset{N-1}{}}\log \left(T\left(j,k\right)\right)\mathrm{wherein}\begin{array}{c}T\left(j,k\right)={\left(\underset{l=1}{\overset{k}{}}{Q}_1\left(j,l\right)Q_2\left(j,l\right)\right)}^{1/2k}\\ Q_1\left(j,k\right)=\frac{\left(w_j,w_{j\left(k,A\right)}\right)}{\left(w_j,w_{j\left(k,v\right)}\right)}\\ Q_2\left(j,k\right)=\frac{\left(r_j,r_{j\left(k,A\right)}\right)}{\left(r_j,r_{j\left(k,v\right)}\right)}\end{array}& \left(5\right)\end{array}$

[0057] Here, rj represents the coordinate of node j in the SOM competitive layer, j(k,A) represents a k-th closest node from a node j in a competitive layer A, d(i,j) represents a Euclid distance between nodes i and j, wi represents a weight vector for a node i in the SOM competitive layer, and j(k,V) represents a k-th closest node from node i in terms of the Euclid distance of the weight vector.

[0058] The TP becomes smaller as the relative positional relationship between the space in the input layer (feature set space) and the space in the competitive layer (prototype space) becomes more similar, as detailed by Bauer et al. in, for example, Bauer, H. U., and Pawelzik, K. R., (1992), Quantifying the neighborhood preservation of self-organizing feature maps. IEEE Trans., Neural Networks, 3, 570-579.

[0059] The map selector 32 utilizes the QE and TP, and selects, as the champion map MAPc, a map having a minimum score value as calculated using the following equation (6) and outputs the selection result. $\begin{array}{cc}\left[\mathrm{Equation}7\right]\left(\frac{\left|{\mathrm{TP}}_i\right|}{{\mathrm{TP}}^{*}}\right)\left(\frac{Q{E}_i}{Q{E}^{*}}\right)& \left(6\right)\end{array}$

[0060] Here, TP* represents a median of the absolute values of TPi, that is, TP*medianTP1, . . . TPM. Similarly, QE* can be represented as QE*medianQE1, . . . QEM. That is, $\begin{array}{cc}{\mathrm{MAP}}_c=\underset{i}{\min }\left\{\left(\frac{|{\mathrm{TP}}_i}{{\mathrm{TP}}^{*}}\right)\left(\frac{{\mathrm{QE}}_i}{{\mathrm{QE}}^{*}}\right)\right\}& \left[\mathrm{Equation}8\right]\end{array}$

[0061] The map selector 32 does not immediately output the selection result of the champion map to the cluster boundary determiner 22 provided in downstream of the map selector 32, but instead outputs at least one signal to the learning condition setter 33. After repeating this process a predetermined number of times, the map selector 32 then outputs the selection result at that point to the cluster boundary determiner 22.

[0062] The learning condition setter 33 outputs, for example, M sets of data, each set including a number of input data for learning N (number of repetitions of learning), a neighborhood distance (t), and a learning coefficient (t). The learning condition setter 33 initially determines these values and a function (N, (t), (t)) based on random parameters or as a set which is determined in advance (hereinafter referred to simply as preset). The learning condition setter 33 also receives an input of selection result of the champion map from the map selector 32 and extracts a set of learning conditions corresponding to the selected map candidate. Using the extracted set of learning conditions as a basis, the learning condition setter 33 creates and assigns M sets of learning conditions and outputs these to the SOM learner 31.

[0063] The prototype adder 34 is provided for adding a prototype to a predetermined position on the prototype map after the cluster boundaries are determined to allow a further learning process. This component will be described in more detail later as this component is also associated with the operation of the cluster boundary determiner 22.

[0064] The learning operation at the map generator 21 will now be described. Initially, the learning condition setter 33 produces and outputs a plurality of sets (for example, M sets) of learning conditions based on parameters which are set randomly or determined in advance. The SOM learner 31 generates M candidates for a prototype map (map candidates) each corresponding to each learning condition set output from the learning condition setter 33 and outputs the map candidates to the map selector 32. The map selector 32 selects, from among the map candidates, a map in which the learning conditions are preferable for the clustering process using both the quantization error and TP (champion map), and outputs the selection result to the learning condition setter 33. The learning condition setter 33 creates a plurality of sets of new learning conditions based on the learning conditions used for creating the champion map, and again outputs the created sets of learning conditions to the SOM learner 31 for creating another plurality of map candidates.

[0065] In this manner, the steps of creation of map candidates, selection of a champion map, and resetting of learning conditions are repeated a predetermined number of times, and a resulting champion map is output to the cluster boundary determiner 22 as a map in which the cluster boundaries are to be set (hereinafter referred to as a boundary setting map).

[0066] Determination of Cluster Boundaries

[0067] The cluster boundary determiner 22 executes processes as exemplified in FIG. 3 using the map input from the map generator 21 as the boundary setting map. More specifically, the cluster boundary determiner 22 assigns a unique number to each of prototypes contained in the input map and generates a provisional clustering result (S1). These numbers may be assigned by assigning numbers from 1 to P (with the number of prototypes being P) in a predetermined order. These numbers represent provisional cluster numbers. In other words, initially, the prototypes are classified into clusters which differ from each other.

[0068] Then, the cluster boundary determiner 22 chooses a prototype pair and calculates a degree of similarity between the weight vectors of the prototypes in the chosen prototype pair (S2). The result of this calculation is stored in the RAM 12 as a table for degree of similarity. A prototype pair referred to herein includes prototype pairs obtained by sequentially selecting a prototype as an observatory prototype and combining the observatory prototype with all of the other prototypes, that is, all combinations of two prototypes. In addition, as the degree of similarity referred to herein, a squared sum (distance) of the differences for the corresponding components of the weight vectors is used.

[0069] The degree of similarity is classified into classes each having a predetermined range of numerical values, and information on occurrence frequency for each class is generated (FIG. 4). A distance wherein the occurrence frequency is the maximum is set as Cd and a predetermined minute amount which is close to 0 is determined, or, alternatively, a distance which is shorter than the distance where the occurrence frequency is maximized and which is a maximum of where the occurrence frequency changes from decreasing to increasing may be set as Cd.

[0070] Next, a process for updating the cluster numbers is started (S3). The cluster number update process is as shown in FIG. 5. In order to simplify the description, the process is explained here using an example wherein a 33 lattice map is used as the prototype map for which the cluster boundaries are to be determined. Initially, for the prototype map, unique numbers of 1 through 9 are assigned to 339 prototypes as shown in the a-state of FIG. 6 at the process S1.

[0071] The cluster boundary determiner 22 sequentially selects a prototype as an observatory prototype (S11). Then, the cluster boundary determiner 22 selects a cluster to which a prototype adjacent to the observatory prototype belongs (within a predetermined distance on the prototype map for which cluster boundaries are provisionally determined) (S12) and chooses the prototype which belongs to the selected cluster (S13).

[0072] In the example shown in FIG. 6, for example, the 1 on the left bottom is selected as the observatory prototype, and for each of the adjacent cluster numbers 1, 4, 5, and 2, prototypes that belong to each cluster are selected. Then, the cluster boundary determiner 22 calculates correlation between each prototype belonging to the clusters selected in process S12 and the observatory prototype as a measure using the following equation (7) (which is a function rapidly and asymptotically approaching 0 from a predetermined differential value with the decrease in the degree of similarity) (S14) and determines the cluster to which the observatory prototype belongs based on the correlation. $\begin{array}{cc}\left[\mathrm{Equation}9\right]F\left(c\right)=\frac{\underset{i\left(c\right)}{}{}^{-{y^{*}-y_k}^2}}{\underset{j}{}{}^{-y^{*}-y_j}}\mathrm{wherein}=-\frac{Ln\left(\right)}{\mathrm{Cd}}& \left(7\right)\end{array}$

[0073] In equation (7), y* represents the weight vector of the observatory prototype, yi represents the weight vector of the i-th prototype, and represents a group of prototype vectors with (c) representing the group of prototype vectors in cluster number c, the parameters Cd and used for determining is obtained at the process S2, and Ln represents the natural logarithm. In other words, in equation (7), the sum of the distances between the observatory prototype and the prototypes belonging to the cluster having the cluster number of c is divided by the overall average. Equation (7) therefore represents correlation between the observatory prototype and the cluster c, and exhibits a larger value for a cluster c which includes a larger number of prototypes having weight vectors with large correlation with the weight vector of the observatory prototype.

[0074] The cluster boundary determiner 22 provisionally determines, as the cluster number of the observatory prototype, the number of cluster which exhibits the maximum value for equation (7) (S15) and stores the provisional determination (S16).

[0075] When the prototype classified into the cluster 1 in the a-state of FIG. 6 is the observatory prototype, for example, as an adjacent prototype, initially no prototype other than the observatory prototype belongs to cluster 1 and no calculation is performed regarding cluster 1. Correlations between the observatory prototype and prototypes belonging to cluster 4, between the observatory prototype and prototypes belonging to cluster 5, and between the observatory prototype and prototypes belonging to cluster 2 are calculated, and when, for example, the shortest distance is observed between the observatory prototype and the prototype belonging to the cluster 4, the cluster to which the observatory prototype belong is changed from cluster 1 to cluster 4 (b-state in FIG. 6). It is also possible to perform the correlation calculations with all prototypes instead of performing the calculations with the adjacent prototypes. With such a configuration, it is possible to gather prototypes that are farther away on the prototype map, but which have relatively short distances in terms of the weight vectors. However, as this configuration requires longer period of time, in the embodiment, a map has been selected in which the distances on the prototype map are not too far different from the distances in terms of the weight vectors by considering evaluation using TP in advance.

[0076] The cluster boundary determiner 22 then checks whether all prototypes have been selected as an observatory prototype (S17), and if there is any prototype which has not been selected (if No), the process returns to S11 and continues from there. If it has been determined at process S17 that all prototypes have been selected (if Yes), the update process of the cluster number is completed.

[0077] The cluster boundary determiner 22 returns to the process shown in FIG. 3 and compares the provisional determination with the cluster numbers before the update process to check whether or not there had been any change in the cluster numbers (whether or not the cluster numbers have been converged) (S4). If there has been any change (if Yes), the process S3 is repeated using the provisional determination as a new provisional clustering result. If it has been determined that there has been no change (if No) in the process S4, that is, if the cluster numbers are converged, the cluster boundary determiner 22 outputs the obtained clustering results.

[0078] Addition of Prototype

[0079] A feature of the embodiment is that the clustering boundary determiner 22 does not immediately output the clustering result as the final result, but rather the clustering boundary determiner 22 can generate at least one output to the prototype adder 34 of the map generator 21. The prototype adder 34 creates a new prototype in the section of boundaries of the clusters by referring to the clustering result and outputs, to the SOM learner 31, a prototype map after the new prototype is added so as to allow a further learning process. This further learning is targeted for fine adjustment, and therefore if, for example, the learning conditions for the learning process before clustering are set as (t)0.2, (t)2.0, and 10000 learning steps for 700 patterns, the learning process after the new prototype is added can have, for example, learning conditions such as (t)0.002, (t)1.0, and 100 repetition of pattern input.

[0080] More specifically, when, for example, the cluster boundary determiner 22 outputs a clustering result as shown in the c-state of FIG. 6 for a prototype map which is provisionally clustered initially as the a-state of FIG. 6, a new prototype is formed at the boundary between clusters 4 and 6 (d-state of FIG. 6). In d-state of FIG. 6, the previous clustering results are shown in parentheses to facilitate the understanding, but these previous clustering results are meaningless after the prototype has been added.

[0081] The new prototype need not be added in the entire region along the cluster boundaries and may instead be added in at least a portion along the cluster boundaries. In this case, it is preferable to determine the portion to which a prototype is to be added based on the number of instances (number of patterns) in which the portion became a closest-neighboring prototype having the shortest distance with respect to the learning input vector (pattern). In learning methods such as SOM learning and VQ learning, the density of prototypes at the central section of a cluster is large and the density of the prototypes is small near the cluster boundary such that the clusters can be used in the U-matrix method. Therefore, for a portion which has a relatively small number of opportunities, a number less than a predetermined threshold value, to become a closest-neighboring prototype with respect to the learning input pattern, that is, a portion where the density of the prototypes is less than a predetermined threshold value, it is possible to assume that the portion is a prototype near the boundary of the clusters. By adding a new prototype to this portion, it is possible to avoid adding new prototypes over the entirety of the boundary, and the efficiency for the re-learning and re-clustering processes can be improved.

[0082] The weight vector of the new prototype to be added is determined using a predetermined statistical calculation result (for example, arithmetic mean) with respect to weight vectors of already-existing prototypes near the position to which the new prototype is to be added (for example, the boundary).

[0083] Operation

[0084] Next, an operation of a data classifier 1 according to the embodiment will be described. First, the learning condition setter 33 outputs a plurality of sets of learning condition parameters S1, S2, . . . , SM and the SOM learner 31 generates a number of prototype maps, the number corresponding to the number of sets of the learning condition parameters (in this case, M). The SOM learner 31 generates a predetermined feature vector based on learning image data input from outside and adjusts coupling weights between each prototype in each prototype map and each component in the feature vector. This operation of the SOM learner 31 is well known from, for example, Kohonen et al. As the learning image data, image data of a target intended for later classification such as, for example, image data relating to eye or image data relating to nose may be used.

[0085] The plurality of prototype maps generated by the SOM learner 31 are output to the map selector 32. Based on quantization error (QE) and topological product (TP) determined through calculations relating to the prototypes included in each map, the map selector 32 selects a map in which the quantization error is small and the matching of the relative positional relationship, indicated by TP, between the space of input layer (feature set space) and the space of competitive layer (prototype space), that is, the matching between the distance between weight vectors and the distance in the competitive layer is high. With such selection, the distance on the map between prototypes which are sensitive to similar image data can be reduced.

[0086] Then, based on the set of learning condition parameters used for learning in the selected map, the learning condition setter 33 again generates a plurality of sets of learning condition parameters and outputs to the SOM learner 31. A plurality of maps are again generated and the map selection process based on QE and TP is again performed. In this manner, the learning condition parameters are recursively adjusted and the formation through learning (learning formation) of maps is recursively performed.

[0087] The cluster boundary determiner 22 operates on a map obtained through the recursive learning as described, sequentially selects a prototype on the map, and collects in a cluster the selected prototype and adjacent prototypes which have a large correlation with the selected prototype. In other words, the cluster boundary determiner 22 determines a cluster to which each prototype belongs based on the positional relationship on the map between the prototypes and the correlation between the prototypes. This process is repeated until the clustering result converges. When the clustering result converges, the clustering boundary determiner 22 outputs the converged clustering result to the prototype adder 34.

[0088] The prototype adder 34 generates a map to which a new prototype is added in the boundary portion of the clusters and outputs the generated map to the SOM learner 31 which then sets predetermined learning conditions and re-executes the learning process. In this process, only one set of learning condition parameters is required, and therefore, only one map is necessary. After the learning process for the map is completed, the map is output to the cluster boundary determiner 22 (without passing through the map selector 32) and the cluster boundary determiner 22 re-executes the clustering process.

[0089] The map obtained as a result of this clustering process is supplied for use in the classification process. In other words, a feature vector is generated for image data input as the classification target and a prototype which has the largest coupling weight with respect to the feature vector (a prototype which is sensitive to the input image data) is found. The cluster number of the cluster to which this prototype belongs is assigned as the classification number for the image data. In this manner, a specific classification number is determined for image data which are similar to each other (for example, image data relating to eye), and different classification numbers are determined and output for image data which differ from each other (for example, image data relating to eye and image data relating to nose). The result of this classification is displayed on the display 16 and is printed using a printer or the like (not shown).

[0090] As described, according to the present embodiment, it is possible to realize autonomous learning and clustering processes without manual setting of parameters. In addition, if the number of prototypes is insufficient, a prototype is autonomously added at the boundary portion of the clusters and learning and classification processes with appropriate number of prototypes are executed.

[0091] Specific Example

[0092] An example of addition of a new prototype according to the present embodiment will now be described. 700 image data to be classified into two categories, eye and nose, were prepared and a learning process was performed using a prototype map having 339 prototypes. For simplicity, one set of learning condition parameters was used (and therefore one map was used) with the parameters set at (t)0.2, (t)2.0, and 10000 repetition for SOM learning using the 700 patterns. As a result of cluster boundary determination for a prototype map obtained with the above conditions, cluster boundaries as shown in FIG. 7 were formed. A data classification process was performed using this map, and it was found that 15 patterns from among the 700 patterns were erroneously classified.

[0093] Then, new prototypes were added as shown in the a-state in FIG. 8 on the cluster boundary (represented by New in FIG. 8), and an additional learning process was performed with (t)0.002, (t)1.0, and a repetition number of pattern input of 100. The clustering boundary determination process was again executed and a clustering result as shown in the b-state of FIG. 8 was obtained. The number of erroneous classification of data according to a data classification process using this resulting map was 0. The weight vectors of the prototypes in the boundary portion were carefully studied and it was found that there was no closest-neighboring prototype for both eye and nose which are the classification targets.

[0094] In another example, cluster boundaries were determined using a map having 3412 prototypes from the beginning through SOM learning with the learning condition parameters being (t)0.2, (t)2.0, and 10000 repetitions of inputs of 700 patterns. A data classification process using this result indicated experimentally that there were some prototypes in the boundary portion which are closest-neighboring prototypes for both eye and nose, and therefore there existed some erroneous classifications. These errors resulted because, in contrast to the embodiment wherein prototypes are added in order to improve the resolution in the portion where cluster boundaries are once formed, in a method wherein a larger number of prototypes are used the learning for prototypes are performed so as to image the pattern distribution in the input space and, thus, the precision of data classification at the cluster boundary portion is not improved. In addition, in the embodiment, because the learning process is performed using a small number of prototypes initially, the time required fro the initial learning process can be shortened. As described above, because the second learning process in the embodiment may be a fine adjustment with the learning condition parameters changed, the total time required for the overall learning process including both the preliminary learning and the secondary learning can be shortened compared to a learning process in which a larger number of prototypes is utilized from the beginning.

[0095] Alternative Example

[0096] In the above description, clusters are determined by performing a learning process through recursive adjustment of learning condition parameters and using correlations between prototypes, new prototypes are added after the preliminary cluster determination, and secondary cluster determination process is applied. It is also possible to independently apply the prototype adding technique to a learning formation of a prototype map which is already being used or to a clustering technique. In this case, in addition to SOM, VQ learning or the like may also be employed for learning of the prototype map.

[0097] In addition, although the above description exemplifies a case of classification of image data, the data classifier according to the embodiment is not limited to such a configuration and may also be applied for classification of other data.