repo/traffic-intelligence: python/ml.py annotate

annotate python/ml.py @ 735:0e875a7f5759 dev

modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities

author	Nicolas Saunier <nicolas.saunier@polymtl.ca>
date	Wed, 12 Aug 2015 00:24:06 -0400
parents	1d4dcb5c8708
children	2472b4d59aea

rev	line source
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	1 #! /usr/bin/env python
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	2 '''Libraries for machine learning algorithms'''
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	3
308 8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	4 import numpy as np
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	5
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	6
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	7 class Model(object):
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	8 '''Abstract class for loading/saving model'''
680 da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	9 def load(self, filename):
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	10 from os import path
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	11 if path.exists(filename):
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	12 self.model.load(filename)
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	13 else:
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	14 print('Provided filename {} does not exist: model not loaded!'.format(filename))
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	15
680 da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	16 def save(self, filename):
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	17 self.model.save(filename)
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	18
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	19 class SVM(Model):
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	20 '''wrapper for OpenCV SimpleVectorMachine algorithm'''
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	21
680 da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	22 def __init__(self):
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	23 import cv2
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	24 self.model = cv2.SVM()
680 da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	25
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	26 def train(self, samples, responses, svm_type, kernel_type, degree = 0, gamma = 1, coef0 = 0, Cvalue = 1, nu = 0, p = 0):
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	27 self.params = dict(svm_type = svm_type, kernel_type = kernel_type, degree = degree, gamma = gamma, coef0 = coef0, Cvalue = Cvalue, nu = nu, p = p)
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	28 self.model.train(samples, responses, params = self.params)
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	29
680 da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	30 def predict(self, hog):
da1352b89d02 classification is working Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 665 diff changeset	31 return self.model.predict(hog)
380 adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	32
adfd4f70ee1d added SVM Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 312 diff changeset	33
665 15e244d2a1b5 corrected bug with circular import for VideoFilenameAddable, moved to base module Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 636 diff changeset	34 class Centroid(object):
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	35 'Wrapper around instances to add a counter'
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	36
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	37 def __init__(self, instance, nInstances = 1):
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	38 self.instance = instance
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	39 self.nInstances = nInstances
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	40
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	41 # def similar(instance2):
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	42 # return self.instance.similar(instance2)
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	43
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	44 def add(self, instance2):
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	45 self.instance = self.instance.multiply(self.nInstances)+instance2
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	46 self.nInstances += 1
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	47 self.instance = self.instance.multiply(1/float(self.nInstances))
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	48
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	49 def average(c):
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	50 inst = self.instance.multiply(self.nInstances)+c.instance.multiply(instance.nInstances)
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	51 inst.multiply(1/(self.nInstances+instance.nInstances))
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	52 return Centroid(inst, self.nInstances+instance.nInstances)
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	53
515 727e3c529519 renamed all draw functions to plot for consistency Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 501 diff changeset	54 def plot(self, options = ''):
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	55 from matplotlib.pylab import text
515 727e3c529519 renamed all draw functions to plot for consistency Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 501 diff changeset	56 self.instance.plot(options)
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	57 text(self.instance.position.x+1, self.instance.position.y+1, str(self.nInstances))
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	58
386 8bc632cb8344 minor Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 382 diff changeset	59 def kMedoids(similarityMatrix, initialCentroids = None, k = None):
8bc632cb8344 minor Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 382 diff changeset	60 '''Algorithm that clusters any dataset based on a similarity matrix
8bc632cb8344 minor Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 382 diff changeset	61 Either the initialCentroids or k are passed'''
8bc632cb8344 minor Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 382 diff changeset	62 pass
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	63
526 21bdeb29f855 corrected bug in initialization of lists and loading trajectories from vissim files Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 515 diff changeset	64 def assignCluster(data, similarFunc, initialCentroids = None, shuffleData = True):
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	65 '''k-means algorithm with similarity function
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	66 Two instances should be in the same cluster if the sameCluster function returns true for two instances. It is supposed that the average centroid of a set of instances can be computed, using the function.
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	67 The number of clusters will be determined accordingly
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	68
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	69 data: list of instances
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	70 averageCentroid: '''
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	71
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	72 from random import shuffle
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	73 from copy import copy, deepcopy
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	74 localdata = copy(data) # shallow copy to avoid modifying data
382 ba813f148ade development for clustering Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 380 diff changeset	75 if shuffleData:
ba813f148ade development for clustering Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 380 diff changeset	76 shuffle(localdata)
636 3058e00887bc removed all issues because of tests with None, using is instead of == or != Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 563 diff changeset	77 if initialCentroids is None:
526 21bdeb29f855 corrected bug in initialization of lists and loading trajectories from vissim files Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 515 diff changeset	78 centroids = [Centroid(localdata[0])]
21bdeb29f855 corrected bug in initialization of lists and loading trajectories from vissim files Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 515 diff changeset	79 else:
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	80 centroids = deepcopy(initialCentroids)
d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	81 for instance in localdata[1:]:
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	82 i = 0
382 ba813f148ade development for clustering Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 380 diff changeset	83 while i<len(centroids) and not similarFunc(centroids[i].instance, instance):
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	84 i += 1
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	85 if i == len(centroids):
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	86 centroids.append(Centroid(instance))
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	87 else:
184 d70e9b36889c initial work on flow vectors and clustering algorithms Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 183 diff changeset	88 centroids[i].add(instance)
183 ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	89
ed944ff45e8c first simple clustering algorithm implementation Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: diff changeset	90 return centroids
308 8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	91
382 ba813f148ade development for clustering Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 380 diff changeset	92 # TODO recompute centroids for each cluster: instance that minimizes some measure to all other elements
ba813f148ade development for clustering Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 380 diff changeset	93
293 ee3302528cdc rearranged new code by Paul (works now) Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 285 diff changeset	94 def spectralClustering(similarityMatrix, k, iter=20):
285 5957aa1d69e1 Integrating Mohamed's changes Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 184 diff changeset	95 '''Spectral Clustering algorithm'''
5957aa1d69e1 Integrating Mohamed's changes Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 184 diff changeset	96 n = len(similarityMatrix)
308 8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	97 # create Laplacian matrix
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	98 rowsum = np.sum(similarityMatrix,axis=0)
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	99 D = np.diag(1 / np.sqrt(rowsum))
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	100 I = np.identity(n)
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	101 L = I - np.dot(D,np.dot(similarityMatrix,D))
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	102 # compute eigenvectors of L
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	103 U,sigma,V = np.linalg.svd(L)
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	104 # create feature vector from k first eigenvectors
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	105 # by stacking eigenvectors as columns
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	106 features = np.array(V[:k]).T
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	107 # k-means
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	108 from scipy.cluster.vq import kmeans, whiten, vq
8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	109 features = whiten(features)
293 ee3302528cdc rearranged new code by Paul (works now) Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 285 diff changeset	110 centroids,distortion = kmeans(features,k, iter)
308 8bafd054cda4 Added a function to compute LCSS distance between two indcators Mohamed Gomaa parents: 184 diff changeset	111 code,distance = vq(features,centroids) # code starting from 0 (represent first cluster) to k-1 (last cluster)
309 80cbafd69109 Added spectral clustering function Mohamed Gomaa parents: 308 diff changeset	112 return code,sigma
563 39de5c532559 place holder functions Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 526 diff changeset	113
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	114 def prototypeCluster(instances, similarities, minSimilarity, similarityFunc = None, minClusterSize = None, randomInitialization = False):
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	115 '''Finds exemplar (prototype) instance that represent each cluster
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	116 Returns the prototype indices (in the instances list) and the cluster label of each instance
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	117
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	118 the elements in the instances list must have a length (method __len__), or one can use the random initialization
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	119 the positions in the instances list corresponds to the similarities
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	120 if similarityFunc is provided, the similarities are calculated as needed (this is faster) if not in similarities (negative if not computed)
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	121 similarities must still be allocated with the right size
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	122
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	123 if an instance is different enough (<minSimilarity),
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	124 it will become a new prototype.
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	125 Non-prototype instances will be assigned to an existing prototype
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	126 if minClusterSize is not None, the clusters will be refined by removing iteratively the smallest clusters
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	127 and reassigning all elements in the cluster until no cluster is smaller than minClusterSize'''
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	128
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	129 # sort instances based on length
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	130 indices = range(len(instances))
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	131 if randomInitialization:
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	132 indices = np.random.permutation(indices)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	133 else:
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	134 def compare(i, j):
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	135 if len(instances[i]) > len(instances[j]):
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	136 return -1
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	137 elif len(instances[i]) == len(instances[j]):
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	138 return 0
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	139 else:
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	140 return 1
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	141 indices.sort(compare)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	142 # go through all instances
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	143 prototypeIndices = [indices[0]]
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	144 for i in indices[1:]:
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	145 if similarityFunc is not None:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	146 for j in prototypeIndices:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	147 if similarities[i][j] < 0:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	148 similarities[i][j] = similarityFunc(instances[i], instances[j])
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	149 similarities[j][i] = similarities[i][j]
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	150 if similarities[i][prototypeIndices].max() < minSimilarity:
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	151 prototypeIndices.append(i)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	152
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	153 # assignment
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	154 indices = [i for i in range(similarities.shape[0]) if i not in prototypeIndices]
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	155 assign = True
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	156 while assign:
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	157 labels = [-1]*similarities.shape[0]
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	158 for i in prototypeIndices:
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	159 labels[i] = i
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	160 for i in indices:
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	161 if similarityFunc is not None:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	162 for j in prototypeIndices:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	163 if similarities[i][j] < 0:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	164 similarities[i][j] = similarityFunc(instances[i], instances[j])
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	165 similarities[j][i] = similarities[i][j]
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	166 prototypeIdx = similarities[i][prototypeIndices].argmax()
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	167 if similarities[i][prototypeIndices[prototypeIdx]] >= minSimilarity:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	168 labels[i] = prototypeIndices[prototypeIdx]
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	169 else:
0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	170 labels[i] = -1 # outlier
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	171 clusterSizes = {i: sum(np.array(labels) == i) for i in prototypeIndices}
735 0e875a7f5759 modified prototypeCluster algorithm to enforce similarity when re-assigning and to compute only the necessary similarities Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 734 diff changeset	172 smallestClusterIndex = min(clusterSizes, key = clusterSizes.get)
731 b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	173 assign = (clusterSizes[smallestClusterIndex] < minClusterSize)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	174 if assign:
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	175 prototypeIndices.remove(smallestClusterIndex)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	176 indices.append(smallestClusterIndex)
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	177
b02431a8234c made prototypecluster generic, in ml module, and added randominitialization Nicolas Saunier <nicolas.saunier@polymtl.ca> parents: 680 diff changeset	178 return prototypeIndices, labels

Mercurial Hosting > traffic-intelligence

annotate python/ml.py @ 735:0e875a7f5759 dev