Evaluation and cluster formation based on element correlation

• US 20050251514A1
• Filed: 04/13/2005
• Published: 11/10/2005
• Est. Priority Date: 04/14/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Houle, Michael Edward
• Application Number:
  US11/104,936
• Publication Number:
  US 20050251514A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

System for calculating a self-confidence value in selection of a cluster including: evaluation unit selecting a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of a reference number of elements each having a higher correlation with a reference element; a neighbor unit selecting a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of reference number of elements having a higher correlation with the relevant member element; and a confidence unit which calculating, for a combination of two member elements available from the cluster, the number of elements included both in the neighbor element set for one member element of the combination and in the neighbor element set for the other member element, and outputting an average of ratios calculated for all the combinations of member elements, as the self-confidence value.

Claims

1. An evaluation system comprising:

an evaluation target cluster selection unit, wherein said system is for calculating a self-confidence value for a cluster formed by selecting some of a plurality of elements having a predetermined degree of correlation with each other, the self-confidence value indicating a degree of confidence in selection of member elements included in the cluster, said evaluation target cluster selection unit to select a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of a reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection unit to select a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element; and

a confidence value calculation unit to calculate a ratio of the number of elements to the reference number, the elements being included both in the neighbor element set for one member element of a combination of two member elements available from the cluster and in the neighbor element set for the other member element, and which outputs a value based on a sum of the ratios calculated for all the combinations of the member elements, as the self-confidence value.

2. The evaluation system according to claim 1,

wherein the confidence value calculation unit defines, as a relay element, any of the reference number of elements each having the higher correlation with the reference element, calculates, for each of the reference number of elements each having the higher correlation with the relay element, the number of all the relay elements available in order to reach the relevant element, calculates a total number of combinations of two relay elements among all the relay elements available in order to reach the relevant element, and outputs, as the self-confidence value, a value based on a sum of the total numbers of the combinations, each of which is calculated for each element.

10. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an evaluation system, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 1.

3. A cluster formation device for forming a cluster by selecting some of a plurality of elements having a predetermined degree of correlation with each other, comprising:

an evaluation target cluster selection unit which selects a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of a reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection unit which selects a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element;

a confidence value calculation unit which calculates a ratio of the number of elements to the reference number, the elements being included both in the neighbor element set for one member element of each combination of two member elements available from the cluster and in the neighbor element set for the other member element, and which outputs a value based on a sum of the ratios calculated for all the combinations of the member elements, as the self-confidence value; and

an element cluster formation unit which determines that the target cluster for evaluation is a cluster to be formed when the self-confidence value is larger than a predetermined reference value.

4. The cluster formation device according to claim 3,

wherein the cluster formation device is a device which defines a plurality of documents as the plurality of elements, and forms the cluster based on keywords included in the documents,

the evaluation target cluster selection unit selects a neighbor element set being a set of the reference number of documents including a set of keywords more similar to a set of keywords of the relevant document in comparison with a predetermined document, as the target cluster for evaluation,

the neighbor element set selection unit selects a neighbor element set being a set of the reference number of elements including a set of keywords more similar to a set of keywords of the relevant document in comparison with each of the documents included in the cluster,

the confidence value calculation unit calculates a ratio of the number of documents to the reference number, the documents being included both in the neighbor element set for one document of a combination of two documents available from the cluster and in the neighbor element set for the other document, and outputs a value based on a sum of the ratios calculated for all the combinations of the documents, as the self-confidence value, and

the element cluster formation unit determines that the target cluster for evaluation is the cluster to be formed when the self-confidence value is larger than the predetermined reference value.

12. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a cluster formation device, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 3.

5. An evaluation system for calculating an evaluation value of particularity of a cluster in comparison with all of a plurality of elements, for the cluster formed by selecting a predetermined reference number of elements among the plurality of elements having a predetermined degree of correlation with each other, the evaluation system comprising:

an evaluation target cluster selection unit which selects a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of the reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection unit which selects a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element;

a confidence value calculation unit which, based on the neighbor element set selected by the neighbor element set selection unit, calculates a self-confidence value indicating a degree of confidence in selection of member elements included in the cluster;

a theoretical value calculation unit which calculates a theoretical value of a self-confidence value to be calculated by the confidence value calculation unit when it is assumed that the neighbor element set selection unit randomly selects a set of the reference number of elements among the plurality of elements, instead of the neighbor element set; and

an evaluation value calculation unit which calculates and outputs a chi-square test value of a self-confidence value for the theoretical value of the self-confidence value, as the evaluation value.

6. The evaluation system according to claim 5, wherein the confidence value calculation unit calculates, for each of the plurality of member elements, a ratio of elements included in the neighbor element set for the relevant member element among the elements included in the cluster, and outputs a value based on a sum of the ratios calculated for each of the member elements, as the self-confidence value.

7. The evaluation system according to claim 5,

wherein the confidence value calculation unit calculates, for each combination of two member elements available from the cluster, a ratio of the number of elements to the reference number, the elements being included in both in the neighbor element set for one member element of the combination and in the neighbor element set for the other member element, and outputs a value based on a sum of the ratios calculated for all the combinations of the member elements, as the self-confidence value.

11. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an evaluation system, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 5.

8. A cluster formation device for forming a cluster by selecting some of a plurality of elements having a predetermined degree of correlation with each other, comprising:

an evaluation target cluster selection unit which selects a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of a reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection unit which selects a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element;

a confidence value calculation unit which, based on the neighbor element set selected by the neighbor element set selection unit, calculates a self-confidence value indicating a degree of confidence in selection of member elements included in the cluster;

a theoretical value calculation unit which calculates a theoretical value of a self-confidence value to be calculated by the confidence value calculation unit when it is assumed that the neighbor element set selection unit randomly selects a set of the reference number of elements among the plurality of elements, instead of the neighbor element set;

an evaluation value calculation unit which calculates and outputs a chi-square test value of a self-confidence value for the theoretical value of the self-confidence value, as the evaluation value; and

an element cluster formation unit for forming a cluster by allowing the evaluation value calculation unit to calculate the evaluation value for each of clusters varying in the reference number of elements within a predetermined range, and by selecting a cluster of which the calculated evaluation value is the largest.

13. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a cluster formation device, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 8.

9. A cluster formation device for forming a cluster from a plurality of elements each having at least one of a plurality of attributes, comprising:

an element set selection unit which selects a set of elements having an attribute in question, for each of the plurality of attributes;

a correlation degree calculation unit which calculates a correlation degree, indicating a degree of correlation of each of the plurality of attributes with each of the other attributes, based on the number of elements having both an attribute in question and another attribute in question;

an attribute cluster formation unit which forms an attribute cluster having a plurality of attributes between which the correlation degree is equal to or more than a reference, based on the calculated correlation degree; and

an element cluster formation unit which determines a set of elements having at least one of the attributes included in the attribute cluster and which outputs the determined set of elements as the cluster.

20. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a cluster formation device, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 9.

14. An evaluation method comprising:

by using a computer, calculating a self-confidence value for a cluster formed by selecting some of a plurality of elements having a predetermined degree of correlation with each other, the self-confidence value indicating a degree of confidence in selection of member elements included in the cluster, the step of calculating comprising;

by the computer,

an evaluation target cluster selection step of selecting a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of a reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection step of selecting a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element; and

a confidence value calculation step of calculating a ratio of the number of elements to the reference number, the elements being included both in the neighbor element set for one member element of a combination of two member elements available from the cluster and in the neighbor element set for the other member element, and outputting a value based on a sum of the ratios calculated for all the combinations of the member elements, as the self-confidence value.

17. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing evaluation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 14.

15. An evaluation method comprising:

by a computer, calculating an evaluation value of particularity of a cluster in comparison with all of a plurality of elements, for the cluster formed by selecting a predetermined reference number of elements among the plurality of elements having a predetermined degree of correlation with each other, the step of calculating comprising;

by the computer,

an evaluation target cluster selection step of selecting a neighbor element set as a target cluster for evaluation, the neighbor element set being a set of the reference number of elements each having a higher correlation with a predetermined reference element;

a neighbor element set selection step of selecting a neighbor element set for each of member elements included in the cluster, the neighbor element set being a set of the reference number of elements each having a higher correlation with the relevant member element;

a confidence value calculation step of, based on the neighbor element set selected by the neighbor element set selection unit, calculating a self-confidence value indicating a degree of confidence in selection of member elements included in the cluster;

a theoretical value calculation step of calculating a theoretical value of a self-confidence value to be calculated by the confidence value calculation unit when it is assumed that the neighbor element set selection unit randomly selects a set of the reference number-of elements among the plurality of elements, instead of the neighbor element set; and

an evaluation value calculation step of calculating and outputting a chi-square test value of a self-confidence value for the theoretical value of the self-confidence value, as the evaluation value.

18. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing evaluation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 15.

16. A cluster formation method comprising:

by using a computer, forming a cluster from a plurality of elements each having at least one of a plurality of attributes, the step of forming comprising;

by the computer,

an element set selection step of selecting a set of elements having an attribute in question, for each of the plurality of attributes;

a correlation degree calculation step of calculating a correlation degree, indicating a degree of correlation of each of the plurality of attributes with each of the other attributes, based on the number of elements having both an attribute in question and another attribute in question;

an attribute cluster formation step of forming an attribute cluster having a plurality of attributes between which the correlation degree is equal to or more than a reference, based on the calculated correlation degree; and

an element cluster formation step of determining a set of elements having at least one of the attributes included in the attribute cluster, and outputting the determined set of elements as the cluster.

19. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing cluster formation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 16.