【机器学习】KNN算法代码练习
本課程是中國大學慕課《機器學習》的“KNN”章節的課后代碼。
課程地址：
https://www.icourse163.org/course/WZU-1464096179
課程完整代碼：
https://github.com/fengdu78/WZU-machine-learning-course
代碼修改并注釋：黃海廣，haiguang2000@wzu.edu.cn
1．近鄰法是基本且簡單的分類與回歸方法。近鄰法的基本做法是：對給定的訓練實例點和輸入實例點，首先確定輸入實例點的個最近鄰訓練實例點，然后利用這個訓練實例點的類的多數來預測輸入實例點的類。
2．近鄰模型對應于基于訓練數據集對特征空間的一個劃分。近鄰法中，當訓練集、距離度量、值及分類決策規則確定后，其結果唯一確定。
3．近鄰法三要素：距離度量、值的選擇和分類決策規則。常用的距離度量是歐氏距離及更一般的pL距離。值小時，近鄰模型更復雜；值大時，近鄰模型更簡單。值的選擇反映了對近似誤差與估計誤差之間的權衡，通常由交叉驗證選擇最優的。
常用的分類決策規則是多數表決，對應于經驗風險最小化。
4．近鄰法的實現需要考慮如何快速搜索k個最近鄰點。kd樹是一種便于對k維空間中的數據進行快速檢索的數據結構。kd樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用kd樹可以省去對大部分數據點的搜索， 從而減少搜索的計算量。
1.距離度量
在機器學習算法中，我們經常需要計算樣本之間的相似度，通常的做法是計算樣本之間的距離。
設和為兩個向量，求它們之間的距離。
這里用Numpy實現，設和為ndarray <numpy.ndarray>，它們的shape都是(N,)
為所求的距離，是個浮點數（float）。
import?numpy?as?np??#注意：運行代碼時候需要導入NumPy庫。歐氏距離(Euclidean distance)
歐幾里得度量(euclidean metric)(也稱歐氏距離)是一個通常采用的距離定義，指在維空間中兩個點之間的真實距離，或者向量的自然長度(即該點到原點的距離)。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
距離公式：
代碼實現：
def?euclidean(x,?y):return?np.sqrt(np.sum((x?-?y)**2))曼哈頓距離(Manhattan distance)
想象你在城市道路里，要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區距離(City Block distance)。
距離公式：
代碼實現：
def?manhattan(x,?y):return?np.sum(np.abs(x?-?y))切比雪夫距離(Chebyshev distance)
在數學中，切比雪夫距離(Chebyshev distance)或是L∞度量，是向量空間中的一種度量，二個點之間的距離定義是其各坐標數值差絕對值的最大值。以數學的觀點來看，切比雪夫距離是由一致范數(uniform norm)(或稱為上確界范數)所衍生的度量，也是超凸度量(injective metric space)的一種。
距離公式：
若將國際象棋棋盤放在二維直角座標系中，格子的邊長定義為1，座標的軸及軸和棋盤方格平行，原點恰落在某一格的中心點，則王從一個位置走到其他位置需要的步數恰為二個位置的切比雪夫距離，因此切比雪夫距離也稱為棋盤距離。例如位置F6和位置E2的切比雪夫距離為4。任何一個不在棋盤邊緣的位置，和周圍八個位置的切比雪夫距離都是1。
代碼實現：
def?chebyshev(x,?y):return?np.max(np.abs(x?-?y))閔可夫斯基距離(Minkowski distance)
閔氏空間指狹義相對論中由一個時間維和三個空間維組成的時空，為俄裔德國數學家閔可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空間(即假設沒有重力，曲率為零的空間)的概念以及表示為特殊距離量的幾何學是與狹義相對論的要求相一致的。閔可夫斯基空間不同于牛頓力學的平坦空間。取1或2時的閔氏距離是最為常用的，即為歐氏距離，而時則為曼哈頓距離。
當取無窮時的極限情況下，可以得到切比雪夫距離。
距離公式：
代碼實現：
def?minkowski(x,?y,?p):return?np.sum(np.abs(x?-?y)**p)**(1?/?p)漢明距離(Hamming distance)
漢明距離是使用在數據傳輸差錯控制編碼里面的，漢明距離是一個概念，它表示兩個(相同長度)字對應位不同的數量，我們以表示兩個字,之間的漢明距離。對兩個字符串進行異或運算，并統計結果為1的個數，那么這個數就是漢明距離。
距離公式：
代碼實現：
def?hamming(x,?y):return?np.sum(x?!=?y)?/?len(x)余弦相似度(Cosine Similarity)
余弦相似性通過測量兩個向量的夾角的余弦值來度量它們之間的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1；并且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。兩個向量有相同的指向時，余弦相似度的值為1；兩個向量夾角為90°時，余弦相似度的值為0；兩個向量指向完全相反的方向時，余弦相似度的值為-1。這結果是與向量的長度無關的，僅僅與向量的指向方向相關。余弦相似度通常用于正空間，因此給出的值為0到1之間。
二維空間為例，上圖的和是兩個向量，我們要計算它們的夾角θ。余弦定理告訴我們，可以用下面的公式求得：
假定向量是
，向量是，兩個向量間的余弦值可以通過使用歐幾里得點積公式求出：如果向量和不是二維而是維，上述余弦的計算法仍然正確。假定和是兩個維向量，是
，是，則與的夾角余弦等于：代碼實現：
from?math?import?*def?square_rooted(x):return?round(sqrt(sum([a*a?for?a?in?x])),3)def?cosine_similarity(x,?y):numerator?=?sum(a?*?b?for?a,?b?in?zip(x,?y))denominator?=?square_rooted(x)?*?square_rooted(y)return?round(numerator?/?float(denominator),?3)print(cosine_similarity([3,?45,?7,?2],?[2,?54,?13,?15]))0.972KNN算法
1．近鄰法是基本且簡單的分類與回歸方法。近鄰法的基本做法是：對給定的訓練實例點和輸入實例點，首先確定輸入實例點的個最近鄰訓練實例點，然后利用這個訓練實例點的類的多數來預測輸入實例點的類。
2．近鄰模型對應于基于訓練數據集對特征空間的一個劃分。近鄰法中，當訓練集、距離度量、值及分類決策規則確定后，其結果唯一確定。
3．近鄰法三要素：距離度量、值的選擇和分類決策規則。常用的距離度量是歐氏距離。值小時，近鄰模型更復雜；值大時，近鄰模型更簡單。值的選擇反映了對近似誤差與估計誤差之間的權衡，通常由交叉驗證選擇最優的。
常用的分類決策規則是多數表決，對應于經驗風險最小化。
4．近鄰法的實現需要考慮如何快速搜索k個最近鄰點。kd樹是一種便于對k維空間中的數據進行快速檢索的數據結構。kd樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用kd樹可以省去對大部分數據點的搜索， 從而減少搜索的計算量。
python實現，遍歷所有數據點，找出個距離最近的點的分類情況，少數服從多數
import?numpy?as?np import?pandas?as?pd import?matplotlib.pyplot?as?plt from?sklearn.datasets?import?load_iris from?sklearn.model_selection?import?train_test_split from?collections?import?Counter導入鳶尾花數據集
iris?=?load_iris() df?=?pd.DataFrame(iris.data,?columns=iris.feature_names) df['label']?=?iris.target df.columns?=?['sepal?length',?'sepal?width',?'petal?length',?'petal?width',?'label']df.head()| 5.1 | 3.5 | 1.4 | 0.2 | 0 |
| 4.9 | 3.0 | 1.4 | 0.2 | 0 |
| 4.7 | 3.2 | 1.3 | 0.2 | 0 |
| 4.6 | 3.1 | 1.5 | 0.2 | 0 |
| 5.0 | 3.6 | 1.4 | 0.2 | 0 |
選擇長和寬的數據進行可視化
plt.figure(figsize=(12,?8)) plt.scatter(df[:50]['sepal?length'],?df[:50]['sepal?width'],?label='0') plt.scatter(df[50:100]['sepal?length'],?df[50:100]['sepal?width'],?label='1') plt.xlabel('sepal?length',?fontsize=18) plt.ylabel('sepal?width',?fontsize=18) plt.legend() plt.show()Numpy實現
class?KNN:def?__init__(self,?X_train,?y_train,?n_neighbors=3,?p=2):"""parameter:?n_neighbors?臨近點個數parameter:?p?距離度量"""self.n?=?n_neighborsself.p?=?pself.X_train?=?X_trainself.y_train?=?y_traindef?predict(self,?X):#?取出n個點knn_list?=?[]for?i?in?range(self.n):dist?=?np.linalg.norm(X?-?self.X_train[i],?ord=self.p)knn_list.append((dist,?self.y_train[i]))for?i?in?range(self.n,?len(self.X_train)):max_index?=?knn_list.index(max(knn_list,?key=lambda?x:?x[0]))dist?=?np.linalg.norm(X?-?self.X_train[i],?ord=self.p)if?knn_list[max_index][0]?>?dist:knn_list[max_index]?=?(dist,?self.y_train[i])#?統計knn?=?[k[-1]?for?k?in?knn_list]count_pairs?=?Counter(knn)#?????????max_count?=?sorted(count_pairs,?key=lambda?x:?x)[-1]max_count?=?sorted(count_pairs.items(),?key=lambda?x:?x[1])[-1][0]return?max_countdef?score(self,?X_test,?y_test):right_count?=?0n?=?10for?X,?y?in?zip(X_test,?y_test):label?=?self.predict(X)if?label?==?y:right_count?+=?1return?right_count?/?len(X_test)data?=?np.array(df.iloc[:150,?[0,?1,?-1]]) X,?y?=?data[:,:-1],?data[:,-1] X_train,?X_test,?y_train,?y_test?=?train_test_split(X,?y,?test_size=0.3)clf?=?KNN(X_train,?y_train)clf.score(X_test,?y_test)0.7777777777777778test_point?=?[6.0,?3.0] print('Test?Point:?{}'.format(clf.predict(test_point)))Test Point: 2.0Scikit-learn實例
sklearn.neighbors.KNeighborsClassifier
n_neighbors: 臨近點個數，即k的個數，默認是5
p: 距離度量，默認
algorithm: 近鄰算法，可選{'auto', 'ball_tree', 'kd_tree', 'brute'}
weights: 確定近鄰的權重
n_neighbors ：int，optional(default = 5) 默認情況下kneighbors查詢使用的鄰居數。就是k-NN的k的值，選取最近的k個點。
weights ：str或callable，可選(默認=‘uniform’) 默認是uniform，參數可以是uniform、distance，也可以是用戶自己定義的函數。uniform是均等的權重，就說所有的鄰近點的權重都是相等的。distance是不均等的權重，距離近的點比距離遠的點的影響大。用戶自定義的函數，接收距離的數組，返回一組維數相同的權重。
algorithm ：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}，可選 快速k近鄰搜索算法，默認參數為auto，可以理解為算法自己決定合適的搜索算法。除此之外，用戶也可以自己指定搜索算法ball_tree、kd_tree、brute方法進行搜索，brute是蠻力搜索，也就是線性掃描，當訓練集很大時，計算非常耗時。kd_tree，構造kd樹存儲數據以便對其進行快速檢索的樹形數據結構，kd樹也就是數據結構中的二叉樹。以中值切分構造的樹，每個結點是一個超矩形，在維數小于20時效率高。ball tree是為了克服kd樹高緯失效而發明的，其構造過程是以質心C和半徑r分割樣本空間，每個節點是一個超球體。
leaf_size ：int，optional(默認值= 30) 默認是30，這個是構造的kd樹和ball樹的大小。這個值的設置會影響樹構建的速度和搜索速度，同樣也影響著存儲樹所需的內存大小。需要根據問題的性質選擇最優的大小。
p ：整數，可選(默認= 2) 距離度量公式。在上小結，我們使用歐氏距離公式進行距離度量。除此之外，還有其他的度量方法，例如曼哈頓距離。這個參數默認為2，也就是默認使用歐式距離公式進行距離度量。也可以設置為1，使用曼哈頓距離公式進行距離度量。
metric ：字符串或可調用，默認為’minkowski’ 用于距離度量，默認度量是minkowski，也就是p=2的歐氏距離(歐幾里德度量)。
metric_params ：dict，optional(默認=None) 距離公式的其他關鍵參數，這個可以不管，使用默認的None即可。
n_jobs ：int或None，可選(默認=None) 并行處理設置。默認為1，臨近點搜索并行工作數。如果為-1，那么CPU的所有cores都用于并行工作。
不同k(n_neighbors)值下的結果：
clf_sk?=?KNeighborsClassifier(n_neighbors=3) clf_sk.fit(X_train,?y_train)KNeighborsClassifier(n_neighbors=3)clf_sk.score(X_test,?y_test)0.7777777777777778clf_sk?=?KNeighborsClassifier(n_neighbors=4) clf_sk.fit(X_train,?y_train) clf_sk.score(X_test,?y_test)0.8clf_sk?=?KNeighborsClassifier(n_neighbors=5) clf_sk.fit(X_train,?y_train) clf_sk.score(X_test,?y_test)0.7555555555555555自動調參吧，試試循環，找到最優的k值
best_score?=?0.0 best_k?=?-1 for?k?in?range(1,?11):knn_clf?=?KNeighborsClassifier(n_neighbors=k)knn_clf.fit(X_train,?y_train)score?=?knn_clf.score(X_test,?y_test)if?score?>?best_score:best_k?=?kbest_score?=?scoreprint("best_k?=?"?+?str(best_k)) print("best_score?=?"?+?str(best_score))best_k = 2 best_score = 0.8KD樹的劃分和搜索
KD樹
KD樹(K-Dimension Tree)，，也可稱之為維樹，可以用更高的效率來對空間進行劃分，并且其結構非常適合尋找最近鄰居和碰撞檢測。KD樹是一種便于對維空間中的數據進行快速檢索的數據結構。KD樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用KD樹可以省去對大部分數據點的搜索，從而減少搜索的計算量。
KD樹是二叉樹，表示對𝑘維空間的一個劃分(partition)。構造KD樹相當于不斷地用垂直于坐標軸的超平面將𝑘維空間切分，構成一系列的維超矩形區域。KD樹的每個結點對應于一個維超矩形區域。
構造KD樹的方法
構造根結點，使根結點對應于維空間中包含所有實例點的超矩形區域；
通過下面的遞歸方法，不斷地對維空間進行切分，生成子結點。
在超矩形區域(結點)上選擇一個坐標軸和在此坐標軸上的一個切分點，確定一個超平面，這個超平面通過選定的切分點并垂直于選定的坐標軸，將當前超矩形區域切分為左右兩個子區域(子結點)；
這時，實例被分到兩個子區域。這個過程直到子區域內沒有實例時終止(終止時的結點為葉結點)。
在此過程中，將實例保存在相應的結點上。
通常，依次選擇坐標軸對空間切分，選擇訓練實例點在選定坐標軸上的中位數(median)為切分點，這樣得到的KD樹是平衡的。
注意，平衡的KD樹搜索時的效率未必是最優的。
對于構建過程，有兩個優化點：
選擇切分維度
根據數據點在各維度上的分布情況，方差越大，分布越分散從方差大的維度開始切分，有較好的切分效果和平衡性。
確定中值點
預先對原始數據點在所有維度進行一次排序，存儲下來，然后在后續的中值選擇中，無須每次都對其子集進行排序，提升了性能。也可以從原始數據點中隨機選擇固定數目的點，然后對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。
from?collections?import?namedtuple from?pprint?import?pformatclass?Node(namedtuple('Node',?'location?left_child?right_child')):def?__repr__(self):return?pformat(tuple(self))#?kd-tree每個結點中主要包含的數據結構如下 class?KdNode(object):def?__init__(self,?dom_elt,?split,?left,?right):self.dom_elt?=?dom_elt??#?k維向量節點(k維空間中的一個樣本點)self.split?=?split??#?整數（進行分割維度的序號）self.left?=?left??#?該結點分割超平面左子空間構成的kd-treeself.right?=?right??#?該結點分割超平面右子空間構成的kd-treeclass?KdTreeCreate(object):def?__init__(self,?data):k?=?len(data[0])??#?數據維度def?CreateNode(split,?data_set):??#?按第split維劃分數據集exset創建KdNodeif?not?data_set:??#?數據集為空return?None#?key參數的值為一個函數，此函數只有一個參數且返回一個值用來進行比較#?operator模塊提供的itemgetter函數用于獲取對象的哪些維的數據，參數為需要獲取的數據在對象中的序號#data_set.sort(key=itemgetter(split))?#?按要進行分割的那一維數據排序data_set.sort(key=lambda?x:?x[split])split_pos?=?len(data_set)?//?2??#?//為Python中的整數除法median?=?data_set[split_pos]??#?中位數分割點split_next?=?(split?+?1)?%?k??#?cycle?coordinates#?遞歸的創建kd樹return?KdNode(median,split,CreateNode(split_next,?data_set[:split_pos]),??#?創建左子樹CreateNode(split_next,?data_set[split_pos?+?1:]))??#?創建右子樹self.root?=?CreateNode(0,?data)??#?從第0維分量開始構建kd樹,返回根節點#?KDTree的前序遍歷 def?preorder(root):print(root.dom_elt)if?root.left:??#?節點不為空preorder(root.left)if?root.right:preorder(root.right)#?對構建好的kd樹進行搜索，尋找與目標點最近的樣本點： from?math?import?sqrt from?collections?import?namedtuple#?定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節點數 result?=?namedtuple("Result_tuple","nearest_point??nearest_dist??nodes_visited")def?find_nearest(tree,?point):k?=?len(point)??#?數據維度def?travel(kd_node,?target,?max_dist):if?kd_node?is?None:return?result([0]?*?k,?float("inf"),0)??#?python中用float("inf")和float("-inf")表示正負無窮nodes_visited?=?1s?=?kd_node.split??#?進行分割的維度pivot?=?kd_node.dom_elt??#?進行分割的“軸”if?target[s]?<=?pivot[s]:??#?如果目標點第s維小于分割軸的對應值(目標離左子樹更近)nearer_node?=?kd_node.left??#?下一個訪問節點為左子樹根節點further_node?=?kd_node.right??#?同時記錄下右子樹else:??#?目標離右子樹更近nearer_node?=?kd_node.right??#?下一個訪問節點為右子樹根節點further_node?=?kd_node.lefttemp1?=?travel(nearer_node,?target,?max_dist)??#?進行遍歷找到包含目標點的區域nearest?=?temp1.nearest_point??#?以此葉結點作為“當前最近點”dist?=?temp1.nearest_dist??#?更新最近距離nodes_visited?+=?temp1.nodes_visitedif?dist?<?max_dist:max_dist?=?dist??#?最近點將在以目標點為球心，max_dist為半徑的超球體內temp_dist?=?abs(pivot[s]?-?target[s])??#?第s維上目標點與分割超平面的距離if?max_dist?<?temp_dist:??#?判斷超球體是否與超平面相交return?result(nearest,?dist,?nodes_visited)??#?不相交則可以直接返回，不用繼續判斷#----------------------------------------------------------------------#?計算目標點與分割點的歐氏距離temp_dist?=?sqrt(sum((p1?-?p2)**2?for?p1,?p2?in?zip(pivot,?target)))if?temp_dist?<?dist:??#?如果“更近”nearest?=?pivot??#?更新最近點dist?=?temp_dist??#?更新最近距離max_dist?=?dist??#?更新超球體半徑#?檢查另一個子結點對應的區域是否有更近的點temp2?=?travel(further_node,?target,?max_dist)nodes_visited?+=?temp2.nodes_visitedif?temp2.nearest_dist?<?dist:??#?如果另一個子結點內存在更近距離nearest?=?temp2.nearest_point??#?更新最近點dist?=?temp2.nearest_dist??#?更新最近距離return?result(nearest,?dist,?nodes_visited)return?travel(tree.root,?point,?float("inf"))??#?從根節點開始遞歸from?time?import?process_time from?random?import?random#?產生一個k維隨機向量，每維分量值在0~1之間 def?random_point(k):return?[random()?for?_?in?range(k)]#?產生n個k維隨機向量 def?random_points(k,?n):return?[random_point(k)?for?_?in?range(n)]N?=?400000 t0?=?process_time() kd2?=?KdTreeCreate(random_points(3,?N))??#?構建包含四十萬個3維空間樣本點的kd樹 ret2?=?find_nearest(kd2,?[0.1,?0.5,?0.8])??#?四十萬個樣本點中尋找離目標最近的點 t1?=?process_time() print("time:?",?t1?-?t0,?"s") print(ret2)time: 6.28125 s Result_tuple(nearest_point=[0.10173282609374357, 0.501003167941415, 0.8000047195369713], nearest_dist=0.002002262336426111, nodes_visited=36)KD樹的繪圖代碼
from?operator?import?itemgetterdef?kdtree(point_list,?depth=0):if?len(point_list)?==?0:return?None#?選擇“基于深度的軸”，以便軸在所有有效值之間循環#?只支持二維axis?=?depth?%?2#?Sort?point?list?and?choose?median?as?pivot?elementpoint_list.sort(key=itemgetter(axis))median?=?len(point_list)?//?2??#?選擇中值點#?創建節點并構造子樹return?Node(location?=?point_list[median],left_child?=?kdtree(point_list[:median],?depth?+?1),right_child?=?kdtree(point_list[median?+?1:],?depth?+?1))import?matplotlib.pyplot?as?plt#?KD樹的線寬 line_width?=?[4.,?3.5,?3.,?2.5,?2.,?1.5,?1.,?.5,?0.3]def?plot_tree(tree,?min_x,?max_x,?min_y,?max_y,?prev_node,?branch,?depth=0):"""?plot?K-D?tree:param?tree??????input?tree?to?be?plotted:param?min_x:param?max_x:param?min_y:param?max_y:param?prev_node?parent's?node:param?branch????True?if?left,?False?if?right:param?depth?????tree's?depth:return?tree?????node"""cur_node?=?tree.location??#?當前樹節點left_branch?=?tree.left_child??#?左分支right_branch?=?tree.right_child??#?右分支#根據樹的深度設置線條的寬度if?depth?>?len(line_width)?-?1:ln_width?=?line_width[len(line_width)?-?1]else:ln_width?=?line_width[depth]k?=?len(cur_node)axis?=?depth?%?k#?畫垂直分割線if?axis?==?0:if?branch?is?not?None?and?prev_node?is?not?None:if?branch:max_y?=?prev_node[1]else:min_y?=?prev_node[1]plt.plot([cur_node[0],?cur_node[0]],?[min_y,?max_y],linestyle='-',color='red',linewidth=ln_width)#?畫水平分割線elif?axis?==?1:if?branch?is?not?None?and?prev_node?is?not?None:if?branch:max_x?=?prev_node[0]else:min_x?=?prev_node[0]plt.plot([min_x,?max_x],?[cur_node[1],?cur_node[1]],linestyle='-',color='blue',linewidth=ln_width)#?畫當前節點plt.plot(cur_node[0],?cur_node[1],?'ko')#?繪制當前節點的左分支和右分支if?left_branch?is?not?None:plot_tree(left_branch,?min_x,?max_x,?min_y,?max_y,?cur_node,?True,depth?+?1)if?right_branch?is?not?None:plot_tree(right_branch,?min_x,?max_x,?min_y,?max_y,?cur_node,?False,depth?+?1)def?create_diagram(tree,?width,?height,?min_val,?max_val,?delta):plt.figure("Kd?Tree",?figsize=(width,?height))plt.axis([min_val?-?delta,?max_val?+?delta,?min_val?-?delta,?max_val?+?delta])plt.grid(b=True,?which='major',?color='0.75',?linestyle='--')plt.xticks([i?for?i?in?range(min_val?-?delta,?max_val?+?delta,?1)])plt.yticks([i?for?i?in?range(min_val?-?delta,?max_val?+?delta,?1)])#?畫出樹plot_tree(tree,?min_val?-?delta,?max_val?+?delta,?min_val?-?delta,max_val?+?delta,?None,?None)plt.title('KD?Tree')def?label_nodes(node,?i):loc?=?node.locationplt.text(loc[0]?+?0.15,?loc[1]?+?0.15,?str(i),?fontsize=10)if?node.left_child:i?=?label_nodes(node.left_child,?i?+?1)if?node.right_child:i?=?label_nodes(node.right_child,?i?+?1)return?idef?draw_target(point,?radius):plt.plot(point[0],?point[1],?marker='o',?color='#ff007f')circle?=?plt.Circle(point,0.3,facecolor='#ff007f',edgecolor='#ff007f',alpha=0.5)plt.gca().add_patch(circle)#?圍繞目標點繪制超球體circle?=?plt.Circle(point,radius,facecolor='#ffd83d',edgecolor='#ffd83d',alpha=0.5)plt.gca().add_patch(circle)def?draw_neighbors(point_list):for?point?in?point_list:#?畫出找到的最近的鄰居plt.plot(point[0],?point[1],?'go')circle?=?plt.Circle(point,0.3,facecolor='#33cc00',edgecolor='#33cc00',alpha=0.5)plt.gca().add_patch(circle)from?graphviz?import?Digraphdef?add_node(dot,?node,?parent_id=None,?i=0,?edge_label=''):loc?=?node.locationnode_id?=?str(i)dot.node(node_id,?f"{i}\n({loc[0]},{loc[1]})")if?parent_id:dot.edge(parent_id,?node_id,?label=edge_label)if?node.left_child:i?=?add_node(dot,?node.left_child,?node_id,?i?+?1,?'l')if?node.right_child:i?=?add_node(dot,?node.right_child,?node_id,?i?+?1,?'r')return?idef?create_graph(tree):dot?=?Digraph(comment='Kd-tree')dot.attr('node',fontsize='20',shape='circle',width='1',fixedsize='true')dot.attr('edge',?arrowsize='0.7')add_node(dot,?tree)return?dot#?point_list?=?[[2,3],[5,7],[9,6],[4,5],[6,4],[7,2]] point_list1?=?[(2,3),(5,7),(9,6),(4,5),(6,4),(7,2)] tree?=?kdtree(point_list1) print(tree) create_graph(tree)((6, 4),((4, 5), ((2, 3), None, None), ((5, 7), None, None)),((9, 6), ((7, 2), None, None), None))max_int?=?10000000 min_int?=?-max_int?-?1 max_float?=?float('inf')def?get_val_range(point_list):min_val?=?max_intmax_val?=?-max_int?-?1for?point?in?point_list:min_v?=?min(point)if?min_v?<?min_val:min_val?=?min_vmax_v?=?max(point)if?max_v?>?max_val:max_val?=?max_vreturn?(min_val,?max_val)min_val,?max_val=get_val_range(point_list1)create_diagram(tree,?8.,?8.,?min_val,?max_val,?1) label_nodes(tree,?0) plt.show()參考
Prof. Andrew Ng. Machine Learning. Stanford University
李航，《統計學習方法》
機器學習練習6 KNN算法
代碼修改并注釋：黃海廣，haiguang2000@wzu.edu.cn
1．近鄰法是基本且簡單的分類與回歸方法。近鄰法的基本做法是：對給定的訓練實例點和輸入實例點，首先確定輸入實例點的個最近鄰訓練實例點，然后利用這個訓練實例點的類的多數來預測輸入實例點的類。
2．近鄰模型對應于基于訓練數據集對特征空間的一個劃分。近鄰法中，當訓練集、距離度量、值及分類決策規則確定后，其結果唯一確定。
3．近鄰法三要素：距離度量、值的選擇和分類決策規則。常用的距離度量是歐氏距離及更一般的pL距離。值小時，近鄰模型更復雜；值大時，近鄰模型更簡單。值的選擇反映了對近似誤差與估計誤差之間的權衡，通常由交叉驗證選擇最優的。
常用的分類決策規則是多數表決，對應于經驗風險最小化。
4．近鄰法的實現需要考慮如何快速搜索k個最近鄰點。kd樹是一種便于對k維空間中的數據進行快速檢索的數據結構。kd樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用kd樹可以省去對大部分數據點的搜索， 從而減少搜索的計算量。
1.距離度量
在機器學習算法中，我們經常需要計算樣本之間的相似度，通常的做法是計算樣本之間的距離。
設和為兩個向量，求它們之間的距離。
這里用Numpy實現，設和為ndarray <numpy.ndarray>，它們的shape都是(N,)
為所求的距離，是個浮點數（float）。
import?numpy?as?np??#注意：運行代碼時候需要導入NumPy庫。歐氏距離(Euclidean distance)
歐幾里得度量(euclidean metric)(也稱歐氏距離)是一個通常采用的距離定義，指在維空間中兩個點之間的真實距離，或者向量的自然長度(即該點到原點的距離)。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
距離公式：
代碼實現：
def?euclidean(x,?y):return?np.sqrt(np.sum((x?-?y)**2))曼哈頓距離(Manhattan distance)
想象你在城市道路里，要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區距離(City Block distance)。
距離公式：
代碼實現：
def?manhattan(x,?y):return?np.sum(np.abs(x?-?y))切比雪夫距離(Chebyshev distance)
在數學中，切比雪夫距離(Chebyshev distance)或是L∞度量，是向量空間中的一種度量，二個點之間的距離定義是其各坐標數值差絕對值的最大值。以數學的觀點來看，切比雪夫距離是由一致范數(uniform norm)(或稱為上確界范數)所衍生的度量，也是超凸度量(injective metric space)的一種。
距離公式：
若將國際象棋棋盤放在二維直角座標系中，格子的邊長定義為1，座標的軸及軸和棋盤方格平行，原點恰落在某一格的中心點，則王從一個位置走到其他位置需要的步數恰為二個位置的切比雪夫距離，因此切比雪夫距離也稱為棋盤距離。例如位置F6和位置E2的切比雪夫距離為4。任何一個不在棋盤邊緣的位置，和周圍八個位置的切比雪夫距離都是1。
代碼實現：
def?chebyshev(x,?y):return?np.max(np.abs(x?-?y))閔可夫斯基距離(Minkowski distance)
閔氏空間指狹義相對論中由一個時間維和三個空間維組成的時空，為俄裔德國數學家閔可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空間(即假設沒有重力，曲率為零的空間)的概念以及表示為特殊距離量的幾何學是與狹義相對論的要求相一致的。閔可夫斯基空間不同于牛頓力學的平坦空間。取1或2時的閔氏距離是最為常用的，即為歐氏距離，而時則為曼哈頓距離。
當取無窮時的極限情況下，可以得到切比雪夫距離。
距離公式：
代碼實現：
def?minkowski(x,?y,?p):return?np.sum(np.abs(x?-?y)**p)**(1?/?p)漢明距離(Hamming distance)
漢明距離是使用在數據傳輸差錯控制編碼里面的，漢明距離是一個概念，它表示兩個(相同長度)字對應位不同的數量，我們以表示兩個字,之間的漢明距離。對兩個字符串進行異或運算，并統計結果為1的個數，那么這個數就是漢明距離。
距離公式：
代碼實現：
def?hamming(x,?y):return?np.sum(x?!=?y)?/?len(x)余弦相似度(Cosine Similarity)
余弦相似性通過測量兩個向量的夾角的余弦值來度量它們之間的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1；并且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。兩個向量有相同的指向時，余弦相似度的值為1；兩個向量夾角為90°時，余弦相似度的值為0；兩個向量指向完全相反的方向時，余弦相似度的值為-1。這結果是與向量的長度無關的，僅僅與向量的指向方向相關。余弦相似度通常用于正空間，因此給出的值為0到1之間。
二維空間為例，上圖的和是兩個向量，我們要計算它們的夾角θ。余弦定理告訴我們，可以用下面的公式求得：
假定向量是
，向量是，兩個向量間的余弦值可以通過使用歐幾里得點積公式求出：如果向量和不是二維而是維，上述余弦的計算法仍然正確。假定和是兩個維向量，是
，是，則與的夾角余弦等于：代碼實現：
from?math?import?*def?square_rooted(x):return?round(sqrt(sum([a*a?for?a?in?x])),3)def?cosine_similarity(x,?y):numerator?=?sum(a?*?b?for?a,?b?in?zip(x,?y))denominator?=?square_rooted(x)?*?square_rooted(y)return?round(numerator?/?float(denominator),?3)print(cosine_similarity([3,?45,?7,?2],?[2,?54,?13,?15]))0.972KNN算法
1．近鄰法是基本且簡單的分類與回歸方法。近鄰法的基本做法是：對給定的訓練實例點和輸入實例點，首先確定輸入實例點的個最近鄰訓練實例點，然后利用這個訓練實例點的類的多數來預測輸入實例點的類。
2．近鄰模型對應于基于訓練數據集對特征空間的一個劃分。近鄰法中，當訓練集、距離度量、值及分類決策規則確定后，其結果唯一確定。
3．近鄰法三要素：距離度量、值的選擇和分類決策規則。常用的距離度量是歐氏距離。值小時，近鄰模型更復雜；值大時，近鄰模型更簡單。值的選擇反映了對近似誤差與估計誤差之間的權衡，通常由交叉驗證選擇最優的。
常用的分類決策規則是多數表決，對應于經驗風險最小化。
4．近鄰法的實現需要考慮如何快速搜索k個最近鄰點。kd樹是一種便于對k維空間中的數據進行快速檢索的數據結構。kd樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用kd樹可以省去對大部分數據點的搜索， 從而減少搜索的計算量。
python實現，遍歷所有數據點，找出個距離最近的點的分類情況，少數服從多數
import?numpy?as?np import?pandas?as?pd import?matplotlib.pyplot?as?plt from?sklearn.datasets?import?load_iris from?sklearn.model_selection?import?train_test_split from?collections?import?Counter導入鳶尾花數據集
iris?=?load_iris() df?=?pd.DataFrame(iris.data,?columns=iris.feature_names) df['label']?=?iris.target df.columns?=?['sepal?length',?'sepal?width',?'petal?length',?'petal?width',?'label']df.head()| 5.1 | 3.5 | 1.4 | 0.2 | 0 |
| 4.9 | 3.0 | 1.4 | 0.2 | 0 |
| 4.7 | 3.2 | 1.3 | 0.2 | 0 |
| 4.6 | 3.1 | 1.5 | 0.2 | 0 |
| 5.0 | 3.6 | 1.4 | 0.2 | 0 |
選擇長和寬的數據進行可視化
plt.figure(figsize=(12,?8)) plt.scatter(df[:50]['sepal?length'],?df[:50]['sepal?width'],?label='0') plt.scatter(df[50:100]['sepal?length'],?df[50:100]['sepal?width'],?label='1') plt.xlabel('sepal?length',?fontsize=18) plt.ylabel('sepal?width',?fontsize=18) plt.legend() plt.show()Numpy實現
class?KNN:def?__init__(self,?X_train,?y_train,?n_neighbors=3,?p=2):"""parameter:?n_neighbors?臨近點個數parameter:?p?距離度量"""self.n?=?n_neighborsself.p?=?pself.X_train?=?X_trainself.y_train?=?y_traindef?predict(self,?X):#?取出n個點knn_list?=?[]for?i?in?range(self.n):dist?=?np.linalg.norm(X?-?self.X_train[i],?ord=self.p)knn_list.append((dist,?self.y_train[i]))for?i?in?range(self.n,?len(self.X_train)):max_index?=?knn_list.index(max(knn_list,?key=lambda?x:?x[0]))dist?=?np.linalg.norm(X?-?self.X_train[i],?ord=self.p)if?knn_list[max_index][0]?>?dist:knn_list[max_index]?=?(dist,?self.y_train[i])#?統計knn?=?[k[-1]?for?k?in?knn_list]count_pairs?=?Counter(knn)#?????????max_count?=?sorted(count_pairs,?key=lambda?x:?x)[-1]max_count?=?sorted(count_pairs.items(),?key=lambda?x:?x[1])[-1][0]return?max_countdef?score(self,?X_test,?y_test):right_count?=?0n?=?10for?X,?y?in?zip(X_test,?y_test):label?=?self.predict(X)if?label?==?y:right_count?+=?1return?right_count?/?len(X_test)data?=?np.array(df.iloc[:150,?[0,?1,?-1]]) X,?y?=?data[:,:-1],?data[:,-1] X_train,?X_test,?y_train,?y_test?=?train_test_split(X,?y,?test_size=0.3)clf?=?KNN(X_train,?y_train)clf.score(X_test,?y_test)0.7777777777777778test_point?=?[6.0,?3.0] print('Test?Point:?{}'.format(clf.predict(test_point)))Test Point: 2.0Scikit-learn實例
sklearn.neighbors.KNeighborsClassifier
n_neighbors: 臨近點個數，即k的個數，默認是5
p: 距離度量，默認
algorithm: 近鄰算法，可選{'auto', 'ball_tree', 'kd_tree', 'brute'}
weights: 確定近鄰的權重
n_neighbors ：int，optional(default = 5) 默認情況下kneighbors查詢使用的鄰居數。就是k-NN的k的值，選取最近的k個點。
weights ：str或callable，可選(默認=‘uniform’) 默認是uniform，參數可以是uniform、distance，也可以是用戶自己定義的函數。uniform是均等的權重，就說所有的鄰近點的權重都是相等的。distance是不均等的權重，距離近的點比距離遠的點的影響大。用戶自定義的函數，接收距離的數組，返回一組維數相同的權重。
algorithm ：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}，可選 快速k近鄰搜索算法，默認參數為auto，可以理解為算法自己決定合適的搜索算法。除此之外，用戶也可以自己指定搜索算法ball_tree、kd_tree、brute方法進行搜索，brute是蠻力搜索，也就是線性掃描，當訓練集很大時，計算非常耗時。kd_tree，構造kd樹存儲數據以便對其進行快速檢索的樹形數據結構，kd樹也就是數據結構中的二叉樹。以中值切分構造的樹，每個結點是一個超矩形，在維數小于20時效率高。ball tree是為了克服kd樹高緯失效而發明的，其構造過程是以質心C和半徑r分割樣本空間，每個節點是一個超球體。
leaf_size ：int，optional(默認值= 30) 默認是30，這個是構造的kd樹和ball樹的大小。這個值的設置會影響樹構建的速度和搜索速度，同樣也影響著存儲樹所需的內存大小。需要根據問題的性質選擇最優的大小。
p ：整數，可選(默認= 2) 距離度量公式。在上小結，我們使用歐氏距離公式進行距離度量。除此之外，還有其他的度量方法，例如曼哈頓距離。這個參數默認為2，也就是默認使用歐式距離公式進行距離度量。也可以設置為1，使用曼哈頓距離公式進行距離度量。
metric ：字符串或可調用，默認為’minkowski’ 用于距離度量，默認度量是minkowski，也就是p=2的歐氏距離(歐幾里德度量)。
metric_params ：dict，optional(默認=None) 距離公式的其他關鍵參數，這個可以不管，使用默認的None即可。
n_jobs ：int或None，可選(默認=None) 并行處理設置。默認為1，臨近點搜索并行工作數。如果為-1，那么CPU的所有cores都用于并行工作。
不同k(n_neighbors)值下的結果：
clf_sk?=?KNeighborsClassifier(n_neighbors=3) clf_sk.fit(X_train,?y_train)KNeighborsClassifier(n_neighbors=3)clf_sk.score(X_test,?y_test)0.7777777777777778clf_sk?=?KNeighborsClassifier(n_neighbors=4) clf_sk.fit(X_train,?y_train) clf_sk.score(X_test,?y_test)0.8clf_sk?=?KNeighborsClassifier(n_neighbors=5) clf_sk.fit(X_train,?y_train) clf_sk.score(X_test,?y_test)0.7555555555555555自動調參吧，試試循環，找到最優的k值
best_score?=?0.0 best_k?=?-1 for?k?in?range(1,?11):knn_clf?=?KNeighborsClassifier(n_neighbors=k)knn_clf.fit(X_train,?y_train)score?=?knn_clf.score(X_test,?y_test)if?score?>?best_score:best_k?=?kbest_score?=?scoreprint("best_k?=?"?+?str(best_k)) print("best_score?=?"?+?str(best_score))best_k = 2 best_score = 0.8KD樹的劃分和搜索
KD樹
KD樹(K-Dimension Tree)，，也可稱之為維樹，可以用更高的效率來對空間進行劃分，并且其結構非常適合尋找最近鄰居和碰撞檢測。KD樹是一種便于對維空間中的數據進行快速檢索的數據結構。KD樹是二叉樹，表示對維空間的一個劃分，其每個結點對應于維空間劃分中的一個超矩形區域。利用KD樹可以省去對大部分數據點的搜索，從而減少搜索的計算量。
KD樹是二叉樹，表示對𝑘維空間的一個劃分(partition)。構造KD樹相當于不斷地用垂直于坐標軸的超平面將𝑘維空間切分，構成一系列的維超矩形區域。KD樹的每個結點對應于一個維超矩形區域。
構造KD樹的方法
構造根結點，使根結點對應于維空間中包含所有實例點的超矩形區域；
通過下面的遞歸方法，不斷地對維空間進行切分，生成子結點。
在超矩形區域(結點)上選擇一個坐標軸和在此坐標軸上的一個切分點，確定一個超平面，這個超平面通過選定的切分點并垂直于選定的坐標軸，將當前超矩形區域切分為左右兩個子區域(子結點)；
這時，實例被分到兩個子區域。這個過程直到子區域內沒有實例時終止(終止時的結點為葉結點)。
在此過程中，將實例保存在相應的結點上。
通常，依次選擇坐標軸對空間切分，選擇訓練實例點在選定坐標軸上的中位數(median)為切分點，這樣得到的KD樹是平衡的。
注意，平衡的KD樹搜索時的效率未必是最優的。
對于構建過程，有兩個優化點：
選擇切分維度
根據數據點在各維度上的分布情況，方差越大，分布越分散從方差大的維度開始切分，有較好的切分效果和平衡性。
確定中值點
預先對原始數據點在所有維度進行一次排序，存儲下來，然后在后續的中值選擇中，無須每次都對其子集進行排序，提升了性能。也可以從原始數據點中隨機選擇固定數目的點，然后對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。
from?collections?import?namedtuple from?pprint?import?pformatclass?Node(namedtuple('Node',?'location?left_child?right_child')):def?__repr__(self):return?pformat(tuple(self))#?kd-tree每個結點中主要包含的數據結構如下 class?KdNode(object):def?__init__(self,?dom_elt,?split,?left,?right):self.dom_elt?=?dom_elt??#?k維向量節點(k維空間中的一個樣本點)self.split?=?split??#?整數（進行分割維度的序號）self.left?=?left??#?該結點分割超平面左子空間構成的kd-treeself.right?=?right??#?該結點分割超平面右子空間構成的kd-treeclass?KdTreeCreate(object):def?__init__(self,?data):k?=?len(data[0])??#?數據維度def?CreateNode(split,?data_set):??#?按第split維劃分數據集exset創建KdNodeif?not?data_set:??#?數據集為空return?None#?key參數的值為一個函數，此函數只有一個參數且返回一個值用來進行比較#?operator模塊提供的itemgetter函數用于獲取對象的哪些維的數據，參數為需要獲取的數據在對象中的序號#data_set.sort(key=itemgetter(split))?#?按要進行分割的那一維數據排序data_set.sort(key=lambda?x:?x[split])split_pos?=?len(data_set)?//?2??#?//為Python中的整數除法median?=?data_set[split_pos]??#?中位數分割點split_next?=?(split?+?1)?%?k??#?cycle?coordinates#?遞歸的創建kd樹return?KdNode(median,split,CreateNode(split_next,?data_set[:split_pos]),??#?創建左子樹CreateNode(split_next,?data_set[split_pos?+?1:]))??#?創建右子樹self.root?=?CreateNode(0,?data)??#?從第0維分量開始構建kd樹,返回根節點#?KDTree的前序遍歷 def?preorder(root):print(root.dom_elt)if?root.left:??#?節點不為空preorder(root.left)if?root.right:preorder(root.right)#?對構建好的kd樹進行搜索，尋找與目標點最近的樣本點： from?math?import?sqrt from?collections?import?namedtuple#?定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節點數 result?=?namedtuple("Result_tuple","nearest_point??nearest_dist??nodes_visited")def?find_nearest(tree,?point):k?=?len(point)??#?數據維度def?travel(kd_node,?target,?max_dist):if?kd_node?is?None:return?result([0]?*?k,?float("inf"),0)??#?python中用float("inf")和float("-inf")表示正負無窮nodes_visited?=?1s?=?kd_node.split??#?進行分割的維度pivot?=?kd_node.dom_elt??#?進行分割的“軸”if?target[s]?<=?pivot[s]:??#?如果目標點第s維小于分割軸的對應值(目標離左子樹更近)nearer_node?=?kd_node.left??#?下一個訪問節點為左子樹根節點further_node?=?kd_node.right??#?同時記錄下右子樹else:??#?目標離右子樹更近nearer_node?=?kd_node.right??#?下一個訪問節點為右子樹根節點further_node?=?kd_node.lefttemp1?=?travel(nearer_node,?target,?max_dist)??#?進行遍歷找到包含目標點的區域nearest?=?temp1.nearest_point??#?以此葉結點作為“當前最近點”dist?=?temp1.nearest_dist??#?更新最近距離nodes_visited?+=?temp1.nodes_visitedif?dist?<?max_dist:max_dist?=?dist??#?最近點將在以目標點為球心，max_dist為半徑的超球體內temp_dist?=?abs(pivot[s]?-?target[s])??#?第s維上目標點與分割超平面的距離if?max_dist?<?temp_dist:??#?判斷超球體是否與超平面相交return?result(nearest,?dist,?nodes_visited)??#?不相交則可以直接返回，不用繼續判斷#----------------------------------------------------------------------#?計算目標點與分割點的歐氏距離temp_dist?=?sqrt(sum((p1?-?p2)**2?for?p1,?p2?in?zip(pivot,?target)))if?temp_dist?<?dist:??#?如果“更近”nearest?=?pivot??#?更新最近點dist?=?temp_dist??#?更新最近距離max_dist?=?dist??#?更新超球體半徑#?檢查另一個子結點對應的區域是否有更近的點temp2?=?travel(further_node,?target,?max_dist)nodes_visited?+=?temp2.nodes_visitedif?temp2.nearest_dist?<?dist:??#?如果另一個子結點內存在更近距離nearest?=?temp2.nearest_point??#?更新最近點dist?=?temp2.nearest_dist??#?更新最近距離return?result(nearest,?dist,?nodes_visited)return?travel(tree.root,?point,?float("inf"))??#?從根節點開始遞歸from?time?import?process_time from?random?import?random#?產生一個k維隨機向量，每維分量值在0~1之間 def?random_point(k):return?[random()?for?_?in?range(k)]#?產生n個k維隨機向量 def?random_points(k,?n):return?[random_point(k)?for?_?in?range(n)]N?=?400000 t0?=?process_time() kd2?=?KdTreeCreate(random_points(3,?N))??#?構建包含四十萬個3維空間樣本點的kd樹 ret2?=?find_nearest(kd2,?[0.1,?0.5,?0.8])??#?四十萬個樣本點中尋找離目標最近的點 t1?=?process_time() print("time:?",?t1?-?t0,?"s") print(ret2)time: 6.28125 s Result_tuple(nearest_point=[0.10173282609374357, 0.501003167941415, 0.8000047195369713], nearest_dist=0.002002262336426111, nodes_visited=36)KD樹的繪圖代碼
from?operator?import?itemgetterdef?kdtree(point_list,?depth=0):if?len(point_list)?==?0:return?None#?選擇“基于深度的軸”，以便軸在所有有效值之間循環#?只支持二維axis?=?depth?%?2#?Sort?point?list?and?choose?median?as?pivot?elementpoint_list.sort(key=itemgetter(axis))median?=?len(point_list)?//?2??#?選擇中值點#?創建節點并構造子樹return?Node(location?=?point_list[median],left_child?=?kdtree(point_list[:median],?depth?+?1),right_child?=?kdtree(point_list[median?+?1:],?depth?+?1))import?matplotlib.pyplot?as?plt#?KD樹的線寬 line_width?=?[4.,?3.5,?3.,?2.5,?2.,?1.5,?1.,?.5,?0.3]def?plot_tree(tree,?min_x,?max_x,?min_y,?max_y,?prev_node,?branch,?depth=0):"""?plot?K-D?tree:param?tree??????input?tree?to?be?plotted:param?min_x:param?max_x:param?min_y:param?max_y:param?prev_node?parent's?node:param?branch????True?if?left,?False?if?right:param?depth?????tree's?depth:return?tree?????node"""cur_node?=?tree.location??#?當前樹節點left_branch?=?tree.left_child??#?左分支right_branch?=?tree.right_child??#?右分支#根據樹的深度設置線條的寬度if?depth?>?len(line_width)?-?1:ln_width?=?line_width[len(line_width)?-?1]else:ln_width?=?line_width[depth]k?=?len(cur_node)axis?=?depth?%?k#?畫垂直分割線if?axis?==?0:if?branch?is?not?None?and?prev_node?is?not?None:if?branch:max_y?=?prev_node[1]else:min_y?=?prev_node[1]plt.plot([cur_node[0],?cur_node[0]],?[min_y,?max_y],linestyle='-',color='red',linewidth=ln_width)#?畫水平分割線elif?axis?==?1:if?branch?is?not?None?and?prev_node?is?not?None:if?branch:max_x?=?prev_node[0]else:min_x?=?prev_node[0]plt.plot([min_x,?max_x],?[cur_node[1],?cur_node[1]],linestyle='-',color='blue',linewidth=ln_width)#?畫當前節點plt.plot(cur_node[0],?cur_node[1],?'ko')#?繪制當前節點的左分支和右分支if?left_branch?is?not?None:plot_tree(left_branch,?min_x,?max_x,?min_y,?max_y,?cur_node,?True,depth?+?1)if?right_branch?is?not?None:plot_tree(right_branch,?min_x,?max_x,?min_y,?max_y,?cur_node,?False,depth?+?1)def?create_diagram(tree,?width,?height,?min_val,?max_val,?delta):plt.figure("Kd?Tree",?figsize=(width,?height))plt.axis([min_val?-?delta,?max_val?+?delta,?min_val?-?delta,?max_val?+?delta])plt.grid(b=True,?which='major',?color='0.75',?linestyle='--')plt.xticks([i?for?i?in?range(min_val?-?delta,?max_val?+?delta,?1)])plt.yticks([i?for?i?in?range(min_val?-?delta,?max_val?+?delta,?1)])#?畫出樹plot_tree(tree,?min_val?-?delta,?max_val?+?delta,?min_val?-?delta,max_val?+?delta,?None,?None)plt.title('KD?Tree')def?label_nodes(node,?i):loc?=?node.locationplt.text(loc[0]?+?0.15,?loc[1]?+?0.15,?str(i),?fontsize=10)if?node.left_child:i?=?label_nodes(node.left_child,?i?+?1)if?node.right_child:i?=?label_nodes(node.right_child,?i?+?1)return?idef?draw_target(point,?radius):plt.plot(point[0],?point[1],?marker='o',?color='#ff007f')circle?=?plt.Circle(point,0.3,facecolor='#ff007f',edgecolor='#ff007f',alpha=0.5)plt.gca().add_patch(circle)#?圍繞目標點繪制超球體circle?=?plt.Circle(point,radius,facecolor='#ffd83d',edgecolor='#ffd83d',alpha=0.5)plt.gca().add_patch(circle)def?draw_neighbors(point_list):for?point?in?point_list:#?畫出找到的最近的鄰居plt.plot(point[0],?point[1],?'go')circle?=?plt.Circle(point,0.3,facecolor='#33cc00',edgecolor='#33cc00',alpha=0.5)plt.gca().add_patch(circle)from?graphviz?import?Digraphdef?add_node(dot,?node,?parent_id=None,?i=0,?edge_label=''):loc?=?node.locationnode_id?=?str(i)dot.node(node_id,?f"{i}\n({loc[0]},{loc[1]})")if?parent_id:dot.edge(parent_id,?node_id,?label=edge_label)if?node.left_child:i?=?add_node(dot,?node.left_child,?node_id,?i?+?1,?'l')if?node.right_child:i?=?add_node(dot,?node.right_child,?node_id,?i?+?1,?'r')return?idef?create_graph(tree):dot?=?Digraph(comment='Kd-tree')dot.attr('node',fontsize='20',shape='circle',width='1',fixedsize='true')dot.attr('edge',?arrowsize='0.7')add_node(dot,?tree)return?dot#?point_list?=?[[2,3],[5,7],[9,6],[4,5],[6,4],[7,2]] point_list1?=?[(2,3),(5,7),(9,6),(4,5),(6,4),(7,2)] tree?=?kdtree(point_list1) print(tree) create_graph(tree)((6, 4),((4, 5), ((2, 3), None, None), ((5, 7), None, None)),((9, 6), ((7, 2), None, None), None))svgmax_int?=?10000000 min_int?=?-max_int?-?1 max_float?=?float('inf')def?get_val_range(point_list):min_val?=?max_intmax_val?=?-max_int?-?1for?point?in?point_list:min_v?=?min(point)if?min_v?<?min_val:min_val?=?min_vmax_v?=?max(point)if?max_v?>?max_val:max_val?=?max_vreturn?(min_val,?max_val)min_val,?max_val=get_val_range(point_list1)create_diagram(tree,?8.,?8.,?min_val,?max_val,?1) label_nodes(tree,?0) plt.show()參考
Prof. Andrew Ng. Machine Learning. Stanford University
李航，《統計學習方法》 葉斯估計。
本站qq群955171419，加入微信群請掃碼：
總結
以上是生活随笔為你收集整理的【机器学习】KNN算法代码练习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 无线网络受限制或无连接处理方法
- 下一篇： 互联网内容平台到底要用到多少AI技术？