An algorithm to create clusters from data pairs in python

Question

I am looking for a smart algorithm or pythonic approach to create clusters from pairs of data.

The input data is structured like this:

[
 (productA,ProductB),
 (productB,ProductC),
 (productC,ProductD),
 (productA,ProductD),
 (productD,ProductB),
 (productC,ProductA),

 (productE,ProductF),
 (productF,ProductG),
 (productG,ProductH),
 (productG,ProductE),
]

and it should be clustered to:

[
(productA,productB,productC,productD),
(productE,productF,productG,productH)
]

How can this be achieved? (The order of the products within the two clusters does not matter)

Any ideas are greatly appreciated!

A cluster is the transitive closure over all products linked via some (directional) pair? Is the relation symmetric? — dhke
– dhke, Commented Jan 26, 2016 at 19:10

unutbu · Accepted Answer · 2016-01-26 19:16:06Z

3

Using networkx, you could build a graph and find the connected components:

import networkx as nx

data = [
 ('productA','productB'),
 ('productB','productC'),
 ('productC','productD'),
 ('productA','productD'),
 ('productD','productB'),
 ('productC','productA'),
 ('productE','productF'),
 ('productF','productG'),
 ('productG','productH'),
 ('productG','productE'),
]

G = nx.Graph()
G.add_edges_from(data)
for connected_component in nx.connected_components(G):
    print(connected_component)

yields

['productG', 'productF', 'productE', 'productH']
['productD', 'productC', 'productB', 'productA']

edited Jan 26, 2016 at 19:16

answered Jan 26, 2016 at 19:10

unutbu

886k197 gold badges1.9k silver badges1.7k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jabb Over a year ago

will try this instantly. Two things to note: 1. I love SO... always a solution to any problem, 2. I love python...

Raunak Agarwal · Accepted Answer · 2016-01-26 19:10:50Z

0

What you are looking for is: Quick Union algorithm.

answered Jan 26, 2016 at 19:10

Raunak Agarwal

7,2486 gold badges41 silver badges62 bronze badges

1 Comment

dhke Over a year ago

QU requires the relation to be transitive, reflexive and symmetric. The examples don't show if the relation is symmetric.

Collectives™ on Stack Overflow

An algorithm to create clusters from data pairs in python

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related