System and method for content-aware co-clustering algorithm based on hourglass model

• US 7,945,668 B1
• Filed: 08/21/2009
• Issued: 05/17/2011
• Est. Priority Date: 08/21/2009
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: Narus, Inc. (Gen Digital Inc.)
• Inventors: Keralapura, Ram, Nucci, Antonio
• Primary Examiner(s): Dharia; Rupal D
• Assistant Examiner(s): HENRY, MARIEGEORGES A
• Application Number:
  US12/545,750
• Time in Patent Office: 634 Days
• Field of Search: 709/223, 709/225, 707/999.001
• US Class Current: 709/225
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method for performing a network operation is disclosed. The method includes obtaining an association matrix representing association parameters between first entities and second entities of the network, generating a reduced matrix of the association matrix by aggregating the first entities into a reduced number of representative entities, partitioning a set containing the representative entities and the second entities into intermediate co-clusters based on a reduced-matrix based cohesiveness criterion, generating an expanded intermediate co-cluster from an intermediate co-cluster, partitioning the expanded intermediate co-cluster into final co-clusters based on an association-matrix based cohesiveness criterion, generating a profile of network activities based on the final co-clusters, and performing the network operation based on the profile of the network activities.

Claims

1. A method for performing a network operation, comprising:

obtaining an association matrix having a plurality of columns corresponding to a plurality of first entities in the network and a plurality of rows corresponding to a plurality of second entities in the network, wherein an element of the association matrix in a column corresponding to a first entity of the plurality of the first entities and in a row corresponding to a second entity of the plurality of the second entities represents an association parameter between the first entity and the second entity;

generating a reduced matrix of the association matrix by aggregating the plurality of columns based on a pre-determined mapping from the plurality of the first entities into a plurality of representative entities, wherein an element of the reduced matrix in a column corresponding to a first representative entity of the plurality of the representative entities and in the row corresponding to the second entity of the plurality of the second entities represents an association parameter between the first representative entity and the second entity;

partitioning, using a processor of a computer, a set comprising the plurality of representative entities and the plurality of second entities into a plurality of intermediate co-clusters based on a first cohesiveness criterion associated with the reduced matrix;

wherein an intermediate co-cluster of the plurality of intermediate co-clusters comprises one or more representative entities of the plurality of representative entities and one or more second entities of the plurality of the second entities;

mapping the one or more representative entities to corresponding first entities within the plurality of first entities based on a reversal of the pre-determined mapping to generate an expanded intermediate co-cluster from the intermediate co-cluster;

wherein the expanded intermediate co-cluster comprises the corresponding first entities and the one or more second entities;

partitioning, using the processor of the computer, the expanded intermediate co-cluster into a plurality of final co-clusters based on a second cohesiveness criterion associated with the association matrix;

generating a profile of network activities based on the plurality of final co-clusters; and

performing the network operation based on the profile of the network activities.

2. The method of claim 1, wherein the partitioning the set comprises:

forming a hierarchical tree of co-clusters associated with the reduced-matrix based on the set comprising the plurality of representative entities and the plurality of second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a first cohesiveness metric, associated with the reduced matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the first cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and the first cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a representative entity from the children co-cluster to add to the another children co-cluster, and

when the first cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of intermediate co-clusters.

3. The method of claim 2,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two representative entities and at least two second entities.

4. The method of claim 2,

wherein the leaf co-cluster comprises a portion of the plurality of representative entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of representative entities and a subset of the portion of the plurality of second entities,

wherein the first cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (representative entity, second entity) pairs within the children co-cluster to a sum of weights of (representative entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the reduced matrix.

5. The method of claim 1, wherein the partitioning the expanded intermediate co-cluster comprises:

forming a hierarchical tree of co-clusters associated with the expanded intermediate co-cluster based on the corresponding first entities and the one or more second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a second cohesiveness metric, associated with the association-matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the second cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and the second cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a first entity from the children co-cluster to add to the another children co-cluster; and

when the second cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of final co-clusters.

6. The method of claim 5,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two first entities and at least two second entities.

7. The method of claim 5,

wherein the leaf co-cluster comprises a portion of the plurality of first entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of first entities and a subset of the portion of the plurality of second entities,

wherein the second cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (first entity, second entity) pairs within the children co-cluster to a sum of weights of (first entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the association matrix.

8. The method of claim 1, wherein a (first entity, second entity) pair of the association matrix comprises at least one of (browsed website, browsing user), (account metric, account user), (word, document containing word), (VoIP speech metric, speaker), and (image feature, image containing image feature).

9. A non-transitory computer readable medium, embodying instructions when executed by the computer to perform a network operation, the instructions comprising functionality for:

obtaining an association matrix having a plurality of columns corresponding to a plurality of first entities in the network and a plurality of rows corresponding to a plurality of second entities in the network, wherein an element of the association matrix in a column corresponding to a first entity of the plurality of the first entities and in a row corresponding to a second entity of the plurality of the second entities represents an association parameter between the first entity and the second entity;

generating a reduced matrix of the association matrix by aggregating the plurality of columns based on a pre-determined mapping from the plurality of the first entities into a plurality of representative entities, wherein an element of the reduced matrix in a column corresponding to a first representative entity of the plurality of the representative entities and in the row corresponding to the second entity of the plurality of the second entities represents an association parameter between the first representative entity and the second entity;

partitioning, using a processor of a computer, a set comprising the plurality of representative entities and the plurality of second entities into a plurality of intermediate co-clusters based on a first cohesiveness criterion associated with the reduced matrix;

wherein an intermediate co-cluster of the plurality of intermediate co-clusters comprises one or more representative entities of the plurality of representative entities and one or more second entities of the plurality of the second entities;

mapping the one or more representative entities to corresponding first entities within the plurality of first entities based on a reversal of the pre-determined mapping to generate an expanded intermediate co-cluster from the intermediate co-cluster;

wherein the expanded intermediate co-cluster comprises the corresponding first entities and the one or more second entities;

partitioning, using the processor of the computer, the expanded intermediate co-cluster into a plurality of final co-clusters based on a second cohesiveness criterion associated with the association matrix;

generating a profile of network activities based on the plurality of final co-clusters; and

performing the network operation based on the profile of the network activities.

10. The non-transitory computer readable medium of claim 9, wherein the partitioning the set comprises:

forming a hierarchical tree of co-clusters associated with the reduced-matrix based on the set comprising the plurality of representative entities and the plurality of second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a first cohesiveness metric, associated with the reduced matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the first cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and a reduced-matrix based cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a representative entity from the children co-cluster to add to the another children co-cluster, and

when the first cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of intermediate co-clusters.

11. The non-transitory computer readable medium of claim 10,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two representative entities and at least two second entities.

12. The non-transitory computer readable medium of claim 10,

wherein the leaf co-cluster comprises a portion of the plurality of representative entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of representative entities and a subset of the portion of the plurality of second entities,

wherein the first cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (representative entity, second entity) pairs within the children co-cluster to a sum of weights of (representative entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the reduced matrix.

13. The non-transitory computer readable medium of claim 9, wherein the partitioning the expanded intermediate co-cluster comprises:

forming a hierarchical tree of co-clusters associated with the expanded intermediate co-cluster based on the corresponding first entities and the one or more second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a second cohesiveness metric, associated with the association-matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the second cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and the second cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a first entity from the children co-cluster to add to the another children co-cluster; and

when the second cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of final co-clusters.

14. The non-transitory computer readable medium of claim 13,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two first entities and at least two second entities.

15. The non-transitory computer readable medium of claim 13,

wherein the leaf co-cluster comprises a portion of the plurality of first entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of first entities and a subset of the portion of the plurality of second entities,

wherein the second cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (first entity, second entity) pairs within the children co-cluster to a sum of weights of (first entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the association matrix.

16. The non-transitory computer readable medium of claim 9, wherein a (first entity, second entity) pair of the association matrix comprises at least one of (browsed website, browsing user), (account metric, account user), (word, document containing word), (VoIP speech metric, speaker), and (image feature, image containing image feature).

17. A system for performing a network operation, comprising:

a processor; and

memory storing instructions when executed by the processor comprising functionalities for;

obtaining an association matrix having a plurality of columns corresponding to a plurality of first entities in the network and a plurality of rows corresponding to a plurality of second entities in the network, wherein an element of the association matrix in a column corresponding to a first entity of the plurality of the first entities and in a row corresponding to a second entity of the plurality of the second entities represents an association parameter between the first entity and the second entity;

generating a reduced matrix of the association matrix by aggregating the plurality of columns based on a pre-determined mapping from the plurality of the first entities into a plurality of representative entities, wherein an element of the reduced matrix in a column corresponding to a first representative entity of the plurality of the representative entities and in the row corresponding to the second entity of the plurality of the second entities represents an association parameter between the first representative entity and the second entity;

partitioning, using a processor of a computer, a set comprising the plurality of representative entities and the plurality of second entities into a plurality of intermediate co-clusters based on a first cohesiveness criterion associated with the reduced matrix;

wherein an intermediate co-cluster of the plurality of intermediate co-clusters comprises one or more representative entities of the plurality of representative entities and one or more second entities of the plurality of the second entities;

mapping the one or more representative entities to corresponding first entities within the plurality of first entities based on a reversal of the pre-determined mapping to generate an expanded intermediate co-cluster from the intermediate co-cluster;

wherein the expanded intermediate co-cluster comprises the corresponding first entities and the one or more second entities;

partitioning, using the processor of the computer, the expanded intermediate co-cluster into a plurality of final co-clusters based on a second cohesiveness criterion associated with the association matrix;

generating a profile of network activities based on the plurality of final co-clusters; and

performing the network operation based on the profile of the network activities.

18. The system of claim 17, wherein the partitioning the set comprises:

forming a hierarchical tree of co-clusters associated with the reduced-matrix based on the set comprising the plurality of representative entities and the plurality of second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a first cohesiveness metric, associated with the reduced matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the first cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and a reduced-matrix based cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a representative entity from the children co-cluster to add to the another children co-cluster, and

when the first cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of intermediate co-clusters.

19. The system of claim 18,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two representative entities and at least two second entities.

20. The system of claim 18,

wherein the leaf co-cluster comprises a portion of the plurality of representative entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of representative entities and a subset of the portion of the plurality of second entities,

wherein the first cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (representative entity, second entity) pairs within the children co-cluster to a sum of weights of (representative entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the reduced matrix.

21. The system of claim 17, wherein the partitioning the expanded intermediate co-cluster comprises:

forming a hierarchical tree of co-clusters associated with the expanded intermediate co-cluster based on the corresponding first entities and the one or more second entities;

recursively partitioning a leaf co-cluster of the hierarchical tree to expand the hierarchical tree, using the processor of the computer, when a second cohesiveness metric, associated with the association-matrix, of a children co-cluster generated by partitioning the leaf co-cluster exceeds a pre-determined threshold, wherein the children co-cluster is attached to the leaf co-cluster in the hierarchical tree thus turning the leaf co-cluster into a parent of the children co-cluster and turning the children co-cluster into another leaf co-cluster;

when the second cohesiveness metric of the children co-cluster exceeds the pre-determined threshold and the second cohesiveness metric of another children co-cluster generated by partitioning the leaf co-cluster is less than the pre-determined threshold, borrowing a first entity from the children co-cluster to add to the another children co-cluster; and

when the second cohesiveness metric of each of all children co-clusters generated by partitioning the leaf co-cluster is less than the pre-determined threshold, assigning the leaf co-cluster as one of the plurality of final co-clusters.

22. The system of claim 21,

wherein each partitioning step of the recursively partitioning step generates two children co-clusters;

and

wherein the leaf co-cluster is partitioned only when the leaf co-cluster comprises at least two first entities and at least two second entities.

23. The system of claim 21,

wherein the leaf co-cluster comprises a portion of the plurality of first entities and a portion of the plurality of second entities,

wherein the children co-cluster comprises a subset of the portion of the plurality of first entities and a subset of the portion of the plurality of second entities,

wherein the second cohesiveness metric of the children co-cluster is defined as a ratio of a sum of weights of (first entity, second entity) pairs within the children co-cluster to a sum of weights of (first entity, second entity) pairs within the leaf co-cluster that originates from the children co-cluster, and

wherein each of the weights is determined from a corresponding element in the association matrix.

24. The system of claim 17, wherein a (first entity, second entity) pair of the association matrix comprises at least one of (browsed website, browsing user), (account metric, account user), (word, document containing word), (VoIP speech metric, speaker), and (image feature, image containing image feature).