#coding=utf-8

 import codecs

 import numpy

 from numpy import *

 import pylab

 def loadDataSet(fileName):

     dataMat = []

     fr = codecs.open(fileName)

     for line in fr.readlines():

         curLine = line.strip().split('\t')

         fltLine = map(float, curLine)

         dataMat.append(fltLine)

     return dataMat    

 def distMeasure(vecA, vecB):

     #print vecA

     dist = sqrt(sum(power(vecA - vecB, 2)))

     return dist

 def kMeansInitCentroids(X, K):

     """

     KMEANSINITCENTROIDS This function initializes K centroids that are to be

     used in K-Means on the dataset X

     centroids = KMEANSINITCENTROIDS(X, K) returns K initial centroids to be

     used with the K-Means on the dataset X.

     """

     n = shape(X)[1]

     centroids = mat(zeros((K,n)))

     for j in range(n):

         #print X[:,j]

         minJ = min(X[:,j])

         rangeJ = float(max(array(X)[:,j]) - minJ)

         centroids[:,j] = minJ + rangeJ * random.rand(K,1)

     return centroids

 def findClosestCentroids(X, centroids):

     """

     FINDCLOSESTCENTROIDS computes the centroid memberships for every example

     idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids

     in idx for a dataset X where each row is a single example. idx = m x 1

     vector of centroid assignments (i.e. each entry in range [1..K])

     """

     # 数据总量

     m = shape(X)[0]

     K = shape(centroids)[0]

     clusterAssment = mat(zeros((m,2)))#create mat to assign data points

                                       #to a centroid, also holds SE of each point

     #centroids = createCent(dataSet, k)

     clusterChanged = True

     while clusterChanged:

         clusterChanged = False

         for i in range(m):#for each data point assign it to the closest centroid

             minDist = inf; minIndex = -1

             # k个中间数据（质心）都与数据i进行欧氏比较，选择距离最近的第minIndex类

             for j in range(K):

                 distJI = distMeasure(centroids[j,:],X[i,:])

                 if distJI < minDist:

                     minDist = distJI; minIndex = j

             if clusterAssment[i,0] != minIndex: clusterChanged = True

             clusterAssment[i,:] = minIndex,minDist**2

     return clusterAssment

 def computeCentroids(X, clusterAssment, K):

     """

     COMPUTECENTROIDS returs the new centroids by computing the means of the

     data points assigned to each centroid.

     centroids = COMPUTECENTROIDS(X, idx, K) returns the new centroids by

     computing the means of the data points assigned to each centroid. It is

     given a dataset X where each row is a single data point, a vector

     idx of centroid assignments (i.e. each entry in range [1..K]) for each

     example, and K, the number of centroids. You should return a matrix

     centroids, where each row of centroids is the mean of the data points

     assigned to it.

     """

     n = shape(X)[1]

     centroids = mat(zeros((K,n)))

     for centroid in range(K):#recalculate centroids

         # nonzero会产生两个array，第一个非零的为序号列表

         ptsInClust = X[nonzero(clusterAssment[:,0].A==centroid)[0]]#get all the point in this cluster

         #print 'ererer:',ptsInClust,'dfdf'

         centroids[centroid,:] = mean(ptsInClust, axis=0) #assign centroid to mean

     return centroids

 def show(dataSet, k, centroids, clusterAssment):

     from matplotlib import pyplot as plt

     numSamples, dim = dataSet.shape

     mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']

     print type(dataSet)

     for i in xrange(numSamples):

         markIndex = int(clusterAssment[i, 0])

         plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

     mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']

     for i in range(k):

         plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)

     plt.show()

 def runkMeans(X, initial_centroids,max_iters, plot_progress):

     """

     RUNKMEANS runs the K-Means algorithm on data matrix X, where each row of X

     is a single example

     [centroids, idx] = RUNKMEANS(X, initial_centroids, max_iters, ...

     plot_progress) runs the K-Means algorithm on data matrix X, where each

     row of X is a single example. It uses initial_centroids used as the

     initial centroids. max_iters specifies the total number of interactions

     of K-Means to execute. plot_progress is a true/false flag that

     indicates if the function should also plot its progress as the

     learning happens. This is set to false by default. runkMeans returns

     centroids, a Kxn matrix of the computed centroids and idx, a m x 1

     vector of centroid assignments (i.e. each entry in range [1..K]).

     """

     (m,n) = shape(X)

     K = shape(initial_centroids)[0]

     centroids = initial_centroids

     clusterAssment = zeros((m,2))

     #Run K-Means

     for i in range(max_iters):

         clusterAssment = findClosestCentroids(X, centroids)

         centroids = computeCentroids(X, clusterAssment, K);

     return centroids, clusterAssment

 def main():

     K =5

     max_iters = 10

     dataSet =  loadDataSet('E://PythonSpace//TextClustering//data//test2.txt')

     X = array(dataSet)

     X = (X - mean(X)) / std(X)

     initial_centroids = kMeansInitCentroids(X, K)

     myCentroids, clusterAssment = runkMeans(X, initial_centroids, max_iters,False);

     print "-------------------------------------"

     show(X, K, myCentroids, clusterAssment)

 main()