盛泓楊

摘要：數(shù)據(jù)分析和預(yù)測(cè)技術(shù)目前已被廣泛用于從醫(yī)學(xué)數(shù)據(jù)庫(kù)中挖掘知識(shí)信息，其中分類(lèi)是一種有監(jiān)督的學(xué)習(xí)方法，可用于設(shè)計(jì)描述重要數(shù)據(jù)類(lèi)別的模型。K近鄰算法（KNN）是一種易于實(shí)現(xiàn)、最受歡迎且高效的模式識(shí)別算法。但是，數(shù)據(jù)集的不均衡可能會(huì)產(chǎn)生不太準(zhǔn)確的結(jié)果。為了解決這個(gè)問(wèn)題，我們將KNN與遺傳算法（GA）結(jié)合在一起進(jìn)行有效的分類(lèi)。該方法使用每次迭代生成的合適個(gè)體擴(kuò)展少數(shù)類(lèi)集。通過(guò)這種方式使不同類(lèi)之間數(shù)量達(dá)到平衡。

關(guān)鍵詞：歸一化編碼;PCA;KNN;GA;召回率;準(zhǔn)確性

1.引言

該算法首先使用歸一化編碼對(duì)數(shù)據(jù)集中的20個(gè)客戶(hù)屬性進(jìn)行歸一化，然后通過(guò)PCA從20個(gè)數(shù)據(jù)集中提取與客戶(hù)是否會(huì)進(jìn)行定期存款有關(guān)的主要屬性，并消除次要屬性，從而將20維屬性減少為3維。為了建立準(zhǔn)確的預(yù)測(cè)模型，總客戶(hù)數(shù)據(jù)集的四分之三用作構(gòu)建模型的訓(xùn)練集，其余四分之一的數(shù)據(jù)用作測(cè)試集以測(cè)試預(yù)測(cè)模型的準(zhǔn)確性。該算法使用KNN預(yù)測(cè)個(gè)人的購(gòu)買(mǎi)意愿。具體方法是選擇最接近該個(gè)體的k個(gè)人（歐拉距離），以投票的形式確定該個(gè)體的類(lèi)別。同時(shí)，采用遺傳算法消除樣本不均衡性，提高了準(zhǔn)確性。測(cè)試數(shù)據(jù)時(shí)，召回率可以達(dá)到99%，相較未優(yōu)化時(shí)的結(jié)果有很大的提升。

2.算法介紹

2.1數(shù)據(jù)預(yù)處理

為了充分利用每種數(shù)據(jù)，該算法對(duì)原始數(shù)據(jù)進(jìn)行了歸一化，并將非數(shù)字?jǐn)?shù)據(jù)映射為Numbers。 為了提高模型訓(xùn)練速度，減少冗余，采用主成分分析（PCA）從多個(gè)屬性中提取主要成分，并在可以高度還原原始信息的情況下，將特征空間的維數(shù)減小為3維。功能標(biāo)準(zhǔn)化以平衡每個(gè)功能范圍：其中是特征j的平均值，Sj是特征j的標(biāo)準(zhǔn)偏差。計(jì)算協(xié)方差矩陣，使用SVD計(jì)算的特征向量，從U中取出前K個(gè)左奇異向量，構(gòu)成一個(gè)約減矩陣，計(jì)算新的特征向量，求各樣本的投影均方誤差，求數(shù)據(jù)的總變差，判斷下式是否成立，其取值可以為 0.001，0.005，0.010，…。其中當(dāng)選擇 =0.001，在特征間 99.9% 的差異性得到保留的情況下，可得k = 3，即選擇最大的三個(gè)特征值所對(duì)應(yīng)的特征向量做為主成分，將20維的數(shù)據(jù)空間降低至3維。

2.2行為預(yù)測(cè)

2.2.1 KNN

該算法使用KNN算法預(yù)測(cè)客戶(hù)行為（即是否訂閱）。

第一步是計(jì)算距離，即測(cè)試的客戶(hù)與訓(xùn)練集中的每個(gè)樣本之間的距離。 計(jì)算方法包括歐幾里得距離，曼哈頓距離，切比雪夫距離，余弦。四種計(jì)算距離的算法a=（，，） 和b=（，，） 在三維空間：

1.歐氏距離：

2.曼哈頓距離：

3.切比雪夫距離：

4.夾角余弦：

經(jīng)過(guò)多次驗(yàn)證，不同的距離算法對(duì)KNN的預(yù)測(cè)結(jié)果沒(méi)有顯著影響，但是在計(jì)算兩點(diǎn)之間的距離時(shí)，歐氏距離算法相對(duì)簡(jiǎn)單并且運(yùn)行速度很快。因此，選擇歐幾里德距離算法來(lái)計(jì)算被測(cè)客戶(hù)與訓(xùn)練集中每個(gè)樣本之間的距離。

通過(guò)該算法，我們獲得了一長(zhǎng)串關(guān)于測(cè)試客戶(hù)與訓(xùn)練集中每個(gè)樣本之間的距離的數(shù)據(jù)，從最小到最大對(duì)它們進(jìn)行了排名，并選擇了最接近測(cè)試客戶(hù)的k個(gè)樣本。經(jīng)過(guò)一系列測(cè)試和驗(yàn)證后，選擇了最合適的k值。

最后，我們提取的k個(gè)樣本分為兩類(lèi)：“是”和“否”。如果屬于“是”的樣本數(shù)量大于“否”，則測(cè)試的客戶(hù)將是“是”;否則，它們將為“否”?！笆恰北硎究蛻?hù)有訂購(gòu)意向，“否”表示客戶(hù)無(wú)意訂購(gòu)。

2.2.2 SVM

在機(jī)器學(xué)習(xí)中，支持向量機(jī)（SVM，也支持向量網(wǎng)絡(luò)）是帶有相關(guān)學(xué)習(xí)算法的監(jiān)督學(xué)習(xí)模型，該算法分析用于分類(lèi)和回歸分析的數(shù)據(jù)。當(dāng)給定一組訓(xùn)練樣本時(shí)，每個(gè)訓(xùn)練示例都標(biāo)記為屬于兩個(gè)類(lèi)別中的一個(gè)或另一個(gè)，則SVM訓(xùn)練算法將構(gòu)建一個(gè)模型，該模型將新示例分配給一個(gè)類(lèi)別或另一個(gè)類(lèi)別，使其成為非概率二進(jìn)制線(xiàn)性分類(lèi)器。SVM模型是將示例表示為空間中的點(diǎn)，并進(jìn)行了映射，以使各個(gè)類(lèi)別的示例被盡可能寬的明顯間隙分開(kāi)。然后，將新示例映射到相同的空間，并根據(jù)它們落在間隙的哪一側(cè)來(lái)預(yù)測(cè)屬于一個(gè)類(lèi)別。

首先，我們?cè)赟VM中使用擬合函數(shù)，并且假設(shè)輸出數(shù)據(jù)大于0.5時(shí)，我們可以認(rèn)為輸入數(shù)據(jù)的類(lèi)別為1，否則，我們認(rèn)為其類(lèi)別為0。

其次，我們?cè)赟VM中使用分類(lèi)函數(shù)，將數(shù)據(jù)輸入到SVM中，然后返回代表輸入數(shù)據(jù)類(lèi)別的數(shù)字.

由上述可知，使用SVM的準(zhǔn)確性和召回率不夠理想，我們認(rèn)為應(yīng)該使用更好的算法來(lái)描述數(shù)據(jù)。通過(guò)比較SVM算法和KNN算法的結(jié)果，可以看出KNN的召回率和準(zhǔn)確性率較高，因此本設(shè)計(jì)選擇了KNN算法。

2.3算法優(yōu)化

從表中可以看出，樣本中“是”和“否”的數(shù)量變化很大，樣本不平衡，導(dǎo)致預(yù)測(cè)模型的準(zhǔn)確率低于50%。 因此，我們需要優(yōu)化KNN算法。有兩種優(yōu)化方法。

2.3.1遺傳算法

遺傳算法屬于一類(lèi)較大的進(jìn)化算法，它們使用自然進(jìn)化啟發(fā)的技術(shù)（例如繼承，變異，選擇和交叉）來(lái)生成優(yōu)化問(wèn)題的解決方案。 該算法利用遺傳算法擴(kuò)展少數(shù)族群，從而消除樣本不等式。

ⅰ.選擇初始人口

運(yùn)算符用于選擇要復(fù)制的個(gè)人。 各種選擇方法有輪盤(pán)賭輪選擇，隨機(jī)選擇，等級(jí)選擇等。 由于訓(xùn)練集的樣本是離散的任意值。 為了適應(yīng)特征，該算法選擇“隨機(jī)選擇”以形成“初始種群”。

ⅱ.交叉

這是獲取兩個(gè)父染色體并從中產(chǎn)生一個(gè)子代的過(guò)程。 該運(yùn)算符將應(yīng)用于創(chuàng)建新樣本。 各種類(lèi)型的交叉算子有單點(diǎn)交叉，兩點(diǎn)交叉，N點(diǎn)交叉等等。 由于每個(gè)樣本僅具有3個(gè)屬性，因此單點(diǎn)交叉是最適合數(shù)據(jù)的運(yùn)算符。

ⅲ.突變

該運(yùn)算符用于更改新的解決方案以尋找更好的解決方案。 突變可防止GA陷入局部最小值。

a（ i ） 值1的概率為1 / m，0的概率為1-1 / m，通常m =20。L是染色體的長(zhǎng)度。

ⅳ.適應(yīng)度函數(shù)

GA中的適應(yīng)度函數(shù)是其表型的目標(biāo)函數(shù)值。 必須先處理染色體，才能計(jì)算適應(yīng)度函數(shù)。

2.3.3數(shù)據(jù)均衡方法（1）

更改訓(xùn)練集樣本不同類(lèi)別的權(quán)重，即將少數(shù)類(lèi)所投票的權(quán)重增大，從而使少數(shù)類(lèi)在投票時(shí)與多數(shù)類(lèi)有相同的選擇權(quán)重.

3.結(jié)果與討論

根據(jù)以上數(shù)據(jù)，如果僅對(duì)測(cè)試集使用KNN分析，則準(zhǔn)確性，召回率和準(zhǔn)確率相對(duì)較低，這是由于訓(xùn)練集中兩種類(lèi)型的樣本嚴(yán)重失衡造成的。 因此，有必要對(duì)KNN算法進(jìn)行優(yōu)化。 具體做法包括權(quán)重法和遺傳算法，可以觀察到它們對(duì)KNN的三個(gè)指標(biāo)-準(zhǔn)確性，召回率和準(zhǔn)確率有不同的影響。 準(zhǔn)確度和準(zhǔn)確率與少數(shù)樣品的重量成反比，與GA后少數(shù)樣品的倍數(shù)成反比。 召回率相反。

參考文獻(xiàn)：

[1]Kubat M，Matwin S.Addressing the course of imbalanced training sets：one-sided selection[C]//Proc of the 14th International Conference on Machine Learning，San Francisco，CA，1997：179-186.

[2]Provost F.Machine leaning from imbalanced data sets.Proc of 17th Nat Conf AAAI，Workshop on Imbalanced Data Sets.Austin： TX，2000： 71—73