㈠ OPTICS聚類演算法的matlab實現
OPTICS聚類演算法代碼，從http://www.pudn.com/downloads238/sourcecode/math/detail1113278.html
該處下載。
% -------------------------------------------------------------------------
% Function:
% [RD,CD,order]=optics(x,k)
% -------------------------------------------------------------------------
% Aim:
% Ordering objects of a data set to obtain the clustering structure
% -------------------------------------------------------------------------
% Input:
% x - data set (m,n); m-objects, n-variables
% k - number of objects in a neighborhood of the selected object
% (minimal number of objects considered as a cluster)
% -------------------------------------------------------------------------
% Output:
% RD - vector with reachability distances (m,1)
% CD - vector with core distances (m,1)
% order - vector specifying the order of objects (1,m)
% -------------------------------------------------------------------------
% Example of use:
% x=[randn(30,2)*.4;randn(40,2)*.5+ones(40,1)*[4 4]];
% [RD,CD,order]=optics(x,4)
% -------------------------------------------------------------------------
%
function [RD,CD,order]=optics(x,k)
[m,n]=size(x);
CD=zeros(1,m);
RD=ones(1,m)*10^10;
% Calculate Core Distances
for i=1:m
D=sort(dist(x(i,:),x));
CD(i)=D(k+1);
end
order=[];
seeds=[1:m];
ind=1;
while ~isempty(seeds)
ob=seeds(ind);
seeds(ind)=[];
order=[order ob];
mm=max([ones(1,length(seeds))*CD(ob);dist(x(ob,:),x(seeds,:))]);
ii=(RD(seeds))>mm;
RD(seeds(ii))=mm(ii);
[i1 ind]=min(RD(seeds));
end
RD(1)=max(RD(2:m))+.1*max(RD(2:m));
function [D]=dist(i,x)
% function: [D]=dist(i,x)
%
% Aim:
% Calculates the Euclidean distances between the i-th object and all objects in x
% Input:
% i - an object (1,n)
% x - data matrix (m,n); m-objects, n-variables
%
% Output:
% D - Euclidean distance (m,1)
[m,n]=size(x);
D=(sum((((ones(m,1)*i)-x).^2)'));
if n==1
D=abs((ones(m,1)*i-x))';
end
㈡ 加密解密字元串的演算法原理
我們經常需要一種措施來保護我們的數據，防止被一些懷有不良用心的人所看到或者破壞。在信息時代，信息可以幫助團體或個人，使他們受益，同樣，信息也可以用來對他們構成威脅，造成破壞。在競爭激烈的大公司中，工業間諜經常會獲取對方的情報。因此，在客觀上就需要一種強有力的安全措施來保護機密數據不被竊取或篡改。數據加密與解密從宏觀上講是非常簡單的，很容易理解。加密與解密的一些方法是非常直接的，很容易掌握，可以很方便的對機密數據進行加密和解密。
一：數據加密方法
在傳統上，我們有幾種方法來加密數據流。所有這些方法都可以用軟體很容易的實現，但是當我們只知道密文的時候，是不容易破譯這些加密演算法的（當同時有原文和密文時，破譯加密演算法雖然也不是很容易，但已經是可能的了）。最好的加密演算法對系統性能幾乎沒有影響，並且還可以帶來其他內在的優點。例如，大家都知道的pkzip，它既壓縮數據又加密數據。又如，dbms的一些軟體包總是包含一些加密方法以使復制文件這一功能對一些敏感數據是無效的，或者需要用戶的密碼。所有這些加密演算法都要有高效的加密和解密能力。
幸運的是，在所有的加密演算法中最簡單的一種就是「置換表」演算法，這種演算法也能很好達到加密的需要。每一個數據段（總是一個位元組）對應著「置換表」中的一個偏移量，偏移量所對應的值就輸出成為加密後的文件。加密程序和解密程序都需要一個這樣的「置換表」。事實上，80x86 cpu系列就有一個指令『xlat』在硬體級來完成這樣的工作。這種加密演算法比較簡單，加密解密速度都很快，但是一旦這個「置換表」被對方獲得，那這個加密方案就完全被識破了。更進一步講，這種加密演算法對於黑客破譯來講是相當直接的，只要找到一個「置換表」就可以了。這種方法在計算機出現之前就已經被廣泛的使用。
對這種「置換表」方式的一個改進就是使用2個或者更多的「置換表」，這些表都是基於數據流中位元組的位置的，或者基於數據流本身。這時，破譯變的更加困難，因為黑客必須正確的做幾次變換。通過使用更多的「置換表」，並且按偽隨機的方式使用每個表，這種改進的加密方法已經變的很難破譯。比如，我們可以對所有的偶數位置的數據使用a表，對所有的奇數位置使用b表，即使黑客獲得了明文和密文，他想破譯這個加密方案也是非常困難的，除非黑客確切的知道用了兩張表。
與使用「置換表」相類似，「變換數據位置」也在計算機加密中使用。但是，這需要更多的執行時間。從輸入中讀入明文放到一個buffer中，再在buffer中對他們重排序，然後按這個順序再輸出。解密程序按相反的順序還原數據。這種方法總是和一些別的加密演算法混合使用，這就使得破譯變的特別的困難，幾乎有些不可能了。例如，有這樣一個詞，變換起字母的順序，slient 可以變為listen，但所有的字母都沒有變化，沒有增加也沒有減少，但是字母之間的順序已經變化了。
但是，還有一種更好的加密演算法，只有計算機可以做，就是字/位元組循環移位和xor操作。如果我們把一個字或位元組在一個數據流內做循環移位，使用多個或變化的方向（左移或右移），就可以迅速的產生一個加密的數據流。這種方法是很好的，破譯它就更加困難！而且，更進一步的是，如果再使用xor操作，按位做異或操作，就就使破譯密碼更加困難了。如果再使用偽隨機的方法，這涉及到要產生一系列的數字，我們可以使用fibbonaci數列。對數列所產生的數做模運算（例如模3），得到一個結果，然後循環移位這個結果的次數，將使破譯次密碼變的幾乎不可能！但是，使用fibbonaci數列這種偽隨機的方式所產生的密碼對我們的解密程序來講是非常容易的。
在一些情況下，我們想能夠知道數據是否已經被篡改了或被破壞了，這時就需要產生一些校驗碼，並且把這些校驗碼插入到數據流中。這樣做對數據的防偽與程序本身都是有好處的。但是感染計算機程序的病毒才不會在意這些數據或程序是否加過密，是否有數字簽名。所以，加密程序在每次load到內存要開始執行時，都要檢查一下本身是否被病毒感染，對與需要加、解密的文件都要做這種檢查！很自然，這樣一種方法體制應該保密的，因為病毒程序的編寫者將會利用這些來破壞別人的程序或數據。因此，在一些反病毒或殺病毒軟體中一定要使用加密技術。
循環冗餘校驗是一種典型的校驗數據的方法。對於每一個數據塊，它使用位循環移位和xor操作來產生一個16位或32位的校驗和 ，這使得丟失一位或兩個位的錯誤一定會導致校驗和出錯。這種方式很久以來就應用於文件的傳輸，例如 xmodem-crc。 這是方法已經成為標准，而且有詳細的文檔。但是，基於標准crc演算法的一種修改演算法對於發現加密數據塊中的錯誤和文件是否被病毒感染是很有效的。
二．基於公鑰的加密演算法
一個好的加密演算法的重要特點之一是具有這種能力：可以指定一個密碼或密鑰，並用它來加密明文，不同的密碼或密鑰產生不同的密文。這又分為兩種方式：對稱密鑰演算法和非對稱密鑰演算法。所謂對稱密鑰演算法就是加密解密都使用相同的密鑰，非對稱密鑰演算法就是加密解密使用不同的密鑰。非常著名的pgp公鑰加密以及rsa加密方法都是非對稱加密演算法。加密密鑰，即公鑰，與解密密鑰，即私鑰，是非常的不同的。從數學理論上講，幾乎沒有真正不可逆的演算法存在。例如，對於一個輸入『a』執行一個操作得到結果『b』,那麼我們可以基於『b』，做一個相對應的操作，導出輸入『a』。在一些情況下，對於每一種操作，我們可以得到一個確定的值，或者該操作沒有定義（比如，除數為0）。對於一個沒有定義的操作來講，基於加密演算法，可以成功地防止把一個公鑰變換成為私鑰。因此，要想破譯非對稱加密演算法，找到那個唯一的密鑰，唯一的方法只能是反復的試驗，而這需要大量的處理時間。
rsa加密演算法使用了兩個非常大的素數來產生公鑰和私鑰。即使從一個公鑰中通過因數分解可以得到私鑰，但這個運算所包含的計算量是非常巨大的，以至於在現實上是不可行的。加密演算法本身也是很慢的，這使得使用rsa演算法加密大量的數據變的有些不可行。這就使得一些現實中加密演算法都基於rsa加密演算法。pgp演算法(以及大多數基於rsa演算法的加密方法)使用公鑰來加密一個對稱加密演算法的密鑰，然後再利用一個快速的對稱加密演算法來加密數據。這個對稱演算法的密鑰是隨機產生的，是保密的，因此，得到這個密鑰的唯一方法就是使用私鑰來解密。
我們舉一個例子：假定現在要加密一些數據使用密鑰『12345』。利用rsa公鑰，使用rsa演算法加密這個密鑰『12345』，並把它放在要加密的數據的前面（可能後面跟著一個分割符或文件長度，以區分數據和密鑰），然後，使用對稱加密演算法加密正文，使用的密鑰就是『12345』。當對方收到時，解密程序找到加密過的密鑰，並利用rsa私鑰解密出來，然後再確定出數據的開始位置，利用密鑰『12345』來解密數據。這樣就使得一個可靠的經過高效加密的數據安全地傳輸和解密。
一些簡單的基於rsa演算法的加密演算法可在下面的站點找到：
ftp://ftp.funet.fi/pub/crypt/cryptography/asymmetric/rsa
三．一個嶄新的多步加密演算法
現在又出現了一種新的加密演算法，據說是幾乎不可能被破譯的。這個演算法在1998年6月1日才正式公布的。下面詳細的介紹這個演算法:
使用一系列的數字（比如說128位密鑰），來產生一個可重復的但高度隨機化的偽隨機的數字的序列。一次使用256個表項，使用隨機數序列來產生密碼轉表，如下所示：
把256個隨機數放在一個距陣中，然後對他們進行排序，使用這樣一種方式（我們要記住最初的位置）使用最初的位置來產生一個表，隨意排序的表，表中的數字在0到255之間。如果不是很明白如何來做，就可以不管它。但是，下面也提供了一些原碼（在下面）是我們明白是如何來做的。現在，產生了一個具體的256位元組的表。讓這個隨機數產生器接著來產生這個表中的其餘的數，以至於每個表是不同的。下一步，使用"shotgun technique"技術來產生解碼表。基本上說，如果 a映射到b，那麼b一定可以映射到a，所以b[a[n]] = n.（n是一個在0到255之間的數）。在一個循環中賦值，使用一個256位元組的解碼表它對應於我們剛才在上一步產生的256位元組的加密表。
使用這個方法，已經可以產生這樣的一個表，表的順序是隨機，所以產生這256個位元組的隨機數使用的是二次偽隨機,使用了兩個額外的16位的密碼.現在，已經有了兩張轉換表，基本的加密解密是如下這樣工作的。前一個位元組密文是這個256位元組的表的索引。或者，為了提高加密效果，可以使用多餘8位的值，甚至使用校驗和或者crc演算法來產生索引位元組。假定這個表是256*256的數組,將會是下面的樣子:
crypto1 = a[crypto0][value]
變數'crypto1'是加密後的數據，'crypto0'是前一個加密數據（或著是前面幾個加密數據的一個函數值）。很自然的，第一個數據需要一個「種子」，這個「種子」 是我們必須記住的。如果使用256*256的表，這樣做將會增加密文的長度。或者，可以使用你產生出隨機數序列所用的密碼，也可能是它的crc校驗和。順便提及的是曾作過這樣一個測試: 使用16個位元組來產生表的索引,以128位的密鑰作為這16個位元組的初始的"種子"。然後，在產生出這些隨機數的表之後，就可以用來加密數據，速度達到每秒鍾100k個位元組。一定要保證在加密與解密時都使用加密的值作為表的索引，而且這兩次一定要匹配。
加密時所產生的偽隨機序列是很隨意的，可以設計成想要的任何序列。沒有關於這個隨機序列的詳細的信息，解密密文是不現實的。例如：一些ascii碼的序列，如「eeeeeeee"可能被轉化成一些隨機的沒有任何意義的亂碼，每一個位元組都依賴於其前一個位元組的密文，而不是實際的值。對於任一個單個的字元的這種變換來說，隱藏了加密數據的有效的真正的長度。
如果確實不理解如何來產生一個隨機數序列，就考慮fibbonacci數列，使用2個雙字（64位）的數作為產生隨機數的種子，再加上第三個雙字來做xor操作。 這個演算法產生了一系列的隨機數。演算法如下：
unsigned long dw1, dw2, dw3, dwmask;
int i1;
unsigned long arandom[256];
dw1 = {seed #1};
dw2 = {seed #2};
dwmask = {seed #3};
// this gives you 3 32-bit "seeds", or 96 bits total
for(i1=0; i1 < 256; i1++)
{
dw3 = (dw1 + dw2) ^ dwmask;
arandom[i1] = dw3;
dw1 = dw2;
dw2 = dw3;
}
如果想產生一系列的隨機數字，比如說，在0和列表中所有的隨機數之間的一些數，就可以使用下面的方法：
int __cdecl mysortproc(void *p1, void *p2)
{
unsigned long **pp1 = (unsigned long **)p1;
unsigned long **pp2 = (unsigned long **)p2;
if(**pp1 < **pp2)
return(-1);
else if(**pp1 > *pp2)
return(1);
return(0);
}
...
int i1;
unsigned long *aprandom[256];
unsigned long arandom[256]; // same array as before, in this case
int aresult[256]; // results go here
for(i1=0; i1 < 256; i1++)
{
aprandom[i1] = arandom + i1;
}
// now sort it
qsort(aprandom, 256, sizeof(*aprandom), mysortproc);
// final step - offsets for pointers are placed into output array
for(i1=0; i1 < 256; i1++)
{
aresult[i1] = (int)(aprandom[i1] - arandom);
}
...
變數'aresult'中的值應該是一個排過序的唯一的一系列的整數的數組，整數的值的范圍均在0到255之間。這樣一個數組是非常有用的，例如：對一個位元組對位元組的轉換表，就可以很容易並且非常可靠的來產生一個短的密鑰（經常作為一些隨機數的種子）。這樣一個表還有其他的用處，比如說：來產生一個隨機的字元，計算機游戲中一個物體的隨機的位置等等。上面的例子就其本身而言並沒有構成一個加密演算法，只是加密演算法一個組成部分。
作為一個測試，開發了一個應用程序來測試上面所描述的加密演算法。程序本身都經過了幾次的優化和修改，來提高隨機數的真正的隨機性和防止會產生一些短的可重復的用於加密的隨機數。用這個程序來加密一個文件，破解這個文件可能會需要非常巨大的時間以至於在現實上是不可能的。
四．結論：
由於在現實生活中，我們要確保一些敏感的數據只能被有相應許可權的人看到，要確保信息在傳輸的過程中不會被篡改，截取，這就需要很多的安全系統大量的應用於政府、大公司以及個人系統。數據加密是肯定可以被破解的，但我們所想要的是一個特定時期的安全，也就是說，密文的破解應該是足夠的困難，在現實上是不可能的，尤其是短時間內。
㈢ 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一樣，如果結點包含的觀測點到達了預先設定的最小值，這個頂點就可以不再分割了。
㈣ Matlab超像素圖像分割【源碼 詳細解析】
超像素圖像分割是一種將像素級圖像抽象為區域級圖像的技術。它通過將位置相鄰且具有相似顏色、亮度、紋理等特徵的像素點組成的小區域進行聚合，形成更具有代表性的大元素。這種新元素將作為圖像處理演算法的基本單位，有助於降低圖像處理的復雜度並剔除異常像素點。理論上，任何過度分割演算法都能生成超像素。在圖像分割中，超像素是指具有相似紋理、顏色、亮度特徵的相鄰相似構成的不規則像素塊。它通過利用像素之間的特徵相似性將像素分組，用較少的超像素代替大量像素，有效地表達圖像特徵。
超像素的判別條件包括Undersegmentation Error、Boundary Recall和Compactness score。Undersegmentation Error評估超像素區域的覆蓋程度，Boundary Recall衡量超像素邊界對圖像物體邊界的覆蓋能力，而Compactness score則衡量超像素是否緊密。
超像素的初始化方法主要有種子像素初始化和矩形區域初始化。SLIC演算法是簡單線性迭代聚類演算法，採用CIELAB顏色空間和XY坐標下的5維特徵向量，通過局部聚類過程生成緊湊且均勻的超像素。SEEDS演算法則將圖像平均分割為矩形區域作為初始超像素。
SLIC演算法具有生成緊湊、整齊的超像素、適用於彩色和灰度圖像、參數設置少等優點。演算法步驟包括初始化種子點、重新選擇種子點、為每個像素點分配類別標簽以及計算距離度量。其中，距離度量包括顏色距離和空間距離。
超像素圖像分割技術在圖像處理中扮演著重要角色，通過降低維度並保持物體邊界信息，提高了圖像處理的效率和准確性。SLIC演算法因其在運行速度、生成超像素的緊湊度、輪廓保持方面的優秀表現而廣受認可。通過合理設置參數，SLIC演算法能夠生成滿足人們期望的分割效果，成為圖像分割領域的有力工具。