##########################
# KNN: k Nearest Neighbors
#输入：newInput: (1xN)的待分类向量
#         dataSet:   (NxM)的训练数据集
#         labels:      训练数据集的类别标签向量
#         k:             近邻数
# 输出：可能性最大的分类标签
##########################

from numpy import
import operator

#创建一个数据集，包含2个类别共4个样本
def createDataSet():
        # 生成一个矩阵，每行表示一个样本
        group = array([[1.0,0.9],[1.0,1.0],[0.1,0.2],[0.0,0.1]])
        # 4个样本分别所属的类别
        labels = ['A', 'A', 'B', 'B']
        return group, labels

# KNN分类算法函数定义
def KNNClassify(newInput, dataSet, labels, k)：
        numSamples = dataSet.shape[0]  #shape[0]表示行数
      
        ## step1：计算距离
        # tile(A, reps)：构造一个矩阵，通过A重复reps次得到
        # the following copy numSamples rows for dataSet
        diff = tile(newInput, (numSamples, 1)) -dataSet #按元素求差值
        squareDiff = diff ** 2 #将差值平方
        squareDist = sum(squaredDiff, axis = 1) # 按行累加

        ##step2：对距离排序
        # argsort() 返回排序后的索引值
        sortedDistIndices = argsort(distance)
        classCount = {} # define a dictionary (can be append element)
        for i in xrange(k):
             ##step 3: 选择k个最近邻
             voteLabel = labels[sortedDistIndices[i]]

             ## step 4:计算k个最近邻中各类别出现的次数
             # when the key voteLabel is not in dictionary classCount，get()
             # will return 0
             classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

##step 5：返回出现次数最多的类别标签
maxCount = 0
for key, value in classCount.items():
         if value > maxCount:
             maxCount = value
             maxIndex = key

         return maxIndex

import KNN
from numpy import * 
#生成数据集和类别标签
dataSet,labels = KNN.createDataSet()
#定义一个未知类别的数据
testX = array([1.2, 1.0])
k=3
#调用分类函数对未知数据分类
outputLabel = KNN.KNNClassify(testX, dataSet, labels, 3)
print "Your input is:", testX, " and classified to class:", outputLabel

testX = array([0.1, 0.3])
outputLabel = KNN.KNNClassify(testX,dataSet, labels, 3)
print "Your input is:", testX, "and classified to class:", outputLabel

Your input is: [1.2 1.0] and classified to class: A
Your input is: [0.1 0.3] and classified to class: B

#过滤垃圾邮件
def textParse(bigString):      #正则表达式进行文本解析
      import re
      listOfTokens = re.split(r'W*', bigString)
      return [tok.lower() for tok in listOfTokens if len(tok) > 2]

def spamTest()
      docList = []; classList = []; fullText = []
      for i in range(1,26):     #导入并解析文本文件
             wordList = textParse(open('email/spam/%d.txt'%i).read())
             docList.append(wordList)
             fullText.extend(wordList)
             classList.append(1)
             wordList = textParse(open('email/ham/%d.txt'%i).read())
             docList.append(wordList)
             fullText.extend(wordList)
             classList.append(0)
      vocabList = createVocabList(docList)
      trainingSet = range(50);testSet = []
      for i in range(10):                  #随机构建训练集
             randIndex = int(random.uniform(0, len(trainingSet)))
             testSet.append(trainingSet[randIndex]) #随机挑选一个文档索引号放入测试集
              del(trainingSet[randIndex])  #将该文档索引号从训练集中剔除
       trainMat = []; trainClasses = []
       for docIndex in trainingSet:
              trainMat.append(setOfWords2Vec(vocabList, docList[docIndex]))
              trainClasses.append(classList[docIndex])
       p0V,p1V,pSpam = trainNBO(array(trainMat), array(trainClasses))
       errorCount = 0
       for docIndex in testSet:        #对测试集进行分类
             wordVector = setOfWords2Vec(vocabList, docList[docIndex])
             if classifyNB(array(wordVector), p0V,p1V != classList[docIndex]:
                 errorCount +=1
        print 'the error rate is:', float(errorCount)/len(testSet)

def loadDataSet():
       dataMat = []; labelMat = []
        fr = open('d:/testSet.txt')
        for line in fr.readlines():
               lineArr = line.strip().split()
               dataMat.append([1.0, float(lineArr[0]), float(lineArr[1])])
               labelMat.append(int(lineArr[2]))
         return dataMat, labelMat

def sigmoid(inX):
      return 1.0/(1+exp(-inX))

def gradAscent(dataMatln, classLabels):
      dataMatrix = mat(dataMatln)  # 将先验数据集转换为NumPy矩阵
      labelMat = mat(classLabels).transpose() #将先验数据的类标签转换为NumPy矩阵
   
      m,n = shape(dataMatrix)
      alpha = 0.001     #设置逼近步长调整系数
      maxCycles = 500  #设置最大迭代次数为500
      weights = ones((n,1)) #weights即为需要迭代求解的参数向量

      for k in range(maxCycles): #heavy on matrix operations
            h = sigmoid(dataMatrix * weights) #代入样本向量求得“样本y” sigmoid转换值
            error = (labelMat - h)    #求差
            weights = weights + alpha * dataMatrix.transpose() * error #根据差值调整参数向量
      return weights

from math import log
import operator

def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    numEntries=len(dataSet)  # 数据条数
    labelCounts={}
    for featVec in dataSet:
        currentLabel=featVec[-1] # 每行数据的最后一个字（类别）
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1  # 统计有多少个类以及每个类的数量
    shannonEnt=0
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
        shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    return shannonEnt

def createDataSet1(): # 创造示例数据
    dataSet = [['长', '粗', '男'],
               ['短', '粗', '男'],
               ['短', '粗', '男'],
               ['长', '细', '女'],
               ['短', '细', '女'],
               ['短', '粗', '女'],
               ['长', '粗', '女'],
               ['长', '粗', '女']]
    labels = ['头发', '声音'] # 两个特征
    return dataSet, labels

def splitDataSet(dataSet, axis, value): # 按某个特征分类后的数据
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet): # 选择最优的分类特征
    numFeatures = len(dataSet[0]) - 1
    print(numFeatures)
    baseEntropy = calcShannonEnt(dataSet) # 原始的熵
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet) # 按特征分类后的熵
        infoGain = baseEntropy - newEntropy # 原始熵与按特征分类后的熵的差值
        if (infoGain > bestInfoGain): # 若按某特征划分后，熵值减少的最大，则次特征为最优分类特征
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList): # 按分类后类别数量排序，比如：最后分类为2男1女，则判定为男：
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet] # 类别：男或女
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet) # 选择最优特征
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}} # 分类结果以字典形式保存
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    #print(featValues)
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

if __name__ == '__main__':
    dataSet, labels = createDataSet1() # 创造示例数据
    print(createTree(dataSet, labels)) # 输出决策树模型结果

{'声音': {'细': '女', '粗': {'头发': {'长': '女', '短': '男'}}}}

digraph Tree {
0 [label="X[1] <= 55.0000
entropy = 0.954434002925
samples = 8", shape="box"] ;
1 [label="entropy = 0.0000
samples = 2
value = [ 2.  0.]", shape="box"] ;
0 -> 1 ;
2 [label="X[1] <= 70.0000
entropy = 0.650022421648
samples = 6", shape="box"] ;
0 -> 2 ;
3 [label="X[0] <= 1.6500
entropy = 0.918295834054
samples = 3", shape="box"] ;
2 -> 3 ;
4 [label="entropy = 0.0000
samples = 2
value = [ 0.  2.]", shape="box"] ;
3 -> 4 ;
5 [label="entropy = 0.0000
samples = 1
value = [ 1.  0.]", shape="box"] ;
3 -> 5 ;
6 [label="entropy = 0.0000
samples = 3
value = [ 0.  3.]", shape="box"] ;
2 -> 6 ;
}