NeuralNet/kmeans.py at master · alexj136/NeuralNet · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from random    import uniform, randint
from copy      import deepcopy
from instances import *
from misc      import *

def minmax(insts):
    '''Return an instance with feature values that are the minimum of all
    feature and label values across the given instances. Return an instance with
    maximum values also.'''

    minFeats = []
    maxFeats = []

    for feat in range(len(insts[0].data)):
        feats = [inst.data[feat] for inst in insts]
        minFeats.append(min(feats))
        maxFeats.append(max(feats))

    return Instance(minFeats, None), Instance(maxFeats, None)

def kRandomPrototypes(k, insts):
    '''Choose k instances from the given list at random to be prototypes.
    The returned Instances are deep copies of the chosen Instances. They do not
    have label values.'''
    return [Instance(deepcopy(insts[i].data), None) for i in \
            [randint(0, len(insts) - 1) for x in range(k)]]

def kMeans(k, insts):
    '''Perform k-means clustering on the given instances. Return the k prototype
    instances (these are not instances from the data set itself).'''

    protos = kRandomPrototypes(k, insts)

    prevClustering = bins(k, insts)
    converged = False

    while not converged:

        # Assignment step - put each instance in the cluster corresponding to
        # its closest prototype
        newClustering = [[] for x in range(k)]
        for inst in insts:
            # Find the prototype closest to this instance and add the instance
            # to the corresponding cluster
            bestIdx = 0
            bestDist = euclideanDist(inst.data, protos[bestIdx].data)
            for idx in range(len(protos)):

                # None prototypes are produced if clusters are empty, so set
                # curDist = bestDist + 1 so we don't put the instance in this
                # cluster
                if protos[idx] is None:
                    curDist = bestDist + 1
                else:
                    curDist = euclideanDist(inst.data, protos[idx].data)

                if curDist < bestDist:
                    bestIdx  = idx
                    bestDist = curDist

            newClustering[bestIdx].append(inst)

        # Recompute the prototypes to be mean values of data in their cluster.
        # If their cluster is now empty, do not update the prototype.
        for idx in range(len(newClustering)):
            meanI = meanInst(newClustering[idx])
            if meanI is not None:
                protos[idx] = meanI

        # If the current clusters contain the same elements as they did last
        # time, we've converged
        foundDiff = False
        prevClusterSets = map(set, prevClustering)
        for cluster in newClustering:
            if set(cluster) not in prevClusterSets:
                foundDiff = True
                break
        converged = not foundDiff

        prevClustering = newClustering

    return protos, newClustering

if __name__ == '__main__':
    insts = parseTrainingData()
    protos = kMeans(2, insts)
    for proto in protos: print proto