分類

? 什么是分類
– 分類模型: 輸入樣本的屬性值，輸出對應的類別，將每個樣本映射到預先定義好的類別
? 常用分類算法

– Knn算法
– 決策樹
– 貝葉斯分類器
– 支持向量機
– 神經網絡
5種算法！！

分類：分為娛樂新聞、民生新聞、
識別到各個類別之間的差距，對于新給的一個新聞，根據歷史信息預測到它的類別

有監督的學習：類別是已經確定的

根據訓練集數據模型的創建、模型的使用
類別是給定的

距離

? 馬氏距離與歐氏距離

最近鄰算法Knn

? 算法主要思想:
1 選取k個和待分類點距離最近的樣本點
2 看1中的樣本點的分類情況，投票決定待分類點所屬的類

先看看自己身邊的朋友是怎么樣的。
k=3歸為紅色類
k=5歸為藍色類

但是沒有給出k到底取多少

距離的概念

歐式距離 直線間距離

馬氏距離 點與點的相似度

貝葉斯分類器

貝葉斯公式：條件概率

原理：不知道確切的分類，但是可以看到表現出來的屬性

到底 落在分布1的概率高還是落在分布2的概率高

根據 先決條件 ，判斷樣本是落在哪一類的

要求屬性之間相互獨立

可能會有一些因果關系的存在

根據所表現出來的，反推出它歸于某一個類的概率

貝葉斯網絡也適用于多分類的情況

決策樹 decision tree

? 什么是決策樹
? 輸入:學習集
? 輸出:分類規則(決策樹)

? 樹中每一個非葉節點表示一個決策，該決策的值導致不同的決策結果(葉節點)或者影 響后面的決策選擇。
? 根據給定的未知分類的元組X，根據其屬性值跟蹤一條由根節點到葉節點的路徑，該 葉節點就是該元組的分類結果預測。

常見的決策樹算法有:

? ID3(->C4.5->C5.0)

?CART(Classification And Regression Tree)
這兩類算法的主要區別在于 分裂屬性時的選擇方法 。

在構建決策樹時，這兩類算法的流程基本一樣，都采用 貪心方法，自頂而下遞歸構建決策樹。

名詞解釋

? 數據分區D
代表了節點上的數據

? 元組屬性列表

? 屬性A
? 結點N
? 類別C

貪心算法構建決策樹

? 1.創建一個結點N。
如果D中的元組都在同一個類別C中，則N作為葉結點，以C標記;
如果屬性列表為空，則N作為葉節點，以D中最多的類別C作為標記。

? 2.根據分裂準則找出“最好”的分裂屬性A，并用該分裂屬性標記N。
1)A是離散的，則 A的每個已知值都產生一個分支;
2)A是連續的，則產生A≤s和A>s兩個分支;
3)若A是連續的，并且必須產生二叉樹，則產生A∈A1和A∈A2兩個分支，其中A1，A2非空且 A1∪A2=A

? 3.若給定的分支中的元組非空，對于D的每一個分支Dj，重復步驟1,2

屬性選擇度量

? 如果我們根據分裂準則把D劃分為較小的分區，最好的情況是每個分區都是純的，即落 在一個給定分區的所有元組都是相同的類。最好的分裂準則就是 令到每個分區盡量的純。
? 屬性選擇度量給學習集中的每個屬性提供了評定。具有最好度量得分的屬性被選為 分裂 屬性 。

熵

? ID3系列算法:基于熵
? 1948年，香農提出了“信息熵”的概念，解決了對系統信息的量化度量問題。

ID3——信息增益

? 信息增益定義為原來的信息需求與新的信息需求之間的差，即
? Gain(A)=Info(D)-InfoA(D)
? Gain(A)表示知道A的值而導致的信息需求的期望減少。 ? 選擇具有最大信息增益的屬性作為分裂屬性

連續值的信息增益

? 對于連續值屬性A，要計算它的信息增益，其實也等價于尋找A的“最佳”分裂點。
? 1.將A的值按遞增排序
?2. 每對相鄰值的中點(v個)是一個可能的分裂點。將A按照這些分裂點做v-1次劃分，
計算每次劃分的InfoA(D)
? 3.選擇具有最小期望信息需求的點作為A的分裂點，并根據該分裂點計算A的信息增益

ID3算法的缺陷

? 信息增益存在著一定的局限性，它會傾向于選擇具有大量值的屬性，但是有時候這種屬 性對分類其實沒有多大作用。

例如每個學生的學號對其成績高低的分類沒有作用，但是 如果利用信息增益來選擇分裂屬性，學號這一屬性的劃分會導致大量分區，每一個分區 都只有一個學生所以每個分區都是純的，但是這樣的劃分對分辨學生成績的高低并沒有 用。

C4.5——增益率

CART

與ID3算法的差異:
1.不是基于信息熵，而是基于 不純度 來評定屬性
2.嚴格的二元劃分。使用ID3算法有可能會產生多叉樹，但是使用CART算法只產生 二叉樹
3.根據y值類型的不同可分為 回歸樹 和 分類樹
連續變量。回歸樹
離散變量。分類樹

分類樹和回歸樹

? 分類樹:y值是 類別
? 回歸樹:y值是 實數
? 異同:1.所用算法思路一致
? 2.評定分裂標準不一樣

分類樹

回歸樹

? 將空間中的點劃分成不同的區域，同一個 區域中的點擁有相同的水平

例子

? Hitters數據集
? 根據籃球球員的各種 數據來預測籃球員的 薪酬的對數值(log salary)

樹的修剪

? 為什么要修剪:避免過度擬合，簡化模型
? 兩種修剪方法:先剪枝與后剪枝

? 先剪枝:通過設定一定的閥值來停止樹的生長
例如，在構建樹模型時，使用信息增益、基尼指數來度量劃分的優劣。可以 預先設定一個閥值，當劃分一個結點的元組到時低于預設的閥值時，停止改 子集的劃分
? 后剪枝:等樹完全生成后再通過刪除結點去修剪決策樹。由于先剪枝中，選擇合適的 閥值存在一定的困難，所以后剪枝更加常用

后剪枝

決策樹的優缺點

? 優點:
?1. 樹模型十分通俗易懂，解釋起來簡單明了
?2. 相對于其他模型，樹模型可以通過圖形模型展示，即使不具備相應專業知識的人可以一名了然
?3.樹模型可以直接處理 定性變量 ，不需要增加虛擬變量

? 缺點:
? 準確率不夠高

從線性判別法說起

? 用 一條直線 來劃分學習集(這條直線一定存在嗎?)
? 然后根據 待測點在直線的哪一邊 決定它的分類

支持向量機SVM

? 支持向量機SVM
– 原創性(非組合)的具有明顯直觀幾何意義的分類算法，具有較高的準確率
– 思想直觀，但細節異常復雜，內容涉及 凸分析算法，核函數，神經網絡 等高深的領域，幾乎可以寫成單獨的大部頭與著。大部分非與業人士會覺得難以理解。
? 兩種情況
– 簡單情況:線性可分，把問題轉化為一個凸優化問題，可以用 拉格朗日乘子法 簡化，然后用既有的算法解決
– 復雜情況:線性不可分，用映射函數 將樣本投射到高維空間 ，使其變成線性可分的情形。利用 核函數 來減少高維 度計算量

? 最優分隔平面

最大邊緣超平面(MMH)

非線性情況

代碼

            
              # -*- coding: utf-8 -*-
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_recall_curve
from sklearn.metrics import classification_report
from sklearn.naive_bayes import BernoulliNB
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cross_validation import train_test_split
import matplotlib.pyplot as plt
import pandas as pd

####knn最鄰近算法####
inputfile = 'd:/data/sales_data.xls'
data = pd.read_excel(inputfile, index_col = u'序號') #導入數據

#數據是類別標簽，要將它轉換為數據
#用1來表示“好”、“是”、“高”這三個屬性，用-1來表示“壞”、“否”、“低”
data[data == u'好'] = 1
data[data == u'是'] = 1
data[data == u'高'] = 1
data[data != 1] = -1
x = data.iloc[:,:3].as_matrix().astype(int)
y = data.iloc[:,3].as_matrix().astype(int)


#拆分訓練數據與測試數據 
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2)


#訓練KNN分類器 
clf = KNeighborsClassifier(algorithm='kd_tree')
clf.fit(x_train, y_train)

#測試結果
answer = clf.predict(x_test)
print(x_test)
print(answer)
print(y_test)
print(np.mean( answer == y_test))

#準確率
precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train))
print(classification_report(y_test, answer, target_names = ['高', '低']))


####貝葉斯分類器####
#訓練貝葉斯分類器
clf = BernoulliNB() 
clf.fit(x_train,y_train)


#測試結果
answer = clf.predict(x_test)
print(x_test)
print(answer)
print(y_test)
print(np.mean( answer == y_test))
print(classification_report(y_test, answer, target_names = ['低', '高']))


####決策樹####
from sklearn.tree import DecisionTreeClassifier as DTC
dtc = DTC(criterion='entropy') #建立決策樹模型，基于信息熵
dtc.fit(x_train, y_train) #訓練模型

#導入相關函數，可視化決策樹。
#導出的結果是一個dot文件，需要安裝Graphviz才能將它轉換為pdf或png等格式。
from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO
with open("tree.dot", 'w') as f:
  f = export_graphviz(dtc, out_file = f)


#測試結果
answer = dtc.predict(x_test)
print(x_test)
print(answer)
print(y_test)
print(np.mean( answer == y_test))
print(classification_report(y_test, answer, target_names = ['低', '高']))


####SVM####
from sklearn.svm import SVC
clf =SVC()
clf.fit(x_train, y_train)  

#測試結果
answer = clf.predict(x_test)
print(x_test)
print(answer)
print(y_test)
print(np.mean( answer == y_test))
print(classification_report(y_test, answer, target_names = ['低', '高']))