和平精英kd怎么算出來(lái)的-和平精英kd是怎么算的算法分享

和平精英手游中，玩家的KD值是衡量玩家游戲水平的重要指標(biāo)，通過(guò)淘汰數(shù)與被淘汰數(shù)的比值來(lái)計(jì)算。

具體而言，KD=淘汰數(shù)/被淘汰數(shù)。簡(jiǎn)單來(lái)說(shuō)，KD就是你殺死對(duì)手的次數(shù)除以你被對(duì)手殺死的次數(shù)。

一般而言，普通玩家的KD值在2-3左右，這是大多數(shù)玩家能達(dá)到的水平。如果一個(gè)玩家的KD值達(dá)到了5-7，那就可以被認(rèn)為是高端玩家了。

而當(dāng)KD數(shù)值達(dá)到8以上時(shí)，這已經(jīng)是頂級(jí)玩家的表現(xiàn)了。如果能夠?qū)D值保持在10以上，那么有很大可能是職業(yè)選手。

作為游戲中的關(guān)鍵性指標(biāo)，KD值可以幫助玩家了解自己的游戲水平，明確提升方向。

和平精英手游中，KD值的高低直接反映了玩家的游戲?qū)嵙Γ婕铱梢酝ㄟ^(guò)提升自己的KD值來(lái)提高游戲體驗(yàn)。

KD值是玩家在游戲中表現(xiàn)的重要反映，玩家可以通過(guò)提高KD值來(lái)提升自己的游戲水平。

02 KNN算法 - KD Tree

KD Tree是KNN算法中用于計(jì)算最近鄰的快速簡(jiǎn)便的構(gòu)建方式。

當(dāng)樣本量少的時(shí)候，用 brute直接搜索最近鄰的方式是可行的。即計(jì)算到所有樣本的距離。但當(dāng)樣本量龐大時(shí)，直接計(jì)算所有樣本距離的工作量很大，這種情況使用 KD Tree可以節(jié)約大量時(shí)間成本。

KD樹(shù)采用從m個(gè)樣本的n維特征中，分別計(jì)算n個(gè)特征取值的方差，用方差最大的第k維特征n k作為根節(jié)點(diǎn)。對(duì)于這個(gè)特征，選擇取值中的中位數(shù) n kv作為樣本的劃分點(diǎn)，對(duì)于小于該值的樣本劃分到左子樹(shù)，對(duì)于大于等于該值的樣本劃分到右子樹(shù)，對(duì)左右子樹(shù)采用同樣的方式找方差最大的特征作為根節(jié)點(diǎn)，遞歸產(chǎn)生KD Tree。

為什么要選擇方差最大的進(jìn)行劃分？

構(gòu)建樹(shù)的目的是加快我的搜索過(guò)程。

既然我想加快我的搜索過(guò)程，要就意味著我最終的數(shù)據(jù)落在某個(gè)葉子節(jié)點(diǎn)上。我希望只需搜索整個(gè)二叉樹(shù)的某一些列即可，那么最好的劃分方式，就是讓我的每個(gè)分支上數(shù)據(jù)的差異性最大化。

那么衡量數(shù)據(jù)差異性的最基礎(chǔ)的數(shù)學(xué)指標(biāo)是什么？

是方差。方差越大，意味著數(shù)據(jù)的離散程度就越大，我將離散程度由大到小的數(shù)據(jù)一分為二，方差小意味著數(shù)據(jù)更集中到了一起。

現(xiàn)在有一個(gè)二維樣本:{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}

1、計(jì)算x1和x2每一列對(duì)應(yīng)的方差

a、通過(guò)pandas計(jì)算出的是樣本方差:

/(n-1)

0| 6.966667

1| 5.366667

dtype: float64

b、通過(guò)numpy計(jì)算出的是總體方差:

/ n

[[2 3]

[5 4]

[9 6]

[4 7]

[8 1]

[7 2]]

[ 5.80555556 4.47222222]

[ 5.80555556 4.47222222]

第一個(gè)樹(shù)的劃分：基于x 1進(jìn)行劃分

[2,4,5,7,8,9]的中位數(shù)是5和7的平均值6。

雖然嚴(yán)格意義上說(shuō)中位數(shù)是6，但是在計(jì)算機(jī)中我們?nèi)藶榈枚xx 1的中位數(shù)是7。

左側(cè)：（2,3）（5,4）（4,7）（7,2）

右側(cè):（9,6）（8,1）

第二個(gè)樹(shù)的劃分：根據(jù)右側(cè)（9,6）（8,1）的x 2進(jìn)行劃分

下側(cè)：x 2≤ 6；上側(cè)x 2＞6

第二個(gè)樹(shù)的劃分：根據(jù)左側(cè)（2,3）（5,4）（4,7）（7,2）的x 2進(jìn)行劃分

尋找2、3、4、7的中位數(shù) 4進(jìn)行劃分

....

注意：每次生成的劃分都是一個(gè)矩形。當(dāng)葉子節(jié)點(diǎn)無(wú)法被繼續(xù)劃分的時(shí)候，KD樹(shù)的構(gòu)建完成，遞歸結(jié)束。

我們生成了KD Tree后，現(xiàn)在就可以去預(yù)測(cè)測(cè)試集里面的樣本目標(biāo)點(diǎn)了。

1、對(duì)于一個(gè)目標(biāo)點(diǎn)，先在KD樹(shù)里找到包含目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)。

2、以目標(biāo)點(diǎn)為圓心，以目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)樣本實(shí)例的距離為半徑，得到一個(gè)超球體，最近鄰的點(diǎn)一定在這個(gè)超球體內(nèi)部。

3、然后返回葉子節(jié)點(diǎn)的父節(jié)點(diǎn)，檢查另一個(gè)子節(jié)點(diǎn)包含的超矩形體是否和超球體相交。

4、如果相交就倒這個(gè)子節(jié)點(diǎn)尋找著是否有更加近的近鄰，有的話就更新最近鄰。

5、如果不相交，直接返回父節(jié)點(diǎn)中的父節(jié)點(diǎn)，在另一個(gè)子樹(shù)繼續(xù)搜索最近鄰。當(dāng)回溯到根節(jié)點(diǎn)時(shí)，算法結(jié)束。

6、此時(shí)保存的最近鄰節(jié)點(diǎn)就是最終的最近鄰。

如果現(xiàn)在想找(2,4.5)這點(diǎn)的最近鄰，該如何操作？

1、畫(huà)出二叉樹(shù)：

2、尋找(2,4.5)這點(diǎn)：

一個(gè)比較好的理解方式：首先找到第一個(gè)最近鄰，然后畫(huà)出一個(gè)圓。然后逐漸收縮圓的半徑，查看每次縮小后的圓是否能夠和矩形相交于一個(gè)更小的最近鄰點(diǎn)，如果有則更新。直到回到根節(jié)點(diǎn)。

kd-treek-d樹(shù)最鄰近查找算法

在k-d樹(shù)中進(jìn)行數(shù)據(jù)查找是關(guān)鍵步驟，主要用于定位與查詢點(diǎn)距離最近的數(shù)據(jù)點(diǎn)。以查詢點(diǎn)（2.1,3.1）為例，首先通過(guò)二叉搜索，快速找到近似點(diǎn)即葉子節(jié)點(diǎn)（2,3）。盡管該點(diǎn)是近似最近鄰，但并非最終答案，因?yàn)榭赡苡懈咏狞c(diǎn)位于以查詢點(diǎn)為圓心、通過(guò)葉子節(jié)點(diǎn)的圓域內(nèi)。為了找到真實(shí)最近鄰，需要執(zhí)行回溯操作：從搜索路徑中的節(jié)點(diǎn)反向查找，看是否有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)。

從（7,2）開(kāi)始二叉查找，最終到達(dá)（2,3）。搜索路徑為。首先將（2,3）視為當(dāng)前最近鄰，計(jì)算其與查詢點(diǎn)的距離為0.1414。然后回溯至其父節(jié)點(diǎn)（5,4），并判斷在該節(jié)點(diǎn)的其他子節(jié)點(diǎn)空間內(nèi)是否有更近的數(shù)據(jù)點(diǎn)。以（2.1,3.1）為圓心，以0.1414為半徑繪制圓。圓未與超平面y=4相交，因此無(wú)需探索（5,4）的右子空間。同樣地，回溯至（7,2），以0.1414為半徑的圓未與x=7相交，無(wú)需探索（7,2）的右子空間。至此，搜索路徑中所有節(jié)點(diǎn)被回溯完畢，最終返回最近鄰點(diǎn)（2,3）和最近距離0.1414。

考慮復(fù)雜一點(diǎn)的例子，如查詢點(diǎn)（2,4.5）。同樣地，從（7,2）開(kāi)始二叉查找，到達(dá)（5,4）節(jié)點(diǎn)時(shí)，由于查詢點(diǎn)的y值為4.5，進(jìn)入右子空間查找到（4,7），形成搜索路徑。將（4,7）視為當(dāng)前最近鄰，計(jì)算其與目標(biāo)距離為3.202。然后回溯至（5,4），計(jì)算距離為3.041。以（2,4.5）為圓心，以3.041為半徑作圓，發(fā)現(xiàn)圓與y=4超平面相交，因此需要探索（5,4）的左子空間。將（2,3）加入搜索路徑中，回溯至（2,3）葉子節(jié)點(diǎn)，（2,3）與（2,4.5）的距離更近，因此更新最近鄰點(diǎn)為（2,3），最近距離為1.5。回溯至（7,2），以1.5為半徑作圓，與x=7分割超平面不相交，至此搜索路徑回溯完畢，返回最近鄰點(diǎn)（2,3）和最近距離1.5。

k-d樹(shù)查詢算法的偽代碼如下。從root節(jié)點(diǎn)開(kāi)始深度優(yōu)先搜索直到葉子節(jié)點(diǎn)，并在stack中存儲(chǔ)已訪問(wèn)節(jié)點(diǎn)。當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時(shí)，設(shè)該節(jié)點(diǎn)為最近鄰節(jié)點(diǎn)。通過(guò)stack執(zhí)行回溯操作：如果當(dāng)前點(diǎn)的距離更近，則更新最近鄰節(jié)點(diǎn)。檢查以最近距離為半徑的圓是否與父節(jié)點(diǎn)的超平面相交。若相交，則必須探索父節(jié)點(diǎn)的另一側(cè)，使用相同的深度優(yōu)先搜索法繼續(xù)查找最近鄰節(jié)點(diǎn)。若不相交，則向上回溯，排除父節(jié)點(diǎn)另一側(cè)的子節(jié)點(diǎn)，不再考慮其范圍。當(dāng)回溯到root節(jié)點(diǎn)時(shí)，搜索完成，得到最近鄰節(jié)點(diǎn)。

kd-tree的構(gòu)建算法

k-d樹(shù)是一個(gè)二叉樹(shù)，每個(gè)節(jié)點(diǎn)表示一個(gè)空間范圍。表1給出的是k-d樹(shù)每個(gè)節(jié)點(diǎn)中主要包含的數(shù)據(jù)結(jié)構(gòu)。

表1 k-d樹(shù)中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型域名數(shù)據(jù)類(lèi)型描述 Node-data數(shù)據(jù)矢量數(shù)據(jù)集中某個(gè)數(shù)據(jù)點(diǎn)，是n維矢量（這里也就是k維） Range空間矢量該節(jié)點(diǎn)所代表的空間范圍 split整數(shù)垂直于分割超平面的方向軸序號(hào) Left k-d樹(shù)由位于該節(jié)點(diǎn)分割超平面左子空間內(nèi)所有數(shù)據(jù)點(diǎn)所構(gòu)成的k-d樹(shù) Right k-d樹(shù)由位于該節(jié)點(diǎn)分割超平面右子空間內(nèi)所有數(shù)據(jù)點(diǎn)所構(gòu)成的k-d樹(shù) parent k-d樹(shù)父節(jié)點(diǎn)從上面對(duì)k-d樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型的描述可以看出構(gòu)建k-d樹(shù)是一個(gè)逐級(jí)展開(kāi)的遞歸過(guò)程。表2給出的是構(gòu)建k-d樹(shù)的偽碼。

表2構(gòu)建k-d樹(shù)的偽碼算法：構(gòu)建k-d樹(shù)（createKDTree）輸入：數(shù)據(jù)點(diǎn)集Data-set和其所在的空間Range輸出：Kd，類(lèi)型為k-d tree 1.If Data-set為空，則返回空的k-d tree 2.調(diào)用節(jié)點(diǎn)生成程序：

（1）確定split域：對(duì)于所有描述子數(shù)據(jù)（特征矢量），統(tǒng)計(jì)它們?cè)诿總€(gè)維上的數(shù)據(jù)方差。以SURF特征為例，描述子為64維，可計(jì)算64個(gè)方差。挑選出最大值，對(duì)應(yīng)的維就是split域的值。數(shù)據(jù)方差大表明沿該坐標(biāo)軸方向上的數(shù)據(jù)分散得比較開(kāi)，在這個(gè)方向上進(jìn)行數(shù)據(jù)分割有較好的分辨率；

（2）確定Node-data域：數(shù)據(jù)點(diǎn)集Data-set按其第split域的值排序。位于正中間的那個(gè)數(shù)據(jù)點(diǎn)被選為Node-data。此時(shí)新的Data-set'= Data-set\Node-data（除去其中Node-data這一點(diǎn)）。 3.dataleft={d屬于Data-set'&& d[split]≤ Node-data[split]}

Left_Range={Range&& dataleft} dataright={d屬于Data-set'&& d[split]> Node-data[split]}

Right_Range={Range&& dataright} 4.left=由（dataleft，Left_Range）建立的k-d tree，即遞歸調(diào)用createKDTree（dataleft，Left_

Range）。并設(shè)置left的parent域?yàn)镵d；

right=由（dataright，Right_Range）建立的k-d tree，即調(diào)用createKDTree（dataright，Right_

Range）。并設(shè)置right的parent域?yàn)镵d。以上述舉的實(shí)例來(lái)看，過(guò)程如下：

由于此例簡(jiǎn)單，數(shù)據(jù)維度只有2維，所以可以簡(jiǎn)單地給x，y兩個(gè)方向軸編號(hào)為0,1，也即split={0,1}。

（1）確定split域的首先該取的值。分別計(jì)算x，y方向上數(shù)據(jù)的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向；

（2）確定Node-data的域值。根據(jù)x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data=（7,2）。該節(jié)點(diǎn)的分割超平面就是通過(guò)（7,2）并垂直于split= 0（x軸）的直線x= 7；

（3）確定左子空間和右子空間。分割超平面x= 7將整個(gè)空間分為兩部分，如圖2所示。x<= 7的部分為左子空間，包含3個(gè)節(jié)點(diǎn){（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個(gè)節(jié)點(diǎn){（9,6），（8,1）}。

如算法所述，k-d樹(shù)的構(gòu)建是一個(gè)遞歸的過(guò)程。然后對(duì)左子空間和右子空間內(nèi)的數(shù)據(jù)重復(fù)根節(jié)點(diǎn)的過(guò)程就可以得到下一級(jí)子節(jié)點(diǎn)（5,4）和（9,6）（也就是左右子空間的'根'節(jié)點(diǎn)），同時(shí)將空間和數(shù)據(jù)集進(jìn)一步細(xì)分。如此反復(fù)直到空間中只包含一個(gè)數(shù)據(jù)點(diǎn)，如圖1所示。最后生成的k-d樹(shù)如圖3所示。