JPH11250094A - Two-phase data cluster method and apparatus, and recording medium recording two-phase data cluster program - Google Patents

Abstract

(57) [Summary] [Problem] To determine the position of an initial cluster nucleus for aggregating a cluster of data in a data space into a specified number of minutes, optimally aggregate the data in the data space, and distribute a large amount of data. Provided are a two-phase data cluster method and apparatus capable of easily grasping a tendency, and a recording medium on which a two-phase data cluster program is recorded. SOLUTION: An initial cluster nucleus is set randomly or statistically by the number of K times in a data space by a user-specified number, an aggregation process is performed using the data and the initial cluster nucleus, and the position of the cluster nucleus as a processing result is output. Then, a cluster nucleus capable of performing the optimal aggregation processing is extracted from the cluster nucleus of the processing result using the evaluation function, the cluster nucleus is set as the initial cluster nucleus, and the aggregation processing is performed again. Cluster nuclei are generated,
Cluster nuclei are extracted from among them, and aggregation processing is performed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a two-phase data cluster method and apparatus for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. More specifically, the present invention is effective for a method of implementing statistical data aggregation in which the distribution status of data existing in a data space is aggregated from all data into a specified number of data smaller than the number of data and determined, and stored. A two-phase data cluster method and apparatus and a two-phase data cluster program capable of realizing the elimination of overlapping of figures displayed on the display device when the information in the device is displayed two-dimensionally on the display device as a group of figures are recorded. It relates to a recording medium.

[0002]

2. Description of the Related Art As a conventional data aggregation method, what is called an initial cluster nucleus is set at random in a data space for a specified number, and the cluster nucleus is moved so that the distance between each cluster nucleus and data is minimized. Then, there is a method to aggregate the data. When the initial cluster nuclei are set at random, the initial cluster nuclei are arbitrarily set in the data space, so that it may not be possible to aggregate each data chunk in the data space.

In order to solve this problem, there is a method of setting a specified number of initial cluster nuclei by existing statistical inference such as a recent centroid sorting method. In this method, as compared with the former random setting, processing in which the initial cluster nucleus corresponds to each data chunk is performed. Hereinafter, it is optimal to divide data blocks generated by the distance relationship of data in the data space one by one and to be able to aggregate them.

[0004] The result of applying the prior art is shown in a simple case.
9 and 10 show a case where the data space is two-dimensional.
The case where the data existing in the data space as shown in FIG. 9 as indicated by black circles “●” are aggregated as the designated number 4 will be described below.

FIG. 10 shows the result of randomly setting an initial cluster kernel and applying the K-means method which is an existing aggregation method. In FIG. 10, a black circle “●” is data, a white triangle “△” is a randomly set initial cluster nucleus, a black triangle “▲” is a cluster nucleus after the aggregation processing, and is a white frame. The enclosed circular area indicates the range of the aggregated data of the nuclear clusters, and the arrow indicates the movement of the cluster nucleus after the aggregation processing. As described above, since the initial cluster nucleus is not set for each data chunk, data cannot be optimally aggregated.

FIG. 11 shows the result of setting an initial cluster kernel using statistical estimation and applying the K-means method which is an existing aggregation method. In FIG. 11, a black circle “●” is data, a white triangle “△” is an initial cluster nucleus set by statistical estimation, a black triangle “▲” is a cluster nucleus after the aggregation processing, The circular area surrounded by the frame indicates the range of the aggregated data of the nuclear clusters, and the arrows indicate the movement of the cluster nuclei after the aggregation processing.

In the method shown in FIG. 11, an initial cluster nucleus is set for each data chunk, and an aggregation result close to the optimum is output, as compared with the case of the random setting shown in FIG. I have. However, when observing the results of the aggregation results C2 and C4, data 3, 19, and 2
4 is more optimal, but since the results are aggregated in C2, this method is not optimal in this part.

The above two problems largely depend on the positions of the initial cluster points. The initial cluster nucleus is set by statistical estimation and the result of the aggregation processing is shown in FIG. 11 at C2, where the data 3, 19, 12, and 2 are assumed to be one lump, and the distance is close to the data. This is because the initial cluster nucleus was set at the point. As a result, the initial cluster nucleus C2 moves so as to aggregate the data 8, 10 together with the data 3, 19, 2 as shown in FIG.
The result shown in FIG.

[0009]

As described above, if the initial cluster nucleus is set in the data space at random or only by statistical inference, the cluster of data is calculated differently from the original cluster in the area. However, there is a problem in that the aggregated result may be output as a set of data different from the set of data existing in the data space.

[0010] Further, when a device that realizes the above-described conventional aggregation method is applied as a pre-processing device of a device that displays information in a storage device as a group of graphics, the display is not displayed on the display device due to the conventional problem described above. There is a problem that a display result is not output while eliminating the overlap caused by the displayed figure and leaving the tendency of the arrangement position of the original figure.

[0011] The present invention has been made in view of the above,
The purpose is to determine the position of the initial cluster nucleus in order to aggregate a cluster of data in the data space into a specified number of minutes, optimally aggregate the data in the data space, and reduce the distribution tendency of a large amount of data. An object of the present invention is to provide a two-phase data cluster method and apparatus which can be easily grasped, and a recording medium on which a two-phase data cluster program is recorded.

[0012]

In order to achieve the above object, according to the present invention, data having a close relationship in a multidimensional data space is aggregated into a desired number of clusters from a large number of data. A two-phase data cluster method for generating clusters in which the number of clusters to be aggregated and the weight of the aggregation process are specified by the distance between cluster nuclei or the extent of data spread within a cluster, in the range of 0 to 1. Weighting parameter α to be determined, and an initial kernel cluster number determination parameter K for determining the initial kernel cluster number from the aggregate cluster number, and an initial cluster kernel which is an initial value of the aggregation process on condition of the designated initial kernel cluster number. Are set randomly or by statistical estimation within the maximum and minimum ranges of each dimension, and the cluster method including the K-means method is applied to the aggregation process, The distance between the star nucleus and each data is calculated for each dimension, the data having a short distance is aggregated into the same cluster, and the weighting parameter α is approached to 1 as an index for extracting the cluster nucleus. Is set to be high, and when the weighting parameter α approaches 0, the weight of the amount related to the distribution ratio of data in each cluster is set to be high, so that the following evaluation function Ci:

## EQU4 ## Ci = (weighting parameter α) * (amount related to distance matrix between cluster nuclei) + (1−weighting parameter α) * (amount related to distance between each data collected in cluster nucleus i and cluster nucleus) The initial cluster nuclei are arranged in descending order of the value of, and only the number of aggregate cluster nuclei specified from the top is extracted as the initial cluster nuclei for the re-aggregation processing, and this extracted cluster nucleus is used as the initial cluster nucleus of the re-aggregation processing The gist is to perform the aggregation process using the data to generate the number of clusters specified by the user.

According to a second aspect of the present invention, there is provided a two-phase data cluster method for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. The number of clusters to be aggregated, the initial cluster nucleus number determination parameter and the data to be aggregated are specified, and the set aggregation number, initial cluster nucleus number determination parameter, the number of dimensions of the data to be aggregated, and the maximum and minimum of each dimension Detect the value and randomly set the initial cluster nucleus in that range or set the initial cluster nucleus using statistical methods from the aggregation target data,
Aggregation processing is performed using the set initial cluster kernel and specified data, the position of the cluster kernel after the processing result in the multidimensional data is generated, and the weighted parameter α of the evaluation function is calculated from the cluster kernel of the generated aggregation processing result. With the aggregation method desired by the user, a specified number of cluster nuclei are extracted, and aggregation processing is performed based on the preferentially extracted cluster nuclei and the specified original data. To output the position, convert the data into graphic information in order to display the generated final cluster nucleus data as a group of figures, and output the generated graphic display information to a display device. And

Furthermore, the present invention according to claim 3 is a two-phase data cluster apparatus for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. The number of clusters to be aggregated and the weighting of the aggregation process are determined from 0 to 1 as to whether to perform the cluster internuclear distance or the extent of data spread in the cluster.
A weighting parameter α specified in the range, an aggregation parameter specifying means for specifying an initial number of nuclear clusters determination parameter K for determining the number of initial nuclear clusters from the number of aggregation clusters, and an initial nuclear cluster specified by the aggregation parameter specifying means. Initial cluster kernel setting means for randomly or statistically estimating initial cluster kernels which are initial values of the aggregation processing on the condition of the number within the maximum and minimum ranges of each dimension, and a cluster method including a K-means method. Aggregation processing means that applies to aggregation processing, calculates the distance between the cluster nucleus and each data for each dimension, and aggregates data with a short distance comprehensively into the same cluster, and weighting parameters as indices for extracting cluster nuclei When α approaches 1, the weight related to the distance between cluster nuclei is set high, and the weighting parameter α is set to 0. Give the evaluation function Ci in the following for the amount of weight is set high on Distributed percentage of data in each cluster:

## EQU5 ## Ci = (weighting parameter α) * (amount related to distance matrix between cluster nuclei) + (1−weighting parameter α) * (amount related to distance between each data collected in cluster nucleus i and cluster nucleus) Priority cluster nucleus extracting means for arranging the initial cluster nuclei in ascending order and extracting only the number of aggregate cluster nuclei specified from the top as the initial cluster nucleus for the re-aggregation processing; The present invention has an aggregation processing re-executing unit that performs aggregation processing by using the cluster nucleus obtained as an initial cluster nucleus of the re-aggregation processing and generates a number of clusters designated by the user.

According to a fourth aspect of the present invention, there is provided a two-phase data cluster apparatus for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. Aggregation parameter specifying means for specifying the number of clusters to be aggregated, the initial cluster nucleus number determination parameter and the data to be aggregated, the set aggregation number, the initial cluster nucleus number determination parameter and the number of dimensions of the data to be aggregated and the dimensions Initial cluster nucleus setting means for detecting the maximum and minimum values and randomly setting the initial cluster nucleus within the range or setting the initial cluster nucleus from the data to be aggregated using a statistical method, and the set initial cluster nucleus Aggregation processing that performs aggregation processing with the data specified as the nucleus and generates the position in the multidimensional data of the cluster nucleus after the processing result And priority cluster nucleus extraction means for extracting a specified number of cluster nuclei by a user's desired aggregation method with the weighting parameter α of the evaluation function from the cluster nuclei of the generated aggregation processing result; Aggregation processing re-execution means for performing aggregation processing based on the original data specified as the cluster kernel and outputting the final cluster kernel data position in the data space. The gist of the present invention is to have a display information generating means for converting and generating data into graphic information for displaying as a group, and a graphic information display device for outputting the generated display information of the graphic to a display device.

In the present invention described in claims 1 to 4,
When aggregating chunks of data represented by those with a close distance between data in a data space with a large amount of data into a specified number so as not to impair the tendency of data distribution, the initial cluster kernel is randomly or randomly By statistical estimation, the data space is set to K times the number specified by the user, aggregation processing including the K-means method is performed using the data and the initial cluster nucleus, the position of the cluster nucleus of the processing result is output, and the evaluation function Ci is used. Extract cluster nuclei that can perform optimal aggregation processing from the cluster nuclei of the processing results,
By setting this cluster nucleus as an initial cluster nucleus and performing aggregation processing again, a cluster nucleus close to a data chunk is generated in the first aggregation processing, and a cluster nucleus is extracted therefrom to perform aggregation processing. , The data blocks in the data space can be aggregated separately.

The operation of the evaluation function will be described. The first term of the evaluation function indicates a quantity related to the distance between cluster nuclei. Since the difference between the distances between cluster nuclei is calculated from the maximum inter-cluster nucleus distance, the smaller this value is, the farther the cluster nucleus is from other cluster nuclei. The second term indicates a quantity related to the distance between the cluster nucleus and the data aggregated therein. Since this amount is the distance between the aggregated data and the cluster nucleus, a cluster nucleus with a small value can be regarded as being composed of data in which clusters themselves are dense. From the above, the cluster nucleus having a small value of the evaluation function satisfies the optimum condition that the data is dense and distant from other cluster nuclei.

Also, by arbitrarily specifying the value of the weighting parameter α by a number between 0 and 1, when the weighting parameter α is close to 0, the value of the first term greatly affects the evaluation function, and the weighting parameter α Is close to 1
The value of the term greatly affects the evaluation function. In other words, if the weighting parameter α is set to a value close to 0, cluster nuclei in which data is dense among candidate cluster nuclei are extracted. Similarly, if the weighting parameter α is set to a value close to 1, cluster nuclei that are distant from other cluster nuclei among the priority cluster nuclei are extracted. By arbitrarily specifying the weighting parameter α, aggregation processing corresponding to data of various distributions can be performed. Therefore, in order to divide and aggregate data clusters that are often dense and could not be detected conventionally, the weighting parameter α is appropriately set, and the first and second terms are used. By performing aggregation processing with cluster nuclei having a small sum as a candidate, cluster nuclei having a small evaluation function are extracted by a designated number with priority, so that a lump of data in the data space is divided and aggregated one by one. can do.

According to a fifth aspect of the present invention, there is provided a two-phase data cluster program for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. A recording medium in which the number of clusters to be aggregated, a weighting parameter α for designating in a range of 0 to 1 whether the weighting of the aggregation processing is to be performed based on the distance between cluster nuclei or the degree of spread of data in the cluster, An initial nuclear cluster number determination parameter K for determining the number of nuclear clusters from the number of aggregated clusters is specified, and the initial cluster nucleus which is an initial value of the aggregation processing is set to the maximum value of each dimension and the initial value of the aggregation process on the condition of the specified number of initial nuclear clusters. It is set randomly or by statistical estimation within the minimum range, and the cluster method including the K-means method is applied to the aggregation processing, and the cluster kernel and The distance between the data is calculated for each dimension, and the data having a short distance is aggregated into the same cluster. When the weighting parameter α is approached to 1 as an index for extracting the cluster nucleus, the weight relating to the distance between the cluster nuclei becomes high. When the weighting parameter α approaches 0, the weight of the amount related to the distribution ratio of the data in each cluster is set to be high.
i:

## EQU6 ## Ci = (weighting parameter α) * (amount related to distance matrix between cluster nuclei) + (1−weighting parameter α) * (amount related to distance between each data collected in cluster nucleus i and cluster nucleus) The initial cluster nuclei are arranged in descending order of the value of, and only the number of aggregate cluster nuclei specified from the top is extracted as the initial cluster nuclei for the re-aggregation processing, and this extracted cluster nucleus is used as the initial cluster nucleus of the re-aggregation processing The gist of the present invention is to record a two-phase data cluster program for generating a cluster designated by the user by performing aggregation processing using the program.

According to the fifth aspect of the present invention, in a data space where a large amount of data exists, a data chunk represented by an object having a short distance between the data is designated so as not to impair the tendency of the data distribution. When aggregating the number of clusters, the initial cluster nucleus is set randomly or statistically by a factor of K times in the data space by the number specified by the user, and the aggregation process is performed with the data and the initial cluster nucleus. By outputting the position, extracting a cluster nucleus capable of performing the optimal aggregation processing from the cluster nucleus of the processing result using the evaluation function Ci, setting this cluster nucleus as an initial cluster nucleus, and performing the aggregation processing again, 1
In the second aggregation processing, a cluster nucleus close to a cluster of data is generated, and a two-phase data cluster program for extracting a cluster nucleus from the cluster nucleus and performing the aggregation processing is recorded on a recording medium. , And its distribution can be improved.

[0021]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a two-phase data cluster device according to one embodiment of the present invention.

The two-phase data cluster device of the present embodiment shown in FIG. 1 has an information storage device 40 for storing data to be consolidated.
1 and the user sets the aggregation condition (data to be aggregated, the number of aggregations, weighting parameter α) by setting condition setting processing display device 40
2-1 using a GUI (Graphical User Interface) component 402-2 and an aggregation condition input device 402 input from an external input device 406;
2. An aggregated data generation device 403 that performs an aggregation process based on the aggregation condition input from Step 2 and display information for displaying the aggregated data as a group of figures in an arrangement method intended by the user under the aggregation condition. The display information generation device 404 includes a display information generation device 404 that performs generation, conversion, and synthesis, and a graphic information conversion display device 405 that displays display information generated, converted, and synthesized by the display information generation device 404 on the display device 405-1.

Further, the aggregated data generation device 403 randomly or statistically estimates more initial cluster nuclei than the number of aggregations specified by the aggregation condition input device 402 in the data space where the data to be aggregated exists. Eye initial point setting device 403-1 and first phase initial point setting device 40
The first-phase aggregation processing device 403-2 that performs aggregation processing on the initial cluster nucleus set in 3-1 and the data to be aggregated, generates a cluster nucleus after the processing, and the result of the aggregation processing of the first phase A second-phase initial point extracting device 403-3 for extracting the specified number of initial cluster kernels based on the evaluation function Ci from the output second-phase initial cluster kernel candidates.
And the second phase aggregation processing device 403-4 which performs aggregation processing on the initial cluster kernel extracted by the second phase initial point extraction device 403-3 and the data in the information storage device 401 designated by the aggregation condition device. It is configured. Further, the aggregation condition input device 402 includes a GUI component 402-2, a setting condition setting processing display device 402-1, a GUI unit 402-3, and a setting screen control device 402-4.

The aggregation condition input device 402 for setting information required for the aggregation processing constitutes an aggregation parameter designating means, and the first phase initial point setting device 403 of the aggregate data generation device 403
-1 constitutes an initial cluster nucleus setting unit, the first phase aggregation processing unit 403-2 constitutes an aggregation processing unit, and the second phase initial point extraction unit 403-3 constitutes a priority cluster nucleus extraction unit. The phase aggregation processing device 403-4 constitutes an aggregation processing execution unit again, the display information generation device 404 constitutes a display information generation unit, and the graphic information display device 405 constitutes a graphic information display unit.

The aggregation parameter designating means constituting the aggregation condition input device 402 determines from 0 to 1 whether the number of clusters to be aggregated and the weighting of the aggregation processing are to be performed based on the distance between cluster nuclei or the degree of spread of data in the cluster. The weighting parameter α specified by the range and the initial nuclear cluster number determination parameter K for determining the initial nuclear cluster number from the aggregated cluster number are specified. Also, the first phase initial point setting device 403
The initial cluster nucleus setting means constituting −1 is required for the first aggregation process in the multidimensional data space by the number of products of the aggregation number specified by the aggregation parameter specifying means and the initial kernel cluster number determination parameter K. An initial cluster kernel is set in data space, randomly or by statistical inference, within the maximum and minimum limits of each dimension.

The aggregation processing means constituting the first-phase aggregation processing device 403-2 performs the first aggregation processing with the distance between the cluster kernel and each data set by the initial cluster kernel setting means. The priority cluster nucleus extraction means that constitutes the second phase initial point extraction device 403-3 extracts the cluster nucleus moved from the initial time by the aggregation process,

(Equation 7) ｛Where N ′ = K × (designated number of aggregations), r _ik is the cluster kernel i (i = 1,.
N ′) indicates the distance between the other cluster nuclei j (j = 1,..., N ′), and r _Max indicates the maximum value of the distance between the cluster nucleus moved by the aggregation processing and the other cluster nucleus.
Here represents the Euclidean distance is the distance, M _i is the cluster nuclei i (i = 1, ..., N ') indicates the number of aggregated data in, r' _ik cluster nuclei i (i = 1, ..., N ') and indicates the distance between M _i pieces of aggregated data thereto, alpha is a weighting parameter, which is a real number between 0 and 1. A cluster kernel is extracted by a designated number from the lowest value of the evaluation function Ci, and the weighting parameter α in the evaluation function Ci is arbitrarily determined between 0 and 1 to obtain the evaluation function Ci. Is freely determined by the values of the first and second terms. When the weighting parameter α is close to 0, the weight of the second term increases, and the density of the data aggregated in each cluster increases. A cluster kernel with a high degree is extracted, and if the weighting parameter α is close to 1, the first
The method of extracting cluster nuclei can be changed such that the weight of the term increases and cluster nuclei that are far from other clusters are extracted.

The consolidation processing re-executing means constituting the second phase consolidation processing device 403-4 performs the consolidation processing again using the cluster nuclei extracted by the priority cluster nucleus extraction means as the initial cluster nuclei with the distance from each data.

In the two-phase data cluster device configured as described above, the user sets the data in the information storage device 401, the number of aggregations, and the weighting parameter α using the GUI component 402-.
2 using the external input device 406. These specified conditions are passed to the setting screen control device 402-4 as appropriate numerical parameters via the GUI unit 402-3. Initial phase nuclei that are larger than the number of aggregations in the passed numerical information are set by the first-phase initial point setting device 403-1, and the first-phase aggregation processing device 403- The aggregation processing is calculated in step 2.

The cluster kernel calculated from the first-phase aggregation processing unit 403-2 is input to the second-phase initial point extraction unit 403-3, and the initial point to be extracted is determined based on the evaluation function Ci. The second phase initial cluster nucleus and the aggregation target data input from the aggregation condition input device 402 are subjected to aggregation processing in the second phase aggregation processor 403-4, and the aggregated cluster nucleus is generated as display information. Transfer to the device 404.

The display information generating device 404 generates, converts, and combines display information for displaying information as a group of figures based on the received result in an arrangement method intended by the user. The generated, converted, and synthesized display information is sent to the graphic information display device 405 and is displayed on the display device 4.
05-1.

As described above, in the present embodiment, the aggregation process for extracting the initial cluster nucleus of the second-phase aggregation process from the cluster nucleus calculated by the two-phase processing method associated with the aggregation process and the first-phase aggregation process. Has been realized.

Next, the operation of the two-phase data cluster device of the present embodiment configured as described above will be described with reference to the flowcharts shown in FIGS.

In FIG. 6, first, the aggregation condition input device 4
The data to be aggregated, the number of aggregations N, the weighting parameter α as an extraction parameter, the parameter K for determining the number of initial nuclear clusters, and the like are designated by the aggregation parameter designation means consisting of 02 (steps S11, S12, S13), and then 1
The initial cluster nucleus specifying unit 403-1 of the phase initial point setting device 403-1 is the initial cluster nucleus 1 that is larger than the number of aggregations.
A phase initial point is generated (steps S15 and S16), and the first phase aggregation processing device 403-2 is provided with the initial cluster kernel.
The first-phase aggregation processing is performed by the aggregation processing means consisting of
Generate a first-phase cluster nucleus (steps S19 and S2)
1).

Next, the priority cluster nucleus extraction means including the second phase initial point extraction device 403-3 designates the second phase processing cluster kernel candidates output as a result of the first phase aggregation processing based on the evaluation function. The initial cluster kernels of the number of aggregations are extracted (steps S23 and S25), and then the second-phase aggregation processing is performed by the aggregation processing re-executing means including the second-phase aggregation processing device 403-4, and the cluster kernels are aggregated. Generate a second-phase cluster nucleus (steps S27 and S2)
9).

Next, the first-phase initial point generation processing by the first-phase initial point setting device 403-1 will be described with reference to the flowchart shown in FIG. In FIG. 7, first, N ′ = (initial nuclear cluster number determination parameter K) * (specified aggregation number N) is calculated, the maximum value and the minimum value of each dimension are obtained, and the parameter I is set to 1 (step). S41, S
42, S43). Then, a processing point is set (step S
45) A random number that is a value between the minimum value and the maximum value is generated for each dimension (step S47), and the generated random numbers are combined (step S51). Then the parameter I
Is incremented by +1 and the initial point setting process is repeatedly performed for all the parameters until the parameter I becomes N ′ (step S53).

Next, the second phase initial point extraction processing by the second phase initial point extraction device 403-3 will be described with reference to the flowchart shown in FIG. In FIG. 8, first, each cluster nucleus is numbered (step S61), and then the distance r _ij between each cluster nucleus is calculated on one side (step S63), and the distance within the cluster is calculated on the other side (step S65). ) Then, the distance r ′ _ij between the original data collected in the cluster kernel i and the cluster kernel is calculated (step S67), and the intra-cluster distance is further calculated until the parameter i becomes N ′ (step S69).

Then, the evaluation function Ci is calculated (step S71), and is set as a second-phase initial point in ascending order of the value of the evaluation function Ci (step S73).

Next, the effects of the present embodiment will be described with reference to FIGS. Here, for simplicity, an example in which the present invention is applied to data in the two-dimensional data space described in the related art will be described. First, the data in the target data space shown in FIG. 2 is aggregated into four clusters as in the case described above. The parameter K used in this example is 2, that is, the number of initial cluster nuclei at the time of the first aggregation processing is doubled to eight.

FIG. 3 shows a state after the first aggregation processing. For the setting of the initial cluster nucleus used in the first aggregation processing, the existing recent centroid sorting method is used.
In FIG. 3, there are eight (= 4 × 2) cluster kernels in the data space. The relationship between the cluster nucleus and the data is calculated using the above-described evaluation function, and an initial cluster nucleus for performing the aggregation process again is extracted. This calculation process is shown in Tables 1, 2, 3, and 4 below.

[0040]

[Table 1] Table 1 is a matrix showing the distance between cluster nuclei necessary for calculating the first term of the evaluation function Ci. For example, cluster kernel 1
Is calculated as 2.132.

[0041]

[Table 2] Table 2 shows the relationship and distance between the data and the cluster nuclei required in the second term of the evaluation function Ci. For example, the data 1 is aggregated in the cluster nucleus 7 and the distance to the cluster nucleus is calculated to be 0.249 (the same applies to other cases).
Table 3 shows the result of calculating each term of the evaluation function Ci from these two equations, increasing the weighting parameter α from 0 to 1 in increments of 0.1, and outputting the evaluation value.

[0042]

[Table 3] The cluster nucleus having a small evaluation value differs for each weighting parameter. Therefore, the priority cluster kernel extracted in Table 2, that is, the cluster kernel with a small evaluation value is shown.

[Table 4] FIG. 4 shows the result of extracting a cluster nucleus, setting the cluster nucleus as an initial cluster nucleus, and performing the aggregation process again according to the result of Table 4 when the weighting parameter α is 0.5. As can be seen from this result, the division and aggregation of C4 and C2, which were impossible with the existing technology, are optimally performed. Table 5 shows the optimality by specific numerical values.

[0043]

[Table 5] Table 5 shows the average of the distance between cluster nuclei when the K-means method is applied to the above data as an existing method and when this method is applied, and the average of the distance between the clustered data and the cluster nuclei in each cluster. The average distance is shown. The former numerical value for the expression given as an example is an index indicating whether the cluster is divided into individual ones, and the smaller the better, the better. The latter numerical value is an index indicating whether or not the data aggregated in each cluster is dense, and the smaller the better, the better. As can be seen from the numerical values, the output of this method is more suitable than the existing method.

Although the above is the result of the aggregation processing limited to certain data, this method changes the extracted cluster nuclei as shown in Table 4 by changing the value of the weighting parameter α. Can be. In the above-described example, when the weighting parameter α is 0.1 and when the weighting parameter α is 0.1.
In the case of 9, the cluster kernels C2 and C output in FIG.
4, C5 and C6 are extracted. As can be seen from the existing methods, the data to be aggregated into such a cluster changes the cluster to be aggregated according to the policy of how to create the cluster. On the other hand, the cluster kernel C1, which is extracted regardless of whether the weighting parameter α is 0.1 or 0.9,
C8 should always be independently extracted even from the distance between data, and this method realizes it. Other than that, in the aggregation processing, it is not known which cluster to enter, in other words, which cluster is considered to be unstable data to be included in the aggregation processing. The weighting parameter α is arbitrarily changed by a value between 0 and 1. It is realized by doing. This method cannot be realized by the conventional method of performing one aggregation process.

FIG. 5 shows an example of the result of the two-phase data cluster device of the present embodiment described above. FIG. 5A is an image diagram of the result of not passing through the two-phase data cluster device of the present embodiment, and FIG. 5B is a diagram illustrating the output of the result of FIG. It is an image figure of a result at the time of applying a two-phase data cluster device. When the two-phase data cluster device of the present embodiment is applied, data in the data space corresponding to each figure is aggregated, and the position of the cluster nucleus output in each aggregation result is converted into a figure,
Output. For example, a set of small triangles near the center of FIG. 5A and a set of larger triangles are aggregated. If only this part is limited, the size of the data corresponding to the size of the triangle is verified, and the data corresponding to the large figure and the data corresponding to the small figure are respectively aggregated. This indicates that the aggregation process can be performed while maintaining the tendency of data that cannot be realized by the existing method.

[0046]

As described above, according to the present invention,
When aggregating chunks of data represented by those with a close distance between data in a data space with a large amount of data into a specified number so as not to impair the tendency of data distribution, the initial cluster kernel is randomly or randomly By statistical estimation, set K times the number of users specified in the data space, perform aggregation processing with the data and the initial cluster kernel,
Output the position of the cluster nucleus of the processing result, extract the cluster nucleus that can perform the optimal aggregation processing from the cluster nucleus of the processing result using the evaluation function, set this cluster nucleus as the initial cluster nucleus, and perform the aggregation processing again. By doing so, a cluster nucleus close to a cluster of data is generated in the first aggregation processing, and a cluster nucleus is extracted from the cluster nucleus.
Since the aggregation process is performed, the block of data in the data space can be divided and aggregated one by one.

Further, according to the present invention, it is possible to optimize the aggregation of the data formed by the distance between the data existing in the data space, and to easily grasp the distribution tendency of a large amount of data. be able to.

Furthermore, according to the present invention, a large amount of data stored in the storage device is aggregated, and the cluster result is displayed as a group of figures on the display screen, thereby outputting a result without overlapping figures. It is possible to

Further, according to the present invention, the initial cluster nucleus is set so that the aggregation processing is optimally performed, and the aggregation processing is performed by setting the initial cluster nucleus randomly or by statistical estimation as in the related art. Rather, a larger number of cluster nuclei than the specified number are first set at random or by statistical guess, and the aggregation processing is performed once, and the initial cluster nuclei necessary for the second aggregation processing are extracted from the processed cluster nuclei. Then, aggregation processing is performed.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of a two-phase data cluster device according to an embodiment of the present invention.

FIG. 2 is a diagram showing a data space before the embodiment is applied.

FIG. 3 shows a first embodiment of the present invention for the data space shown in FIG. 2;
It is a figure showing the result of having applied the aggregation processing of the time.

FIG. 4 shows a result of the aggregation processing after extracting a priority cluster nucleus by using an evaluation function in order to execute the aggregation processing again from the cluster nuclei having more than the designated aggregation number, and is a result of the first aggregation processing shown in FIG. FIG. 14 is a diagram illustrating a result of executing the aggregation process again on the.

FIG. 5 is an example of a result of the two-phase data cluster device of the present embodiment, and FIG. 5A is an image diagram showing a result of not passing through the two-phase data cluster device of the present embodiment, and FIG. Is for the data for which the result of FIG.
It is an image figure of a result at the time of applying the two-phase data cluster device of this embodiment.

FIG. 6 is a flowchart showing the operation of the two-phase data cluster device of the embodiment shown in FIG.

FIG. 7 is a flowchart showing a first phase initial point generation process by the first phase initial point setting device used in the embodiment shown in FIG. 1;

FIG. 8 is a flowchart showing a second-phase initial point extraction process by the second-phase initial point extraction device used in the embodiment shown in FIG. 1;

FIG. 9 is a diagram showing a data space before application for explaining a conventional process.

10 is a diagram showing a result of randomly setting initial cluster kernels in the data space of FIG. 9 and applying a K-means method which is an existing aggregation method.

11 sets an initial cluster kernel using statistical estimation for the data space of FIG.
FIG. 14 is a diagram showing the result of applying the averaging method.

[Explanation of symbols]

 401 Information storage device 402 Aggregation condition input device 403 Aggregated data generation device 403-1 First phase initial point setting device 403-2 First phase aggregation processing device 403-3 Second phase initial point extraction device 403-4 Second phase aggregation Processing device 404 Display information generation device 405 Graphic information conversion display device 405-1 Display device 406 External input device

 ────────────────────────────────────────────────── ─── Continued on the front page (72) Inventor Tetsuya Iizuka 3-19-2 Nishishinjuku, Shinjuku-ku, Tokyo Nippon Telegraph and Telephone Corporation

Claims (5)

[Claims] 1. A two-phase data cluster method for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data, comprising: A weighting parameter α that specifies in a range from 0 to 1 whether the weighting of the processing is performed based on the distance between cluster nuclei or the extent of the data in the cluster, and an initial kernel for determining the number of initial kernel clusters from the number of aggregated clusters. A parameter K for determining the number of clusters is designated, and an initial cluster nucleus, which is an initial value of the aggregation processing, is set randomly or by statistical estimation within the maximum and minimum ranges of each dimension on the condition of the designated number of initial nuclear clusters. , Applying the clustering method including the K-means method to the aggregation processing, calculating the distance between the cluster kernel and each data for each dimension,
When data with a short distance is aggregated into the same cluster and the weighting parameter α is approached to 1 as an index for extracting cluster nuclei, the weight related to the distance between cluster nuclei is set high. When the weighting parameter α is approached to 0, The following evaluation function Ci for setting the weight of the quantity relating to the distribution ratio of the data in each cluster to be high: ## EQU1 ## Ci = (weighting parameter α) * (quantity related to distance matrix between cluster nuclei) + ( 1-weighting parameter α) * (initial cluster nuclei are arranged in ascending order of the value of the distance between each data aggregated in cluster nuclei i and the cluster nuclei), and only the number of aggregate cluster nuclei specified from the top is re-aggregated Extraction as initial cluster nucleus for processing, and using this extracted cluster nucleus as the initial cluster nucleus for reaggregation processing, aggregation processing And generating a number of clusters specified by the user. 2. A two-phase data cluster method for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data, comprising: By specifying the parameter for determining the number of cluster nuclei and the data to be aggregated, the set number of aggregations, the initial parameter for determining the number of cluster nuclei, the number of dimensions of the data to be aggregated, and the maximum and minimum values of each dimension are detected. The cluster nucleus is set randomly or an initial cluster nucleus is set from the data to be aggregated by using a statistical method, and the aggregation process is performed using the set initial cluster nucleus and the specified data. A position in the multidimensional data is generated, and from the cluster nucleus of the generated aggregation processing result, the The user extracts the specified number of cluster nuclei using the aggregation method desired by the user, performs aggregation processing based on the extracted cluster nuclei and the specified original data, and positions the final cluster nuclei in the data space. And converting the data into graphic information in order to display the generated final cluster nucleus data as a set of graphics, and outputting the generated graphics display information to a display device. Two-phase data cluster method. 3. A two-phase data cluster apparatus for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data, the number of clusters to be aggregated, A weighting parameter α that specifies in a range from 0 to 1 whether the weighting of the processing is performed based on the distance between cluster nuclei or the extent of the data in the cluster, and an initial kernel for determining the number of initial kernel clusters from the number of aggregated clusters. Aggregation parameter designating means for designating the number-of-clusters determination parameter K, and an initial cluster kernel which is an initial value of the aggregation processing on the condition of the number of initial kernel clusters designated by the aggregation parameter designating means within a maximum and minimum range of each dimension. Initial cluster nucleus setting means, which is set randomly or by statistical estimation, and cluster methods including the K-means method are aggregated. It was applied to the distance between the clusters nucleus and each data is calculated for each dimension,
Aggregation processing means that aggregates data having a short distance comprehensively into the same cluster, and when the weighting parameter α is brought close to 1 as an index for extracting cluster nuclei, the weight related to the distance between cluster nuclei is set high. When the value approaches 0, the weight of the amount relating to the variance of the data in each cluster is set high. The following evaluation function Ci: ## EQU2 ## Ci = (weighting parameter α) * (distance matrix between cluster nuclei) Amount) + (1−weighting parameter α) * (amount related to the distance between each data aggregated in cluster kernel i and cluster kernel) The initial cluster kernels are arranged in ascending order, and the number of aggregate cluster kernels specified from the top Cluster nucleus extraction means for extracting only the initial cluster nucleus for the re-aggregation processing, and extraction from the priority cluster nucleus extraction means A two-phase data cluster apparatus comprising: an aggregation processing re-executing unit that performs aggregation processing by using the cluster nucleus obtained as an initial cluster nucleus of the re-aggregation processing and generates a number of clusters designated by a user. 4. A two-phase data cluster apparatus for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated from a large number of data into a desired number of aggregated clusters, the number of clusters to be aggregated, An aggregation parameter specifying means for specifying the cluster nucleus number determination parameter and the data to be aggregated, and detects the set aggregation number, the initial cluster nucleus number determination parameter, the number of dimensions of the data to be aggregated, and the maximum and minimum values of each dimension. Initial cluster nucleus setting means that randomly sets the initial cluster nuclei within the range or sets the initial cluster nuclei from the data to be aggregated using a statistical method, and aggregates with the set initial cluster nuclei and specified data An aggregation processing means for performing processing and generating a position in the multidimensional data of the cluster kernel after the processing result; Priority cluster nucleus extraction means for extracting a specified number of cluster nuclei by the user's desired aggregation method using the weighting parameter α of the evaluation function from the cluster nuclei of the processing result, and original data designated as the cluster nucleus extracted preferentially Aggregation processing re-executing means that performs aggregation processing based on the data and outputs the final cluster nucleus position in the data space, and figures for displaying the generated final cluster nucleus data as a set of figures A two-phase data cluster device, comprising: display information generating means for converting and generating data into the information of the above; and a graphic information display device for outputting display information of the generated graphic to a display device. 5. A recording medium recording a two-phase data cluster program for generating a cluster in which data having a close relationship in a multidimensional data space is aggregated into a desired number of aggregated clusters from a large number of data. The number of clusters to perform, the weighting of the aggregation process is determined by the distance between cluster nuclei or the extent of data spread within the cluster, a weighting parameter α specifying in the range of 0 to 1, the initial number of nuclear clusters is determined from the number of aggregated clusters The parameter K for determining the number of initial nuclear clusters for performing the calculation is specified, and the initial cluster nuclei, which are the initial values of the aggregation processing, are randomly or statistically determined within the maximum and minimum ranges of each dimension, based on the specified number of initial nuclear clusters. The cluster method including the K-means method is applied to the aggregation process, and the distance between the cluster kernel and each data is calculated for each dimension. Calculation Te and,
When data with a short distance is aggregated into the same cluster and the weighting parameter α is approached to 1 as an index for extracting cluster nuclei, the weight related to the distance between cluster nuclei is set high. When the weighting parameter α is approached to 0, The following evaluation function Ci for setting the weight of the amount related to the distribution ratio of data in each cluster to be high: Ci = (weighting parameter α) * (amount related to distance matrix between cluster nuclei) + ( 1-weighting parameter α) * (initial cluster nuclei are arranged in ascending order of the value of the distance between each data aggregated in cluster nuclei i and the cluster nuclei), and only the number of aggregate cluster nuclei specified from the top is re-aggregated Extraction as initial cluster nucleus for processing, and using this extracted cluster nucleus as the initial cluster nucleus for reaggregation processing, aggregation processing And generating a user-specified number of clusters.