上一學期主要的學習和研究任務是模式識別、信號理論和圖像處理，實際上這些領域都與機器學習有或多或少的交集。因此，仍在繼續深入閱讀《機器學習》、觀看斯坦福大學的機器學習課程。在此過程中因為未來課題組項目的要求，需要接觸Python，因此選擇了《機器學習實戰》這本書，同時參考教材和視頻一起學習。事實上該書的理論研究不夠深入，只能算是練習Python并驗證一些著名的機器學習算法的工具書了。
在介紹k-近鄰算法之前，對機器學習算法進行簡單的分類和梳理：簡單來說，機器學習主要分為兩大類，有監督學習(supervised learning)和無監督學習(unsupervised learning)。有監督學習又可分兩類：分類（classification.）和回歸（regression），分類的任務就是把一個樣本劃為某個已知類別，每個樣本的類別信息在訓練時需要給定，比如人臉識別、行為識別、目標檢測等都屬于分類。回歸的任務則是預測一個數值，比如給定房屋市場的數據（面積，位置等樣本信息）來預測房價走勢。而無監督學習也可以成兩類：聚類（clustering）和密度估計（density estimation）,聚類則是把一堆數據聚成弱干組，沒有類別信息；密度估計則是估計一堆數據的統計參數信息來描述數據,比如深度學習的RBM。
作為開頭章節，作者介紹了簡單而容易理解的k-近鄰(kNN)算法。該算法在模式識別一書中與Parzen窗估計放在一起講，屬于非參數估計的方法。這類方法用于處理任意形式的概率分布而不必事先考慮概率密度的參數形式。
更多關于非參數估計方法的介紹：[http://blog.csdn.net/liyuefeilong/article/details/45274325](http://blog.csdn.net/liyuefeilong/article/details/45274325)
在使用k-近鄰算法前，需要了解算法的優缺點和適用性：?
優點：精度高，對異常數據不敏感，無數據輸入假定?
缺點：時間和空間復雜度均較高?
適用的數據類型：數值型和標識型
基本K均值算法的基本思路為：首先你需要有一組訓練樣本，也稱作訓練樣本集。該集合中每個樣本的分類類別都是已知的，也就是我們知道每個數據與所屬分類的對應關系。此時，可以輸入一個待預測的數據，將新數據的每個特征與訓練樣本集中每個數據的特征進行比較，根據一種比較結果（如歐氏距離），找出`k`?個與待預測數據最相似的訓練樣本，看看這些訓練樣本都是屬于哪一類的，最后就是秉承“多數占優”的原則：既然待預測數據與很多個某A類的訓練樣本都很近，和其他類不是很相近，那就把預測數據判定為A類吧。
在以上描述中提出使用歐氏距離作為待預測數據和訓練樣本集的比較結果，即假設測試樣本為`a`，而`xi`表示訓練樣本集中的第`i`個樣本，測試樣本和訓練樣本均有`n`個特征屬性，則測試樣本和訓練樣本之間的歐氏距離定義為：
通常該算法的k是不大于20的正整數。當`k=7`?時，根據上述歐氏距離公式計算出78個與待預測數據最近的訓練樣本，在這7個實例中，某個分類出現的次數最多，則預測數據就被分到該類。
以下是根據《機器學習實戰》一書寫的代碼，直接實現了k-近鄰算法，由于對python不十分熟悉，因此對于kNN的算法實現難度主要存在于Numpy的使用上，但畢竟這是學習python的一個好機會，以下為算法的代碼實現：
~~~
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 29 14:36:02 2015
Input: data: vector of test sample (1xN)
sample: size m data set of known vectors (NxM)
labels: labels of the sample (1xM vector)
k: number of neighbors
Output: the class label
@author: peng__000
"""
from numpy import *
import operator
from os import listdir
# training samples
sample = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
# the labels of samples
label = ['A', 'A', 'B', 'B']
def classify(data, sample, label, k):
SampleSize = sample.shape[0] # 訓練樣本集的行數
DataMat = tile(data, (SampleSize, 1)) #將data擴展到和訓練樣本集sample一樣的行數
delta = (DataMat - sample)**2
distance = (delta.sum(axis = 1))**0.5 # 以上三步計算歐氏距離
sortedDist = distance.argsort() # 對歐氏距離向量進行排序
classCount = {}
# 以下操作獲取距離最近的k個樣本的標簽
for i in range(k):
votedLabel = label[sortedDist[i]]
classCount[votedLabel] = classCount.get(votedLabel, 0) + 1
result = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
return result[0][0]
print classify([10,0], sample, label, 3) # test
~~~
這段簡短的代碼除了一些矩陣的操作、簡單的排序操作外沒有復雜的運算。
在簡單完成k-近鄰算法的實現后，接下來需要將算法的應用到別的場景，根據書本《機器學習實戰》上的教程，主要測試了針對約會網站的分類和手寫識別系統。
總的來說，k-近鄰算法是模式識別和機器學習領域中最簡單且最有效的分類算法，缺點是運算速度差強人意，而且在算法執行過程中須保存全部數據集，如果訓練數據集非常巨大，必須使用大量的存儲空間，此時算法的性能會大大降低。k-近鄰算法的另一個缺陷是無法給出任何數據的基礎結構信息，因此也無法知曉平均實例樣本和典型實例樣本具有什么樣的特征。通過實驗過程也可以發現，對參數的選取和調整要根據實際情況進行多次實驗才能達到比較理想的效果。
