kd樹python

❶ 怎樣才算是一個合格的機器學習工程師

舉個反面例子你就知道了。像我本人，在相關知識上掌握的一般般，基本概念倒是知道的差不多，但是讓我上來就推導幾個公式，細致地講解幾個概念，隨手coding幾個模型就得gg。給我一個任務，調研出要用的技術路線倒是不難（畢竟很多任務就那麼些東西）。但是上手後遇到各個問題處理的又是一頭包，什麼數據太少、樣本分布不均衡、模型效果不佳，等等具體的問題都解決的不好。都說了是工程師，肯定能解決實際問題才是合格的工程師，所以對我取反就行了。

❷ 如何准備機器學習工程師的面試

機器學習工程師崗位面試主要看機器學習掌握得如何，自己做的相關項目，以及coding能力。機器學習大概問過lr，svm，pr曲線，樸素貝葉斯的assumption，ensemble方法，決策樹節點用哪個特徵進行劃分，gbdt原理，random forest原理，pca和lda降維原理，寫k means和gmm公式，特徵選擇的方法有哪些，cnn與rnn的區別，你所知道的距離度量方式，你所知道的loss function，蓄水池抽樣。過了簡歷說明你做的項目跟面試官所在團隊做的東西相似度比較高，所以面試官一般會比較懂你做的項目。在問的時候，面試官會問你一些他覺得該項目的難點，以及你是如何解決的，比如樣本不平衡問題，負樣本如何挑選等問題。面試前一定要好好過一下自己做的項目，想一想你是面試官你會問自己什麼問題。

❸ python 如何畫出KD數

簡單的KNN演算法在為每個數據點預測類別時都需要遍歷整個訓練數據集來求解距離，這樣的做法在訓練數據集特別大的時候並不高效，一種改進的方法就是使用kd樹來存儲訓練數據集，這樣可以使KNN分類器更高效。
KD樹的主要思想跟二叉樹類似，我們先來回憶一下二叉樹的結構，二叉樹中每個節點可以看成是一個數，當前節點總是比左子樹中每個節點大，比右子樹中每個節點小。而KD樹中每個節點是一個向量(也可能是多個向量)，和二叉樹總是按照數的大小劃分不同的是，KD樹每層需要選定向量中的某一維，然後根據這一維按左小右大的方式劃分數據。在構建KD樹時，關鍵需要解決2個問題：（1）選擇向量的哪一維進行劃分（2）如何劃分數據。第一個問題簡單的解決方法可以是選擇隨機選擇某一維或按順序選擇，但是更好的方法應該是在數據比較分散的那一維進行劃分（分散的程度可以根據方差來衡量）。好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數來進行劃分，這樣問題2也得到了解決。下面是建立KD樹的Python代碼：
def build_tree(data, dim, depth):
"""
建立KD樹

Parameters
----------
data:numpy.array
需要建樹的數據集
dim:int
數據集特徵的維數
depth:int
當前樹的深度
Returns
-------
tree_node:tree_node namedtuple
樹的跟節點
"""
size = data.shape[0]
if size == 0:
return None
# 確定本層劃分參照的特徵
split_dim = depth % dim
mid = size / 2
# 按照參照的特徵劃分數據集
r_indx = np.argpartition(data[:, split_dim], mid)
data = data[r_indx, :]
left = data[0: mid]
right = data[mid + 1: size]
mid_data = data[mid]
# 分別遞歸建立左右子樹
left = build_tree(left, dim, depth + 1)
right = build_tree(right, dim, depth + 1)
# 返回樹的根節點
return Tree_Node(left=left,
right=right,
data=mid_data,
split_dim=split_dim)


對於一個新來的數據點x，我們需要查找KD樹中距離它最近的節點。KD樹的查找演算法還是和二叉樹查找的演算法類似，但是因為KD樹每次是按照某一特定的維來劃分，所以當從跟節點沿著邊查找到葉節點時候並不能保證當前的葉節點就離x最近，我們還需要回溯並在每個父節點上判斷另一個未查找的子樹是否有可能存在離x更近的點（如何確定的方法我們可以思考二維的時候，以x為原點，當前最小的距離為半徑畫園，看是否與劃分的直線相交，相交則另一個子樹中可能存在更近的點），如果存在就進入子樹查找。
當我們需要查找K個距離x最近的節點時，我們只需要維護一個長度為K的優先隊列保持當前距離x最近的K個點。在回溯時，每次都使用第K短距離來判斷另一個子節點中是否存在更近的節點即可。下面是具體實現的python代碼：
def search_n(cur_node, data, queue, k):
"""
查找K近鄰，最後queue中的k各值就是k近鄰

Parameters
----------
cur_node:tree_node namedtuple
當前樹的跟節點
data:numpy.array
數據
queue:Queue.PriorityQueue
記錄當前k個近鄰，距離大的先輸出
k:int
查找的近鄰個數
"""
# 當前節點為空，直接返回上層節點
if cur_node is None:
return None
if type(data) is not np.array:
data = np.asarray(data)
cur_data = cur_node.data
# 得到左右子節點
left = cur_node.left
right = cur_node.right
# 計算當前節點與數據點的距離
distance = np.sum((data - cur_data) ** 2) ** .5
cur_split_dim = cur_node.split_dim
flag = False # 標記在回溯時是否需要進入另一個子樹查找
# 根據參照的特徵來判斷是先進入左子樹還是右子樹
if data[cur_split_dim] > cur_data[cur_split_dim]:
tmp = right
right = left
left = tmp
# 進入子樹查找
search_n(left, data, queue, k)
# 下面是回溯過程
# 當隊列中沒有k個近鄰時，直接將當前節點入隊，並進入另一個子樹開始查找
if len(queue) < k:

neg_distance = -1 * distance
heapq.heappush(queue, (neg_distance, cur_node))
flag = True
else:
# 得到當前距離數據點第K遠的節點
top_neg_distance, top_node = heapq.heappop(queue)
# 如果當前節點與數據點的距離更小，則更新隊列（當前節點入隊，原第k遠的節點出隊）
if - 1 * top_neg_distance > distance:
top_neg_distance, top_node = -1 * distance, cur_node
heapq.heappush(queue, (top_neg_distance, top_node))
# 判斷另一個子樹內是否可能存在跟數據點的距離比當前第K遠的距離更小的節點
top_neg_distance, top_node = heapq.heappop(queue)
if abs(data[cur_split_dim] - cur_data[cur_split_dim]) < -1 * top_neg_distance:
flag = True
heapq.heappush(queue, (top_neg_distance, top_node))
# 進入另一個子樹搜索
if flag:
search_n(right, data, queue, k)525354555657

以上就是KD樹的Python實踐的全部內容，由於本人剛接觸python不久，可能實現上並不優雅，也可能在演算法理解上存在偏差，如果有任何的錯誤或不足，希望各位賜教。

❹ 從小白到機器學習演算法工程師，我做了哪些准備

機器學習方面的面試主要分成三個部分： 1. 演算法和理論基礎 2. 工程實現能力與編碼水平 3. 業務理解和思考深度 1. 理論方面，我推薦最經典的一本書《統計學習方法》，這書可能不是最全的，但是講得最精髓，薄薄一本，適合面試前突擊准備。 我認為一些要點是： 統計學習的核心步驟：模型、策略、演算法，你應當對logistic、SVM、決策樹、KNN及各種聚類方法有深刻的理解。能夠隨手寫出這些演算法的核心遞歸步的偽代碼以及他們優化的函數表達式和對偶問題形式。 非統計學習我不太懂，做過復雜網路，但是這個比較深，面試可能很難考到。 數學知識方面，你應當深刻理解矩陣的各種變換，尤其是特徵值相關的知識。 演算法方面：你應當深刻理解常用的優化方法：梯度下降、牛頓法、各種隨機搜索演算法（基因、蟻群等等），深刻理解的意思是你要知道梯度下降是用平面來逼近局部，牛頓法是用曲面逼近局部等等。 2. 工程實現能力與編碼水平 機器學習從工程實現一般來講都是某種數據結構上的搜索問題。 你應當深刻理解在1中列出的各種演算法對應應該採用的數據結構和對應的搜索方法。比如KNN對應的KD樹、如何給圖結構設計數據結構？如何將演算法map-red化等等。 一般來說要麼你會寫C，而且會用MPI，要麼你懂Hadoop，工程上基本都是在這兩個平台實現。實在不濟你也學個python吧。 3. 非常令人失望地告訴你盡管機器學習主要會考察1和2 但是實際工作中，演算法的先進性對真正業務結果的影響，大概不到30%。當然演算法必須要足夠快，離線演算法最好能在4小時內完成，實時演算法我沒搞過，要求大概更高。 機器學習大多數場景是搜索、廣告、垃圾過濾、安全、推薦系統等等。對業務有深刻的理解對你做出來的系統的結果影響超過70%。這里你沒做過實際的項目，是完全不可能有任何體會的，我做過一個推薦系統，沒有什麼演算法上的高大上的改進，主要是業務邏輯的創新，直接就提高了很明顯的一個CTR（具體數目不太方便透露，總之很明顯就是了）。如果你做過實際的項目，一定要主動說出來，主動讓面試官知道，這才是最大最大的加分項目。 最後舉個例子，阿里內部機器學習挑戰賽，無數碾壓答主10000倍的大神參賽。最後冠軍沒有用任何高大上的演算法而是基於對數據和業務的深刻理解和極其細致的特徵調優利用非常基本的一個演算法奪冠。所以啥都不如真正的實操擼幾個生產項目啊。