CROSS-DOMAIN CLUSTERABILITY EVALUATION FOR CROSS-GUIDED DATA CLUSTERING BASED ON ALIGNMENT BETWEEN DATA DOMAINS

• US 20110167064A1
• Filed: 01/06/2010
• Published: 07/07/2011
• Est. Priority Date: 01/06/2010
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: BHATTACHARYA, INDRAJIT, JOSHI, SACHINDRA, ACHTERMANN, JEFFREY M., ENGLISH, KEVIN W. Jr., GODBOLE, SHANTANU R., VERMA, ASHISH, SRINIVASAN, ASHWIN
• Granted Patent: US 8,229,929 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system and associated method for evaluating cross-domain clusterability upon a target domain and a source domain. The cross-domain clusterability is calculated as a linear combination of a target clusterability and a source-target pair matchability, by use of a trade-off parameter that determines relative contribution of the target clusterability and the source-target pair matchability. The target clusterability quantifies how clusterable the target domain is. The source-target pair matchability is calculated as an average of a target-side matchability and a source-side matchability, which quantifies how well target centroids of the target domain are aligned with the source centroids and how well source centroids of the source domain are aligned with the target centroids, respectively.

Claims

1. A method for evaluating cross-domain clusterability upon a target domain and a source domain, said method comprising:

a processor of a computer system receiving the source domain and the target domain, wherein the source domain comprises at least one source data item and the target domain comprises at least one target data item;

said processor calculating target clusterability as an average of a respective clusterability of said at least one target data item such that the target clusterability quantifies how clusterable the target domain is, wherein the respective clusterability of a target data item of said at least one target data item quantifies how unambiguously the target data item can be assigned to a respective true target centroid associated with the target data item;

said processor calculating target-side matchability as an average of a respective matchability of each target centroid of the target domain to source centroids of the source domain such that the target-side matchability quantifies how well target centroids of the target domain are aligned with the source centroids;

said processor calculating source-side matchability as an average of a respective matchability of each source centroid of said source centroids to the target centroids such that the source-side matchability quantifies how well the source centroids are aligned with the target centroids;

said processor calculating source-target pair matchability as an average of the target-side matchability and the source-side matchability;

said processor calculating cross-domain clusterability between the target domain and the source domain as a linear combination of the calculated target clusterability and the calculated source-target pair matchability by use of a trade-off parameter that indicates relative contribution of the target clusterability and the source-target pair matchability to the cross-domain clusterability; and

said processor transferring the calculated cross-domain clusterability to a device selected from an output device of the computer system, a storage device of the computer system, a remote computer system coupled to the computer system, and a combination thereof.

2. The method of claim 1, wherein the target clusterability Cab(T| C^t) is Cab(T| C^t)=Σ

<sub>{tiε

T}</sub>Cab(t_i| C^t)/|T|, wherein the respective clusterability Cab(t_i| C^t) of an i-th target data item t_i of said at least one target data item of the target domain T is Cab(t_i| C^t)=sim(t_i, C_*^t(t_i))−

max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim(t_i, C_j^t) is a respective similarity of the i-th target data item t_i to a respective true target centroid of the i-th target data item t_i, denoted as C_*^t(t_i), and wherein a second term max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t) is a largest value among all respective similarities of each target data item t_i to a respective target centroid C_j^t that is not the respective true target centroid C_*^t(t_i).

3. The method of claim 1, wherein the target-side matchability Mab( C^t| C^s) is Mab( C^t| C^s)=Σ

_CitMab( C_i^t| C^s)/|C^t|, wherein the respective matchability Mab( C^t| C^s) of an i-th target centroid C_i^t of the target domain to the source centroids C^s is Mab( C_i^t| C^s)=sim^x( C_i^t, C_*^s( C_i^t))−

max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_i^t, C_*^s( C_i^t)) is a first cross-domain similarity between the i-th target centroid C_i^t and a nearest source centroid C_*^s( C_i^t), the first term being the largest value among all similarity values between the i-th target centroid C_i^t and the source centroids C^s, and wherein a second term max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s) is a largest value among all cross-domain domain similarities between the i-th target centroid C_i^t and a respective source centroid C_j^s that is not the nearest source centroid C_*^s( C_i^t).

4. The method of claim 1, wherein the source-side matchability Mab( C^s| C^t) is Mab( C^s| C^t)=Σ

_CjsMab( C_j^s| C^t)/|C_s|, wherein the respective matchability Mab( C_j^s| C^t) of a j-th source centroid C_j^s of the source domain to the target centroids C^t is Mab( C_j^s| C^t)=sim^x( C_j^s, C_*^t( C_j^s))−

max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_j^s, C_*^t( C_j^s)) is a first cross-domain similarity between the j-th source centroid and a nearest target centroid C_*^t( C_j^s), the first term being the largest value among all similarity values between the j-th source centroid C_j^s and the target centroids C^t, and wherein a second term max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t) is a largest value among all cross-domain similarities between the j-th source centroid C_j^s and a respective target centroid C_i^t that is not the nearest target centroid C_*^t( C_j^s).

5. The method of claim 1, wherein the cross-domain clusterability Cab(T|C^s,C^t) between the target domain and the source domain is Cab(T|C^s,C^t)=α

Cab(T|C^t)+(1−

α

)Mab(C^s,C^t), wherein the calculated target clusterability Cab(T|C^t) has a value from a first range of [−

1.0,+1.0], wherein the calculated source-target pair matchability Mab(C^s,C^t) has a value from a second range of [0.0, 1.0], and wherein the trade-off parameter α

has a value from a third range of [0.0, 1.0].

6. A computer program product comprising:

a computer readable storage medium having a computer readable program code embodied therein, said computer readable program code containing instructions that perform a method for evaluating cross-domain clusterability upon a target domain and a source domain, said method comprising;

receiving the source domain and the target domain, wherein the source domain comprises at least one source data item and the target domain comprises at least one target data item;

calculating target clusterability as an average of a respective clusterability of said at least one target data item such that the target clusterability quantifies how clusterable the target domain is, wherein the respective clusterability of a target data item of said at least one target data item quantifies how unambiguously the target data item can be assigned to a respective true target centroid associated with the target data item;

calculating target-side matchability as an average of a respective matchability of each target centroid of the target domain to source centroids of the source domain such that the target-side matchability quantifies how well target centroids of the target domain are aligned with the source centroids;

calculating source-side matchability as an average of a respective matchability of each source centroid of said source centroids to the target centroids such that the source-side matchability quantifies how well the source centroids are aligned with the target centroids;

calculating source-target pair matchability as an average of the target-side matchability and the source-side matchability;

calculating cross-domain clusterability between the target domain and the source domain as a linear combination of the calculated target clusterability and the calculated source-target pair matchability by use of a trade-off parameter that indicates relative contribution of the target clusterability and the source-target pair matchability to the cross-domain clusterability; and

transferring the calculated cross-domain clusterability to a device selected from an output device of a computer system, a storage device of the computer system, a remote computer system coupled to the computer system, and a combination thereof.

7. The computer program product of claim 6, wherein the target clusterability Cab(T| C^t) is Cab(T| C^t)=Σ

<sub>{tiε

T}</sub>Cab(t_i| C^t)/|T|, wherein the respective clusterability Cab(t_i| C^t) of an i-th target data item t_i of said at least one target data item of the target domain T is Cab(t_i| C^t)=sim(t_i, C_*^t (t_i))−

max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim(t_i, C_j^t) is a respective similarity of the i-th target data item t_i to a respective true target centroid of the i-th target data item t_i, denoted as C_*^t(t_i), and wherein a second term max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t) is a largest value among all respective similarities of each target data item t_i to a respective target centroid C_j^t that is not the respective true target centroid C_*^t(t_i).

8. The computer program product of claim 6, wherein the target-side matchability Mab( C^t| C^s) is Mab( C^t| C^s)=Σ

_CitMab( C_i^t| C^s)/|C^t|, wherein the respective matchability Mab( C_i^t| C^s) of an i-th target centroid C_i^t of the target domain to the source centroids C^s is Mab( C_i^t| C^s)=sim^x( C_i^t, C_*^s( C_i^t))−

max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s, for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_i^t, C_*^s( C_i^t)) is a first cross-domain similarity between the i-th target centroid C_i^t and a nearest source centroid C_*^s( C_i^t), the first term being the largest value among all similarity values between the i-th target centroid C_i^t and the source centroids C^s, and wherein a second term max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s) is a largest value among all cross-domain domain similarities between the i-th target centroid C_i^t and a respective source centroid C_j^s that is not the nearest source centroid C_*^s( C_i^t).

9. The computer program product of claim 6, wherein the source-side matchability Mab( C^s| C^t) is Mab( C^s| C^t)=Σ

_Cjs Mab( C_j^s| C^t)/|C^s|, wherein the respective matchability Mab( C_j^s| C^t) of a j-th source centroid C_j^s of the source domain to the target centroids C^t is Mab( C_j^s| C^t)=sim^x( C_j^s, C_*^t( C_j^s))−

max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_j^s, C_*^t( C_j^s)) is a first cross-domain similarity between the j-th source centroid C_j^s and a nearest target centroid C_*^t( C_j^s), the first term being the largest value among all similarity values between the j-th source centroid C_j^s and the target centroids C^t, and wherein a second term max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t) is a largest value among all cross-domain similarities between the j-th source centroid C_j^s and a respective target centroid C_i^t that is not the nearest target centroid C_*^t( C_j^s).

10. The computer program product of claim 6, wherein the cross-domain clusterability Cab(T|C^s,C^t) between the target domain T and the source domain is Cab(T|C^s,C^t)=α

Cab(T|C^t)+(1−

α

)Mab(C^s,C^t), wherein the calculated target clusterability Cab(T|C^t) has a value from a first range of [−

1.0,+1.0], wherein the calculated source-target pair matchability Mab(C^s,C^t) has a value from a second range of [0.0, 1.0], and wherein the trade-off parameter α

has a value from a third range of [0.0, 1.0].

11. A computer system comprising a processor and a computer readable memory unit coupled to the processor, said computer readable memory unit containing instructions that when run by the processor implement a method for evaluating cross-domain clusterability upon a target domain and a source domain, said method comprising:

receiving the source domain and the target domain, wherein the source domain comprises at least one source data item and the target domain comprises at least one target data item;

calculating target clusterability as an average of a respective clusterability of said at least one target data item such that the target clusterability quantifies how clusterable the target domain is, wherein the respective clusterability of a target data item of said at least one target data item quantifies how unambiguously the target data item can be assigned to a respective true target centroid associated with the target data item;

calculating target-side matchability as an average of a respective matchability of each target centroid of the target domain to source centroids of the source domain such that the target-side matchability quantifies how well target centroids of the target domain are aligned with the source centroids;

calculating source-side matchability as an average of a respective matchability of each source centroid of said source centroids to the target centroids such that the source-side matchability quantifies how well the source centroids are aligned with the target centroids;

calculating source-target pair matchability as an average of the target-side matchability and the source-side matchability;

calculating cross-domain clusterability between the target domain and the source domain as a linear combination of the calculated target clusterability and the calculated source-target pair matchability by use of a trade-off parameter that indicates relative contribution of the target clusterability and the source-target pair matchability to the cross-domain clusterability; and

transferring the calculated cross-domain clusterability to a device selected from an output device of the computer system, a storage device of the computer system, a remote computer system coupled to the computer system, and a combination thereof.

12. The computer system of claim 11, wherein the target clusterability Cab(T| C^t) is Cab(T| C^t)=Σ

<sub>{tiε

T}</sub>Cab(t_i| C^t))/|T|, wherein the respective clusterability Cab(t_i| C^t) of an i-th target data item t_i of said at least one target data item of the target domain T is Cab(t_i| C^t)=sim(t_i, C_*^t(t_i))−

max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim(t_i, C_j^t) is a respective similarity of the i-th target data item t_i to a respective true target centroid of the i-th target data item t_i, denoted as C_*^t(t_i), and wherein a second term max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t) is a largest value among all respective similarities of each target data item t_i to a respective target centroid C_j^t that is not the respective true target centroid C_*^t(t_i).

13. The computer system of claim 11, wherein the target-side matchability Mab( C^t| C^s) is Mab( C^t| C^s)=Σ

_CitMab( C_i^t| C^s)/|C^t|, wherein the respective matchability Mab( C_i^t| C^s) of an i-th target centroid C_i^t of the target domain to the source centroids C^s is Mab( C_i^t| C^s)=sim^x( C_i^t, C_*^s( C_i^t))−

max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_i^t, C_*^s( C_i^t)) is a first cross-domain similarity between the i-th target centroid C_i^t and a nearest source centroid C_*^s( C_i^t), the first term being the largest value among all similarity values between the i-th target centroid C_i^t and the source centroids C^s, and wherein a second term max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s) is a largest value among all cross-domain domain similarities between the i-th target centroid C_i^t and a respective source centroid C_j^s that is not the nearest source centroid C_*^s ( C_i^t).

14. The computer system of claim 11, wherein the source-side matchability Mab( C^s| C^t) is Mab( C^s| C^t)=Σ

_CjsMab( C_j^s| C^t)/|C^s|, wherein the respective matchability Mab( C_j^s| C^t) of a j-th source centroid C_j^s of the source domain to the target centroids C^t is Mab( C_j^s| C^t)=sim^x( C_j^s, C_*^t( C_j^s)−

max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_j^s, C_*^t( C_j^s)) is a first cross-domain similarity between the j-th source centroid C_j^s and a nearest target centroid C_*^t( C_j^s), the first term being the largest value among all similarity values between the j-th source centroid C_j^s and the target centroids C^t, and wherein a second term max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t) is a largest value among all cross-domain similarities between the j-th source centroid C_j^s and a respective target centroid C_i^t that is not the nearest target centroid C_*^t( C_j^s).

15. The computer system of claim 11, wherein the cross-domain clusterability Cab(T|C^s,C^t) between the target domain T and the source domain is Cab(T|C^s,C^t)=α

Cab(T|C^t)+(1−

α

)Mab(C^s,C^t), wherein the calculated target clusterability Cab(T|C^t) has a value from a first range of [−

1.0,+1.0], wherein the calculated source-target pair matchability Mab(C^s,C^t) has a value from a second range of [0.0, 1.0], and wherein the trade-off parameter α

has a value from a third range of [0.0, 1.0].

16. A process for supporting computer infrastructure, said process comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable code in a computing system, wherein the code in combination with the computing system is capable of performing a method for evaluating cross-domain clusterability upon a target domain and a source domain, said method comprising:

receiving the source domain and the target domain, wherein the source domain comprises at least one source data item and the target domain comprises at least one target data item;

calculating target clusterability as an average of a respective clusterability of said at least one target data item such that the target clusterability quantifies how clusterable the target domain is, wherein the respective clusterability of a target data item of said at least one target data item quantifies how unambiguously the target data item can be assigned to a respective true target centroid associated with the target data item;

calculating target-side matchability as an average of a respective matchability of each target centroid of the target domain to source centroids of the source domain such that the target-side matchability quantifies how well target centroids of the target domain are aligned with the source centroids;

calculating source-side matchability as an average of a respective matchability of each source centroid of said source centroids to the target centroids such that the source-side matchability quantifies how well the source centroids are aligned with the target centroids;

calculating source-target pair matchability as an average of the target-side matchability and the source-side matchability;

calculating cross-domain clusterability between the target domain and the source domain as a linear combination of the calculated target clusterability and the calculated source-target pair matchability by use of a trade-off parameter that indicates relative contribution of the target clusterability and the source-target pair matchability to the cross-domain clusterability; and

transferring the calculated cross-domain clusterability to a device selected from an output device of the computer system, a storage device of the computer system, a remote computer system coupled to the computer system, and a combination thereof.

17. The process of claim 16, wherein the target clusterability Cab(T| C^t) is Cab(T| C^t)=Σ

<sub>{tiε

T}</sub>Cab(t_i| C^t)/|T|, wherein the respective clusterability Cab(t_i| C^t) of an i-th target data item t_i of said at least one target data item of the target domain T is Cab(t_i| C^t)=sim(t_i, C_*^t(t_i))−

max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim(t_i, C_j^t) is a respective similarity of the i-th target data item t_i to a respective true target centroid of the i-th target data item t_i, denoted as C_*^t(t_i), and wherein a second term max<sub>{ Cjt≠

C*t(ti)}</sub>sim(t_i, C_j^t) is a largest value among all respective similarities of each target data item t_i to a respective target centroid C_j^t that is not the respective true target centroid C_*^t(t_i).

18. The process of claim 16, wherein the target-side matchability Mab( C^t| C^s) is Mab( C^t| C^s)=Σ

_CitMab( C_i^t| C^s)/|C^t|, wherein the respective matchability Mab( C_i^t| C^s) of an i-th target centroid C_i^t of the target domain to the source centroids C^S is Mab( C_i^t| C^s)=sim^x( C_i^t, C_*^s( C_i^t))−

max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_i^t, C_*^s( C_i^t)) is a first cross-domain similarity between the i-th target centroid C_i^t and a nearest source centroid C_*^s( C_i^t), the first term being the largest value among all similarity values between the i-th target centroid C_i^t and the source centroids C^s, and wherein a second term max<sub>{ Cjs≠

C*s( Cit)}</sub>sim^x( C_i^t, C_j^s) is a largest value among all cross-domain domain similarities between the i-th target centroid C_i^t and a respective source centroid C_j^s that is not the nearest source centroid C_*^s( C_i^t).

19. The process of claim 16, wherein the source-side matchability Mab( C^s| C^t) is Mab( C^s| C^t)=Σ

_CjsMab( C_j^s| C^t)/|C^s|, wherein the respective matchability Mab( C_j^s| C^t) of a j-th source centroid C_j^s of the source domain to the target centroids C^t is Mab( C_j^s| C^t)=sim^x( C_j^s, C_*^t( C_j^s))−

max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s,C_i^t), for integer i being greater than or equal to 1 and smaller than or equal to k, wherein a first term sim^x( C_j^s, C_*^t( C_j^s)) is a first cross-domain similarity between the j-th source centroid C_j^s and a nearest target centroid C_*^t( C_j^s), the first term being the largest value among all similarity values between the j-th source centroid C_j^s and the target centroids C^t, and wherein a second term max<sub>{ Cit≠

C*t( Cjs)}</sub>sim^x( C_j^s, C_i^t) is a largest value among all cross-domain similarities between the j-th source centroid C_j^s and a respective target centroid C_i^t that is not the nearest target centroid C_*^t( C_j^s).

20. The process of claim 16, wherein the cross-domain clusterability Cab(T|C^s,C^t) between the target domain T and the source domain is Cab(T|C^s,C^t)=α

Cab(T|C^t)+(1−

α

)Mab(C^s,C^t), wherein the calculated target clusterability Cab(T|C^t) has a value from a first range of [−

1.0, +1.0], wherein the calculated source-target pair matchability Mab(C^s,C^t) has a value from a second range of [0.0, 1.0], and wherein the trade-off parameter α

has a value from a third range of [0.0, 1.0].