lazy演算法

⑵ 用沐神的方法閱讀PyTorch FX論文

作者丨BBuf

來源丨GiantPandaCV

編輯丨極市平台

torch.fx 對於PyTorch來說確實是一個比較好的工作，因為它消除了一些動態圖和靜態圖的Gap。比如在圖改寫方面， torch.fx 讓PyTorch想做一些其它靜態圖框架的運算元融合優化非常容易。並侍差閉且 torch.fx 讓後訓練量化和感知訓練量化以及AMP等的實現難度大大降低，這得益於我們可以直接在Python層操作這個IR，所以我認為這是一個不錯的工作。尤其是對使用PyTorch開發的演算法工程師來說，現慶洞在可以基於這個特性大開腦洞了。 torch.fx 的賣點就是，它使用純Python語言實現了一個可以捕獲PyTorch程序的計算圖並轉化為一個IR的庫，並且非常方便的在這個IR上做Pass，同時提供將變換後的IR Codegen合法的Python代碼功能。我覺得算是達到了在Eager下寫Pass就像做鏈表插入刪除題目一樣順滑。

PyTorch FX論文的鏈接在： https://arxiv.org/pdf/2112.08429.pdf 。

下面我就以沐神的論文閱讀順序來分享一下閱讀體驗，幫助大家搞清楚PyTorch FX這個特性到底是什麼，以及它可以在PyTorch中發揮什麼作用。

摘要部分簡單指明了像PyTorch這種基於動態圖執行模式的深度學習框架雖然提升了用戶的易用性。但是在一些真實場景中，用戶可能是需要捕獲和變換程序結構（也可以直接理解為神經網路的結構）來進行性能優化，可視化，分析和硬體調優等。為了解決這個痛點，PyTorch設計了 torch.fx 這個模塊來做PyTorch程序的捕獲和變換，這個模塊是純Python開發的。

這一節主要是講了一下 torch.fx 的賣點，就是說動態圖雖然易用性很強，但是圖結構不能被提前感知和變換，但通過這篇論文的 torch.fx 模塊，這件事就成啦！

早期的圖模式或者叫 define-and-run 的靜態圖框架有Caffe，TensorFlow等，它們設計了一個表示圖的IR，用戶通過調用這些框架提供的API來構建IR。然後我們可以在這個IR上做程序微分，將IR切分到設備上實現並行，量化，性能優化等等。但這些事情一般都要求開發者在領域特定的語言上去做，比如以OneFlow的靜態圖模式為例，要做圖切分，量化，性能優化等老裂都需要基於C++去開發，並且調試也會相對比較難（要藉助pdb，gdb等等專業工具）。

現在的eager模式或者叫 define-by-run 的動態圖框架有PyTorch，TensorFlow Eager模式等，它們可以隨心所欲的讓用戶基於腳本語言編程並且可以解決大多數的訓練（基於自動微分）和預測任務。但是有一些變換比如 「量化和運算元融合」 是不能直接做的，而這一點在靜態圖模式下則很簡單。為了消除這種Gap，動態圖框架需要一種從用戶的程序捕獲圖結構的方法來使能這些變換。

在捕獲和變換程序時，eager和graph模式的深度學習框架都必須在 「捕獲程序結構」 、 「程序特化」 和 「保存程序的IR的設計」 方面做出選擇。這些選擇的組合決定了可在框架中表示的 「程序空間」 、 「編寫變換的難易程度」以及「生成的變換程序的性能」 。 「一般來說，支持程序的高性能運行需要更復雜的捕獲框架和IR，從而使轉換更難編寫」 。每一段相關工作我就不詳細過了，只描述每一段工作的核心是在說什麼，相關細節大家可以查看原始論文。

這一節提到了PyTorch的 jit.trace ，MxNet Gluon，TensorFlow的 tf.function 等程序捕獲方法，並指出這些方法只能處理Python的一些子集。然後，TorchScript通過在AST上分析可以處理控制流和更多的Python語法。然後還提了一下Julia和Swift For TensorFlow中將捕獲程序結構的介面集成到了非Python的宿主語言中，要使用的話需要用戶放棄Python生態系統。

對於 a+b 這個Python語句來說，這個表達式對 a 和 b 的類型沒有限制。但當深度學習框架捕獲程序時一般會對這兩個變數進行特化，以便它們只對特定類型或者張量有效。在深度學習框架中處理的大多數程序都是特化類型的程序，特化程度越高，能夠處理的輸入就越少。例如 torch.jit.trace 在執行trace的時候只能處理某些擁有合法輸入shape的輸入。接下來還討論了LazyTensor和Jax的 jit 來說明為了更好的處理特化程序中捕獲的失敗，它們做了哪些努力。

深度學習框架都有自己的IR設計，Caffe和TensorFlow使用Protocol Buffers格式。而PyTorch和MxNet使用C++數據結構來表示IR並額外綁定到Python。這些IR設計在runtime階段表現都會比較好並且可以統一被序列化。但從另外一個角度來說，這些IR表示相比於純Python語言的表示都需要更高的學習成本。接下來，這一節討論了控制流和狀態的問題，用來表明要處理這些問題需要設計較為復雜的IR以及要基於這個IR做較為復雜的分析才行。

基於上面幾點，論文提出了 torch.fx 的基本設計原則：

這一節主要對一些相關工作進行了展開，以此來突出 torch.fx 的核心賣點，就是說我雖然不能像TorchScript這樣的IR處理一些比較難的Case（比如動態控制流），但是我在神經網路這個領域里做得夠用就可以了。最關鍵的是我的實現很簡單，是純Python的庫，這樣用戶寫變換就會很簡單，學習成本會很小並且易用。（簡單不代表不強大！

以簡單為基本原則， torch.fx 通過符號跟蹤來捕獲程序，並通過一個簡單的6個指令的IR來表示它們，並基於這個IR重新生成Python代碼來運行它。為了避免JIT特化中的重捕獲的復雜性， torch.fx 沒有對程序本身進行特化，而是依靠變換來決定在捕獲期間需要實現哪些特化。用戶也可以配置符號跟蹤的過程來實現自定義捕獲需求。

Figure1給我們展示了使用 torch.fx.symbolic_trace 捕獲程序的例子，輸入可以是一個 torch.nn.Mole 或者函數，並且捕獲之後的結構被存在一個Graph對象裡面。該 Graph 對象和 GraphMole 中的模塊參數相結合， GraphMole 是 torch.nn.Mole 的子類，其 forward 方法運行捕獲的 Graph 。我們可以列印此圖的 Nodes 以查看捕獲的 IR。 placeholder 節點表示輸入，單個 output 節點表示 Graph 的結果。 call_function 節點直接引用了它將調用的 Python 函數。 call_method 節點直接調用其第一個參數的方法。 Graph 被重組為 Python 代碼（ traced.code ）以供調用。

Figure2展示了使用 torch.fx 進行變換的示例。變換是找到一個激活的所有實例並將它們替換為另一個。在這里，我們使用它來將 gelu 替換 relu 。

torch.fx 的符號跟蹤機制使用一個Proxy數據結構來記錄給定一個輸入之後經過了哪些Op。Proxy是一個ck-typed類型的Python類記錄了在它之上的的屬性訪問和調用方法，是程序中真實Op的上層抽象。ck-typed可以看一下這里的介紹： https://zh.wikipedia.org/wiki/%E9%B8%AD%E5%AD%90%E7%B1%BB%E5%9E%8B 。PyTorch的運算元以及Python子集的某些函數都會被這個Proxy包裝一次，然後在符號跟蹤傳入的是一個 nn.Mole 時，會對這個 nn.Mole 中的子 nn.Mole 也進行Proxy包裝，當然還包含輸入數據。這樣程序中的輸入和其它Op都是ck-typed類型的Proxy對象，我們就可以執行這個程序了，也就是符號跟蹤的過程。符號跟蹤的過程通過一個 Tracer 類進行配置，它的方法可以被重寫以控制哪些值被作為Proxy對象保留，哪些值被unpack。（Proxy記錄下來的Op可以進行unpack，unpack之後可以拿到真實的Tensor, Parameter和運算符等等）。通過Proxy和Tracer類的配合， torch.fx 就可以完成PyTorch程序的符號跟蹤，需要注意的是這里的符號跟蹤的意思就是運行一遍這個被代理之後的 nn.Mole 的forward。

torch.fx 的中間表示（IR）由一個Python數據結構 Graph 來做的。這個 Graph 實際上是一個包含一系列 Node 的線性表。節點有一個字元串操作碼 opcode ，描述節點代表什麼類型的操作（操作碼的語義可以在附錄 A.1 中找到）。節點有一個關聯的目標，它是調用節點（ call_mole 、 call_function 和 call_method ）的調用目標。最後，節點有 args 和 kwargs ，在trace期間它們一起表示 Python 調用約定中的目標參數（每個opcode對應的 args 和 kwargs 的語義可以在附錄 A.2 中找到）。節點之間的數據依賴關系表示為 args 和 kwargs 中對其他節點的引用。

torch.fx 將程序的狀態存儲在 GraphMole 類中。 GraphMole 是轉換程序的容器，暴露轉換後生成的代碼，並提供 nn.Mole 類似的參數管理APIs。 GraphMole 可以在任何可以使用普通的 nn.Mole 的地方使用，以提供轉換後的代碼和PyTorch 生態系統的其餘部分之間的互操作性。

torch.fx 變換pipline的最後階段是代碼生成。 torch.fx 並不是退出 Python 生態系統並進入定製的運行時，而是從變換後的 IR 生成有效的 Python 源代碼。然後將此變換後的代碼載入到 Python 中，生成一個可調用的 Python 對象，並作為 forward 方法安裝在 GraphMole 實例上。使用代碼生成允許將 torch.fx 變換的結果安裝在模型中並用於進一步的變換。例如，在圖3中，我們拿到trace原始程序的結果並將其安裝為新模塊中的激活函數。

到這里PyTorch FX特性就精讀完了，但查看FX的論文可以發現還有一節叫作Design Decisions，分別介紹了Symbolic Tracing，Configurable Program Capture，AoT Capture without Specialization，Python-based IR and Transforms等等FX實現中依賴的一些想法和 決策，以及它們的好處等。我理解這一節就是Introction的加強版，所以就不繼續講解這一小節了，如果你擔心會錯過什麼細節知識可以閱讀論文原文。

torch.fx 的一個目標就是簡化深度學習模型產生的IR，下面的Figure5以ResNet50為例展示了TorchScript IR和 torch.fx IR的差別，相比於TorchScript IR， torch.fx IR確實簡單並且可讀性更強。

我們知道後量化以及量化感知訓練可以提示程序推理時的性能，下面的Figure6就展示了基於 torch.fx 實現的後量化（使用FBGEMM量化運算元）應用在DeepRecommender模型之後，在Intel Xeon Gold 6138 CPU @2.00GHz上的性能表現。基於 torch.fx 實現的後量化模型推理速度相比float類型的模型要高3.3倍。並且基於 torch.fx 實現量化操作相比基於TorchScript IR要簡單很多。

torch.fx 還可以做Op融合，Figure7展示了基於 torch.fx 做了Conv+BN融合後應用在ResNet50上，在n NVIDIA Tesla V100-SXM2 16GB with CUDA version 11.0 和 Intel Xeon Gold 6138 CPU @ 2.00GHz的性能表現，可以看到在GPU上減少了約6%的latency，在CPU上減少了約40%的latency（多線程）和約18%的latency（單線程）。

除此之外 torch.fx 還可以應用在FLOPs計算，內存帶寬使用分析，工作負載的數據值大小估計等，用來分析程序運行時的內存和速度。 torch.fx 還可以用在形狀推斷，以及模型對應的DAG可視化作圖等等。

最後， torch.fx 在runtime階段還支持通過ASIC加速（即將 torch.fx 中的運算元lowering到對應的ASIC上），下面的Figure8展示了基於 torch.fx 推理ResNet50和LearningToPaint並將運算元lowering到TensorRT之後的加速情況：

torch.fx 對於PyTorch來說確實是一個比較好的工作，因為它消除了一些動態圖和靜態圖的Gap。比如在圖改寫方面， torch.fx 讓PyTorch想做一些其它靜態圖框架的運算元融合優化非常容易。並且 torch.fx 讓後訓練量化和感知訓練量化以及AMP等的實現難度大大降低，這得益於我們可以直接在Python層操作這個IR，所以我認為這是一個不錯的工作。尤其是對使用PyTorch開發的演算法工程師來說，現在可以基於這個特性大開腦洞了。我之前圍繞FX也做了一個QAT的工作，感興趣可以閱讀：基於OneFlow實現量化感知訓練： https://zhuanlan.hu.com/p/397650514

最後總結一下， torch.fx 的賣點就是，它使用純Python語言實現了一個可以捕獲PyTorch程序的計算圖並轉化為一個IR的庫，並且非常方便的在這個IR上做Pass，同時提供將變換後的IR Codegen合法的Python代碼功能。我覺得算是達到了在Eager下寫Pass就像做鏈表插入刪除題目一樣順滑。

沐神的論文閱讀方法，感覺確實比較科學，文章末尾再贊一次。

⑶ 使用Node.js如何實現K最近鄰分類演算法

源於數據挖掘的一個作業， 這里用Node.js技術來實現一下這個機器學習中最簡單的演算法之一k-nearest-neighbor演算法(k最近鄰分類法)。
k-nearest-neighbor-classifier
還是先嚴謹的介紹下。急切學習法（eager learner）是在接受待分類的新元組之前就構造了分類模型，學習後的模型已經就緒，急著對未知的元組進行分類，所以稱為急切學習法，諸如決策樹歸納，貝葉斯分類等都是急切學習法的例子。惰性學習法（lazy learner）正好與其相反，直到給定一個待接受分類的新元組之後，才開始根據訓練元組構建分類模型，在此之前只是存儲著訓練元組，所以稱為惰性學習法，惰性學習法在分類進行時做更多的工作。
本文的knn演算法就是一種惰性學習法，它被廣泛應用於模式識別。knn基於類比學習，將未知的新元組與訓練元組進行對比，搜索模式空間，找出最接近未知元組的k個訓練元組，這里的k即是knn中的k。這k個訓練元祖就是待預測元組的k個最近鄰。
balabala了這么多，是不是某些同學想大喊一聲..speak Chinese! 還是來通俗的解釋下，然後再來看上面的理論應該會明白很多。小時候媽媽會指著各種各樣的東西教我們，這是小鴨子，這個紅的是蘋果等等，那我們哼哧哼哧的看著應答著，多次被教後再看到的時候我們自己就能認出來這些事物了。主要是因為我們在腦海像給這個蘋果貼了很多標簽一樣，不只是顏色這一個標簽，可能還有蘋果的形狀大小等等。這些標簽讓我們看到蘋果的時候不會誤認為是橘子。其實這些標簽就對應於機器學習中的特徵這一重要概念，而訓練我們識別的過程就對應於泛化這一概念。一台iphone戴了一個殼或者屏幕上有一道劃痕，我們還是能認得出來它，這對於我們人來說非常簡單，但蠢計算機就不知道怎麼做了，需要我們好好調教它，當然也不能過度調教2333，過度調教它要把其他手機也認成iphone那就不好了，其實這就叫過度泛化。
所以特徵就是提取對象的信息，泛化就是學習到隱含在這些特徵背後的規律，並對新的輸入給出合理的判斷。
我們可以看上圖，綠色的圓代表未知樣本，我們選取距離其最近的k個幾何圖形，這k個幾何圖形就是未知類型樣本的鄰居，如果k=3，我們可以看到有兩個紅色的三角形，有一個藍色的三正方形，由於紅色三角形所佔比例高，所以我們可以判斷未知樣本類型為紅色三角形。擴展到一般情況時，這里的距離就是我們根據樣本的特徵所計算出來的數值，再找出距離未知類型樣本最近的K個樣本，即可預測樣本類型。那麼求距離其實不同情況適合不同的方法，我們這里採用歐式距離。
綜上所述knn分類的關鍵點就是k的選取和距離的計算。
2. 實現
我的數據是一個xls文件，那麼我去npm搜了一下選了一個叫node-xlrd的包直接拿來用。
// node.js用來讀取xls文件的包
var xls = require('node-xlrd');
然後直接看文檔實例即可，把數據解析後插入到自己的數據結構里。
var data = [];// 將文件中的數據映射到樣本的屬性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 讀取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件讀取完畢後 執行測試
run();
});
然後定義一個構造函數Sample表示一個樣本，這里是把剛生成的數據結構里的對象傳入，生成一個新的樣本。
// Sample表示一個樣本
var Sample = function (object) {
// 把傳過來的對象上的屬性克隆到新創建的樣本上
for (var key in object)
{
// 檢驗屬性是否屬於對象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定義一個樣本集的構造函數
// SampleSet管理所有樣本 參數k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 將樣本加入樣本數組
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然後我們會在樣本的原型上定義很多方法，這樣每個樣本都可以用這些方法。
// 計算樣本間距離 採用歐式距離
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 計算歐式距離
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 將鄰居樣本根據與預測樣本間距離排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判斷被預測樣本類別
Sample.prototype.guessType = function(k) {
// 有兩種類別 1和-1
var types = { '1': 0, '-1': 0 };
// 根據k值截取鄰居裡面前k個
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判斷鄰居里哪個樣本類型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我這里的數據有a-k共11個屬性，樣本有1和-1兩種類型，使用truetype和type來預測樣本類型和對比判斷是否分類成功。
最後是樣本集的原型上定義一個方法，該方法可以在整個樣本集里尋找未知類型的樣本，並生成他們的鄰居集，調用未知樣本原型上的方法來計算鄰居到它的距離，把所有鄰居按距離排序，最後猜測類型。
// 構建總樣本數組，包含未知類型樣本
SampleSet.prototype.determineUnknown = function() {

for (var i in this.samples)
{
// 如果發現沒有類型的樣本
if ( ! this.samples[i].type)
{
// 初始化未知樣本的鄰居
this.samples[i].neighbors = [];
// 生成鄰居集
for (var j in this.samples)
{
// 如果碰到未知樣本 跳過
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 計算所有鄰居與預測樣本的距離
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有鄰居按距離排序
this.samples[i].sortByDistance();
// 猜測預測樣本類型
this.samples[i].guessType(this.k);
}
}
};
最後分別計算10倍交叉驗證和留一法交叉驗證的精度。
留一法就是每次只留下一個樣本做測試集，其它樣本做訓練集。
K倍交叉驗證將所有樣本分成K份，一般均分。取一份作為測試樣本，剩餘K-1份作為訓練樣本。這個過程重復K次，最後的平均測試結果可以衡量模型的性能。
k倍驗證時定義了個方法先把數組打亂隨機擺放。
// helper函數 將數組里的元素隨機擺放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩餘測試代碼好寫，這里就不貼了。
測試結果為
用餘弦距離等計算方式可能精度會更高。
3. 總結
knn演算法非常簡單，但卻能在很多關鍵的地方發揮作用並且效果非常好。缺點就是進行分類時要掃描所有訓練樣本得到距離，訓練集大的話會很慢。
可以用這個最簡單的分類演算法來入高大上的ML的門，會有點小小的成就感。

⑷ KNN演算法常見問題總結

給定測試實例，基於某種距離度量找出訓練集中與其最靠近的k個實例點，然後基於這k個最近鄰的信息來進行預測。

通常，在分類任務中可使用「投票法」，即選擇這k個實例中出現最多的標記類別作為預測結果；在回歸任務中可使用「平均法」，即將這k個實例的實值輸出標記的平均值作為預測結果；還可基於距離遠近進行加權平均或加權投票，距離越近的實例權重越大。

k近鄰法不具有顯式的學習過程，事實上，它是懶惰學習（lazy learning）的著名代表，此類學習技術在訓練階段僅僅是把樣本保存起來，訓練時間開銷為零，待收到測試樣本後再進行處理。

KNN一般採用歐氏距離，也可採用其他距離度量，一般的Lp距離：

KNN中的K值選取對K近鄰演算法的結果會產生重大影響。如果選擇較小的K值，就相當於用較小的領域中的訓練實例進行預測，「學習」近似誤差（近似誤差：可以理解為對現有訓練集的訓練誤差）會減小，只有與輸入實例較近或相似的訓練實例才會對預測結果起作用，與此同時帶來的問題是「學習」的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果選擇較大的K值，就相當於用較大領域中的訓練實例進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入實例較遠（不相似的）訓練實例也會對預測器作用，使預測發生錯誤，且K值的增大就意味著整體的模型變得簡單。

在實際應用中，K值一般取一個比較小的數值，例如採用交叉驗證法來選擇最優的K值。經驗規則：k一般低於訓練樣本數的平方根

1、計算測試對象到訓練集中每個對象的距離

2、按照距離的遠近排序

3、選取與當前測試對象最近的k的訓練對象，作為該測試對象的鄰居

4、統計這k個鄰居的類別頻率

5、k個鄰居里頻率最高的類別，即為測試對象的類別

輸入X可以採用BallTree或KDTree兩種數據結構，優化計算效率，可以在實例化KNeighborsClassifier的時候指定。

KDTree

基本思想是，若A點距離B點非常遠，B點距離C點非常近， 可知A點與C點很遙遠，不需要明確計算它們的距離。 通過這樣的方式，近鄰搜索的計算成本可以降低為O[DNlog(N)]或更低。 這是對於暴力搜索在大樣本數N中表現的顯著改善。KD 樹的構造非常快，對於低維度 (D<20) 近鄰搜索也非常快, 當D增長到很大時，效率變低： 這就是所謂的 「維度災難」 的一種體現。

KD 樹是一個二叉樹結構，它沿著數據軸遞歸地劃分參數空間，將其劃分為嵌入數據點的嵌套的各向異性區域。 KD 樹的構造非常快：因為只需沿數據軸執行分區, 無需計算D-dimensional 距離。 一旦構建完成, 查詢點的最近鄰距離計算復雜度僅為O[log(N)]。 雖然 KD 樹的方法對於低維度 (D<20) 近鄰搜索非常快, 當D增長到很大時, 效率變低。

KD樹的特性適合使用歐氏距離。

BallTree

BallTree解決了KDTree在高維上效率低下的問題，這種方法構建的樹要比 KD 樹消耗更多的時間，但是這種數據結構對於高結構化的數據是非常有效的， 即使在高維度上也是一樣。

KD樹是依次對K維坐標軸，以中值切分構造的樹；ball tree 是以質心C和半徑r分割樣本空間，每一個節點是一個超球體。換句簡單的話來說，對於目標空間(q, r)，所有被該超球體截斷的子超球體內的所有子空間都將被遍歷搜索。

BallTree通過使用三角不等式減少近鄰搜索的候選點數:|x+y|<=|x|+|y|通過這種設置, 測試點和質心之間的單一距離計算足以確定距節點內所有點的距離的下限和上限. 由於 ball 樹節點的球形幾何, 它在高維度上的性能超出 KD-tree, 盡管實際的性能高度依賴於訓練數據的結構。

BallTree適用於更一般的距離。

1、優點

非常簡單的分類演算法沒有之一，人性化，易於理解，易於實現

適合處理多分類問題，比如推薦用戶

可用於數值型數據和離散型數據，既可以用來做分類也可以用來做回歸

對異常值不敏感

2、缺點

屬於懶惰演算法，時間復雜度較高，因為需要計算未知樣本到所有已知樣本的距離

樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差，可以調整樣本權值改善

可解釋性差，無法給出類似決策樹那樣的規則

向量的維度越高，歐式距離的區分能力就越弱

樣本空間太大不適合，因為計算量太大，預測緩慢

文本分類

用戶推薦

回歸問題

1）所有的觀測實例中隨機抽取出k個觀測點，作為聚類中心點，然後遍歷其餘的觀測點找到距離各自最近的聚類中心點，將其加入到該聚類中。這樣，我們就有了一個初始的聚類結果，這是一次迭代的過程。

2）我們每個聚類中心都至少有一個觀測實例，這樣，我們可以求出每個聚類的中心點（means），作為新的聚類中心，然後再遍歷所有的觀測點，找到距離其最近的中心點，加入到該聚類中。然後繼續運行2）。

3）如此往復2），直到前後兩次迭代得到的聚類中心點一模一樣。

本演算法的時間復雜度：O(tkmn)，其中，t為迭代次數，k為簇的數目，m為記錄數，n為維數；

空間復雜度：O((m+k)n)，其中，k為簇的數目，m為記錄數，n為維數。

適用范圍：

K-menas演算法試圖找到使平凡誤差准則函數最小的簇。當潛在的簇形狀是凸面的，簇與簇之間區別較明顯，且簇大小相近時，其聚類結果較理想。前面提到，該演算法時間復雜度為O(tkmn)，與樣本數量線性相關，所以，對於處理大數據集合，該演算法非常高效，且伸縮性較好。但該演算法除了要事先確定簇數K和對初始聚類中心敏感外，經常以局部最優結束，同時對「雜訊」和孤立點敏感，並且該方法不適於發現非凸面形狀的簇或大小差別很大的簇。

1）首先，演算法只能找到局部最優的聚類，而不是全局最優的聚類。而且演算法的結果非常依賴於初始隨機選擇的聚類中心的位置。我們通過多次運行演算法，使用不同的隨機生成的聚類中心點運行演算法，然後對各自結果C通過evaluate(C)函數進行評估，選擇多次結果中evaluate(C)值最小的那一個。k-means++演算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠

2）關於初始k值選擇的問題。首先的想法是，從一個起始值開始，到一個最大值，每一個值運行k-means演算法聚類，通過一個評價函數計算出最好的一次聚類結果，這個k就是最優的k。我們首先想到了上面用到的evaluate(C)。然而，k越大，聚類中心越多，顯然每個觀測點距離其中心的距離的平方和會越小，這在實踐中也得到了驗證。第四節中的實驗結果分析中將詳細討論這個問題。

3）關於性能問題。原始的演算法，每一次迭代都要計算每一個觀測點與所有聚類中心的距離。有沒有方法能夠提高效率呢？是有的，可以使用k-d tree或者ball tree這種數據結構來提高演算法的效率。特定條件下，對於一定區域內的觀測點，無需遍歷每一個觀測點，就可以把這個區域內所有的點放到距離最近的一個聚類中去。這將在第三節中詳細地介紹。

相似點：都包含這樣的過程，給定一個點，在數據集中找離它最近的點。即二者都用到了NN(Nears Neighbor)演算法，一般用KD樹來實現NN。

k-d tree 與 ball tree

1）k-d tree[5]

把n維特徵的觀測實例放到n維空間中，k-d tree每次通過某種演算法選擇一個特徵(坐標軸)，以它的某一個值作為分界做超平面，把當前所有觀測點分為兩部分，然後對每一個部分使用同樣的方法，直到達到某個條件為止。

上面的表述中，有幾個地方下面將會詳細說明：（1）選擇特徵（坐標軸）的方法 （2）以該特徵的哪一個為界 （3）達到什麼條件演算法結束。

(1)選擇特徵的方法

計算當前觀測點集合中每個特徵的方差，選擇方差最大的一個特徵，然後畫一個垂直於這個特徵的超平面將所有觀測點分為兩個集合。

（2)以該特徵的哪一個值為界 即垂直選擇坐標軸的超平面的具體位置。

第一種是以各個點的方差的中值（median）為界。這樣會使建好的樹非常地平衡，會均勻地分開一個集合。這樣做的問題是，如果點的分布非常不好地偏斜的，選擇中值會造成連續相同方向的分割，形成細長的超矩形(hyperrectangles)。

替代的方法是計算這些點該坐標軸的平均值，選擇距離這個平均值最近的點作為超平面與這個坐標軸的交點。這樣這個樹不會完美地平衡，但區域會傾向於正方地被劃分，連續的分割更有可能在不同方向上發生。

（3）達到什麼條件演算法結束

實際中，不用指導葉子結點只包含兩個點時才結束演算法。你可以設定一個預先設定的最小值，當這個最小值達到時結束演算法。

圖6中，星號標注的是目標點，我們在k-d tree中找到這個點所處的區域後，依次計算此區域包含的點的距離，找出最近的一個點（黑色點），如果在其他region中還包含更近的點則一定在以這兩個點為半徑的圓中。假設這個圓如圖中所示包含其他區域。先看這個區域兄弟結點對應區域，與圓不重疊；再看其雙親結點的兄弟結點對應區域。從它的子結點對應區域中尋找（圖中確實與這個雙親結點的兄弟結點的子結點對應區域重疊了）。在其中找是否有更近的結點。

k-d tree的優勢是可以遞增更新。新的觀測點可以不斷地加入進來。找到新觀測點應該在的區域，如果它是空的，就把它添加進去，否則，沿著最長的邊分割這個區域來保持接近正方形的性質。這樣會破壞樹的平衡性，同時讓區域不利於找最近鄰。我們可以當樹的深度到達一定值時重建這棵樹。

然而，k-d tree也有問題。矩形並不是用到這里最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外，矩形甚至是正方形並不是用在這里最完美的形狀，由於它的角。如果圖6中的圓再大一些，即黑點距離目標點點再遠一些，圓就會與左上角的矩形相交，需要多檢查一個區域的點，而且那個區域是當前區域雙親結點的兄弟結點的子結點。

為了解決上面的問題，我們引入了ball tree。

2）ball tree[4]

解決上面問題的方案就是使用超球面而不是超矩形劃分區域。使用球面可能會造成球面間的重疊，但卻沒有關系。ball tree就是一個k維超球面來覆蓋這些觀測點，把它們放到樹裡面。圖7（a)顯示了一個2維平麵包含16個觀測實例的圖,圖7（b）是其對應的ball tree，其中結點中的數字表示包含的觀測點數。

不同層次的圓被用不同的風格畫出。樹中的每個結點對應一個圓，結點的數字表示該區域保含的觀測點數，但不一定就是圖中該區域囊括的點數，因為有重疊的情況，並且一個觀測點只能屬於一個區域。實際的ball tree的結點保存圓心和半徑。葉子結點保存它包含的觀測點。

使用ball tree時，先自上而下找到包含target的葉子結點，從此結點中找到離它最近的觀測點。這個距離就是最近鄰的距離的上界。檢查它的兄弟結點中是否包含比這個上界更小的觀測點。方法是：如果目標點距離兄弟結點的圓心的距離大於這個圓的圓心加上前面的上界的值，則這個兄弟結點不可能包含所要的觀測點。（如圖8）否則，檢查這個兄弟結點是否包含符合條件的觀測點。

那麼，ball tree的分割演算法是什麼呢？

選擇一個距離當前圓心最遠的觀測點i1，和距離i1最遠的觀測點 i2，將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心，然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑。對包含n個觀測點的超圓進行分割，只需要線性的時間。

與k-d tree一樣，如果結點包含的觀測點到達了預先設定的最小值，這個頂點就可以不再分割了。

⑸ knn演算法是什麼

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

介紹

KNN演算法本身簡單有效，它是一種lazy-learning演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為n，那麼KNN的分類時間復雜度為O(n)。

KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。