色AV久天,色潮不卡亚洲无码,美国91久久

1?k 近鄰算法

?? $k$ 近鄰算法的思想是：給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的 $k$ 個(gè)實(shí)例，這 $k$ 個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分為這個(gè)類。
??算法 3.1 ( $k$ 近鄰算法)
??輸入：訓(xùn)練數(shù)據(jù)集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ 其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\mathcal{Y}=\{c_1,c_2,\dots,c_K\}$ ， $i=1,2,\dots,N$ ；實(shí)例向量 $x$ ；
??輸出：實(shí)例 $x$ 所屬的類 $y$ ；
??(1) 根據(jù)給定的度量距離，在訓(xùn)練集 $T$ 中找出與 $x$ 最鄰近的 $k$ 個(gè)點(diǎn)，涵蓋這 $k$ 個(gè)點(diǎn)的 $x$ 的鄰域作 $N_k(x)$ ；
??(2) 在 $N_k(x)$ 中根據(jù)分類決策規(guī)則決定 $x$ 的類別 $y$ ： $y=\text{arg}\max\limits_{c_j}\sum\limits_{x_i\in N_k(x)} I(y_i=c_j),\quad i=1,2,\dots,N;\ j=1,2,\dots,K$ ??式中， $I$ 為指示函數(shù)，即當(dāng) $y_i=c_i$ 時(shí) $I$ 為 1，否則 $I$ 為 0。

$k$ 近鄰法的特殊情況是 $k=1$ 的情形，稱為最近鄰算法；

$k$ 近鄰法沒有顯式的學(xué)習(xí)過程；

$k$ 值、度量距離以及分類決策規(guī)則是 $k$ 近鄰法的三個(gè)基本要素。當(dāng)訓(xùn)練集以及三個(gè)基本要素確定后，對(duì)于任何一個(gè)新的輸入實(shí)例，它所屬的類唯一地確定。

??從算法的步驟不難發(fā)現(xiàn)，KNN 是一種 lazy-learning 算法，分類器不需要進(jìn)行訓(xùn)練，即訓(xùn)練過程的時(shí)間復(fù)雜度為 0。KNN 分類的計(jì)算復(fù)雜度和訓(xùn)練集中的實(shí)例數(shù)目成正比，也就是說，如果訓(xùn)練集中實(shí)例總數(shù)為 $n$ ，那么 KNN 的分類時(shí)間復(fù)雜度為 $O(n)$ 。

2?k 近鄰模型

2.1?度量距離

??設(shè)特征空間 $\mathcal{X}=\mathbb{R}^n$ ， $x_i,x_j\in\mathcal{X}$ ， $x_i=(x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)})^T$ ， $x_i,x_j$ 的 $L_p$ 距離定義為 $L_p(x_i,x_j)= \left(\sum\limits_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\right)^{\frac{1}{p}}$ 其中 $p\geqslant 1$ 。

當(dāng) $p=2$ 時(shí)，稱為歐式距離： $L_2(x_i,y_j) = \left(\sum\limits_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|^2\right)^{\frac{1}{2}}$

當(dāng) $p=1$ 時(shí)，稱為曼哈頓距離： $L_1(x_i,y_j) = \sum\limits_{l=1}^{n} |x_i^{(l)}-x_j^{(l)}|$

當(dāng) $p=\infty$ 時(shí)，稱為切比雪夫距離： $L_\infty(x_i,y_j) = \max\limits_{l} |x_i^{(l)}-x_j^{(l)}|$

2.2?k 值的選擇

?? $k$ 值的選則會(huì)對(duì) $k$ 近鄰法的結(jié)果產(chǎn)生重大影響。
??若選則的 $k$ 值較小，學(xué)習(xí)的近似誤差會(huì)減小，只有與輸入實(shí)例較近的點(diǎn)會(huì)對(duì)預(yù)測結(jié)果起作用；但學(xué)習(xí)的估計(jì)誤差會(huì)增大，預(yù)測結(jié)果會(huì)對(duì)近鄰的點(diǎn)的實(shí)例點(diǎn)十分敏感，容易發(fā)生過擬合。反之，若選則的 $k$ 值較大，可以減少學(xué)習(xí)的估計(jì)誤差，但是學(xué)習(xí)的近似誤差會(huì)增大。

2.3?分類決策規(guī)則

?? $k$ 近鄰法中的決策規(guī)則往往采用多數(shù)表決規(guī)則。多數(shù)表決規(guī)則 (majority voting rule) 有如下解釋：若分類的損失函數(shù)為 0-1 損失函數(shù)，分類函數(shù)為 $f:\mathbb{R}^n\rightarrow \{c_1,c_2,\dots,c_K\}$ 那么誤分類的概率是 $P(Y\neq f(X))=1-P(Y=f(X))$ 對(duì)給定的實(shí)例 $x\in\mathcal{X}$ ，其最近鄰的 $k$ 個(gè)訓(xùn)練實(shí)例點(diǎn)構(gòu)成集合 $N_k(x)$ 。若涵蓋 $N_k(x)$ 的區(qū)域類別是 $c_j$ ，那么誤分類是 $\frac{1}{k}\sum\limits_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum\limits_{x_i\in N_k(x)}I(y_i=c_j)$ 要使誤分類率最小即經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，就要使 $\sum\limits_{x_i\in N_k(x)}I(y_i=c_j)^{}$ 最大，所以多數(shù)表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。

3?k 近鄰法的實(shí)現(xiàn)：kd 樹

1. 背景 ^[1]
??一般說來，索引結(jié)構(gòu)中相似性查詢有兩種基本的方式：
??(1) 范圍查詢：范圍查詢時(shí)給定查詢點(diǎn)和查詢距離閾值，從數(shù)據(jù)集中查找所有與查詢點(diǎn)距離小于閾值的數(shù)據(jù)。
??(2) k 近鄰查詢：就是給定查詢點(diǎn)及正整數(shù) k，從數(shù)據(jù)集中找到距離查詢點(diǎn)最近的K個(gè)數(shù)據(jù)；當(dāng) k=1 時(shí)，它就是最近鄰查詢。
??同樣，針對(duì)特征點(diǎn)匹配也有兩種方法：
??(1) 線性掃描，也就是我們常說的窮舉搜索，依次計(jì)算樣本集中每個(gè)樣本到輸入實(shí)例點(diǎn)的距離，然后抽取出計(jì)算出來的最小距離的點(diǎn)即為最近鄰點(diǎn)。此種辦法簡單直白，但當(dāng)樣本集或訓(xùn)練集很大時(shí)，計(jì)算將會(huì)非常耗時(shí)，明顯是不足取的。
??(2) 構(gòu)建數(shù)據(jù)索引，因?yàn)閷?shí)際數(shù)據(jù)一般都會(huì)呈現(xiàn)簇狀的聚類形態(tài)，因此我們想到建立數(shù)據(jù)索引，然后再進(jìn)行快速匹配。索引樹是一種樹結(jié)構(gòu)索引方法，其基本思想是對(duì)搜索空間進(jìn)行層次劃分。根據(jù)劃分的空間是否有混疊可以分為 Clipping 和 Overlapping 兩種。前者劃分空間沒有重疊，其代表就是 k-d 樹；后者劃分空間相互有交疊，其代表為 R 樹。

2. 構(gòu)造 kd 樹
??kd 樹中，kd 代表 k-dimension，每個(gè)節(jié)點(diǎn)即為一個(gè)k維的點(diǎn)。構(gòu)造 kd 樹的思想就是將每個(gè)非葉節(jié)點(diǎn)想象為一個(gè)分割超平面，用垂直于坐標(biāo)軸的超平面將空間分為兩個(gè)部分，這樣遞歸的從根節(jié)點(diǎn)不停的劃分，直到?jīng)]有實(shí)例為止。具體算法如下：
??算法 3.2 (構(gòu)造平衡 kd 樹)
??輸入： $k$ 維空間數(shù)據(jù)集 $T=\{ x_1,x_2,\dots, x_N\}$ ，其中 $x_i = ( x_i^{( 1 )} , x_i^{(2)} , ? ? , x_i^{(k)})^T$ ， $i=1,2,\dots,N$ ；
??輸出：kd 樹；
??(1) 開始：構(gòu)造根結(jié)點(diǎn)，根結(jié)點(diǎn)對(duì)應(yīng)于包含 $T$ 的 $k$ 維空間的超矩形區(qū)域。
??選擇 $^{(1)}$ 為坐標(biāo)軸，以 $T$ 中所有實(shí)例的 $x^{(1)}$ 坐標(biāo)的中位數(shù)為切分點(diǎn)，將根結(jié)點(diǎn)對(duì)應(yīng)的超矩形區(qū)域切分為兩個(gè)子區(qū)域。切分由通過切分點(diǎn)并與坐標(biāo)軸 $x^{(1)}$ 垂直的超平面實(shí)現(xiàn)。
??由根結(jié)點(diǎn)生成深度為1的左、右子結(jié)點(diǎn)：左子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo) $x^{(1)}$ 小于切分點(diǎn)的子區(qū)域，右子結(jié)點(diǎn)對(duì)應(yīng)于坐標(biāo) $x^{(1)}$ 大于切分點(diǎn)的子區(qū)域。
??將落在切分超平面上的實(shí)例點(diǎn)保存在根結(jié)點(diǎn)。
??(2) 重復(fù)：對(duì)深度為 $j$ 的結(jié)點(diǎn)，選擇 $x^{(l)}$ 為切分的坐標(biāo)軸， $l＝j(luò)(\text{mod} \ k)+1$ ，以該結(jié)點(diǎn)的區(qū)域中所有實(shí)例的 $x^{(l)}$ 坐標(biāo)的中位數(shù)為切分點(diǎn)，將該結(jié)點(diǎn)對(duì)應(yīng)的超矩形區(qū)域切分為兩個(gè)子區(qū)域。切分由通過切分點(diǎn)并與坐標(biāo)軸 $x^{(l)}$ 垂直的超平面實(shí)現(xiàn)。
??由該結(jié)點(diǎn)生成深度為 $j+1$ 的左、右子結(jié)點(diǎn)：左子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo) $x^{(l)}$ 小于切分點(diǎn)的子區(qū)域，右子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo) $x^{(l)}$ 大于切分點(diǎn)的子區(qū)域。
??將落在切分超平面上的實(shí)例點(diǎn)保存在該結(jié)點(diǎn)。
??(3) 直到兩個(gè)子區(qū)域沒有實(shí)例存在時(shí)停止。從而形成 kd 樹的區(qū)域劃分。

??構(gòu)造 kd 樹的規(guī)則有三種：隨機(jī)劃分（玄學(xué)）、輪換劃分（每個(gè)維度輪著劃分）與方差劃分（優(yōu)先劃分方差較大的維度）。

書中介紹的是輪換劃分：

隨著樹的深度增加，循環(huán)的選取坐標(biāo)軸，作為分割超平面的法向量。例如 3-d tree，根節(jié)點(diǎn)選取 x 軸，根節(jié)點(diǎn)的孩子選取 y 軸，根節(jié)點(diǎn)的孫子選取 z 軸，根節(jié)點(diǎn)的曾孫子選取 x 軸，這樣循環(huán)下去。

每次均為所有對(duì)應(yīng)實(shí)例的中位數(shù)的實(shí)例作為切分點(diǎn)，切分點(diǎn)作為父節(jié)點(diǎn)，左右兩側(cè)為劃分的作為左右兩子樹。

對(duì)于輪換劃分以中位數(shù) (期望時(shí)間復(fù)雜度 $\Theta(n)$ ) 的實(shí)例點(diǎn)作為切分點(diǎn)故有遞推式： $T(n)=2T(n/2)+\Theta(n)$ 根據(jù) 主定理有 $a=2$ ， $b=2$ ， $\log_b a=1$ ， $f(n)=\Theta(n)$ ；
基準(zhǔn)函數(shù)為 $\Theta(n^{\log_b a})=\Theta(n)$ ；
故有期望時(shí)間復(fù)雜度為 $T(n) = \Theta(n\log n)$

3. 搜索 kd 樹
??搜索 kd 樹的思想就是根據(jù)所給定的目標(biāo)點(diǎn)，搜索其最近鄰。首先找到包含目標(biāo)點(diǎn)的葉節(jié)點(diǎn)；然后從該葉節(jié)點(diǎn)出發(fā)，一次回退到父節(jié)點(diǎn)；不斷查抄與目標(biāo)點(diǎn)最鄰近的節(jié)點(diǎn)，當(dāng)確定不可能存在更近的節(jié)點(diǎn)是終止。這樣搜索就被限制在空間的局部區(qū)域上。具體算法如下：
??算法 3.3 (用 kd 樹的最近鄰搜索)
??輸入：已構(gòu)造的 kd 樹，目標(biāo)點(diǎn) x；
??輸出：x 的最近鄰
??(1) 在 kd 樹種找出包含目標(biāo)點(diǎn)x的葉結(jié)點(diǎn)：從根結(jié)點(diǎn)出發(fā)，遞歸地向下搜索 kd 樹。若目標(biāo)點(diǎn) x 當(dāng)前維的坐標(biāo)小于切分點(diǎn)的坐標(biāo)，則移動(dòng)到左子結(jié)點(diǎn)，否則移動(dòng)到右子結(jié)點(diǎn)，直到子結(jié)點(diǎn)為葉結(jié)點(diǎn)為止。
??(2) 以此葉結(jié)點(diǎn)為“當(dāng)前最近點(diǎn)”。
??(3) 遞歸的向上回溯，在每個(gè)結(jié)點(diǎn)進(jìn)行以下操作：
????(a) 如果該結(jié)點(diǎn)保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)距離目標(biāo)點(diǎn)更近，則更新 “當(dāng)前最近點(diǎn)”，也就是說以該實(shí)例點(diǎn)為 “當(dāng)前最近點(diǎn)”。
????(b) 當(dāng)前最近點(diǎn)一定存在于該結(jié)點(diǎn)一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域，檢查子結(jié)點(diǎn)的父結(jié)點(diǎn)的另一子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否有更近的點(diǎn)。具體做法是，檢查另一子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否以目標(biāo)點(diǎn)位球心，以目標(biāo)點(diǎn)與 “當(dāng)前最近點(diǎn)” 間的距離為半徑的圓或超球體相交：
??如果相交，可能在另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點(diǎn)更近的點(diǎn)，移動(dòng)到另一個(gè)子結(jié)點(diǎn)，接著，繼續(xù)遞歸地進(jìn)行最近鄰搜索；如果不相交，則向上回溯。
??(4) 當(dāng)回退到根結(jié)點(diǎn)時(shí)，搜索結(jié)束，最后的 “當(dāng)前最近點(diǎn)” 即為 x 的最近鄰點(diǎn)。

??如果實(shí)例點(diǎn)是隨機(jī)分布的，那么kd樹搜索的期望計(jì)算復(fù)雜度是 $\Theta(\log N)$ ，這里的 $N$ 是訓(xùn)練實(shí)例樹。所以說，kd 樹更適用于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時(shí)的 k 近鄰搜索，當(dāng)空間維數(shù)接近訓(xùn)練實(shí)例數(shù)時(shí)，它的效率將會(huì)退化至線性掃描的速度。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Day7~8 第三章 k 近鄰

Day7~8 第三章 k 近鄰

1?k 近鄰算法

2?k 近鄰模型

2.1?度量距離

2.2?k 值的選擇

2.3?分類決策規(guī)則

3?k 近鄰法的實(shí)現(xiàn)：kd 樹

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Day7~8 第三章 k 近鄰

1?k 近鄰算法

2?k 近鄰模型

2.1?度量距離

2.2?k 值的選擇

2.3?分類決策規(guī)則

3?k 近鄰法的實(shí)現(xiàn)：kd 樹

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av