Clusteringtest.ipynb

Kernel: Python [conda env:DAND]

Clustering 1

1 point 1.In this programming problem and the next you'll code up the clustering algorithm from lecture for computing a max-spacing k-clustering.

Download the text file below.

clustering1.txt

This file describes a distance function (equivalently, a complete graph with edge costs). It has the following format:

[number_of_nodes]

[edge 1 node 1] [edge 1 node 2] [edge 1 cost]

[edge 2 node 1] [edge 2 node 2] [edge 2 cost]

...

There is one edge (i,j) for each choice of 1≤i<j≤n, where n is the number of nodes.

For example, the third line of the file is "1 3 5250", indicating that the distance between nodes 1 and 3 (equivalently, the cost of the edge (1,3)) is 5250. You can assume that distances are positive, but you should NOT assume that they are distinct.

Your task in this problem is to run the clustering algorithm from lecture on this data set, where the target number k of clusters is set to 4. What is the maximum spacing of a 4-clustering?

ADVICE: If you're not getting the correct answer, try debugging your algorithm using some small test cases. And then post them to the discussion forum!

edges = [map(int, x.split(' ')) for x in open('clustering1.txt', 'r').read().split('\n')[1:-1]]

edges.sort(key=lambda x: x[2])

vertices = {}
for edge in edges:
    vertices[edge[0]] = edge[0]
    vertices[edge[1]] = edge[1]

costs = {}
for v in vertices:
    costs[v] = 0

cluster_count = len(vertices)

for edge in edges:
    head1 = vertices[edge[0]]
    while vertices[head1] != head1:
        head1 = vertices[head1] 

    head2 = vertices[edge[1]]
    while vertices[head2] != head2:
        head2 = vertices[head2] 

    if head1 != head2:
        if cluster_count <= 4:
            spacing_distance = edge[2]
            break
        vertices[head2] = head1
        costs[head1] += (edge[2] + costs[head2])
        cluster_count -= 1

print spacing_distance

106

Cluster 2

2.In this question your task is again to run the clustering algorithm from lecture, but on a MUCH bigger graph. So big, in fact, that the distances (i.e., edge costs) are only defined implicitly, rather than being provided as an explicit list.

The data set is below.

clustering_big.txt

The format is:

[# of nodes] [# of bits for each node's label]

[first bit of node 1] ... [last bit of node 1]

[first bit of node 2] ... [last bit of node 2]

...

For example, the third line of the file "0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1" denotes the 24 bits associated with node #2.

The distance between two nodes u and v in this problem is defined as the Hamming distance--- the number of differing bits --- between the two nodes' labels. For example, the Hamming distance between the 24-bit label of node #2 above and the label "0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1" is 3 (since they differ in the 3rd, 7th, and 21st bits).

The question is: what is the largest value of k such that there is a k-clustering with spacing at least 3? That is, how many clusters are needed to ensure that no pair of nodes with all but 2 bits in common get split into different clusters?

NOTE: The graph implicitly defined by the data file is so big that you probably can't write it out explicitly, let alone sort the edges by cost. So you will have to be a little creative to complete this part of the question. For example, is there some way you can identify the smallest distances without explicitly looking at every pair of nodes?

vertices = ["".join(x.split(' ')) for x in open('clustering_big.txt', 'r').read().split('\n')[1:-1]]

def invert(bit):
    if bit != '0' and bit != '1':
        raise ValueError
    return '1' if bit == '0' else '0'

def similar(v):
    out = []
    for i in range(len(v)):
        out.append(v[:i]+invert(v[i]) + v[i+1:])
        for j in range(i+1, len(v)):
            out.append(v[:i]+invert(v[i])+v[i+1:j]+invert(v[j])+v[j+1:])
    return out
 
heads = {}
for v in vertices:
    heads[v] = v
clusters = len(heads) 
#print clusters
for v in vertices:
    v_head = heads[v]
    while heads[v_head] != v_head:
        v_head = heads[v_head]

    for friend in similar(v):
        if heads.get(friend):
            head = heads[friend]
            while heads[head] != head:
                head = heads[head]
            if v_head != head:
                heads[head] = v_head
                clusters -= 1
print clusters

6118