李曉明

現(xiàn)在，人工智能很熱。人工智能應(yīng)用中有些很基本的需求，分類(lèi)即為其中最常見(jiàn)的一種。分類(lèi)關(guān)心的是如何將一個(gè)對(duì)象歸到已知類(lèi)別中。例如，人可以分為少年、青年、中年、老年四個(gè)類(lèi)別，商品可以分為廉價(jià)和高檔兩個(gè)類(lèi)別，學(xué)生在課堂上的表現(xiàn)可分為積極踴躍、沉穩(wěn)細(xì)致、不以為然三個(gè)類(lèi)別，網(wǎng)購(gòu)者可分為隨性和理性?xún)煞N類(lèi)別，等等。在日常生活中，這種分類(lèi)主要憑感覺(jué)。而如果用計(jì)算機(jī)來(lái)做，則每一種類(lèi)別都需要通過(guò)一些數(shù)據(jù)特征予以刻畫(huà)，每一個(gè)對(duì)象或者說(shuō)個(gè)體都是通過(guò)一個(gè)“數(shù)據(jù)點(diǎn)”來(lái)表示，如后面要講的一個(gè)網(wǎng)購(gòu)的例子，其數(shù)據(jù)特征就用了“每月網(wǎng)購(gòu)次數(shù)”和“每次平均花費(fèi)”。一個(gè)每月網(wǎng)購(gòu)10次、每次平均花費(fèi)120元的人則用數(shù)據(jù)點(diǎn)（10，120）來(lái)表示。

不難體會(huì)到，把一個(gè)個(gè)體歸到預(yù)設(shè)的類(lèi)別中，有些比較容易，有些則很不容易。鑒于分類(lèi)在現(xiàn)實(shí)中有廣泛的應(yīng)用，人們發(fā)明了多種算法，應(yīng)對(duì)各種不同的情形。本文介紹兩個(gè)最基本的算法——K近鄰（KNN）算法和支持向量機(jī)（SVM）算法。

這兩個(gè)算法的基本思路都很簡(jiǎn)單直觀。KNN的實(shí)現(xiàn)容易理解，因而人工智能的教材里一般都會(huì)有它。SVM的常規(guī)實(shí)現(xiàn)需要較深的數(shù)學(xué)基礎(chǔ)，因而一般初等人工智能教材都沒(méi)有它。不過(guò)，由于SVM實(shí)在很重要，最近也看到有嘗試在中學(xué)人工智能教材中介紹它[1]，只是在介紹了算法基本思想后用了一句“這個(gè)問(wèn)題可以用優(yōu)化方法求解，但具體過(guò)程已經(jīng)超出了同學(xué)們現(xiàn)階段的知識(shí)儲(chǔ)備，等到同學(xué)們以后學(xué)習(xí)了相關(guān)的數(shù)學(xué)工具后，就可以求解了”就結(jié)束了。本文將從一個(gè)不同的視角描述一個(gè)實(shí)現(xiàn)SVM的算法，該算法從效率上講沒(méi)有常規(guī)的SVM算法高，但用到的數(shù)學(xué)知識(shí)在中學(xué)生可理解的范疇內(nèi)，他們應(yīng)該能夠編程實(shí)現(xiàn)，因而適合中學(xué)的教學(xué)。

一般而言，設(shè)計(jì)分類(lèi)算法的目的是實(shí)現(xiàn)一個(gè)所謂“分類(lèi)器”（程序）。分類(lèi)器的實(shí)現(xiàn)通常都是基于一批已知類(lèi)別的數(shù)據(jù)，形成某些規(guī)則，來(lái)做未知類(lèi)別對(duì)象的類(lèi)別判斷，圖1是一個(gè)概念圖。

實(shí)現(xiàn)一個(gè)分類(lèi)器的基礎(chǔ)是一個(gè)預(yù)先給定的類(lèi)別集合C={C1，C2，...，Cm}和一批已知類(lèi)別的樣本數(shù)據(jù)集D={d1，d2，...，dn}。不同分類(lèi)算法的區(qū)別一般體現(xiàn)在所形成的分類(lèi)規(guī)則上。

類(lèi)別集合C通常是人們根據(jù)需要或經(jīng)驗(yàn)事先確定的，有一定現(xiàn)實(shí)含義，如本文開(kāi)始時(shí)提到的那些。樣本數(shù)據(jù)集D怎么做到類(lèi)別已知的呢？通常是采用人工標(biāo)注給定，也就是事先找來(lái)一批有代表性的數(shù)據(jù)，請(qǐng)有背景知識(shí)的人一一給打上類(lèi)別標(biāo)簽。這項(xiàng)工作一方面很重要，對(duì)后續(xù)自動(dòng)分類(lèi)的質(zhì)量有基礎(chǔ)性影響，另一方面在互聯(lián)網(wǎng)經(jīng)濟(jì)中的需求越來(lái)越普遍，因而形成了一種新職業(yè)——數(shù)據(jù)標(biāo)注員。

在分類(lèi)問(wèn)題中，一個(gè)核心的概念是兩個(gè)數(shù)據(jù)點(diǎn)之間的距離。所謂判斷一個(gè)數(shù)據(jù)點(diǎn)該屬于哪個(gè)類(lèi)，本質(zhì)上就是看它離哪個(gè)類(lèi)的已知數(shù)據(jù)點(diǎn)更近。而“距離”在不同的應(yīng)用背景下可能有不同的定義。我們以二維數(shù)據(jù)空間為例，給出三種常見(jiàn)的距離定義，如圖2所示。

設(shè)（x1，y1）和（x2，y2）為兩個(gè)數(shù)據(jù)點(diǎn)p1和p2的坐標(biāo)，歐式距離、曼哈頓距離和余弦相似度①分別為：

其中，前面兩個(gè)都有“數(shù)值越小越接近（相似）”的含義，而余弦相似度定義在區(qū)間[0，1]，越大越相似。若余弦相似度為1，意味著兩個(gè)數(shù)據(jù)點(diǎn)同在一條通過(guò)原點(diǎn)的直線上。體會(huì)這幾個(gè)定義的含義，讀者對(duì)它們適用的不同場(chǎng)合能有些直覺(jué)認(rèn)識(shí)。

一般而言，KNN和SVM處理的數(shù)據(jù)點(diǎn)都可以是高維的，用多于三個(gè)特征分量來(lái)表示一個(gè)對(duì)象的特征。本文為突出要點(diǎn)，只考慮二維的情形，于是有如圖3所示的視覺(jué)形象，便于解釋有關(guān)細(xì)節(jié)。

圖3（a）示意在二維數(shù)據(jù)空間中有兩種已經(jīng)標(biāo)注（分別用圓和三角表示）類(lèi)型的樣本數(shù)據(jù)。它們大致分布在空間中兩個(gè)不同的區(qū)域，任何兩個(gè)數(shù)據(jù)點(diǎn)之間都可以談?wù)撃撤N距離。我們特別注意到，同類(lèi)數(shù)據(jù)之間的距離不一定就比異類(lèi)之間的小。圖3（b）示意出現(xiàn)了一個(gè)未知類(lèi)別的數(shù)據(jù)（x），它應(yīng)該屬于哪一類(lèi)呢？

● KNN算法基本思路

針對(duì)樣本數(shù)據(jù)D，KNN算法采用了一種可以說(shuō)是體現(xiàn)“近朱者赤，近墨者黑”和“少數(shù)服從多數(shù)”原則的直截了當(dāng)?shù)乃悸?。它一一?jì)算待分類(lèi)數(shù)據(jù)x與樣本數(shù)據(jù)集D中所有數(shù)據(jù)的距離，然后取其中最小的K個(gè)（也就是“KNN”中的K，而NN表示“最近的鄰點(diǎn)”），看它們分別屬于哪一個(gè)類(lèi)，判定x應(yīng)該屬于K中出現(xiàn)較多的那個(gè)類(lèi)。

采用什么距離定義和具體應(yīng)用有關(guān)，為和后面的例子對(duì)應(yīng)，下面的算法描述采用了余弦相似度作為距離。

● KNN分類(lèi)算法（如表1）

● 算法運(yùn)行例

假設(shè)我們考慮對(duì)網(wǎng)購(gòu)者的分類(lèi)，用“每月網(wǎng)購(gòu)次數(shù)”和“每次平均花費(fèi)”兩個(gè)量來(lái)刻畫(huà)每一個(gè)用戶(hù)，要看一個(gè)人是“隨性”（S）還是“理性”（R）②。有一個(gè)已經(jīng)人工標(biāo)好類(lèi)型的樣本數(shù)據(jù)如圖4（a）所示，現(xiàn)在有一個(gè)用戶(hù)每月網(wǎng)購(gòu)5次，平均花費(fèi)40元，即她的數(shù)據(jù)是x=（5，40）。問(wèn)她是屬于隨性網(wǎng)購(gòu)者還是理性網(wǎng)購(gòu)者？

采用KNN算法對(duì)這個(gè)用戶(hù)分類(lèi)，采用余弦相似度作為距離度量，首先算得x=（4，50）與16個(gè)已知數(shù)據(jù)的距離，如圖4（b）第1列所示。為方便查看，我們把那些距離按照與1接近的程度的排序放在表中最右邊一列。（注意，對(duì)余弦距離而言，越接近1表示越“近”）

現(xiàn)在，如果取K=1，看到離x最近的（6，45）是“S”，于是x應(yīng)該被分類(lèi)為“S”。如果取K=3，離x最近的3個(gè)都是“S”，如果取K=5，離x最近的5個(gè)里有4個(gè)“S”1個(gè)“R”，等等。你覺(jué)得應(yīng)該認(rèn)為x是隨性網(wǎng)購(gòu)者還是理性網(wǎng)購(gòu)者呢？顯然，認(rèn)為這個(gè)x是一個(gè)隨性網(wǎng)購(gòu)者比較合理。

● 算法性質(zhì)的分析

這是一個(gè)正確的算法嗎？如果考慮的是2-分類(lèi)，即類(lèi)別數(shù)為2，且K為奇數(shù)，KNN算法總會(huì)有一個(gè)輸出，建議x應(yīng)該屬于哪一類(lèi)。因此不存在停機(jī)或收斂之類(lèi)的問(wèn)題。問(wèn)題可能在于它給出的建議到底有多靠譜。這樣，除了給出x當(dāng)屬于哪個(gè)類(lèi)別外，還可以給出一個(gè)概率，即在TOP-K中，占優(yōu)類(lèi)型的數(shù)據(jù)在整個(gè)K中的占比。例如，在上面的例子中，K=3，這個(gè)占比就是100%，K=5，這個(gè)占比就是80%。如果類(lèi)別數(shù)大于2，則還需要有一個(gè)方法來(lái)做“平手消解”，當(dāng)某兩類(lèi)在TOP-K中有相同出現(xiàn)時(shí)決定取哪一個(gè)。

一個(gè)分類(lèi)器的質(zhì)量常常用“準(zhǔn)確度”（accuracy）指標(biāo)來(lái)評(píng)價(jià)。假設(shè)一共有p個(gè)測(cè)試數(shù)據(jù)x1，x2，…，xp，對(duì)它們分完類(lèi)后人工一一做檢查。用r表示分類(lèi)錯(cuò)誤的個(gè)數(shù)，準(zhǔn)確度就是p/（p+r）。

這個(gè)算法的效率如何呢？

KNN分類(lèi)算法的計(jì)算復(fù)雜度與樣本集大小（n）有關(guān)，與樣本屬性的維數(shù)有關(guān)。在我們討論的二維情況下，從算法描述中可以看到，計(jì)算余弦距離時(shí)間復(fù)雜度是O（n）。算法第3行找出n個(gè)相似度中的TOP-K，一般算法是O（k*n），采用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)可以做到O（k*logn）。

在學(xué)過(guò)了算法園地專(zhuān)欄前面十多個(gè)算法后，現(xiàn)在學(xué)KNN算法，讀者可能會(huì)產(chǎn)生一種十分不一樣的感覺(jué)。首先，這種算法看起來(lái)好簡(jiǎn)單，直截了當(dāng)好理解，其邏輯與前面討論過(guò)的那些相比要淺顯許多。其次，給出的分類(lèi)結(jié)果到底有多靠譜，一般來(lái)說(shuō)是沒(méi)法證明的。事實(shí)上，像分類(lèi)這樣的問(wèn)題，現(xiàn)實(shí)中經(jīng)常就是沒(méi)有客觀標(biāo)準(zhǔn)。但為了能推進(jìn)研究，人們通常會(huì)準(zhǔn)備一些有代表性的測(cè)試數(shù)據(jù)集（benchmark）用于比較不同方法的效果。當(dāng)然，最終效果如何，只能通過(guò)實(shí)際應(yīng)用檢驗(yàn)了。

● SVM概念與算法目標(biāo)

下面討論SVM，它有一個(gè)聽(tīng)起來(lái)很高深的名字“支持向量機(jī)”。我們不被它困擾，來(lái)看具體是什么意思。還是用圖3的數(shù)據(jù)，畫(huà)出SVM分類(lèi)概念的示意圖，如圖5（a）所示。

可以看到，圖中除了數(shù)據(jù)點(diǎn)，還有將兩類(lèi)數(shù)據(jù)點(diǎn)分開(kāi)的直線。SVM就是要基于樣本數(shù)據(jù)點(diǎn)，算出一條那樣的直線（y=ax+b），從而可對(duì)擬分類(lèi)數(shù)據(jù)依照它是在直線的左右來(lái)賦予類(lèi)別，這個(gè)示例就是左邊為“圓”，右邊為“三角”。不過(guò)，讀者可能馬上注意到圖5（a）中有兩條直線，它們對(duì)于待分類(lèi)數(shù)據(jù)點(diǎn)（x）分類(lèi)的結(jié)論是不同的，于是就有了哪個(gè)更好的問(wèn)題。SVM怎么考慮呢？SVM要求一條“最優(yōu)的”直線。

什么叫“最優(yōu)的”直線？SVM采用的觀點(diǎn)是離它最近的數(shù)據(jù)點(diǎn)盡量遠(yuǎn)。形象地看，就是在兩類(lèi)數(shù)據(jù)之間“最窄”處的中線。圖5（b）是一個(gè)示意，根據(jù)兩類(lèi)數(shù)據(jù)點(diǎn)的情況，我們分別畫(huà)了一個(gè)外包凸多邊形（這種多邊形在計(jì)算幾何學(xué)中叫“凸包”），這樣它們之間的“通道”也看得很清楚了③。如果我們能確定兩個(gè)凸包上距離最近的兩個(gè)點(diǎn)（不一定都恰好在頂點(diǎn)上），做連接它們的線段，再做該線段的垂直平分線，就得到了SVM的結(jié)果，如圖5（c）所示。

下面給出的SVM算法就是求這樣一條直線的算法。讀者能感到與前面的KNN很不同，那里是基于樣本數(shù)據(jù)直接對(duì)數(shù)據(jù)點(diǎn)（x）做分類(lèi)。不過(guò)，讀者也能意識(shí)到，一旦有了這樣一條直線，判斷一個(gè)數(shù)據(jù)（x）應(yīng)該屬于哪一類(lèi)就是一件平凡的事情，用不著專(zhuān)門(mén)說(shuō)了。

● 一種SVM分類(lèi)器算法

下面描述的算法相對(duì)比較宏觀（如表2），有利于讀者把握整體概念。其中的細(xì)節(jié)在后面做進(jìn)一步闡述。另外，所提到的距離此時(shí)均為歐幾里德距離。

下面來(lái)討論其中的要點(diǎn)。首先，理解這個(gè)算法的細(xì)節(jié)（包括編程實(shí)現(xiàn)）所需的主要數(shù)學(xué)知識(shí)為平面向量的知識(shí)，這在高中新教材中已有覆蓋，見(jiàn)參考文獻(xiàn)[2]的第6章。具體包括平面上兩個(gè)點(diǎn)的距離公式、一個(gè)點(diǎn)到一條直線的距離公式（由此得到點(diǎn)到線段的距離公式）、根據(jù)一個(gè)點(diǎn)的坐標(biāo)和斜率確定直線y=ax+b的方法等。下面以算法中的最后一步（5）為例，展示處理這類(lèi)問(wèn)題的樣式。已知由（x1，y1）和（x2，y2）確定的線段，要確定垂直平分線y=ax+b中的參數(shù)a和b。

算法的第2、3、4步只涉及距離的計(jì)算和排序，不用贅述。算法的第1步，從一個(gè)平面數(shù)據(jù)點(diǎn)集得到它的凸包。這是計(jì)算幾何學(xué)中的一種基本運(yùn)算，人們研究出了許多簡(jiǎn)單易懂的算法，陳道蓄教授在本專(zhuān)欄上一期，也就是2020年第21期上介紹了其中兩種[3]，在此也不贅述，有興趣的讀者可自行查閱學(xué)習(xí)。

● 算法的性質(zhì)分析

先看計(jì)算復(fù)雜性。若第1步采用[3]中介紹的第二個(gè)算法，復(fù)雜性是O（nlogn）。第2步和第3步計(jì)算距離，若不采用任何優(yōu)化，為O（n2）。第4和第5步是常數(shù)時(shí)間?？偟膩?lái)說(shuō)，復(fù)雜性為O（n2）。

為什么算法得到的直線y=ax+b就是最優(yōu)的一條直線？由于它是在兩個(gè)最短距離的點(diǎn)（x1，y1）和（x2，y2）之間，這意味著兩類(lèi)數(shù)據(jù)之間不可能有更寬的通道。而由于它是“垂直平分線”，這意味著它做到了讓“離它最近的數(shù)據(jù)點(diǎn)盡量遠(yuǎn)”。

不過(guò)，細(xì)心的讀者可能問(wèn)到一個(gè)更加微妙的問(wèn)題。那就是，記即數(shù)據(jù)點(diǎn)（? ? ? ）和（? ? ? ）之間線段的長(zhǎng)度，那么兩個(gè)數(shù)據(jù)點(diǎn)離上述直線的距離都是d/2。為什么樣本數(shù)據(jù)中不可能有其他的數(shù)據(jù)點(diǎn)，離直線的距離小于d/2呢？這與凸包的性質(zhì)有關(guān)，與直線是“垂直平分線”有關(guān)，也與算法中第3步強(qiáng)調(diào)了要包括“點(diǎn)與邊的距離”有關(guān)。鼓勵(lì)有興趣的讀者思考體會(huì)一下這背后的“玄機(jī)”。當(dāng)然，也歡迎有疑問(wèn)的讀者與我們交流。

本文形成過(guò)程中與陳道蓄教授有過(guò)深入討論，他指出SVM算法中的第2步可以省去，進(jìn)而第4步也可以省去了。想想的確如此。不過(guò)文中保留了原樣，留作讀者思考為什么那兩步可以省去。

釋?zhuān)孩偌雌矫嫔蟽蓚€(gè)向量夾角的余弦值，其表達(dá)式的推導(dǎo)可見(jiàn)高中數(shù)學(xué)教材[2]。

②用什么特征來(lái)表示所關(guān)心的類(lèi)型，與對(duì)應(yīng)用背景的理解直接相關(guān)。這里采用兩個(gè)特征分量只是用來(lái)說(shuō)明算法運(yùn)行的過(guò)程，實(shí)際應(yīng)用中為區(qū)分隨性和理性消費(fèi)者會(huì)比這要求更多。

③這里，我們總假設(shè)兩個(gè)凸多邊形是不重疊的。

參考文獻(xiàn)：

[1]湯曉鷗，陳玉琨.人工智能基礎(chǔ)（高中版）[M].上海：華東師范大學(xué)出版社，2018，4：35.

[2]薛彬，張淑梅.數(shù)學(xué)（第二冊(cè)）[M].北京：人民教育出版社，2019，7：34.

[3]陳道蓄.平面上的凸包計(jì)算[J].中國(guó)信息技術(shù)教育，2020（21）：25-29.

注：作者系北京大學(xué)計(jì)算機(jī)系原系主任。