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

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

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

表1 算法對比

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

1 K-Means聚類

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

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

(1)

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

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

(2)

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

2 約束種子K-means算法

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

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

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

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

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

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

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

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

③Ti分類的初始中心為

(3)

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

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

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

3 實驗及結(jié)果分析

3.1 數(shù)據(jù)準備

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

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

3.2 K值選擇

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

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

3.3 聚類及對比實驗

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

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

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

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

表3 ARI指標對比

4 結(jié)束語

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

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