Data division apparatus, data division method and program

• US 20060269144A1
• Filed: 03/22/2006
• Published: 11/30/2006
• Est. Priority Date: 05/25/2005
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hatano, Hisaaki, Kubota, Kazuto, Morita, Chie, Nakase, Akihiko
• Granted Patent: US 7,882,050 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques

Abstract

According to an aspect of the present invention, there is provided with a data division apparatus which divides multi-dimensional data, including: a data input unit which inputs multi-dimensional data; a division plane candidate creator which creates a plurality of division plane candidates for dividing the multi-dimensional data; a data provisional division unit which provisionally divides the multi-dimensional data by using the division plane candidate to generate clusters; a model generator which generates models from the clusters; an evaluation value calculator which calculates an evaluation value on the basis of the generated models and the multi-dimensional data; a division candidate selector which compares evaluation values respectively corresponding to the division plane candidates and selects a division plane candidate having a highest evaluation value; and a data division unit which divides the multi-dimensional data by using the selected division plane candidate.

Claims

1. A data division apparatus which divides multi-dimensional data including a plurality of data pieces, comprising:

a data input unit which inputs the multi-dimensional data;

a division plane candidate creator which creates a plurality of division plane candidates for dividing the multi-dimensional data;

a data provisional division unit which provisionally divides the multi-dimensional data by using the division plane candidates to generate clusters from each of the division plane candidates, the clusters each including one or more data piece;

a model generator which generates models representing the clusters, per each of the division plane candidates;

an evaluation value calculator which calculates evaluation values for evaluating the division plane candidates, on the basis of the models generated associated with the division plane candidates and the multi-dimensional data;

a division candidate selector which compares evaluation values respectively corresponding to the division plane candidates and selects a division plane candidate having a highest evaluation value; and

a data division unit which divides the multi-dimensional data by using the selected division plane candidate.

2. The data division apparatus according to claim 1, wherein the data division unit outputs divided multi-dimensional data obtained by dividing the multi-dimensional data to the division plane candidate creator, and

if the division plane candidate having the highest evaluation value does not satisfy a continuation condition, the division candidate selector outputs a signal indicating processing termination.

3. The data division apparatus according to claim 1, further comprising a data discretization unit which discretizes the multi-dimensional data input by the data input unit,

wherein at least any of the division plane candidate creator, the data provisional division unit, the model generator, the evaluation value calculator, and the data division unit uses discretized multi-dimensional data as the multi-dimensional data.

4. The data division apparatus according to claim 1, wherein the evaluation value calculator calculates the evaluation value on the basis of the generated models, clusters respectively corresponding to the generated models, and the number of data pieces contained in the multi-dimensional data.

5. The data division apparatus according to claim 1, wherein the evaluation value calculator

calculates errors of the generated models on the basis of the generated models and clusters respectively corresponding to the generated models,

divides an error of a model corresponding to the multi-dimensional data by the number of data pieces contained in the multi-dimensional data,

calculates model evaluation values respectively of the models on the basis of the calculated errors of the models, a result value of the dividing, and numbers of data pieces respectively contained in the clusters, and

calculates the evaluation value based on the model evaluation values of the models.

6. The data division apparatus according to claim 5, wherein the evaluation value calculator calculates the model evaluation value of each of the models by subtracting a product of the dividing result value and the number of data pieces contained in each of the clusters and a parameter value from the calculated error of each of the models.

7. The data division apparatus according to claim 5, wherein the evaluation value calculator adopts a minimum value among the model evaluation values of the models as the evaluation value.

8. The data division apparatus according to claim 1, further comprising:

a merging candidate generator which generates a plurality of cluster combinations as merging candidates, from clusters finally generated as a result of division conducted by the data division unit;

a merging candidate selector which selects a merging candidate from the merging candidates;

a further model generator which generates a model from the merging candidate;

a merging evaluation value calculator which calculates an error of the model generated by the further model generator, and calculates a difference between a computed value based on errors of models corresponding to clusters contained in the merging candidate and a computed value based on the error of the model generated by the further model generator, as a merging evaluation value; and

a merging unit which merges clusters included in the merging candidate and generates a new cluster if the merging evaluation value satisfies a merging reference.

9. The data division apparatus according to claim 1, wherein the division candidate selector

generates new division plane candidates between the selected division plane candidate and division plane candidate adjacent to the selected division plane candidate, and outputs the generated new division plane candidates to the data provisional division unit, and

compares an evaluation value corresponding to the selected division plane candidate and evaluation values corresponding to the new division plane candidates, and selects a division plane candidate having a highest evaluation value.

10. The data division apparatus according to claim 9, wherein the division candidate selector generates the new division plane candidates so as to separate data pieces included between the selected division plane candidate and the adjacent division plane candidate.

11. The data division apparatus according to claim 1, wherein

the division plane candidate creator creates a plurality of division plane candidates for each of a plurality of dimension combinations including a common target dimension, the target dimension being a dimension that becomes a target variable at time of model generation, and

the division candidate selector adopts a division plane candidate having a highest evaluation value from among division plane candidates selected respectively from the dimension combinations.

12. The data division apparatus according to claim 11, wherein the dimension combinations include at least one same dimension besides the target dimension.

13. The data division apparatus according to claim 1, wherein the evaluation value calculator comprises:

a class number assigning unit which assigns a class number to clusters after provisional division;

a classification rule generator which generates a classification rule to predict a class number from an explanatory dimension in the multi-dimensional data; and

an expanded evaluation value calculator which calculates an expanded evaluation value based on at least either of precision and size of the classification rule and the evaluation value,

wherein the division candidate selector uses the expanded evaluation value instead of the evaluation value to select a division plane candidate.

14. The data division apparatus according to claim 13, wherein the expanded evaluation value calculator calculates the expanded evaluation value by adding a value obtained by multiplying the precision of the classification rule by a first weighting coefficient and a value obtained by multiplying the size of the classification rule by a second weighting coefficient to the evaluation value.

15. The data division apparatus according to claim 13, wherein the classification rule generator generates a decision tree as the classification rule.

16. The data division apparatus according to claim 1,

wherein the division plane candidate creator creates a plurality of division plane candidates for each of a plurality of dimension combinations including a common target dimension, and

the data division unit outputs finally a plurality of data division results correspondingly to the plurality of dimension combinations, and

the data division apparatus further comprises:

a class number assigning unit which assigns a class number to clusters included in the data division result;

a classification rule generator which generates a classification rule to predict a class number from an explanatory dimension in the multi-dimension data;

an expanded evaluation value calculator which calculates an expanded evaluation value based on models corresponding to the clusters in the data division result, the multi-dimensional data, and at least either of the precision and size of the classification rule; and

a data division selector which selects a data division result having a highest expanded evaluation value.

17. A data division apparatus which divides multi-dimensional data including a plurality of data pieces, comprising:

a data input unit which inputs the multi-dimensional data;

a division plane candidate creator which creates a plurality of division plane candidates for dividing the multi-dimensional data;

a data provisional division unit which provisionally divides the multi-dimensional data by using the division plane candidates to generate clusters from each of the division plane candidates, the clusters each including one or more data piece;

a model generator which generates models representing the clusters, per each of the division plane candidates;

a grouping unit which generates new clusters by grouping data pieces in the multi-dimensional data, based on which of the generated models each data piece in the multi-dimensional data is close to, per each of the division plane candidates;

an evaluation value calculator which calculates evaluation values for evaluating the groupings associated with the division plane candidates, based on the models generated associated with the division plane candidates and the new clusters generated associated with the division plane candidates; and

a division candidate selector which compares evaluation values respectively corresponding to the division plane candidates and selects grouping result corresponding a division plane candidate having a highest evaluation value.

18. The data division apparatus according to claim 17, wherein the evaluation value calculator outputs the generated new clusters to the model generator, and passes a late calculated evaluation value to the division candidate selector.

19. A data division method which divides multi-dimensional data including a plurality of data pieces, comprising:

inputting the multi-dimensional data;

creating a plurality of division plane candidates for dividing the multi-dimensional data;

provisionally dividing the multi-dimensional data by using the division plane candidates to generate clusters from each of the division plane candidates, the clusters each including one or more data piece;

generating models representing the clusters, per each of the division plane candidates;

calculating evaluation values for evaluating the division plane candidates, on the basis of the models generated associated with the division plane candidates and the multi-dimensional data;

comparing evaluation values respectively corresponding to the division plane candidates and selecting a division plane candidate having a highest evaluation value;

dividing the multi-dimensional data by using the selected division plane candidate; and

performing the creating, the dividing, the generating, the calculating, the comparing and the dividing for divided multi-dimensional data.

20. A program for inducing a computer to execute:

reading out multi-dimensional data including a plurality of data pieces, from a storage device;

creating a plurality of division plane candidates for dividing the multi-dimensional data;

provisionally dividing the multi-dimensional data by using the division plane candidates to generate clusters from each of the division plane candidates, the clusters each including one or more data piece;

generating models representing the clusters, per each of the division plane candidates;

calculating evaluation values for evaluating the division plane candidates, on the basis of the models generated associated with the division plane candidates and the multi-dimensional data;

comparing evaluation values respectively corresponding to the division plane candidates and selecting a division plane candidate having a highest evaluation value;

dividing the multi-dimensional data by using the selected division plane candidate; and

performing the creating, the dividing, the generating, the calculating, the comparing, the dividing for divided multi-dimensional data.