kNN算法和決策樹

　　kNN

　　kNN算法的原理很簡單，就是將新數據的特征與樣本集中相應的特征進行比較，然后提取將樣本集中特征最相似的數據的分類標簽作為新數據的標簽，一般的，只選取數據集中前k個最相似的元素，因此該算法被稱為kNN，通常k取不大于20的整數。

　　下面看書上給出的實例：

　　from numpy import *

　　import operator

　　def createdataset():

　　group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

　　labels=['a','a','b','b']

　　return group,labels

　　group,labels=createdataset()

　　def classify(inx,dataset,labels,k):

　　datasetsize=dataset.shape[0]

　　diffmat=tile(inx,(datasetsize,1)) - dataset

　　sqdiffmat=diffmat**2

　　sqdistance=sqdiffmat.sum(axis=1)

　　distance=sqdistance**0.5 #計算距離，也就是比較特征

　　sorteddist=distance.argsort()

　　classcount={}

　　for i in range(k):

　　votelabel=labels[sorteddist[i]]

　　classcount[votelabel]=classcount.get(votelabel,0)+1 #為字典classcount創建前k個最近的數據的標簽對應出現次數的鍵值對

　　sortedclasscount=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)

　　return sortedclasscount[0][0]

　　print(classify([0,0],group,labels,3))

　　首先，定義了一個createdataset()函數用來生成數據樣本集，然后定義的classify()函數有4個輸人參數:用于分類的輸人向量是inx，輸入的訓練樣本集為dataset, 標簽向量為labels 最后的參數k表示用于選擇最近鄰居的數目其中標簽向量的元素數目和矩 陣如dataset的行數相同。

　　dataset.shape[0]返回dataset數組的第二維，也就是二維數組的行數，此例中為4，接下來的tile函數將inx數組的第二維重復了四次，第一維重復一次，也就是將inx數組從一行變成了4行，每一行都是原來的inx數組，這樣就與dataset數組的行列數是一樣的，用于接下來計算inx與每個數據樣本的距離，這里的sqdiffmat.sum(axis=1)表示每一行的數組求和，這里返回一個長度為4的一維數組，每一個元素都是sqdiffmat對應一行的和，下面的argsort()函數將distance中的元素從小到大排列，提取其對應的index(索引)，然后輸出到sorteddist。

　　然后創建了一個空字典classcount，在接下來的for循環中為字典classcount創建了前k個最近的數據的標簽對應出現次數的鍵值對

　　接下來有一個sorted函數，它的語法如下：

　　sorted(iterable, key=None, reverse=False)

　　iterable – 可迭代對象。

　　key – 主要是用來進行比較的元素，只有一個參數，具體的函數的參數就是取自于可迭代對象中，指定可迭代對象中的一個元素來進行排序。

　　reverse – 排序規則，reverse = True 降序 ， reverse = False 升序(默認)。

　　items函數返回字典中可遍歷的(鍵, 值) 元組數組。

　　operator.itemgetter函數的作用是獲取對象哪些維的數據，參數是表示維的序號。

　　在這個例子中這個sorted函數的作用就是對字典classcount所生成的元組數組按照標簽對應出現的次數進行降序排序，最后整個classify函數返回的sortedclasscount[0][0]就是出現次數最多的標簽，以此作為待劃分數據的分類標簽。最后運行結果為 b 。

　　決策樹

　　決策樹偽代碼如下：

　　檢測數據集中的每個子項是否屬于同一分類：

　　If so return 類標簽;

　　Else

　　尋找劃分數據集的最好特征

　　劃分數據集

　　創建分支節點

　　for 每個劃分的子集

　　調用決策樹函數并增加返回結果到分支節點中

　　return 分支節點

　　下面根據偽代碼一步一步實現

　　熵

　　在劃分數據集之前之后信息發生的變化稱為信息增益，知道如何計算信息增益，我們就可以 計算每個特征值劃分數據集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇，集合信息的度量方式稱為香農熵或者簡稱為熵，熵定義為信息的期望值。

　　如果待分類的事務可能劃分在多個分類之中， 則符號x的信息定義為 l(x)=-lb(p(x))，p(x)為選擇該分類的概率。

　　要計算熵，則需要計算所有類別所有可能值包含的信息期望值。下面給出書上的計算熵代碼：

　　from math import log

　　def c_shannon_ent(data_set):

　　num_entries=len(data_set)

　　label_counts={}

　　for feat_vec in data_set:

　　current_label=feat_vec[-1]

　　if current_label not in label_counts.keys():

　　label_counts[current_label]=0

　　label_counts[current_label]+=1

　　shannon_ent=0.0

　　for key in label_counts:

　　prob=float(label_counts[key])/num_entries

　　shannon_ent-=prob*log(prob,2)

　　return shannon_ent

　　def create_data_set():

　　data_set=[[1,1,'yes'],[1,0,'no'],[0,1,'no'],[1,1,'yes'],[0,1,'no']]

　　labels=['no surfacing','flippers']

　　return data_set,labels

　　my_data,labels=create_data_set()

　　print(c_shannon_ent(my_data))

　　keys()函數用于返回一個字典所有的鍵。不難看出label_counts是一個將類別與屬于該類別的樣本數作為鍵值對的字典。實際上，對于data_set上的一個隨機變量x，x為yes所屬類的概率為2/5，x為no的概率為3/5，那么x的熵為-(2/5)*lb(2/5)-(3/5)*lb(3/5)，也就是上面代碼中計算的data_set的熵。(在這個實例中，yes和no對應的是最終分類標簽(是否為魚)，前面的1，0是用于判斷的特征數據，所以按照yes和no的分類來計算data_set的熵)熵越高，代表數據的無序程度就越高。

　　劃分數據集

　　先看看書上的對于給定特征劃分數據集的代碼：

　　def split_data_set(data_set,axis,value):

　　ret_data_set=[]

　　for feat_vec in data_set:

　　if feat_vec[axis]==value:

　　reduced_feat_vec=feat_vec[:axis]

　　reduced_feat_vec.extend(feat_vec[axis+1:])

　　ret_data_set.append(reduced_feat_vec)

　　return ret_data_set

　　這段代碼還是很容易看懂的，首先創建了一個新列表，然后對于符合所輸入的特征的數據就截取到 reduced_feat_vec中(把特征值截掉了)，然后再將 reduced_feat_vec添入新建的列表ret_data_set中作為一個元素，這樣就得到了一個符合所選特征值的數據集ret_data_set。

　　選擇最好的數據集劃分方式

　　def choose_best_feature_to_split(data_set):

　　num_features=len(data_set[0])-1

　　base_entropy=c_shannon_ent(data_set)

　　best_info_gain=0.0;best_feature=-1

　　for i in range(num_features):

　　feat_list=[example[i] for example in data_set]

　　unique_vals=set(feat_list)

　　new_entropy=0.0

　　for value in unique_vals:

　　sub_data_set=split_data_set(data_set,i,value)

　　prob=len(sub_data_set)/float(len(data_set))

　　new_entropy+=prob*c_shannon_ent(sub_data_set)

　　info_gain=base_entropy-new_entropy

　　if(info_gain>best_info_gain):

　　best_info_gain=info_gain

　　best_feature=i

　　return best_feature

　　如果上面都看懂了，那么看懂這一段代碼也不會難的。

　　首先用一個變量存儲特征總數，一個變量存儲初始熵，然后每選一個特征，就用一個集合unique_vals存儲該特征所有可能的取值，再根據這個對該特征進行分類并且計算分類后的熵，最后計算出信息增益info_gain，然后從所有特征值中找出信息增益最大的一個，輸出該特征值。為什么找信息增益最大的呢?上面說到在劃分數據集之前之后信息發生的變化稱為信息增益，也就是劃分前后的熵之差，而熵越高，表明無序程度越大，信息增益實際上就是無序程度減少的程度，越大就表明分類后的無序程度越小。

　　構建決策樹

　　def major_cnt(class_list):

　　class_count={}

　　for vote in class_list:

　　if vote not in class_count.keys():class_count[vote]=0

　　class_count[vote]+=1

　　sorted_class_count=sorted(class_count.items,key=operator.itemgetter,reverse=True)

　　return sorted_class_count[0][0]

　　def create_tree(data_set,labels):

　　class_list=[example[-1] for example in data_set]

　　if class_list.count(class_list[0])==len(class_list):

　　return class_list[0]

　　if len(data_set[0])==1:

　　return major_cnt(class_list)

　　best_feat=choose_best_feature_to_split(data_set)

　　best_feat_label=labels[best_feat]

　　my_tree={best_feat_label:{}}

　　del(labels[best_feat])

　　feat_values=[example[best_feat] for example in data_set]

　　unique_vals=set(feat_values)

　　for value in unique_vals:

　　sub_labels=labels[:]

　　my_tree[best_feat_label][value]=create_tree(split_data_set(data_set,best_feat,value),sub_labels)

　　return my_tree

　　第一個函數和Knn里的一段代碼是很相似的，這里不再多說。

　　第二個函數有兩個參數：數據集data_set和標簽labels，標簽對該算法來說不是必須的，只是能表明數據的內在意義。

　　create_tree中第一個if表示如果數據都是同一類就返回該類別，第二個if表示特征用完后數據仍然不是同一類則返回出現次數最多的分類標簽。然后就是選取最好的特征進行分類，再對分好類的數據集執行同樣的操作，最后生成整顆樹，代碼還是相當簡單的。

　　最后給出完整的代碼：鄭州人流價格 http://www.zzzykdfk.com/

　　from math import log

　　import operator

　　def c_shannon_ent(data_set):

　　num_entries=len(data_set)

　　label_counts={}

　　for feat_vec in data_set:

　　current_label=feat_vec[-1]

　　if current_label not in label_counts.keys():

　　label_counts[current_label]=0

　　label_counts[current_label]+=1

　　shannon_ent=0.0

　　for key in label_counts:

　　prob=float(label_counts[key])/num_entries

　　shannon_ent-=prob*log(prob,2)

　　return shannon_ent

　　def create_data_set():

　　data_set=[[1,1,'yes'],[1,0,'no'],[0,1,'no'],[1,1,'yes'],[0,1,'no']]

　　labels=['no surfacing','flippers']

　　return data_set,labels

　　def split_data_set(data_set,axis,value):

　　ret_data_set=[]

　　for feat_vec in data_set:

　　if feat_vec[axis]==value:

　　reduced_feat_vec=feat_vec[:axis]

　　reduced_feat_vec.extend(feat_vec[axis+1:])

　　ret_data_set.append(reduced_feat_vec)

　　return ret_data_set

　　def choose_best_feature_to_split(data_set):

　　num_features=len(data_set[0])-1

　　base_entropy=c_shannon_ent(data_set)

　　best_info_gain=0.0;best_feature=-1

　　for i in range(num_features):

　　feat_list=[example[i] for example in data_set]

　　unique_vals=set(feat_list)

　　new_entropy=0.0

　　for value in unique_vals:

　　sub_data_set=split_data_set(data_set,i,value)

　　prob=len(sub_data_set)/float(len(data_set))

　　new_entropy+=prob*c_shannon_ent(sub_data_set)

　　info_gain=base_entropy-new_entropy

　　if(info_gain>best_info_gain):

　　best_info_gain=info_gain

　　best_feature=i

　　return best_feature

　　def major_cnt(class_list):

　　class_count={}

　　for vote in class_list:

　　if vote not in class_count.keys():class_count[vote]=0

　　class_count[vote]+=1

　　sorted_class_count=sorted(class_count.items,key=operator.itemgetter,reverse=True)

　　return sorted_class_count[0][0]

　　def create_tree(data_set,labels):

　　class_list=[example[-1] for example in data_set]

　　if class_list.count(class_list[0])==len(class_list):

　　return class_list[0]

　　if len(data_set[0])==1:

　　return major_cnt(class_list)

　　best_feat=choose_best_feature_to_split(data_set)

　　best_feat_label=labels[best_feat]

　　my_tree={best_feat_label:{}}

　　del(labels[best_feat])

　　feat_values=[example[best_feat] for example in data_set]

　　unique_vals=set(feat_values)

　　for value in unique_vals:

　　sub_labels=labels[:]

　　my_tree[best_feat_label][value]=create_tree(split_data_set(data_set,best_feat,value),sub_labels)

　　return my_tree

　　data,labels=create_data_set()

　　print(create_tree(data,labels))

　　輸出結果：{‘no surfacing’:{0:‘no’,1:{‘flippers’:{0:‘no’,1:‘yes’}}}}