<s> from __future__ import print_function , unicode_literals , division <EOL> import copy <EOL> import random <EOL> import sys <EOL> try : <EOL> import numpy <EOL> except ImportError : <EOL> pass <EOL> from nltk . cluster . util import VectorSpaceClusterer <EOL> from nltk . compat import python_2_unicode_compatible <EOL> @ python_2_unicode_compatible <EOL> class KMeansClusterer ( VectorSpaceClusterer ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , num_means , distance , repeats = <NUM_LIT:1> , <EOL> conv_test = <NUM_LIT> , initial_means = None , <EOL> normalise = False , svd_dimensions = None , <EOL> rng = None , avoid_empty_clusters = False ) : <EOL> """<STR_LIT>""" <EOL> VectorSpaceClusterer . __init__ ( self , normalise , svd_dimensions ) <EOL> self . _num_means = num_means <EOL> self . _distance = distance <EOL> self . _max_difference = conv_test <EOL> assert not initial_means or len ( initial_means ) == num_means <EOL> self . _means = initial_means <EOL> assert repeats >= <NUM_LIT:1> <EOL> assert not ( initial_means and repeats > <NUM_LIT:1> ) <EOL> self . _repeats = repeats <EOL> self . _rng = ( rng if rng else random . Random ( ) ) <EOL> self . _avoid_empty_clusters = avoid_empty_clusters <EOL> def cluster_vectorspace ( self , vectors , trace = False ) : <EOL> if self . _means and self . _repeats > <NUM_LIT:1> : <EOL> print ( '<STR_LIT>' ) <EOL> meanss = [ ] <EOL> for trial in range ( self . _repeats ) : <EOL> if trace : print ( '<STR_LIT>' , trial ) <EOL> if not self . _means or trial > <NUM_LIT:1> : <EOL> self . _means = self . _rng . sample ( list ( vectors ) , self . _num_means ) <EOL> self . _cluster_vectorspace ( vectors , trace ) <EOL> meanss . append ( self . _means ) <EOL> if len ( meanss ) > <NUM_LIT:1> : <EOL> for means in meanss : <EOL> means . sort ( key = sum ) <EOL> min_difference = min_means = None <EOL> for i in range ( len ( meanss ) ) : <EOL> d = <NUM_LIT:0> <EOL> for j in range ( len ( meanss ) ) : <EOL> if i != j : <EOL> d += self . _sum_distances ( meanss [ i ] , meanss [ j ] ) <EOL> if min_difference is None or d < min_difference : <EOL> min_difference , min_means = d , meanss [ i ] <EOL> self . _means = min_means <EOL> def _cluster_vectorspace ( self , vectors , trace = False ) : <EOL> if self . _num_means < len ( vectors ) : <EOL> converged = False <EOL> while not converged : <EOL> clusters = [ [ ] for m in range ( self . _num_means ) ] <EOL> for vector in vectors : <EOL> index = self . classify_vectorspace ( vector ) <EOL> clusters [ index ] . append ( vector ) <EOL> if trace : print ( '<STR_LIT>' ) <EOL> new_means = list ( map ( self . _centroid , clusters , self . _means ) ) <EOL> difference = self . _sum_distances ( self . _means , new_means ) <EOL> if difference < self . _max_difference : <EOL> converged = True <EOL> self . _means = new_means <EOL> def classify_vectorspace ( self , vector ) : <EOL> best_distance = best_index = None <EOL> for index in range ( len ( self . _means ) ) : <EOL> mean = self . _means [ index ] <EOL> dist = self . _distance ( vector , mean ) <EOL> if best_distance is None or dist < best_distance : <EOL> best_index , best_distance = index , dist <EOL> return best_index <EOL> def num_clusters ( self ) : <EOL> if self . _means : <EOL> return len ( self . _means ) <EOL> else : <EOL> return self . _num_means <EOL> def means ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _means <EOL> def _sum_distances ( self , vectors1 , vectors2 ) : <EOL> difference = <NUM_LIT:0.0> <EOL> for u , v in zip ( vectors1 , vectors2 ) : <EOL> difference += self . _distance ( u , v ) <EOL> return difference <EOL> def _centroid ( self , cluster , mean ) : <EOL> if self . _avoid_empty_clusters : <EOL> centroid = copy . copy ( mean ) <EOL> for vector in cluster : <EOL> centroid += vector <EOL> return centroid / ( <NUM_LIT:1> + len ( cluster ) ) <EOL> else : <EOL> if not len ( cluster ) : <EOL> sys . stderr . write ( '<STR_LIT>' ) <EOL> sys . stderr . write ( '<STR_LIT>' ) <EOL> assert ( False ) <EOL> centroid = copy . copy ( cluster [ <NUM_LIT:0> ] ) <EOL> for vector in cluster [ <NUM_LIT:1> : ] : <EOL> centroid += vector <EOL> return centroid / len ( cluster ) <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' % ( self . _means , self . _repeats ) <EOL> def demo ( ) : <EOL> from nltk . cluster import KMeansClusterer , euclidean_distance <EOL> vectors = [ numpy . array ( f ) for f in [ [ <NUM_LIT:2> , <NUM_LIT:1> ] , [ <NUM_LIT:1> , <NUM_LIT:3> ] , [ <NUM_LIT:4> , <NUM_LIT:7> ] , [ <NUM_LIT:6> , <NUM_LIT:7> ] ] ] <EOL> means = [ [ <NUM_LIT:4> , <NUM_LIT:3> ] , [ <NUM_LIT:5> , <NUM_LIT:5> ] ] <EOL> clusterer = KMeansClusterer ( <NUM_LIT:2> , euclidean_distance , initial_means = means ) <EOL> clusters = clusterer . cluster ( vectors , True , trace = True ) <EOL> print ( '<STR_LIT>' , vectors ) <EOL> print ( '<STR_LIT>' , clusters ) <EOL> print ( '<STR_LIT>' , clusterer . means ( ) ) <EOL> print ( ) <EOL> vectors = [ numpy . array ( f ) for f in [ [ <NUM_LIT:3> , <NUM_LIT:3> ] , [ <NUM_LIT:1> , <NUM_LIT:2> ] , [ <NUM_LIT:4> , <NUM_LIT:2> ] , [ <NUM_LIT:4> , <NUM_LIT:0> ] , [ <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:3> , <NUM_LIT:1> ] ] ] <EOL> clusterer = KMeansClusterer ( <NUM_LIT:2> , euclidean_distance , repeats = <NUM_LIT:10> ) <EOL> clusters = clusterer . cluster ( vectors , True ) <EOL> print ( '<STR_LIT>' , vectors ) <EOL> print ( '<STR_LIT>' , clusters ) <EOL> print ( '<STR_LIT>' , clusterer . means ( ) ) <EOL> print ( ) <EOL> vector = numpy . array ( [ <NUM_LIT:3> , <NUM_LIT:3> ] ) <EOL> print ( '<STR_LIT>' % vector , end = '<STR_LIT:U+0020>' ) <EOL> print ( clusterer . classify ( vector ) ) <EOL> print ( ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> demo ( ) </s>
