JP7659766B2 - Information processing device, information processing method, and program - Google Patents

Description

The present disclosure relates to an information processing device, an information processing method, and a program, for example, an information processing device, an information processing method, and a program that sequentially inputs input vectors belonging to an arbitrary class and learns the input distribution structure of the input vectors.

A method called Self-Organizing Incremental Neural Network (SOINN) has been proposed as a learning method that grows neurons as needed during learning (Patent Document 1). SOINN has many advantages, such as being able to learn non-stationary inputs by autonomously managing the number of nodes, and being able to extract an appropriate number of classes and topological structures even for classes with complex distribution shapes. As an example of an application of SOINN, for example, in pattern recognition, after learning classes of hiragana characters, it is possible to additionally learn classes of katakana characters, etc.

As an example of such SOINN, a method called E-SOINN (Enhanced SOINN) has been proposed. E-SOINN allows for online additional learning, which adds learning at any time, and has the advantage of being more efficient than batch learning. Therefore, E-SOINN allows additional learning even when the learning environment changes to a new environment. E-SOINN also has the advantage of being highly resistant to noise in the input data.

However, SOINNs including E-SOINN have problems such as the learning results differing depending on the input order of the input data, and the learning accuracy decreasing when high-dimensional data of 1000 dimensions or more is used as the input data. To solve these problems, a method called LB-SOINN (Load Balance Self-Organizing Incremental Neural Network) has been proposed (Patent Document 2). LB-SOINN treats the load of a node in the network as a node learning time, detects a node with a large node learning time, and generates a new node on the edge connecting the detected node to an adjacent node, the new node having a weight vector determined based on the weight vector of the detected node. This alleviates the increase in the learning time of the detected node, and by generating a new node in its vicinity, the structure of the input data can be learned more accurately.

JP 2008-217246 A JP 2014-164396 A

However, it was found that when learning input vectors using SOINN as described above, the influence of noise can cause clusters that should be separated to be connected by edges, resulting in the problem that the distribution of input vectors cannot be accurately learned.

Figure 13 shows an example of input data with little noise. The input data shown in Figure 13 is a combination of two parts of two-dimensional input vectors distributed in an arc shape. Figure 14 shows the network structure obtained by learning the input data in Figure 13 using the above-mentioned SOINN. In this case, since there is little noise, the distribution of the input vectors can be learned almost accurately.

However, in noisy input data, the influence of the input vectors caused by the noise becomes large between the regions (clusters) in which the input data is distributed. Figure 15 shows an example of input data in which noise has been added to the input data in Figure 13. The input data shown in Figure 15 has two parts in which the two-dimensional input vectors are distributed in an arc shape, but the boundaries are unclear due to the influence of noise. Figure 16 shows the network structure obtained by learning the input data in Figure 15 using the above-mentioned SOINN. In this case, due to the influence of noise, two clusters that should be separated are connected by an edge caused by the noise and become one cluster. Therefore, it can be seen that the distribution of the input vectors cannot be learned accurately.

In this way, even if clusters that should be separated are not, it may be possible to appropriately separate the clusters by deleting unnecessary edges. For example, a length threshold that specifies the length of the edges to be deleted can be given, and edges longer than the length threshold can be deleted. However, determining an appropriate value for the length threshold requires trial and error to find an appropriate length threshold by repeating the edge deletion process while changing the length threshold and observing the learning results after edge deletion.

For example, even if edges are deleted using the average edge length as the length threshold, there may be cases where the edges are not deleted sufficiently. Figure 17 shows an example of edge deletion. As shown in Figure 17, in the network before edge deletion at the top, edges are deleted using the average edge length as the length threshold, but unnecessary edges may remain as in the central network after edge deletion. In such cases, unnecessary edges can be deleted as in the lower network in Figure 17 by manually adjusting the length threshold to a shorter value and performing edge deletion again. However, this requires manual work, which is time-consuming and inefficient.

In this way, using a single length threshold often makes it impossible to separate clusters, but it is also possible to use a multi-stage edge removal process in which an edge removal process is performed using one length threshold to separate clusters, and then an edge removal process is performed again using a different length threshold. Even in this case, however, the optimal length threshold and the optimal number of times to repeat the edge removal process must be found by trial and error.

The present invention has been made in consideration of the above circumstances, and aims to provide an information processing device, information processing method, and program that can accurately learn the structure of input data by automatically performing edge deletion processing.

In one embodiment, an information processing device is an information processing device that sequentially inputs input vectors and learns the input distribution structure of the input vectors as a network structure in which multiple nodes described by multidimensional vectors and multiple edges connecting two of the nodes are arranged, the information processing device includes a learning processing unit that acquires multiple initial learning results obtained by learning the same input data using multiple unsupervised learning methods, and sequentially selects one initial learning result from the multiple initial learning results, sequentially selects each of the multiple edges included in the selected initial learning result as an edge of interest, and performs a process of deleting an edge longer than the edge of interest from the selected initial learning result and deleting an edge longer than the edge of interest from the selected initial learning result. a separation degree calculation unit that calculates a degree of cluster separation in a case where an edge is deleted from the initial learning result that has been selected, and a degree of cluster separation in a case where an edge is deleted from the initial learning result that has been selected, an edge deletion processing unit that deletes from the selected initial learning result an edge that is equal to or greater than a length threshold that is a length of an edge of interest corresponding to the Mth largest degree of cluster separation among the degrees of cluster separation calculated for the multiple edges, and a learning result pair consisting of two selectable intermediate learning results from a plurality of intermediate learning results that are the multiple initial learning results after the edge deletion by the edge deletion processing unit, a cluster pair consisting of two clusters selected one by one from each of the two intermediate learning results of the selected learning result pair, and ... a distance matrix calculation unit that calculates a distance matrix indicating the distance between a node belonging to one cluster and a node belonging to another cluster; an evaluation index calculation unit that obtains the minimum value of each column and row for each distance matrix and calculates an evaluation index for each distance matrix based on the number of the obtained minimum values that satisfy a predetermined condition; a score calculation unit that calculates, for each cluster of each intermediate learning result, a score indicating the degree of similarity between one cluster included in one intermediate learning result and a cluster of another intermediate learning result, based on the evaluation index of the distance matrix calculated for all the learning result pairs; and a score calculation unit that obtains the minimum value of the scores calculated for each cluster of each intermediate learning result, and calculates the maximum of the obtained multiple minimum values. a termination determination unit that updates the value of M by adding 1 to M if the stroke count is greater than a stroke count threshold, and terminates the process of deleting edges if the stroke count is less than the stroke count threshold; a learning result selection unit that selects a final learning result from a plurality of intermediate learning results based on the scores of each cluster of each intermediate learning result calculated by the score calculation unit when the termination determination unit determines that the process of deleting edges is to be terminated; and a clustering unit that clusters the final learning results. Each time the value of M is updated, the edge deletion processing unit, the distance matrix calculation unit, the score calculation unit, the stroke count calculation unit, and the termination determination unit repeat the process.

In one embodiment of the information processing device, in the above information processing device, the degree of separation of the clusters is preferably 0 when the cluster to which the target edge belongs does not separate into two clusters after the edge is deleted, and has a value other than 0 when the cluster is separated.

In one embodiment of the information processing device, in the above information processing device, it is desirable that the degree of separation of the clusters has a positive or negative value when the cluster to which the target edge belongs is separated into two clusters.

In one embodiment of the information processing device, in the above information processing device, when the cluster to which the target edge belongs is separated into two clusters, it is desirable that the degree of separation of the clusters is larger in the case of a positive value and is smaller in the case of a negative value, the closer the numbers of nodes in the two separated clusters are.

In one embodiment of the information processing device, in the above information processing device, when the cluster to which the target edge belongs is separated into two clusters, it is desirable that the degree of separation of the clusters is such that, when the number of nodes contained in the two separated clusters is greater, the value becomes larger in the case of a positive value, and the value becomes smaller in the case of a negative value.

An information processing device according to an embodiment of the present invention is the above information processing device,
When n _k1 is the number of nodes in cluster k1 that exists when an edge longer than the edge of interest is deleted, and n _k2 is the number of nodes in cluster k2 that exists when an edge longer than the edge of interest is deleted, it is desirable that the degree of separation D of the clusters be defined by the following formula.

In one embodiment of the information processing device, in the above information processing device, the score calculation unit generates an evaluation index matrix composed of evaluation indexes for all pairs between two clusters selected one from each of the two intermediate learning results based on the evaluation indexes calculated for all distance matrices, calculates a score indicating whether a cluster included in one learning result is similar to a cluster of another learning result based on the evaluation indexes included in the evaluation index matrix, and generates a score matrix including scores for clusters belonging to all learning results, and it is desirable that the learning result selection unit selects a final learning result from the multiple learning results based on the score matrix.

In one embodiment of the information processing device, in the above information processing device, it is desirable that the evaluation index calculation unit calculates the average distance between nodes belonging to each of the two clusters, calculates the average of the two average distances calculated, and calculates an evaluation index for each distance matrix based on the number of minimum values in each column and each row of each distance matrix that are equal to or greater than the average value.

In one embodiment of the information processing device, in the above information processing device, it is desirable that the evaluation index is a value obtained by dividing the number of minimum values in each column and each row of each distance matrix that are greater than or equal to the average value by the total number of nodes belonging to the two clusters.

In one embodiment of the information processing device, in the above information processing device, it is desirable that the score calculation unit compares each evaluation index included in the evaluation index matrix with a threshold value, assigns a score based on the comparison result, and calculates a total score for each cluster.

In one embodiment of the information processing device, in the above information processing device, it is desirable that the learning result selection unit obtains the minimum value among the total scores of the clusters belonging to each intermediate learning result, and selects the intermediate learning result corresponding to the maximum value among the obtained minimum values.

In one embodiment of the information processing method, an input vector is input sequentially, and an input distribution structure of the input vector is learned as a network structure in which a plurality of nodes described by a multidimensional vector and a plurality of edges connecting two of the nodes are arranged, in the information processing method, a plurality of initial learning results obtained by learning the same input data using a plurality of unsupervised learning methods are obtained, one initial learning result is selected from the plurality of initial learning results in order, one cluster is selected from the one selected initial learning result in order, each of a plurality of edges included in the selected cluster is selected in order as an edge of interest, the degree of separation of the cluster is calculated in a case where an edge longer than the edge of interest is deleted from the network structure, and in a case where an edge having a length equal to or longer than the edge of interest is deleted from the network structure, and an edge having a length equal to or longer than the edge of interest is deleted from the selected cluster based on the degree of cluster separation calculated for each edge of interest, an edge having a length equal to or greater than a length threshold, which is the length of the edge of interest corresponding to the Mth largest degree of cluster separation, is selected from a plurality of intermediate learning results that are the plurality of initial learning results after the edge deletion, a learning result pair consisting of two selectable intermediate learning results is selected, a cluster pair consisting of two clusters selected one from each of the two selected intermediate learning results is selected, and a cluster pair consisting of the selectable clusters is selected from the plurality of intermediate learning results after the edge deletion. For all raster pairs, a distance matrix indicating the distance between a node belonging to one cluster and a node belonging to the other cluster is calculated, the minimum value of each column and row of each distance matrix is obtained, and an evaluation index for each distance matrix is calculated based on the number of the obtained minimum values that satisfy a predetermined condition, and a score indicating the degree of similarity between a cluster included in one intermediate learning result and a cluster of another intermediate learning result is calculated for each cluster of each intermediate learning result based on the evaluation index of the distance matrix calculated for all the learning result pairs, and the minimum of the scores calculated for each cluster of each intermediate learning result is calculated. the distance matrix calculation, ...

In one embodiment, a program causes a computer to sequentially input an input vector and learn the input distribution structure of the input vector as a network structure in which a plurality of nodes described by a multidimensional vector and a plurality of edges connecting two of the nodes are arranged, the program includes a process of acquiring a plurality of initial learning results obtained by learning the same input data using a plurality of unsupervised learning methods, a process of sequentially selecting one initial learning result from the plurality of initial learning results and sequentially selecting one cluster from the selected one initial learning result, and a process of sequentially selecting each of a plurality of edges included in the selected cluster as an edge of interest and selecting an edge longer than the edge of interest. a process of calculating a degree of cluster separation in a case where an edge having a length equal to or greater than the edge of interest is deleted from the network structure and a process of deleting an edge having a length equal to or greater than a length threshold, which is the length of the edge of interest corresponding to the Mth largest degree of cluster separation, from the selected clusters based on the degree of cluster separation calculated for each edge of interest; a process of selecting a learning result pair consisting of two selectable intermediate learning results from a plurality of intermediate learning results which are the plurality of initial learning results after the edge deletion, selecting a cluster pair consisting of two clusters selected one from each of the two selected intermediate learning results, and selecting one of the clusters for each of the selectable cluster pairs. A process of calculating a distance matrix indicating the distance between a node belonging to a raster and a node belonging to another cluster, a process of obtaining a minimum value for each column and row of each distance matrix, and calculating an evaluation index for each distance matrix based on the number of the obtained minimum values that satisfy a predetermined condition, a process of calculating, for each cluster of each intermediate learning result, a score indicating the degree of similarity between one cluster included in one intermediate learning result and a cluster of another intermediate learning result, based on the evaluation index of the distance matrix calculated for all the learning result pairs, and a process of obtaining a minimum value of the scores calculated for each cluster of each intermediate learning result, and unifying the maximum value of the obtained multiple minimum values. a process of calculating a distance matrix based on the score of each cluster of each intermediate learning result, a process of adding 1 to M to update the value of M if the stroke count is greater than a stroke count threshold, and terminating the process of deleting edges if the stroke count is less than the stroke count threshold; and a process of selecting a final learning result from a plurality of intermediate learning results based on the calculated scores of each cluster of each intermediate learning result if it is determined that the process of deleting edges is to be terminated; and a process of clustering the final learning results. Each time the value of M is updated, the process of deleting edges, the process of calculating the distance matrix, the process of calculating the score, the process of calculating the stroke count, and the process of determining the termination are repeated.

According to the present invention, it is possible to provide an information processing device, an information processing method and a program that can accurately learn the structure of input data by automatically performing edge deletion processing.

FIG. 1 is a diagram illustrating an example of a system configuration for realizing an information processing device according to a first embodiment. FIG. 1 is a diagram illustrating a schematic configuration of an information processing device according to a first embodiment. 4 is a flowchart of a process in the information processing device according to the first embodiment; 4 is a flowchart of a process in the information processing device according to the first embodiment; This figure shows a schematic diagram of a first example of the change in cluster between deleting an edge that is longer than the edge (case 1) and deleting an edge that is longer than the edge (case 2). This figure shows a schematic diagram of a second example of the change in cluster between deleting an edge that is longer than the edge (case 1) and deleting an edge that is longer than the edge (case 2). FIG. 13 is a diagram illustrating an example in which a cluster diversity change amount dS is 0. FIG. 13 is a diagram illustrating an example of a case where the cluster diversity change amount dS is not 0. FIG. 13 is a diagram showing an overview of edge deletion in the first embodiment. FIG. 13 is a diagram showing an example of input data used for edge deletion in the first embodiment. FIG. 11 is a diagram showing a network structure when edge deletion processing is performed on the input data in FIG. 10 . FIG. 13 is a diagram showing an example of a network and pixel count obtained when a two-stage edge deletion process is performed. FIG. 13 is a diagram illustrating an example of input data with little noise. FIG. 14 is a diagram showing a network structure obtained by learning the input data of FIG. 13 using the above-mentioned SOINN. FIG. 14 is a diagram showing an example of input data obtained by adding noise to the input data shown in FIG. 13; FIG. 16 is a diagram showing a network structure obtained by learning the input data of FIG. 15 using the above-mentioned SOINN. FIG. 13 is a diagram illustrating an example of deleting an edge.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings. In each drawing, the same elements are given the same reference numerals, and duplicate explanations will be omitted as necessary.

First embodiment
FIG. 1 is a diagram showing an example of a system configuration for realizing an information processing device according to the first embodiment. The information processing device 100 can be realized by a computer 1000 such as a dedicated computer or a personal computer (PC). However, the computer does not need to be physically single, and may be multiple when performing distributed processing. As shown in FIG. 1, the computer 1000 has a CPU (Central Processing Unit) 1001, a ROM (Read Only Memory) 1002, and a RAM (Random Access Memory) 1003, which are connected to each other via a bus 1004. Note that an OS software for operating the computer will not be described, but it is assumed that the computer that constructs this information processing device also has such software.

An input/output interface 1005 is also connected to the bus 1004. The input/output interface 1005 is connected to, for example, an input unit 1006 including a keyboard, a mouse, a sensor, etc., a display including a CRT, an LCD, etc., an output unit 1007 including a headphone, a speaker, etc., a storage unit 1008 including a hard disk, etc., and a communication unit 1009 including a modem, a terminal adapter, etc.

The CPU 1001 executes various processes according to various programs stored in the ROM 1002 or various programs loaded from the storage unit 1008 to the RAM 1003, and in this embodiment, for example, executes the processes of each part of the information processing device 100 described later. A GPU (Graphics Processing Unit) may be provided to execute various processes according to various programs stored in the ROM 1002 or various programs loaded from the storage unit 1008 to the RAM 1003, as with the CPU 1001, and in this embodiment, for example, executes the processes of each part of the information processing device 100 described later. The GPU is suitable for applications in which standardized processes are performed in parallel, and by applying it to processes in a neural network described later, it is possible to improve the processing speed compared to the CPU 1001. The RAM 1003 also appropriately stores data necessary for the CPU 1001 and the GPU to execute various processes.

The communication unit 1009 performs communication processing, for example, via the Internet (not shown), transmits data provided by the CPU 1001, and outputs data received from a communication partner to the CPU 1001, RAM 1003, and memory unit 1008. The memory unit 1008 communicates with the CPU 1001 and stores and erases information. The communication unit 1009 also performs communication processing of analog or digital signals with other devices.

The input/output interface 1005 is also connected to a drive 1010 as necessary, and, for example, a magnetic disk 1011, an optical disk 1012, a flexible disk 1013, or a semiconductor memory 1014 is appropriately attached, and computer programs read from them are installed in the memory unit 1008 as necessary.

Next, each process in the information processing device 100 according to the present embodiment will be described. The information processing device 100 has a non-hierarchical neural network in which nodes described by multidimensional vectors are arranged, and the neural network is stored in a storage unit such as the RAM 1003.

The neural network in this embodiment is a self-replicating neural network that inputs an input vector into the neural network and automatically increases the number of nodes placed in the neural network based on the input vector. By using a self-replicating neural network, the number of nodes can be automatically increased, so it is not limited to stationary environments in which input vectors are given randomly from the input vector space, but can also be used in non-stationary environments in which, for example, the class to which the input vector belongs is switched at regular intervals and an input vector is given randomly from the class after the switch.

The neural network in this embodiment has a non-hierarchical structure. By adopting a non-hierarchical structure, additional learning can be performed without specifying the timing to start learning in other layers. In other words, additional learning can be performed online.

The input data is input as a multidimensional input vector belonging to an arbitrary class. For example, the input vector is stored in a temporary storage unit (e.g., RAM 1003) and is input sequentially to the neural network stored in the temporary storage unit.

In the following, for simplicity, the neural network in this embodiment will also be referred to simply as the network.

The information processing device 100 according to the first embodiment will be specifically described below. The information processing device 100 learns (clusters) input data including multiple multidimensional vectors as data elements using an unsupervised learning method, for example, the various SOINN methods described above, and obtains a learning result represented as a network consisting of multiple nodes and edges connecting two nodes. The information processing device 100 then automatically determines a length threshold that serves as a criterion for edge deletion, and can obtain a learning result having a network with a more suitable structure by deleting edges that are equal to or greater than this length threshold.

Figure 2 shows a schematic configuration of the information processing device 100 according to the first embodiment. The information processing device 100 has a learning processing unit 1, a separation degree calculation unit 2, an edge deletion processing unit 3, a distance matrix calculation unit 4, an evaluation index calculation unit 5, a score calculation unit 6, a pixel number calculation unit 7, a termination determination unit 8, a learning result selection unit 9, and a clustering unit 10. Note that, on the hardware side, the functional configuration shown in Figure 2 is realized by cooperation between software and hardware resources such as the above-mentioned CPU 1001.

The learning processing unit 1 learns multiple input vectors, for example using the above-mentioned E-SOINN or LB-SOINN, to obtain a network structure composed of nodes and edges. In this embodiment, the learning processing unit 1 is configured to learn (cluster) input data including multiple multidimensional vectors under multiple different unsupervised learning conditions, to obtain multiple learning results with different network structures. Hereinafter, the multiple learning results with different network structures obtained by the learning processing unit 1 are referred to as multiple initial learning results.

The separation degree calculation unit 2 calculates the degree to which the clusters are separated by deleting an edge of a selected cluster.

The edge deletion processing unit 3 determines a length threshold to be used for edge deletion based on the calculated degree of cluster separation, and performs a process of deleting edges in the selected cluster based on the determined length threshold. Note that edge deletion can be performed all at once after the learning results are obtained, so it is a relatively simple process and can be easily implemented. In addition, it can be applied to any network consisting of nodes and edges, regardless of the learning method. Note that, hereinafter, the network structure obtained after deleting edges from the initial learning result is referred to as the intermediate learning result.

After the edge deletion process for all clusters included in all initial learning results has been completed and multiple intermediate learning results have been obtained, the distance matrix calculation unit 4 selects two clusters from each of two different intermediate learning results and calculates a distance matrix whose components are the distances between the nodes included therein.

The evaluation index calculation unit 5 calculates an evaluation index indicating the similarity between the two selected clusters based on the distance matrix. After calculating the evaluation indexes for all pairs of two clusters selectable from the two different selected intermediate learning results, the evaluation index calculation unit 5 may output an evaluation index matrix whose components are the cluster similarities between the two different intermediate learning results.

The score calculation unit 6 calculates a score indicating the similarity between the two selected different intermediate learning results based on the evaluation matrix index. After calculating the scores for all pairs of two selectable different intermediate learning results, the score calculation unit 6 may output a score matrix whose components are the scores of the two different intermediate learning results.

The stroke ratio calculation unit 7 calculates a stroke ratio indicating the similarity between multiple intermediate learning results.

The termination determination unit 8 determines whether to repeat the edge removal process based on the calculated pixel count.

When the learning result selection unit 9 determines that the edge deletion process is completed, it selects one intermediate learning result from the multiple intermediate learning results after the edge deletion process in accordance with predetermined conditions.

The clustering unit 10 clusters one selected initial learning result and outputs the final learning result.

Below, the processing performed by the information processing device 100 is explained in detail. Figures 3 and 4 show a flowchart of the processing in the information processing device 100 according to the first embodiment.

Step SA1
The learning processing unit 1 performs learning of the input data through the following steps SA11 and SA12.

Step SA11
The learning processing unit 1 reads input data. The input data is stored in, for example, the above-mentioned RAM 1003 or the storage unit 1008, and the learning processing unit 1 can read the input data as needed.

Step SA12
The learning processing unit 1 sequentially inputs and learns multidimensional input vectors, which are elements of input data, to obtain a learning result having a network structure composed of nodes and edges connecting the nodes. In this embodiment, the learning processing unit 1 obtains a plurality of different initial learning results by learning the same input data under a plurality of different unsupervised learning conditions. The plurality of different unsupervised learning conditions may be the same unsupervised learning method with parameters used for learning changed, or may be different unsupervised learning methods, or may be a combination of both. As described above, the learning result obtained by the learning processing unit 1 is referred to as the initial learning result. Needless to say, the network structures of the plurality of initial learning results obtained by learning under a plurality of different unsupervised learning conditions are different from each other.

Step SA2
The separation degree calculation unit 2 calculates the amount of change in cluster diversity, which is the degree of cluster separation, by the following steps SA21 to SA27.

Step SA21
The degree of separation calculation unit 2 determines whether any of the multiple initial learning results has not yet been selected as the selected learning result SR.

Step SA22
When there are initial learning results that have not been selected as the selected learning result SR, the separation degree calculation unit 2 selects one of the initial learning results as the selected learning result SR.

Step SA23
The separation degree calculation unit 2 determines whether or not there is any side that has not been selected as the side of interest among the sides included in the selection learning result SR. If there is no side that has not been selected as the side of interest, the process returns to step SA21.

Step SA24
If there is an edge that has not been selected as the edge of interest among the edges included in the selected cluster, the separation degree calculation unit 2 selects one edge from among the edges as the edge of interest.

Step SA25
The separation degree calculation unit 2 calculates a cluster diversity amount S1 when edges longer than the edge of interest are removed, and a cluster diversity amount S2 when edges the length of which is equal to or longer than the edge of interest are removed.

Next, the degree of cluster separation used in determining the length threshold in this embodiment will be described. When determining the length threshold, it is desirable to select the length of the shortest edge among the edges connecting the clusters as the length threshold. In other words, it is desirable to select the length of the edge deleted when the clusters are first separated when the edges between the clusters are deleted in order of length as the length threshold. If it can be set in this way, the clusters can be separated without any edges remaining between the clusters and without needlessly deleting edges within the clusters. However, even if edges of noise nodes or noise clusters (clusters formed by gathering noise nodes) are deleted, it is recognized as a kind of cluster separation, but the length threshold that causes this kind of cluster separation cannot be said to be appropriate. Therefore, when determining the length threshold, it is necessary to take into account the state of the clusters formed by separation (especially the number of nodes belonging to the cluster and the ratio of divided nodes).

Therefore, in this embodiment, the degree of cluster separation (in this embodiment, the amount of change in cluster diversity, described later) is introduced to determine whether clusters will separate and whether the separated cluster is a noise cluster only when an edge longer than the edge length is deleted. This makes it possible to delete edges using an appropriate length threshold determined based on the degree of cluster separation.

In this embodiment, the degree of cluster separation is a value that each edge has, and when comparing the case where an edge longer than that edge is deleted (referred to as case 1) with the case where an edge longer than that edge is deleted (referred to as case 2), if the number of clusters is increased in case 2 compared to case 1, it is an index that has the property of taking a finite value in the first direction, and taking 0 if there is no change.

Below, the change in clusters when comparing Case 1 and Case 2 will be explained with reference to the figures. Figure 5 shows a schematic first example of the change in clusters when an edge longer than a certain edge is deleted (Case 1) and when an edge longer than that edge is deleted (Case 2). In this example, edge E2 is the edge of interest when deleting edges, and in both Cases 1 and 2, the cluster before the edge deletion remains as a single cluster without being separated even though the number of edges is reduced. In this embodiment, as described above, the degree of cluster separation at this time is 0.

Next, Figure 6 shows a second example of the change in clusters between deleting an edge longer than the edge (Case 1) and deleting an edge longer than the edge (Case 2). In this example, edge E1 is the edge of interest and is deleted. In Case 1, the cluster before the edge deletion remains as one cluster without separation even though the number of edges is reduced, whereas in Case 2 it is separated into two clusters. In this embodiment, as described above, the degree of cluster separation at this time is a finite value in the first direction.

In both Figs. 5 and 6, the difference between the edge connection structure in case 1 and the edge connection structure in case 2 is whether the edge of interest remains without being deleted. It can be understood that there are two cluster change modes: a non-separation mode (Fig. 5) in which the original cluster does not separate even if the edge of interest is deleted, and a separation mode (Fig. 6) in which the original cluster is separated into two new clusters by deleting the edge of interest. As described above, in the non-separation mode, the cluster separation degree of the edge of interest (edge E2 in Fig. 5) is 0, and in the separation mode (edge E1 in Fig. 6), the cluster separation degree is a finite value in the first direction. Therefore, by obtaining the cluster separation degree for a certain edge of interest, it is possible to determine whether the original cluster will not separate (non-separation mode) or will separate into two clusters by deleting the edge of interest.

ここで、ｎ_ｋ１は注目する辺よりも長い辺を削除した場合（場合１）に存在するクラスタｋ１のノード数であり、右辺第１項（ｎ_ｋ１を含む項）は全てのクラスタｋ１に対する総和を意味する。ｎ_ｋ２は注目する辺以上の長さの辺を削除した場合（場合２）に存在するクラスタｋ２のノード数であり、右辺第２項（ｎ_ｋ２を含む項）は全てのクラスタｋ２に対する総和を意味する。ここでは、クラスタ分離度合いＤを式［２］のように定義したが、以下の式［３］のように定義しても同じ意味である。

ここで、ｎ_ｊ０は注目する辺よりも長い辺を削除した場合（場合１）に、注目する辺が属するクラスタ（古クラスタ）に含まれるノード数である。ｎ_ｊは注目する辺以上の長さの辺を削除した場合（場合２）に、古クラスタが分離されて生じた２つクラスタのそれぞれ（クラスタｊ）のノード数、又は、分離しない場合では古クラスタのノード数である。 In this embodiment, the cluster separation degree D is defined as follows:

Here, n _k1 is the number of nodes in cluster k1 that exists when an edge longer than the edge of interest is deleted (case 1), and the first term on the right hand side (term including n _k1 ) means the total for all clusters k1. n _k2 is the number of nodes in cluster k2 that exists when an edge longer than the edge of interest is deleted (case 2), and the second term on the right hand side (term including n _k2 ) means the total for all clusters k2. Here, the degree of cluster separation D is defined as in formula [2], but it can also be defined as in the following formula [3] with the same meaning.

Here, _nj0 is the number of nodes included in the cluster (old cluster) to which the edge of interest belongs when an edge longer than the edge of interest is deleted (case 1), and _nj is the number of nodes in each of the two clusters (cluster j) that are generated when the old cluster is separated when an edge longer than the edge of interest is deleted (case 2), or the number of nodes in the old cluster when no separation occurs.

As described above, the degree of cluster separation shown in equations [2] and [3] is 0 if the number of clusters does not increase, and takes a finite value in the first direction (a positive value in the configuration of this embodiment) if the number of clusters increases.

This makes it possible to detect which edge length should be used as the threshold to separate the clusters. As described below, the degree of cluster separation has the property that when the corresponding pre-separation cluster separates, the closer the node ratios of new cluster 1 and new cluster 2 are, the greater the degree of cluster separation in the first direction (positive direction in the configuration of this embodiment), and the greater the number of nodes in the old cluster, the greater the degree of cluster separation in the first direction (positive direction in the configuration of this embodiment). Therefore, based on the magnitude of the degree of cluster separation, it is possible to detect the length threshold at which the original cluster separates into a suitable cluster.

Equations [2] and [3] are merely examples of the degree of cluster separation, and a value obtained by multiplying the value defined by equations [2] and [3] by a predetermined value may be used as the degree of cluster separation. Note that the degree of cluster separation may be defined using other functions that behave in a similar manner, other than functions such as equations [2] and [3].

When clusters are separated, it is desirable that the value of the cluster separation degree takes a finite value in the first direction (a positive value in the configuration of this embodiment) regardless of how the cluster is divided, but when the cluster is divided into a small cluster and a large cluster, it does not have to take a finite value in the first direction (it may take 0 or a negative value in the configuration of this embodiment). For example, the cluster separation degree may be defined as follows using natural logarithms:

In formula [4], if a cluster with 100 nodes is assumed to be divided into a cluster with 99 nodes and a cluster with 1 node, the degree of cluster separation is -0.010..., a negative value. If the cluster is divided into two clusters at a ratio other than this ratio, the degree of cluster separation is a positive value. A cluster with 100 nodes is divided into a cluster with 99 nodes and a cluster with 1 node when nodes generated by noise or the like are divided into different clusters, and such division is considered to be insignificant. Therefore, it can be considered that the cluster division can be appropriately expressed using the degree of cluster separation defined in formula [4].

In the above, the first direction is assumed to be the positive direction, but the first direction may be the negative direction. For example, the value obtained by multiplying the right side of equation [4] by a negative number may be used as the degree of cluster separation.

式［５］において、ｎ_ＡＬＬは全ノード数、Ｎ_ｃはクラスタの数、ｋはクラスタのラベルであり１以上Ｎ_ｃ以下の整数、ｎ_ｋはクラスタｋのノード数である。 In this embodiment, the degree of cluster separation may be calculated as a cluster diversity change amount dS, which is a difference in the cluster diversity amount S defined by the following equation [5].

In equation [5], _nALL is the total number of nodes, _Nc is the number of clusters, k is the label of the cluster and is an integer between 1 and _Nc , and _nk is the number of nodes in cluster k.

Using the cluster diversity S defined as in equation [5], for each edge, the cluster diversity is calculated when an edge longer than that edge is deleted (case 1) and when an edge longer than that edge is deleted (case 2), and the difference dS is calculated, which is the same as equation [2].

In the following, in this embodiment, for ease of understanding, an example will be described in which the cluster diversity is calculated in both cases 1 and 2 as the degree of cluster separation, and the cluster diversity change amount dS, which is the difference between them, is calculated. Needless to say, the following example is merely one example, and the degree of cluster separation may be calculated directly without explicitly defining the cluster diversity amount as in equation [5].

Step SA26
The separation degree calculation unit 2 calculates the above-mentioned cluster diversity change amount dS=S2-S1 as the cluster separation degree, and returns the process to step SA23.

Step SA27
If it is determined in step SA21 that there is no initial learning result that has not been selected as the selected learning result SR among the multiple initial learning results, the separation degree calculation unit 2 resets the learning results and the edge selection history, and then proceeds to step SA3.

Here, we will briefly explain the cluster diversity change amount dS. Figure 7 shows a schematic example of a case where the cluster diversity change amount dS is 0. Figure 7 shows an example of a cluster having a total of 12 nodes, 3 vertically and 4 horizontally, with these 12 nodes connected in a lattice shape by edges. The three edges extending horizontally in the center are designated E1 to E3 from the bottom, with the length of the edges increasing in the order of edge E1, edge E2, and edge E3.

In FIG. 7, when the edge of interest is edge E2, if the cluster diversity amount S1 is calculated with edge E3 removed, S1 = 12 log(12) - 12 log(12) = 0. Also, when the cluster diversity amount S2 is calculated with edges E2 and E3 removed, S2 = 12 log(12) - 12 log(12) = 0. In this case, the cluster diversity change amount dS is S2 - S1 = 0, because the clusters were not separated when the edge of interest is E2. As shown in FIG. 7, it can be seen that when the edge of interest is E2, the clusters are not separated from case 1 to case 2. Therefore, the cluster diversity amount does not change. As described above, the cluster diversity change amount, which is the degree of cluster separation, is 0 if the number of clusters does not change.

Next, FIG. 8 shows a schematic example of a case where the cluster diversity change amount dS is not 0. The cluster in FIG. 8 is the same as that in FIG. 7. In FIG. 8, when the edge of interest is edge E1, if the cluster diversity amount S1 is calculated with edges E2 and E3 removed, S1 = 12 log (12) - 12 log (12) = 0. In contrast, when the cluster diversity amount S2 is calculated with edges E1 to E3 removed, S2 = 12 log (12) - 6 log (6) - 6 log (6) = 8.137. In this case, the cluster diversity change amount dS is S2 - S1 = 8.317, but this is because the cluster is separated when the edge of interest is E1. As shown in FIG. 8, when the edge of interest is E1, it can be seen that the cluster is separated from case 1 to case 2. Therefore, the cluster diversity amount also changes. As described above, the cluster diversity change amount, which is the degree of cluster separation, takes a finite value in the first direction (positive direction in this embodiment) when the number of clusters changes.

In this way, by calculating the cluster diversity change amount dS for the edge of interest and checking whether the cluster diversity change amount dS is a value other than 0, it is possible to determine whether the cluster will be divided.

The cluster diversity change amount dS has the property that it is a large value when a cluster is divided evenly and a small value when it is divided unequally. For example, when a cluster with 100 nodes is divided into a cluster with 10 nodes and a cluster with 90 nodes, the cluster diversity change amount dS is 32.5. In contrast, when a cluster with 100 nodes is divided into two clusters with 50 nodes, the cluster diversity change amount dS is 69.3. In this way, it can be seen that even when clusters with the same number of nodes are divided, the cluster diversity change amount dS is larger when the number of divided nodes is equal.

Furthermore, the cluster diversity change amount dS has the property that the greater the number of nodes belonging to each cluster, the larger the value, even if the number of clusters after splitting is the same. If we imagine splitting a cluster with two nodes into two clusters with one node, the number of nodes in the two clusters after splitting will be the same, but the cluster diversity change amount dS will be a small value of 1.39. In this way, when the number of nodes in the original cluster is small, the cluster diversity change amount dS will be a small value. In this case, it can be interpreted that a small cluster created by noise or the like has been split.

Based on the above properties of the cluster diversity change amount dS, by specifying the length of the edge to be deleted based on the magnitude of the value of the cluster diversity change amount dS, it is possible to preferably detect cases in which the number of nodes is large and the clusters are divided into approximately equal clusters, and to eliminate cases in which the number of nodes is unbalanced and the number of nodes in the cluster before division is small.

Step SA3
The edge deletion processing unit 3 deletes a predetermined edge from each learning result by the following steps SA31 to SA37.

Step SA31
The edge deletion processor 3 sets the initial value of the edge deletion level M, which indicates the upper limit of the number of times the edge deletion process is repeated, to "0" (that is, M=0).

Step SA32
The edge deletion processing unit 3 determines whether there is any initial learning result that has not yet been selected as the selected learning result SR among the multiple initial learning results. If there is no initial learning result that has not yet been selected as the selected learning result SR among the multiple initial learning results, the process proceeds to step SA37.

Step SA33
If there is an initial learning result that has not been selected as the selected learning result SR, the edge deletion processing unit 3
One of these initial learning results is selected as a selected learning result SR.

Step SA34
The edge deletion processing unit 3 determines whether there is an Mth largest value among the cluster diversity change amounts dS calculated for each edge of the selective learning result SR. For example, the edge deletion processing unit 3 may sort the calculated cluster diversity change amounts dS in descending order and determine whether there is an Mth cluster diversity change amount dS. If there is no Mth cluster diversity change amount dS, the edge deletion processing unit 3 returns the process to step SA32.

Step SA35
The edge deletion processing unit 3 selects the Mth largest cluster diversity change amount dS among the cluster diversity change amounts dS calculated for each edge of the selection learning result SR, and determines the length of the edge of interest corresponding to the selected cluster diversity change amount dS as the length threshold _LTH . Note that M=0 is executed so that no edges are deleted. For example, an edge length longer than the lengths of all edges is determined as the threshold _LTH .

Step SA36
The edge deletion processing unit 3 compares the length of each edge included in the selected learning result SR with the length threshold _LTH , and deletes edges whose lengths are equal to or greater than the length threshold _LTH from the selected learning result SR. Then, the process returns to step SA32.

As mentioned above, the network structure obtained after the above-mentioned edges are deleted from the initial learning result is called the intermediate learning result.

The effect of the edge deletion process according to this embodiment will be considered below. Fig. 9 shows an overview of edge deletion in the first embodiment. First, a length threshold _LTH1 for the maximum cluster diversity change amount dS1 is set, and based on this, edges of the cluster to which the target edge EA1 belongs that have a length equal to or greater than the threshold _LTH1 are deleted (first edge deletion). As a result, the original cluster is separated into two clusters, a left one and a right one.

Next, a length threshold _LTH2 corresponding to the cluster diversity change amount dS2 next to the maximum cluster diversity change amount dS1 is set, and among the edges of the left cluster to which the target edge EA2 belongs, edges having a length equal to or greater than the threshold _LTH2 are deleted (second edge deletion). As a result, the left cluster is further divided into two clusters.

Next, a length threshold _LTH3 corresponding to the cluster diversity change amount dS3 that is the next largest after the cluster diversity change amount dS2 is set, and among the edges of the right cluster to which the target edge EA3 belongs, edges with a length equal to or greater than the threshold _LTH3 are deleted (third edge deletion). As a result, the right cluster is further divided into two clusters.

Here, an example of edge deletion according to this embodiment will be described. Figure 10 shows an example of input data used for edge deletion in embodiment 1. The input data in this embodiment is distributed in six clusters, with an area where three clusters are close to each other and an area where two clusters are close to each other, with the boundaries being unclear due to noise.

Figure 11 shows the network structure when edge deletion processing is performed on the input data in Figure 10. Before edge deletion, nodes corresponding to nearby clusters are connected by edges, and it can be seen that the clusters cannot be separated. Furthermore, a cluster in an area where three clusters are close to each other and a cluster in an area where two nearby clusters are close to each other are connected by a single edge. In contrast, after edge deletion, edges caused by noise have been properly deleted, and it can be seen that the six clusters have been separated.

As described above, this configuration allows for more appropriate edge deletion processing for each cluster to which the edge of interest belongs by deleting edges in stages. This makes it possible to suppress unnecessary edge deletion processing and learn the distribution of input vectors more accurately.

Step SA37
If it is determined in step SA32 that there is no initial learning result that has not yet been selected as the selected learning result SR among the multiple initial learning results or there is no initial learning result that has not yet been selected as the selected learning result SR among the multiple learning results, the selection history of the initial learning results performed by the edge deletion processing unit 3 is reset. Then, the process proceeds to step SA4.

Step SA4
Distance matrix calculation unit 4 selects a pair of two clusters from the pair of intermediate learning results in which two edges have been deleted, and calculates a distance matrix for the two selected clusters, in the following steps SA41 to SA45.

Step SA41
The distance matrix calculation unit 4 determines whether there is any pair of two intermediate learning results that has not yet been selected as a processing target, among the pairs of two intermediate learning results that have been arbitrarily selected from the intermediate learning results. If there is no pair of intermediate learning results that has not yet been selected, the process proceeds to step SA8.

Step SA42
If there are any unselected intermediate learning result pairs, the distance matrix calculation unit 4 selects one intermediate learning result pair from among them. Hereinafter, the pair of intermediate learning results selected here is referred to as a selected learning result pair, and the intermediate learning results included in the selected learning result pair are SA and SB.

Step SA43
The distance matrix calculation unit 4 determines whether there is any pair of clusters that has not yet been selected as a processing target among the pairs of clusters that are each made up of one cluster arbitrarily selected from the intermediate learning result SA of the selected learning result pair and one cluster arbitrarily selected from the intermediate learning result SB. If there is no pair of clusters that has not yet been selected, the process proceeds to step SA6.

Step SA44
If there are unselected cluster pairs, the distance matrix calculation unit 4 selects one cluster pair from among them. Specifically, the distance matrix calculation unit 4 selects one cluster pair including a cluster A arbitrarily selected from p clusters CA1 to CAp (p is an integer equal to or greater than 1) included in the intermediate learning result SA from which edges have been deleted, and a cluster B arbitrarily selected from q clusters CB1 to CBq (q is an integer equal to or greater than 1) included in the intermediate learning result SB from which edges have been deleted. Hereinafter, the cluster pair selected here is referred to as a selected cluster pair.

Step SA45
The distance matrix calculation unit 4 calculates the distances d aibj between all pairs of nodes a1 to am (ai, 1≦i≦m) included in cluster A and nodes b1 to bn (bj, 1≦j≦n) included in cluster B, and calculates a distance _matrix D with m rows and n columns for the selected cluster pairs.

Step SA5
After step SA45, the evaluation index calculation unit 5 calculates an evaluation index indicating the degree of similarity between the two clusters of the selected cluster pair through the following steps SA51 to SA54.

Step SA51
The evaluation index calculation unit 5 obtains the minimum value min _ai (i.e., min _a1 to min _am ) for each row (d _aib1 to d _aibn ) of the distance matrix D, and obtains the minimum value minb _j (i.e., min _b1 to min _bn ) for each column (d _a1bj to d _ambj ) of the distance matrix D.

式［７］において、ｄ_ｉはノードｉとノードｉの属するクラスタに含まれるノードとの距離の最小値である。
なお、式［７］のｄ_ｍｅａｎは例であり、例えば以下の式［８］のように定義してもよい。

Step SA52
The evaluation index calculation unit 5 calculates the average distance _dmean between nodes belonging to the same cluster. Since _dmean is the average distance between nodes identified as being in the same cluster, if the distance is greater than this average value, the nodes are identified as different nodes, and if the distance is shorter than this average value, the nodes are identified as being in the same cluster. For example, _dmean can be written as follows:

In formula [7], d _i is the minimum distance between node i and the nodes contained in the cluster to which node i belongs.
Note that d _mean in equation [7] is an example, and may be defined as, for example, the following equation [8].

Furthermore, d _mean may be set to the larger or smaller value of the values shown in the following expressions [9] and [10].

Furthermore, separate d _mean may be prepared for the minimum values min _a1 to min _am of each row and the minimum values min _b1 to min _bn of each column, and used accordingly. For the minimum values min _a1 to min _am of each row, d _mean calculated only for cluster A may be used, for example, as shown in formula [11]. For the minimum values min _b1 to min _bn of each column, d _mean calculated only for cluster B may be used, for example, as shown in formula [12].

In the above, a network including a plurality of nodes has been described, but when input data is learned by SOINN or the like, the network includes a plurality of nodes and a plurality of edges connecting two nodes. In this way, when edges exist between nodes, it is desirable to use the average length of edges belonging to the same cluster as d _mean . Since edges represent the relationship between nodes and edge lengths represent their similarity, by using edges, it is possible to prevent the distance to a node that happens to exist in the vicinity due to the influence of noise from being used in the calculation of d _mean . In addition, in this embodiment, the arithmetic mean (arithmetic mean) is used as the average length, but this is not limited as long as the central tendency of the distance distribution between neighboring nodes can be expressed numerically. For example, another average index such as the square mean, the geometric mean, or the harmonic mean may be used as the average length, or another statistical representative value such as the median or the mode may be used. In the following, the term "average distance" is used to include the average index and statistical representative value described above in addition to the arithmetic mean.

Step SA53
The evaluation index calculation unit 5 counts the number NUMa of the minimum values min _a1 to min _am in each row that are equal to or greater than the average distance d _mean , and counts the number NUMb of the minimum values min _b1 to min _bn in each column that are equal to or greater than the average distance d _mean .

Step SA54
The evaluation index calculation unit 5 divides the sum of the acquired numbers NUMa and NUMb by the total number of nodes in clusters A and B (m+n) to calculate an evaluation index ES.

Here, the number of nodes that are not similar between the two clusters is detected by counting the number of the minimum values that are equal to or greater than the average value _dmean . In addition, the ratio of the number of nodes that are not similar to the total number of nodes is calculated by dividing the number of nodes that are not similar in the formula [13] by the total number of nodes in the two clusters. In other words, the evaluation index ES can be said to be a value that represents the dissimilarity, where a large value indicates that the two clusters are not similar, and a small value indicates that the two clusters are similar.

In this embodiment, the evaluation index calculation unit 5 performs this for all pairs of any one of the p clusters CA1 to CAp included in the intermediate learning result SA and any one of the q clusters CB1 to CBq included in the intermediate learning result SB. Then, the evaluation index calculation unit 5 calculates the evaluation index for all pairs of two clusters.

Step SA6: Generating an Evaluation Index Matrix If it is determined in step SA43 that there is no pair of clusters that has not yet been selected as a processing target among the selected learning result pairs, the evaluation index calculation unit 5 generates an evaluation index matrix EM with p rows and q columns. That is, the row numbers of the evaluation index matrix EM indicate the numbers of clusters included in the intermediate learning result SA, and the column numbers indicate the numbers of clusters included in the intermediate learning result SB.

Step SA7: Score Calculation The score calculation unit 6 compares each evaluation index included in the evaluation index matrix EM with a threshold value TH, and gives a high score (e.g., score +1) to both clusters that constitute an evaluation index ES that is equal to or less than the threshold value TH (similar), and gives a low score (e.g., score 0) to both clusters that constitute an evaluation index ES that is greater than the threshold value (not similar). Then, the total score of each cluster (CA1 to CAp) of the intermediate learning result SA is calculated. In other words, the total of the scores given to each row (ES _i1 , ..., SE _iq ) of the evaluation index matrix EM is calculated for each row. The total of the scores of (ES _i1 , ..., ES _iq ) is the score of cluster CAi. In addition, the total score of each cluster (CB1 to CBq) of the intermediate learning result SB is calculated. In other words, the total of the scores given to each column (ES _1j , ..., SE _pj ) of the evaluation index matrix EM is calculated for each column. The sum of the scores of (ES _1j , ..., SE _pj ) is the score of cluster CBj. Note that the method of calculating the score is not limited to this, and it is also possible to add an application such as adding a high score to the one that is equal to or less than the threshold TH and has the lowest evaluation index ES in each row (the one that is most similar) or the one that has the lowest evaluation index ES in each column (the one that is most similar).

In this embodiment, the above total score is calculated for all pairs of any two intermediate learning results selected from the multiple intermediate learning results. In other words, the distance matrix calculation unit 4 and the evaluation index calculation unit 5 perform the above-mentioned distance matrix calculation, evaluation index calculation, and evaluation index matrix generation for all pairs of any two intermediate learning results selected from the multiple intermediate learning results. Then, based on these calculation results, the score calculation unit 6 obtains the total score for each cluster of each intermediate learning result. After that, the process returns to step SA41.

Step SA8
In step SA41, when it is determined that there is no pair of two intermediate learning results selectable from the multiple intermediate learning results that has not yet been selected as a processing target, the score calculation unit 6 generates a score matrix. Specifically, the score calculation unit 6 generates a score matrix SM with r columns in which the row numbers are cluster numbers, as shown in the following formula [15], based on the acquired total score. Here, an element S _ij of the matrix SM is the total score in the cluster i of the jth intermediate learning result (j is an integer between 1 and M). Specifically, it is the sum of all the total scores of the cluster i of the jth intermediate learning result calculated by the score calculation unit 6 for all pairs of the jth intermediate learning result and all other intermediate learning results. In addition, there are elements that do not exist in the matrix SM. For example, if the cluster i of the jth intermediate learning result does not exist, S _ij is empty and does not participate in calculations.

Step SA9
The pixel number calculation unit 7 calculates the pixel number by the following steps SA91 and SA92.

Step SA91
The stroke number calculation unit 7 refers to the score matrix SM and obtains the minimum scores S _m1 to S _mr for each intermediate learning result, that is, the stroke number calculation unit 7 obtains the minimum scores S _m1 to S _mr for each row of the score matrix SM.

式［１６］にあるように、画一度ＵＮは、最小得点Ｓ_ｍ１～Ｓ_ｍｒの最大値から求められる。換言すると、画一度ＵＮは、所属する全てのクラスタが好適に他の学習結果のクラスタと似ている学習結果から求められる。 Step SA92
The stroke number calculation unit 8 calculates the stroke number UN based on the acquired minimum scores S _m1 to S _mr . The stroke number UN is calculated, for example, by the following formula: Here, N is the number of all learning results.

As shown in formula [16], the stroke number UN is determined from the maximum value of the minimum scores S _m1 to S _mr . In other words, the stroke number UN is determined from a training result in which all clusters to which the training result belongs are preferably similar to the clusters of other training results.

If the value of stroke-per-unit UN is large, it means that in at least one learning result, all clusters belonging to that learning result have high scores, i.e., they are very similar to the clusters of other learning results. If the value of stroke-per-unit UN is small, it means that in every learning result, at least one cluster has low scores, i.e., they are not similar to the clusters of other learning results.

The stroke count UN tends to decrease as the edge deletion level M value increases, i.e., as the number of times the edge deletion process is repeated increases, the edge deletion progresses and the clusters become more diverse. In other words, if the stroke count UN becomes smaller than a specified value by increasing the number of times the edge deletion process is repeated, it can be understood that the clusters have become more diverse and that dissimilar clusters have come into existence in all learning results. Therefore, the stroke count UN can be used to determine the timing to stop the repetition of the edge deletion process.

Figure 12 shows an example of intermediate learning results and pixel count UN obtained when a two-stage edge deletion process is performed. In Figure 12, similar clusters are surrounded by dashed lines. As can be seen from Figure 12, after the first stage of edge deletion process, clusters that depend on the input data structure are generated by the edge deletion, but after the second stage of edge deletion process, noise-like clusters that depend on the method and parameters of each learning result are generated. The results after the first stage of edge deletion process are suitable for clustering, but the results after the second stage of edge deletion process are not suitable for clustering.

In this example, the stroke count UN changes so that it is 3, which is the minimum score among all learning results ( _S01 to _S04 ), or 100%, before the edge deletion process, 2, which is the minimum score among learning results 1 to 3 ( _S11 to _S13 ), or 75%, after the first-stage edge deletion process, and 0, which is the minimum score among all learning results ( _S01 to _S04 ), or 25%, after the second-stage edge deletion process. In this case, for example, by setting the stroke count threshold TH _UN to 40%, the edge deletion process can be stopped at a state after the second-stage edge deletion process where the clusters are deemed to be appropriately separated or close to being appropriately separated.

Step SB1
The end determination unit 8 compares the image number UN with a predetermined image number threshold value _{TH_UN} .

Step SB2
If the pixel number UN is equal to or greater than the pixel number threshold value TH _UN (UN≧TH _UN ), the end determination unit 8 increases the edge deletion level M by 1 (M=M+1) and returns the process to step SA32.

Step SB3
If the image number UN is smaller than the image number threshold value TH _UN (UN<TH _UN ), the learning result selection unit 9 selects the final learning result based on the following steps SB31 to SB33.

Step SB31
The learning result selection unit 9 selects a group consisting of a plurality of intermediate learning results in which edges have been deleted at edge deletion level M-1. Which group to select may be determined appropriately depending on the application. Note that, although the learning result selection unit 9 has been described here as selecting a group consisting of a plurality of intermediate learning results in which edges have been deleted at edge deletion level M-1, it may also select a group consisting of a plurality of intermediate learning results in which edges have been deleted at edge deletion level M, as necessary.

Step SB32
The learning result selection unit 9 refers to the score matrix SM and obtains the minimum scores Smin1 to Sminr for each intermediate learning result.

Step SB33
The learning result selection unit 9 selects the intermediate learning result with the maximum value among the acquired minimum scores Smin1 to Sminr as the final learning result to be adopted. In other words, the learning result selection unit 9 extracts, for each intermediate learning result, the score of the cluster that is most dissimilar to the clusters included in the other intermediate learning results, and then selects the intermediate learning result having the most similar cluster from among them as the final learning result.

Step SB4
The clustering unit 10 performs class classification by referring to the nodes and edges of the selected final learning result. In the class classification, for example, processing such as assigning cluster numbers or labeling to the clusters included in the final learning result is performed.

As described above, according to this configuration, it is possible to repeat the edge deletion process an appropriate number of times by automatically determining the edge deletion level M. This makes it possible to accurately learn the structure of the input data by automatically performing the edge deletion process.

Other embodiments The present invention is not limited to the above-mentioned embodiments, and can be modified as appropriate without departing from the spirit of the present invention. For example, as for the distance measure indicating the distance between nodes, any distance measure such as Euclidean distance, cosine distance, Manhattan distance, and fractional distance can be applied as the distance measure between nodes. In general, Euclidean distance is used when the input data is low-dimensional, and cosine distance, Manhattan distance, and fractional distance are used when the input data is high-dimensional.

In the above embodiment, the judgment of the magnitude of two values has been described, but this is merely an example, and the case where the two values are equal in the judgment of the magnitude of two values may be handled as necessary. In other words, for the judgment of whether the first value is equal to or greater than the second value or smaller than the second value, either may be adopted as necessary. For the judgment of whether the first value is equal to or less than the second value or larger than the second value, either may be adopted. In other words, when the magnitude judgment of two values is performed to obtain two judgment results, the case where the two values are equal may be included in either of the two judgment results as necessary.

In addition, in SOINN, a process of connecting edges is performed in learning input vectors. In this case, it is possible to perform a process equivalent to the edge deletion process described above by connecting only edges whose length is equal to or less than the length threshold _LTH . In other words, it is sufficient to obtain a network in which only edges whose length is equal to or less than the length _threshold LTH are connected to nodes, and the selection of edges to be connected to nodes may be performed by the edge deletion process described above, or may be performed in the process of connecting edges performed in the process of learning input vectors in SOINN.

In the above embodiment, the present invention has been described mainly as a hardware configuration, but the present invention is not limited to this, and any process can be realized by having a CPU (Central Processing Unit) execute a computer program. In this case, the computer program can be stored using various types of non-transitory computer readable medium and supplied to the computer. Non-transitory computer readable medium includes various types of tangible storage medium. Examples of non-transitory computer-readable media include magnetic recording media (e.g., flexible disks, magnetic tapes, hard disk drives), magneto-optical recording media (e.g., magneto-optical disks), CD-ROMs (Read Only Memory), CD-Rs, CD-R/Ws, and semiconductor memories (e.g., mask ROMs, PROMs (Programmable ROMs), EPROMs (Erasable PROMs), flash ROMs, and RAMs (random access memories)). The program may also be provided to the computer by various types of transient computer-readable media. Examples of transient computer-readable media include electrical signals, optical signals, and electromagnetic waves. The transient computer-readable medium can provide the program to the computer via a wired communication path such as an electric wire or optical fiber, or via a wireless communication path.

REFERENCE SIGNS LIST 1 Learning processing unit 2 Separation degree calculation unit 3 Edge deletion processing unit 4 Distance matrix calculation unit 5 Evaluation index calculation unit 6 Score calculation unit 7 Pixel number calculation unit 8 End determination unit 9 Learning result selection unit 10 Clustering unit 1000 Computer 1001 CPU
1002 ROM
1003 RAM
1004 Bus 1005 Input/Output Interface 1006 Input Unit 1007 Output Unit 1008 Storage Unit 1009 Communication Unit 1010 Drive 1011 Magnetic Disk 1012 Optical Disk 1013 Flexible Disk 1014 Semiconductor Memory 100 Information Processing Apparatus

Claims (13)

An information processing device that sequentially inputs an input vector and learns an input distribution structure of the input vector as a network structure in which a plurality of nodes described by a multidimensional vector and a plurality of edges connecting two of the nodes are arranged,
a learning processing unit that acquires a plurality of initial learning results obtained by learning the same input data using a plurality of unsupervised learning methods;
a separation degree calculation unit which sequentially selects one initial learning result from the plurality of initial learning results, sequentially selects each of a plurality of edges included in the selected initial learning result as an edge of interest, and calculates a degree of separation of clusters in a case where an edge longer than the edge of interest is deleted from the selected initial learning result and in a case where an edge having a length equal to or longer than the edge of interest is deleted from the selected initial learning result;
an edge deletion processing unit that deletes edges having a length equal to or greater than a length threshold, the length of the edge of interest corresponding to the Mth largest degree of cluster separation among the degrees of cluster separation calculated for the plurality of edges, from the selected initial learning result;
a distance matrix calculation unit that selects a learning result pair consisting of two selectable intermediate learning results from a plurality of intermediate learning results that are the plurality of initial learning results after the edge deletion by the edge deletion processing unit, selects a cluster pair consisting of two clusters selected one from each of the two intermediate learning results of the selected learning result pair, and calculates a distance matrix indicating the distance between a node belonging to one cluster and a node belonging to the other cluster for all of the selectable cluster pairs;
an evaluation index calculation unit that obtains the minimum value of each column and each row for each distance matrix, and calculates an evaluation index for each distance matrix based on the number of the obtained minimum values that satisfy a predetermined condition;
a score calculation unit that calculates, for each cluster of each intermediate learning result, a score indicating a degree of similarity between one cluster included in one intermediate learning result and a cluster of another intermediate learning result, based on an evaluation index of the distance matrix calculated for all the learning result pairs;
a stroke count calculation unit that obtains a minimum value of the scores calculated for each cluster of each intermediate learning result, and calculates a maximum value of the obtained minimum values as a stroke count;
a termination determination unit that adds 1 to M to update the value of M when the pixel count is greater than a pixel count threshold, and terminates the process of deleting edges when the pixel count is less than the pixel count threshold;
a learning result selection unit that selects a final learning result from the plurality of intermediate learning results based on the score of each cluster of each intermediate learning result calculated by the score calculation unit when the termination determination unit determines that the process of deleting edges is terminated;
A clustering unit that clusters the final learning result,
Each time the value of M is updated, the edge deletion processing unit, the distance matrix calculation unit, the score calculation unit, the pixel number calculation unit, and the end determination unit repeat the process.
Information processing device. The degree of separation of the clusters is 0 when the cluster to which the edge of interest belongs is not separated into two clusters after the edge is deleted, and has a value other than 0 when the cluster is separated.
The information processing device according to claim 1 . The degree of separation of the clusters has a positive or negative value when the cluster to which the edge of interest belongs is separated into two clusters.
The information processing device according to claim 2 . When the cluster to which the edge of interest belongs is separated into two clusters, the closer the numbers of nodes in the two separated clusters are, the larger the degree of separation of the clusters becomes if the degree of separation is a positive value, and the smaller the degree of separation becomes if the degree of separation is a negative value.
The information processing device according to claim 3 . When the cluster to which the edge of interest belongs is separated into two clusters, the greater the number of nodes contained in the two separated clusters, the larger the degree of separation of the clusters becomes if the value is positive, and the smaller the value becomes if the value is negative.
5. The information processing device according to claim 3. When n _k1 is the number of nodes in cluster k1 that exists when an edge longer than the edge of interest is deleted, and n _k2 is the number of nodes in cluster k2 that exists when an edge longer than the edge of interest is deleted, the degree of separation D of the clusters is defined by the following formula:

The information processing device according to claim 2 . The score calculation unit:
generating an evaluation index matrix composed of evaluation indexes for all pairs between two clusters selected one by one from each of the two intermediate learning results based on the evaluation indexes calculated for all distance matrices;
calculating a score indicating whether a cluster included in one learning result is similar to a cluster of another learning result based on the evaluation indexes included in the evaluation index matrix;
Generate a score matrix including scores for the clusters belonging to all the learning results;
the learning result selection unit selects a final learning result from the plurality of intermediate learning results based on the score matrix.
The information processing device according to claim 1 . The evaluation index calculation unit is
calculating an average distance between nodes belonging to each of the two clusters, and calculating an average value of the two calculated average distances;
Calculating an evaluation index for each distance matrix based on the number of minimum values equal to or greater than the average value among the minimum values in each column and each row of each distance matrix;
The information processing device according to claim 7. The evaluation index is a value obtained by dividing the number of the minimum values in each column and each row of each distance matrix that are equal to or greater than the average value by the total number of nodes belonging to the two clusters.
The information processing device according to claim 8. the score calculation unit compares each evaluation index included in the evaluation index matrix with a threshold, assigns a score based on a comparison result, and calculates a total score for each cluster.
9. The information processing device according to claim 7 or 8. the learning result selection unit obtains a minimum value among the total scores of clusters belonging to each intermediate learning result, and selects the intermediate learning result corresponding to the maximum value among the obtained minimum values.
The information processing device according to claim 10. 1. An information processing method executed by a computer, comprising: inputting an input vector in sequence; and learning an input distribution structure of the input vector as a network structure in which a plurality of nodes described by a multidimensional vector and a plurality of edges connecting two of the nodes are arranged, the method comprising:
The computer,
Obtaining a plurality of initial learning results obtained by learning the same input data using a plurality of unsupervised learning methods;
selecting one initial learning result from the plurality of initial learning results in order, and selecting one cluster from the selected one initial learning result in order;
selecting each of a plurality of edges included in the selected cluster as an edge of interest in turn, and calculating the degree of separation of the clusters when an edge longer than the edge of interest is deleted from the network structure and when an edge longer than or equal to the edge of interest is deleted from the network structure;
based on the calculated cluster separation degree for each edge of interest, delete edges having a length equal to or greater than a length threshold, the length of the edge of interest corresponding to the Mth largest cluster separation degree, from the selected cluster;
selecting a learning result pair consisting of two selectable intermediate learning results from the intermediate learning results that are the initial learning results after the edge deletion, selecting a cluster pair consisting of two clusters, one selected from each of the two selected intermediate learning results, and calculating a distance matrix indicating the distance between a node belonging to one cluster and a node belonging to the other cluster for all of the selectable cluster pairs;
obtaining a minimum value for each column and row of each distance matrix, and calculating an evaluation index for each distance matrix based on the number of the obtained minimum values that satisfy a predetermined condition;
calculating, for each cluster in each intermediate learning result, a score indicating a degree of similarity between one cluster included in one intermediate learning result and a cluster in another intermediate learning result, based on the evaluation index of the distance matrix calculated for all of the learning result pairs;
A minimum value of the scores calculated for each cluster of each intermediate learning result is obtained, and a maximum value of the obtained minimum values is calculated as a pixel count;
if the pixel count is greater than a pixel count threshold, add 1 to M to update the value of M, and if the pixel count is less than a pixel count threshold, end the process of deleting edges;
When it is determined that the process of deleting edges is to be terminated, a final learning result is selected from the multiple intermediate learning results for the previous period based on the calculated scores of each cluster of each intermediate learning result;
Clustering the final learning result;
Each time the value of M is updated, the deletion of the edge, the calculation of the distance matrix, the calculation of the score, the calculation of the pixel number, and the determination of the end are repeated.
Information processing methods. A program for causing a computer to perform a process of sequentially inputting an input vector and learning an input distribution structure of the input vector as a network structure in which a plurality of nodes described by a multidimensional vector and a plurality of edges connecting two of the nodes are arranged, the program comprising:
A process of acquiring a plurality of initial learning results obtained by learning the same input data using a plurality of unsupervised learning methods;
a process of sequentially selecting one initial learning result from the plurality of initial learning results and sequentially selecting one cluster from the selected one initial learning result;
a process of sequentially selecting each of a plurality of edges included in the selected cluster as an edge of interest, and calculating a degree of separation of the cluster when an edge longer than the edge of interest is deleted from the network structure, and when an edge longer than the edge of interest is deleted from the network structure;
a process of deleting edges from the selected cluster, the edges having a length equal to or greater than a length threshold, the length being the edge of interest corresponding to the Mth largest degree of cluster separation, based on the degree of cluster separation calculated for each edge of interest;
a process of selecting a learning result pair consisting of two selectable intermediate learning results from a plurality of intermediate learning results that are the plurality of initial learning results after edge deletion, selecting a cluster pair consisting of two clusters selected one from each of the two selected intermediate learning results, and calculating a distance matrix indicating the distance between a node belonging to one cluster and a node belonging to the other cluster for all of the selectable cluster pairs;
A process of obtaining the minimum value of each column and each row for each distance matrix, and calculating an evaluation index for each distance matrix based on the number of the obtained minimum values that satisfy a predetermined condition;
a process of calculating, for each cluster of each intermediate learning result, a score indicating a degree of similarity between one cluster included in one intermediate learning result and a cluster of another intermediate learning result, based on an evaluation index of the distance matrix calculated for all the learning result pairs;
A process of obtaining a minimum value of the scores calculated for each cluster of each intermediate learning result, and calculating a maximum value of the obtained minimum values as a pixel count;
updating the value of M by adding 1 if the pixel count is greater than a pixel count threshold, and terminating the process of deleting edges if the pixel count is less than the pixel count threshold;
a process of selecting a final learning result from the multiple intermediate learning results in the previous period based on the calculated scores of each cluster of each intermediate learning result when it is determined that the process of deleting edges is to be terminated;
A process of clustering the final learning result.
Each time the value of M is updated, the process of deleting the edge, the process of calculating the distance matrix, the process of calculating the score, the process of calculating the pixel count, and the process of determining whether the edge has been deleted are repeated.
program.

Images