崔學(xué)婷，柯永忠，孫茂鵬，司義品，高 杰

(1.北京航空航天大學(xué)，北京 100191;2天信達(dá)信息技術(shù)有限公司，北京 100022)

航空貨運(yùn)安檢過程中，開箱檢查環(huán)節(jié)非常重要，耗時(shí)費(fèi)力。為了在保障航空安全的同時(shí)，提高安檢效率，對(duì)不同信用評(píng)級(jí)的貨運(yùn)代理人的貨物可采用“差異化安檢”。對(duì)于信用評(píng)級(jí)低的代理人，提高開包率，重點(diǎn)檢查；而信用評(píng)級(jí)高的代理人，提高過檢便利性，從而在整體上提高安檢效率。目前，對(duì)航空貨運(yùn)代理人的信用評(píng)級(jí)方法主要有層次分析法和扣分法。這兩種算法在數(shù)據(jù)獲取的便利性和評(píng)價(jià)時(shí)效性上，都有其局限性，見表1。

表1 算法對(duì)比

針對(duì)以上兩種算法的局限性，筆者提出利用貨運(yùn)安檢數(shù)據(jù)進(jìn)行代理人信用評(píng)級(jí)分析。隨著安檢信息系統(tǒng)的廣泛使用，積累了大量的貨運(yùn)安檢數(shù)據(jù)，易于獲取，且時(shí)效性高。因是未標(biāo)記數(shù)據(jù)，需采用聚類的方法。其中K-Means算法[12]常被用于用戶畫像，或企業(yè)信用評(píng)級(jí)等領(lǐng)域。但K-Means算法也存在兩點(diǎn)不足：對(duì)初始簇的中心敏感，以及針對(duì)不規(guī)則聚類簇效果差，無法保證所得結(jié)果是用戶指定分類。為了解決這兩個(gè)問題，提高聚類的準(zhǔn)確性，筆者采用半監(jiān)督學(xué)習(xí)的約束種子K-Means方法。在傳統(tǒng)K-Means算法的基礎(chǔ)上，通過引入少量帶標(biāo)記數(shù)據(jù)，來得到符合用戶需求的聚類效果。

1 K-Means聚類

K-Means算法以各類樣本中心代表該簇，初始中心是隨機(jī)選擇的，重復(fù)計(jì)算多次，過程如下：

①K-Means算法首先從樣本集中隨機(jī)選擇K個(gè)樣本，作為初始聚類中心，代表K個(gè)簇。C={C1,C2,…,Ci,…,Ck}為K個(gè)聚類中心。假設(shè)樣本集為X={X1，X2，…，Xj，…，Xn}且Xj∈Rm，m為樣本維度。計(jì)算每個(gè)樣本Xj到中心點(diǎn)的距離d(Xj,Ci):

(1)

公式(1)中，g表示數(shù)據(jù)的第g維。

②每個(gè)樣本點(diǎn)都有其對(duì)應(yīng)的距離最近的中心點(diǎn)，將該樣本點(diǎn)劃分到該中心點(diǎn)所在簇中，全部分類后重新計(jì)算各個(gè)簇的中心。記第i類數(shù)據(jù)為Xi={Xi1，Xi2，…，Xip，…，Xiq}，其中q表示該樣本規(guī)模，新的中心Ci計(jì)算式為：

(2)

③得到新的中心點(diǎn)后，通過公式(1)(2)重復(fù)以上步驟，直到各個(gè)簇的中心點(diǎn)不再變化。此時(shí)得到的中心點(diǎn)即為最終聚類中心，樣本點(diǎn)所屬的簇即為該樣本的分類標(biāo)記。

2 約束種子K-means算法

約束種子K-Means算法的思想是：在判斷某個(gè)樣本是否屬于某個(gè)類時(shí)，依然采用與中心的距離來判斷；對(duì)于已經(jīng)有標(biāo)簽的樣本，將它們固定好屬于哪個(gè)類，這些帶標(biāo)簽的樣本，確定了各個(gè)類初始的聚類中心；而對(duì)于其他不帶標(biāo)簽的數(shù)據(jù)，則根據(jù)其與各類中心的距離來判斷。

該算法主要分為5個(gè)步驟進(jìn)行：①根據(jù)帶標(biāo)記的數(shù)據(jù)，計(jì)算每個(gè)類的初始中心；②計(jì)算每個(gè)未標(biāo)記樣本到K個(gè)中心的距離；③選擇距離最小的類作為該樣本的類；④重新計(jì)算各類中心；⑤重復(fù)2步～4步，直到所有類中心都不再變化，或達(dá)到最大迭代值。

2.1 導(dǎo)入帶標(biāo)記數(shù)據(jù)

由貨檢信息系統(tǒng)的貨運(yùn)安檢數(shù)據(jù)，統(tǒng)計(jì)后得到代理人的數(shù)據(jù)，經(jīng)航空貨運(yùn)安檢相關(guān)人士對(duì)部分典型的數(shù)據(jù)進(jìn)行標(biāo)記，如對(duì)安檢件數(shù)很多(該代理人體量大)，開包率很小，危險(xiǎn)品數(shù)很小，開包結(jié)果良好的代理人評(píng)為優(yōu)；對(duì)安檢件數(shù)很少，開包率卻很高，危險(xiǎn)品數(shù)較多，開包結(jié)果較差，存在大量移交、退運(yùn)、暫扣的包裹等，這類代理人被標(biāo)記為差；此外選一些各項(xiàng)指標(biāo)處于中等級(jí)別的代理人，標(biāo)記為中。將這些已標(biāo)記的數(shù)據(jù)，導(dǎo)入到將進(jìn)行聚類分析的無標(biāo)記數(shù)據(jù)中，共同作為半監(jiān)督聚類的輸入數(shù)據(jù)。

2.2 根據(jù)帶標(biāo)記數(shù)據(jù)計(jì)算初始類中心

在K-Means算法中，初始K個(gè)聚類中心是隨機(jī)值，因此聚類結(jié)果受初始值影響，并非每次結(jié)果都一致，且K-Means算法按照數(shù)據(jù)本身的特點(diǎn)來分類，因此其得到的結(jié)果可能并未與用戶想要的分類效果一致。在原始代理人數(shù)據(jù)上增加一個(gè)屬性，表示代理人級(jí)別。行業(yè)專家標(biāo)記過的數(shù)據(jù)，在級(jí)別屬性中分別填入相應(yīng)的數(shù)值，其他未標(biāo)記的數(shù)據(jù)該屬性為空值。將全部這些數(shù)據(jù)作為約束種子K-Means算法的輸入，具體計(jì)算過程如下：

①找到所有帶標(biāo)記的數(shù)據(jù)，并找到所有分類T={T1,T2,…,Ti,…,Tk}。

②對(duì)每一個(gè)分類Ti，找出所有級(jí)別屬性為Ti的已標(biāo)記數(shù)據(jù)Xj={Xj1,Xj2,…,Xjm,…,Xjn}，其中{j1,j2,…,jm,…,jn}為代理人級(jí)別為Ti的已標(biāo)記數(shù)據(jù)在原始數(shù)據(jù)集中的下標(biāo)，n為該類別已標(biāo)記數(shù)據(jù)的個(gè)數(shù)。

③Ti分類的初始中心為

(3)

④由式(3)計(jì)算得到的所有的類別的初始中心，C={CT1,CT2,…,CTm,…,CTk}，由上述初始中心集，代替K-Means算法中的K個(gè)隨機(jī)初始中心。

2.3 對(duì)未標(biāo)記數(shù)據(jù)重復(fù)K-Means過程

對(duì)未標(biāo)記數(shù)據(jù)運(yùn)用K-Means算法中的式(1)，計(jì)算到每個(gè)中心點(diǎn)的距離，選取距離最近的中心點(diǎn)，將其分到該中心點(diǎn)所在分類后，重新計(jì)算各類中心。對(duì)其中一個(gè)類Ti，對(duì)所有屬于該簇的數(shù)據(jù)，包括已標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)，運(yùn)用公式(3)計(jì)算新的類中心CTi。對(duì)每個(gè)類都得到新的中心點(diǎn)后，重復(fù)上述步驟，不斷更新類的中心，直到各類的中心點(diǎn)不再變化，得到最終的聚類中心，未標(biāo)記數(shù)據(jù)所屬簇的類別，即為該代理人所對(duì)應(yīng)的級(jí)別。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 數(shù)據(jù)準(zhǔn)備

本研究獲取某機(jī)場(chǎng)2017年的5 300余條貨檢數(shù)據(jù)，經(jīng)過數(shù)據(jù)清洗和統(tǒng)計(jì)相關(guān)的數(shù)值后，得到160余條代理人數(shù)據(jù)。航空貨檢數(shù)據(jù)字段說明，見表2中第1列是貨檢數(shù)據(jù)字段名稱，第2列是字段中文解釋，第3列是貨檢數(shù)據(jù)示例。

表2 貨檢數(shù)據(jù)字段說明

3.2 K值選擇

運(yùn)行約束種子K-Means算法前，首先要設(shè)置類簇的個(gè)數(shù)，即K值，確定數(shù)據(jù)被分為幾個(gè)簇。輪廓系數(shù)在算法中是評(píng)判結(jié)果優(yōu)劣的方法，設(shè)定分類數(shù)K后，計(jì)算對(duì)應(yīng)的輪廓系數(shù)Sk，求取最大值。此時(shí)的K值則為最佳的聚類數(shù)目，同時(shí)最大的Sk被稱作最佳聚類輪廓系數(shù)，此時(shí)的聚類結(jié)果認(rèn)為是最佳聚類。如圖1所示，K為3時(shí)輪廓系數(shù)最大。

圖1 輪廓系數(shù)與不同類簇?cái)?shù)之間的關(guān)系

3.3 聚類及對(duì)比實(shí)驗(yàn)

筆者利用貨運(yùn)安檢系統(tǒng)數(shù)據(jù)，引入少量已標(biāo)記數(shù)據(jù)，采用半監(jiān)督約束種子K-Means聚類算法進(jìn)行分析。作為對(duì)照分析，用傳統(tǒng)K-Means算法進(jìn)行了聚類分析。為了能直觀地對(duì)比聚類效果，選取貨檢總件數(shù)、開包數(shù)量、危險(xiǎn)品數(shù)量3個(gè)維度進(jìn)行可視化展示。見圖2和圖3。

從圖2可以看出，當(dāng)K為3時(shí)，K-Means會(huì)將危險(xiǎn)品率高的，開包率高的代理人分在兩個(gè)不同的簇中，如圖中黑圈標(biāo)出的兩個(gè)代理人，這顯然不符合實(shí)際的評(píng)價(jià)標(biāo)準(zhǔn)。危險(xiǎn)品率高的和開包率高的代理人，都應(yīng)屬于評(píng)級(jí)低的級(jí)別。引入帶標(biāo)記數(shù)據(jù)，運(yùn)用約束種子K-Means算法后的聚類結(jié)果，如圖3所示，可以看出，當(dāng)代理人體量較小時(shí)，開包率高的與危險(xiǎn)品數(shù)目比例高的代理人都劃分為信用低的評(píng)級(jí)，這個(gè)分類結(jié)果更符合現(xiàn)實(shí)中的意義。

圖2 K-Means聚類結(jié)果 圖3 約束種子K-Means聚類結(jié)果

為了進(jìn)一步說明約束種子K-Means算法，對(duì)聚類效果的改進(jìn)，用ARI(adjusted rand index)指標(biāo)來進(jìn)行衡量。Vinh等指出ARI指標(biāo)是目前最好的聚類評(píng)價(jià)指標(biāo)。ARI取值范圍為[-1,1]，值越大意味著聚類結(jié)果與真實(shí)情況越吻合。首先準(zhǔn)備一部分帶標(biāo)記的代理人數(shù)據(jù)，作為測(cè)試集。用兩種方法分別進(jìn)行聚類，將標(biāo)記結(jié)果與測(cè)試集中的原有標(biāo)記進(jìn)行比較，計(jì)算ARI指標(biāo)。由表3可看出，約束種子K-Means的ARI數(shù)值更高，即該算法給出的評(píng)級(jí)結(jié)果與代理人的實(shí)際信用等級(jí)水平更接近。

表3 ARI指標(biāo)對(duì)比

4 結(jié)束語(yǔ)

筆者目的是找到一種更加客觀、實(shí)時(shí)地對(duì)航空貨運(yùn)代理人信用等級(jí)進(jìn)行評(píng)估的方法。利用航空貨運(yùn)安檢信息系統(tǒng)的數(shù)據(jù)，采用半監(jiān)督學(xué)習(xí)的約束種子K-Means聚類方法，對(duì)航空貨運(yùn)代理人進(jìn)行評(píng)級(jí)。

具體而言，利用半監(jiān)督約束種子K-Means聚類算法，對(duì)航空貨運(yùn)代理人的安檢數(shù)據(jù)進(jìn)行分析，聚類結(jié)果可以有效地將代理人分為若干類。為了表明半監(jiān)督約束種子K-Means算法的優(yōu)越性，筆者對(duì)比了此算法與K-Means的聚類結(jié)果。半監(jiān)督約束種子K-Means聚類的準(zhǔn)確率比K-Means高；另外，通過對(duì)代理人的評(píng)級(jí)，可以直觀地得到各代理人的信用水平，從而為合理安排安檢資源，提高效率提供了合理建議；可以追蹤每周代理人信用水平的變化，給予鼓勵(lì)或督促改進(jìn)，從而可以為代理人的監(jiān)管，提供科學(xué)合理的支撐。