Analysis of clustered data
A method may include obtaining a set of tags and a set of items in which each item is pre-sorted into a cluster and each item corresponds to one or more tags. The method may include generating a bipartite graph that includes the set of tags as a first set of nodes and the clusters of items as a second set of nodes. Relationships between tags and items may be represented as edges between the first nodes and the second nodes. The bipartite graph may be modeled as a quadratic programming formulation, and cluster descriptor sets that each include one or more of the tags may be determined by solving the quadratic programming formulation of the bipartite graph, each of the cluster descriptor sets providing an explanation of how one or more clusters of items were pre-sorted. The method may include analyzing the items based on the luster descriptor sets.
1 . A method, comprising:
obtaining a set of tags and a set of items, wherein each item of the set of items is pre-sorted into a cluster by an unsupervised machine learning model and each item corresponds to one or more tags included in the set of tags;
generating a graph that includes the set of tags as a first set of nodes and the clusters of items as a second set of nodes of the graph, wherein relationships between tags and items are represented as edges between first nodes associated with the first set of nodes and second nodes associated with the second set of nodes;
modeling the graph as a quadratic programming formulation;
converting the quadratic programming formulation into a quadratic unconstrained binary optimization (QUBO) problem, the converting into the QUBO problem allowing for solving of the quadratic programming formulation using a digital annealer, wherein the quadratic programming formulation of the graph includes one or more weights corresponding to one or more metrics including at least one of: a tag redundancy, a node coverage, a tag balance, and a tag locality that indicates a degree to which the tags provide indication of how the one or more clusters of items were pre-sorted, and
the quadratic programming formulation is represented by
min
∑
l
=
1
k
∑
j
∈
T
x
l
(
j
)
-
P
1
∑
l
=
1
k
∑
i
,
j
∈
T
B
i
,
j
x
l
(
i
)
x
l
(
j
)
+
P
2
∑
l
=
1
k
∑
i
∈
C
l
(
1
-
z
(
i
)
)
∑
j
∈
t
i
x
l
(
j
)
“x l (j)” represents a first binary function, “T” represents the set of tags, “C l ” represents the cluster, “z(i)” represents a second binary function, “B i,j ” represents a n×n modularity matrix corresponding to the graph, “P 1 ” and “P 2 ” represent weighting parameters in which “P 1 ” represents a tag locality and “P 2 ” represents uncovered items included in the cluster;
solving the QUBO problem using the digital annealer;
determining one or more cluster descriptor sets that each include one or more of the tags based on the solving of the QUBO problem, each of the cluster descriptor sets providing an indication of how one or more clusters of items were pre-sorted;
analyzing the set of items based on the one or more cluster descriptor sets; and
providing an explanation regarding clustering of the set of items by the unsupervised machine learning model based on the analyzing of the set of items.
2 . The method of claim 1 , wherein the set of tags is a plurality of hashtags and the set of items is a plurality of user accounts on a social media platform.
3 . The method of claim 1 , wherein the set of tags is a plurality of image labels and the set of items is a plurality of images.
4 . The method of claim 1 , wherein the set of tags is a plurality of gene characteristics and the set of items is a plurality of gene sequences.
5 . One or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed, cause a system to perform operations, the operations comprising:
obtaining a set of tags and a set of items, wherein each item of the set of items is pre-sorted into a cluster by an unsupervised machine learning model and each item corresponds to one or more tags included in the set of tags;
generating a graph that includes the set of tags as a first set of nodes and the clusters of items as a second set of nodes of the graph, wherein relationships between tags and items are represented as edges between first nodes associated with the first set of nodes and second nodes associated with the second set of nodes;
modeling the graph as a quadratic programming formulation;
converting the quadratic programming formulation into a quadratic unconstrained binary optimization (QUBO) problem, the converting into the QUBO problem allowing for solving of the quadratic programming formulation using a digital annealer, wherein the quadratic programming formulation of the graph includes one or more weights corresponding to one or more metrics including at least one of: a tag redundancy, a node coverage, a tag balance, and a tag locality that indicates a degree to which the tags provide indication of how the one or more clusters of items were pre-sorted, and
the quadratic programming formulation is represented by
min
∑
l
=
1
k
∑
j
∈
T
x
l
(
j
)
-
P
1
∑
l
=
1
k
∑
i
,
j
∈
T
B
i
,
j
x
l
(
i
)
x
l
(
j
)
+
P
2
∑
l
=
1
k
∑
i
∈
C
l
(
1
-
z
(
i
)
)
∑
j
∈
t
i
x
l
(
j
)
“x l (j)” represents a first binary function, “T” represents the set of tags, “C l ” represents the cluster, “z(i)” represents a second binary function, “B i,j ” represents a n×n modularity matrix corresponding to the graph, “P 1 ” and “P 2 ” represent weighting parameters in which “P 1 ” represents a tag locality and “P 2 ” represents uncovered items included in the cluster;
solving the QUBO problem using the digital annealer;
determining one or more cluster descriptor sets that each include one or more of the tags based on the solving of the QUBO problem, each of the cluster descriptor sets providing an indication of how one or more clusters of items were pre-sorted;
analyzing the set of items based on the one or more cluster descriptor sets; and
providing an explanation regarding clustering of the set of items by the unsupervised machine learning model based on the analyzing of the set of items.
6 . The one or more non-transitory computer-readable storage media of claim 5 , wherein the set of tags is a plurality of hashtags and the set of items is a plurality of user accounts on a social media platform.
7 . The one or more non-transitory computer-readable storage media of claim 5 , wherein the set of tags is a plurality of image labels and the set of items is a plurality of images.
8 . The one or more non-transitory computer-readable storage media of claim 5 , wherein the set of tags is a plurality of gene characteristics and the set of items is a plurality of gene sequences.
9 . A system comprising:
one or more processors; and
one or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed, cause the system to perform operations, the operations comprising:
obtaining a set of tags and a set of items, wherein each item of the set of items is pre-sorted into a cluster by an unsupervised machine learning model and each item corresponds to one or more tags included in the set of tags;
generating a graph that includes the set of tags as a first set of nodes and the clusters of items as a second set of nodes of the graph, wherein relationships between tags and items are represented as edges between first nodes associated with the first set of nodes and second nodes associated with the second set of nodes;
modeling the graph as a quadratic programming formulation;
converting the quadratic programming formulation into a quadratic unconstrained binary optimization (QUBO) problem, the converting into the QUBO problem allowing for solving of the quadratic programming formulation using a digital annealer, wherein the quadratic programming formulation of the graph includes one or more weights corresponding to one or more metrics including at least one of: a tag redundancy, a node coverage, a tag balance, and a tag locality that indicates a degree to which the tags provide indication of how the one or more clusters of items were pre-sorted, and
the quadratic programming formulation is represented by
min
∑
l
=
1
k
∑
j
∈
T
x
l
(
j
)
-
P
1
∑
l
=
1
k
∑
i
,
j
∈
T
B
i
,
j
x
l
(
i
)
x
l
(
j
)
+
P
2
∑
l
=
1
k
∑
i
∈
C
l
(
1
-
z
(
i
)
)
∑
j
∈
t
i
x
l
(
j
)
“x l (j)” represents a first binary function, “T” represents the set of tags, “C l ” represents the cluster, “z(i)” represents a second binary function, “B i,j ” represents a n×n modularity matrix corresponding to the graph, “P 1 ” and “P 2 ” represent weighting parameters in which “P 1 ” represents a tag locality and “P 2 ” represents uncovered items included in the cluster;
solving the QUBO problem using the digital annealer;
determining one or more cluster descriptor sets that each include one or more of the tags based on the solving of the QUBO problem, each of the cluster descriptor sets providing an indication of how one or more clusters of items were pre-sorted;
analyzing the set of items based on the one or more cluster descriptor sets; and
providing an explanation regarding clustering of the set of items by the unsupervised machine learning model based on the analyzing of the set of items.
10 . The system of claim 9 , wherein the set of tags is a plurality of hashtags and the set of items is a plurality of user accounts on a social media platform.
11 . The system of claim 9 , wherein the set of tags is a plurality of image labels and the set of items is a plurality of images.
12 . The system of claim 9 , wherein the set of tags is a plurality of gene characteristics and the set of items is a plurality of gene sequences.