鄧惠俊

（萬博科技職業(yè)學院智能信息學院，安徽合肥230031）

0 引 言

在大數(shù)據(jù)時代，數(shù)據(jù)分類是最基礎的數(shù)據(jù)分析技術和任務之一。雖然相關學者已經(jīng)提出了很多自動數(shù)據(jù)分類算法，但這些算法并不適合所有應用場景，而且以“黑盒系統(tǒng)”形式存在的自動分類算法影響其可解釋性和可信度，對諸如圖像、視頻等高維復雜數(shù)據(jù)更是如此［1］。由于用戶傾向于根據(jù)高層特征解讀信息、度量相識度，而自動分類算法則依賴底層特征，所以二者間易形成語義鴻溝。允許用戶參與分類過程，將用戶的領域知識融入分類算法，有助于提高分類的可解釋性和可信度［2-4］。

近年來，基于機器學習的分類算法，尤其是基于深度學習的分類算法在很多領域表現(xiàn)優(yōu)異，已經(jīng)成為主流分類算法［5］?；跈C器學習的分類算法從訓練樣本中學習構建分類規(guī)則，首先，依據(jù)用戶的領域知識制作訓練樣本，使其蘊含用于分類的領域知識，然后，通過訓練將領域知識間接融入分類算法，從而部分克服語義鴻溝問題。但基于機器學習的分類算法需要足夠多的高質量訓練樣本，而大量高質量訓練樣本并不易得，甚至對很多探索式數(shù)據(jù)的分析，起初根本無訓練樣本。所以如何獲取高質量訓練樣本備受關注。

對于難以獲得大量標注數(shù)據(jù)的問題，主動學習有助于通過僅標注信息量較高的數(shù)據(jù)，達到減少標注工作量的目的［6］。文獻［7］提出基于主動學習的交互式分類算法構建過程，首先，在初始分類算法基礎上，通過主動學習不斷推送對學習算法有價值的數(shù)據(jù)供標注，然后，進一步優(yōu)化分類算法，接著，推送新的數(shù)據(jù)，如此循環(huán)直到獲得滿意的分類算法。其基本思想是用少量高質量訓練數(shù)據(jù)獲得與大量隨機選擇的訓練數(shù)據(jù)性能相當?shù)姆诸愃惴ǎ瑴p輕標注數(shù)據(jù)的工作量和計算負擔［8］，而且通過交互參與分類算法的構造過程，可將領域知識融入分類算法。

文獻［7］中的基于主動學習的分類算法雖然具有交互性，但只能通過簡單的數(shù)據(jù)列表標注類別，或挑選相關/不相關樣本等做簡單交互。如果能以更有意義和有效的方式呈現(xiàn)數(shù)據(jù)，則可更好地了解數(shù)據(jù)集的結構及相互關系，更好地進行決策和交互，進而完成分類。文獻［1］提出了一套完整的可視分類算法（visual classification methodology，VCM），將點可視化等技術融入分類流水線，以支持和控制分類過程。

在某些分類問題中，類別和待分類數(shù)據(jù)都是可排序的，如交警根據(jù)基本車況、交通違法記錄、交通事故記錄等信息將相關車輛分為高危車輛、中危車輛、低危車輛3類，車輛和車輛類別均可根據(jù)危險度排序。在某些場合，用戶較易確定數(shù)據(jù)之間的相對順序關系，但較難確定其具體類別，比如知道車輛A比車輛B危險，但并不清楚車輛的具體類別?；谏鲜鲇^察，筆者認為將數(shù)據(jù)順序關系認知融入分類過程能減輕認知負擔，優(yōu)化分類效果，然而文獻［1，7］中的交互分類算法都不支持此模式，為此，本文提出一種排序支持的交互分類算法，該算法同時支持標注數(shù)據(jù)類別信息和改變數(shù)據(jù)間的相對順序關系，充分利用數(shù)據(jù)類別認知和數(shù)據(jù)順序關系認知，達到減輕認知負擔、優(yōu)化分類結果的目的。

論文的主要貢獻有：（1）提出排序支持的交互式分類流程，將對數(shù)據(jù)順序關系的認知融入分類過程。（2）提出一種候選樣本推薦策略，允許在推薦的少量樣本中進行類別或順序標注。（3）提出一種評估分類算法性能的可視化方法，可直觀地觀察分類算法的性能，幫助決策所需的迭代次數(shù)。（4）基于基本車況、交通違法記錄、交通事故記錄等信息，將車輛分為高危車輛、中危車輛、低危車輛3類，驗證了本文算法的有效性。

1 相關工作

1.1 可視交互分類

文獻［9-10］提出的交互構建決策樹方法，提供了決策樹的優(yōu)化和剪枝算法，并通過關聯(lián)視圖和交互技術綜合分析了決策樹及相關數(shù)據(jù)。但這些算法只針對決策樹，且采用的是基于屬性的可視化方法，難以處理高維數(shù)據(jù)。

文獻［11］提出了基于線性判別分析（linear discriminant analysis，LDA）的 iVisClassifier系統(tǒng)，以提升不同類別之間的分離度，經(jīng)重新標注后，進行LDA投影，從而允許增量插入用戶的領域知識；針對在圖像或視頻搜索時缺少合適的訓練集和難以進行充分標注等問題，文獻［12］開發(fā)了可視反饋的可視分析系統(tǒng)，允許用戶接受或拒絕某個/某些數(shù)據(jù)用于訓練模型，從而將用戶知識融入模型，是一種較有效的用戶分析工具。

文獻［13］用級聯(lián)散點圖展示了分類算法各階段不同類別數(shù)據(jù)的分布情況；文獻［14］用t-SNE投影算法在2D散點圖中展示數(shù)據(jù)，并提供了標注數(shù)據(jù)、評估分類結果質量、發(fā)現(xiàn)誤標注區(qū)域（數(shù)據(jù)）的工具；文獻［1］提出了一套通用的交互分類框架，該框架支持漸進式分類各階段，并創(chuàng)造性地用相似樹表達數(shù)據(jù)間的相似度。

與文獻［1，11-12，14］等類似，本文提出一種交互分類流程?；贚DA算法在2D散點圖中展示高維數(shù)據(jù)及其相關性，供觀察和交互，從而逐步優(yōu)化模型。這是由于LDA算法具有監(jiān)督降維功能，能夠在投影結果中體現(xiàn)當前的分類情況，便于觀察分類結果的漸進優(yōu)化過程。本文算法與其他交互分類算法的最大區(qū)別在于，本文算法支持輸入數(shù)據(jù)之間的順序關系，并將其用于優(yōu)化交互分類。

1.2 可視交互排序

常見系統(tǒng)大多支持交互排序，如微軟的Excel和蘋果的Numbers均可基于用戶定義的公式對表格進行排序，但這類系統(tǒng)主要用于數(shù)據(jù)的生成、修改和展示，其可根據(jù)某列（屬性）對所有行（數(shù)據(jù)）進行排序，并不直接支持多屬性排序。

不少系統(tǒng)專門設計了排序交互界面。Table Lens［15］是基于魚眼的專用高維數(shù)據(jù)可視化技術，可在單個視圖中展示大量數(shù)據(jù)。與Table Lens類似，ValueCharts［16］和 LineUp［17］可 通 過點 擊 、拖 拉 調 整屬性權重，創(chuàng)建自定義排序，快速得到排序結果。但這類系統(tǒng)均要求指定相關屬性的權重，以創(chuàng)建合適的排序。

也有為特定領域/應用專門設計的排序系統(tǒng)。如文獻［18］為增強時序數(shù)據(jù)的可視化效果設計了相應的排序方法；文獻［19］基于文檔搜索結果的相關分數(shù)進行了可視化排序；文獻［20］用node-link同時展示了多種方法的排序結果。

文獻［21］在已知數(shù)據(jù)的相對順序未知其影響屬性時，允許輸入部分數(shù)據(jù)的順序關系，并基于ranking-SVM將輸入的順序關系應用于全部數(shù)據(jù)。筆者認同文獻［21］的觀點，并將文獻［21］的方法集成為分類流程，進一步發(fā)展了排序支持的交互分類算法。

2 排序支持的交互數(shù)據(jù)分類算法

為支持同時輸入數(shù)據(jù)類別認知和順序關系認知，本文設計了如圖1所示的界面。在視圖（a）中選中實例可標注相應類別，在視圖（b）中通過拖拽可指定實例的順序關系。無論視圖（a）還是（b），均只需指定少量實例的類別屬性和順序關系，通過訓練SVM和ranking-SVM分別得到分類模型和排序模型，并將分類模型和排序模型應用于所有數(shù)據(jù)。如果出現(xiàn)數(shù)據(jù)分類結果與排序結果不一致的情況，則意味著數(shù)據(jù)分類和（或）排序存在錯誤，可挑出錯誤數(shù)據(jù)將其作為候選標注數(shù)據(jù)，并在視圖（c）中顯示，通過顏色編碼的方式在視圖（a）和（b）中標注，同時，對3個視圖中所需標注數(shù)據(jù)的類別屬性或順序關系給予提示，輸入后進一步更新分類模型和排序模型。重復上述過程，直到獲得滿意的分類模型，交互分類流程如圖2所示。為幫助用戶更好地判斷當前分類模型的性能，還定義了一系列評估指標，如圖1（d）所示。

圖1 系統(tǒng)總界面Fig.1 System general interface

2.1 數(shù)據(jù)類別屬性展示和交互

通過降維算法將高維數(shù)據(jù)投影至二維空間，并在2D散點圖中展示，幫助了解數(shù)據(jù)的總體情況。散點圖中每個圓圈表示一條數(shù)據(jù)記錄，圓圈顏色表示數(shù)據(jù)類別。采用半透明方式繪制圓圈，以減少視覺遮擋，改善視覺效果；對系統(tǒng)推薦的候選標注數(shù)據(jù)，以加粗圓圈輪廓線方式凸顯（如圖3所示）。在2D散點圖中，通過點擊選中的某個數(shù)據(jù)實例進行類別屬性標注，完成標注后，點擊“更新分類模型”按鈕更新。系統(tǒng)將更新后的分類模型應用于所有數(shù)據(jù)，進而更新推薦數(shù)據(jù)，刷新視圖。

圖2 排序支持的交互分類流程Fig.2 Interactive classification process supported by sorting

圖3 基于散點圖的類別屬性展示與交互Fig.3 Display and interaction of category attributes based on scatter plot

2.1.1 高維數(shù)據(jù)投影

高維數(shù)據(jù)投影是實現(xiàn)在低維空間（如2D散點圖）中進行高維數(shù)據(jù)可視化的常用方法。常用的投影技術有主成分分析（PCA）、多維尺度變換（MDS）、線 性 判 別 分 析（LDA）、核 判 別 分 析（KDA）、隨機近鄰嵌入（SNE）、t分布隨機近鄰嵌入（t-SNE）等［22］。本文采用迭代式分類算法觀察分類結果及其變化，并做出相應決策。利用LDA算法的監(jiān)督性，可基于每輪迭代的分類結果進行新一輪投影。

本文還支持t-SNE投影?？紤]初始狀態(tài)下無分類信息，無法進行LDA投影，只能觀察數(shù)據(jù)本身，并可在LDA和t-SNE 2種投影方式之間切換。圖4展示了t-SNE及2種不同分類情況下的LAD投影效果。

圖4 投影效果對比Fig.4 Comparison of projection effects

2.1.2 基于SVM的分類模型

支持向量機（supported vector machine，SVM）是一種小樣本學習方法，訓練和預測的速度都較快，常被用于交互分類。如文獻［1，13］采用的均為SVM模型。本文也采用基于SVM的分類模型，當點擊“更新分類模型”按鈕后，系統(tǒng)基于所標注的類別屬性數(shù)據(jù)訓練SVM，最終獲得的SVM模型即為分類模型，再將其應用于所有數(shù)據(jù)。

因沒有采用增量式SVM模型［23］，本文方法每次都需重新訓練SVM。未來可采用增量式SVM模型，以加快訓練速度，保持模型的一致性。

2.2 順序關系可視化和交互

文獻［22］提出一種交互式高維數(shù)據(jù)排序系統(tǒng)Podium，本文借鑒Podium的界面設計和排序方法，采用如圖5所示的排序視圖展示和交互。主體采用電子表格展示數(shù)據(jù)的詳細屬性，通過拖拽調整順序關系，通過點擊“更新排序模型”按鈕進行更新。與更新分類模型類似，系統(tǒng)將更新后的排序模型應用于所有數(shù)據(jù)，進而更新推薦數(shù)據(jù)，刷新視圖。

圖5 基于表格的順序關系展示和交互Fig.5 Table-based order relationship display and interaction

與Podium不同，本文方法在電子表格中用不同的字體顏色編碼類別屬性，用淺背景色標注推薦數(shù)據(jù)（見圖5）。另外，也可在視圖中直接選中數(shù)據(jù)實例標注類別屬性，散點圖隨之同步更新。

Ranking-SVM［24］直觀地將經(jīng)典二分類SVM模型應用于排序。標準SVM模型的訓練集由一個二元 組 (di，yi)構 成 ，其 中 di∈Rm，是 m 維 向 量 ，yi∈{1，-1}表示類別。在排序問題中，因為已知di和dj的順序關系，所以ranking-SVM構造二元組的方式通常為

根據(jù)di和dj，判斷SVM模型的優(yōu)劣，進而將排序問題轉換為二分類問題。本文采用康奈爾大學JOACHIMS［24］所實現(xiàn)的 ranking-SVM 模型［25］。

與SVM模型類似，ranking-SVM模型也不支持增量訓練。

2.3 候選標注數(shù)據(jù)的挑選、排序和可視化

候選標注數(shù)據(jù)指系統(tǒng)推薦標注的數(shù)據(jù)。標注這類數(shù)據(jù)能最大限度地優(yōu)化分類模型和（或）排序模型，不用直接面對大量原始數(shù)據(jù)，僅需關注少量候選標注數(shù)據(jù)，可極大地減輕對模型的認知負擔。

本文面向類別之間有順序關系的分類問題，比如按危險度將車輛分為高危車輛、中危車輛、低危車輛3類，此處隱含高危車輛＞中危車輛＞低危車輛的關系。

2.3.1 候選標注數(shù)據(jù)的挑選

假設當前有數(shù)據(jù)集 D={d0，d1，…，dn}，數(shù)據(jù)將被劃分為類別 C={c1，c2，…，cL}，其中 ci滿足 c1＞c2＞…＞cL。如果數(shù)據(jù)di和dj之間的順序關系與其所述類別間的順序關系不一致，即滿足

采用SPSS13.0統(tǒng)計分析軟件。計量資料均以±s表示。采用配對t檢驗比較不同測量方法所得的數(shù)據(jù)，P＜0.05為差異具有統(tǒng)計學意義。

則認為當前分類模型和（或）排序模型對數(shù)據(jù)di和dj的處理不正確，需要將數(shù)據(jù)di和dj推送給用戶，以進一步確認其類別和（或）順序關系。

如果直接采用式（2）所示的關系，則可能導致推薦的數(shù)據(jù)過多。如表1所示，假設所有數(shù)據(jù)的類別都為c1，但數(shù)據(jù)d1被錯誤地標注為類別c2，那么所有數(shù)據(jù) d1，d2，…，d5都會被選作候選標注數(shù)據(jù)，導致推薦數(shù)據(jù)冗余。因此，本文要求di和dj在滿足式（2）的同時滿足在順序隊列中彼此相鄰。具體推薦算法偽代碼如下：

輸 入 。 二 元 組 序 列 (d1，y1)，(d2，y2)，… ，(dn，yn)，其 中d1＞d2＞…＞dn

表1 候選標注數(shù)據(jù)例子Table 1 Candidate labeled data example

輸出。候選數(shù)據(jù)點對 (di1，di2)，(di3，di4)，…

開始

for（i=1；i＜n；i++）

｛

j=i+1；

｛

將(di，dj)加入候選數(shù)據(jù)點對；

｝

｝

結束；

2.3.2 候選標注數(shù)據(jù)的排序

上述算法在迭代之初可能會出現(xiàn)較多候選標注數(shù)據(jù)，因此需對候選標注數(shù)據(jù)進行排序。本文算法基于以下2個假設。

①邊界點聚集效應假設。由于分類模型易錯分處于分類邊界點的數(shù)據(jù)，因此多數(shù)候選標注數(shù)據(jù)應聚集于分類邊界點附近。

由于真實分類邊界的未知性，本文提出邊界點聚集效應假設：如果某一候選標注數(shù)據(jù)在分類邊界周圍，那么附近應該有很多其他候選標注數(shù)據(jù)?；谝陨险J識，本文用候選標注數(shù)據(jù)聚集度評估其與邊界的距離，計算式為

其中，{d1，d2，…，dL}表示所有候選標注數(shù)據(jù)點。

②邊界點標注困難假設。由于有時難以確定處于邊界點的數(shù)據(jù)的具體類別或順序，因此更傾向于標注其他可確定的數(shù)據(jù)。基于此假設，在迭代初期，優(yōu)先處理遠離邊界點的數(shù)據(jù)有利于降低認知難度，實現(xiàn)模型的快速迭代。

2.3.3 候選標注數(shù)據(jù)的可視化

分類視圖與排序視圖展示的候選標注數(shù)據(jù)點并不突出，為將注意力聚焦于候選標注數(shù)據(jù)，本文設計了如圖6所示的候選標注數(shù)據(jù)視圖。為更好地觀察候選標注數(shù)據(jù)間的順序關系，用數(shù)據(jù)對(di，dj)的方式展示，用 max(I(di)，I(dj))定義(di，dj)的優(yōu)先級，其含義為數(shù)據(jù)對中越遠離分類邊界的數(shù)據(jù)，受到關注的優(yōu)先級越高。所有候選標注數(shù)據(jù)均按優(yōu)先級順序在候選標注數(shù)據(jù)視圖中展示。

圖6 候選標注數(shù)據(jù)視圖Fig.6 Candidate annotation data view

2.4 分類結果質量的評估和可視化

交互分類算法是由用戶驅動的迭代過程，通過觀察到的信息評估當前分類結果，進而決定是否繼續(xù)迭代。雖然可根據(jù)散點圖、電子表格觀察分類結果，但難以對分類結果的質量形成直觀認識，為此，設計了如圖7所示的評估視圖。由圖7可知，A區(qū)域展示模型一致度P，P表示分類結果與排序結果的一致程度，P越大，表示分類結果質量越高，P∈ [0，1]，計算式為

其中，D表示數(shù)據(jù)點集，C表示候選點集。

圖7 分類結果質量評估視圖Fig.7 Classification result quality measurement view

以高危車輛、中危車輛、低危車輛的分類問題為例，由式（4），低危車輛-中危車輛與低危車輛-高危車輛不一致對P的影響相同，而實際上二者存在差別，因此，采用如圖8所示的(m-1)×(m-1)三角陣展示不同類別之間出現(xiàn)混淆的候選數(shù)據(jù)點，三角陣的橫坐標從左到右依次為c1，c2，…，cm，縱坐標從上到下依次為c2，c3，…，cm，在第 (i，j)區(qū)域中展示ci和cj之間出現(xiàn)混淆的候選數(shù)據(jù)點，落在同一區(qū)域的多個候選數(shù)據(jù)點用t-SNE投影布局，根據(jù)候選點聚集度I(di)進行著色，有助于深入了解當前分類結果的質量。在圖7所示的分類結果中，B、C、D區(qū)域分別對應低危車輛-高危車輛、低危車輛-中危車輛、中危車輛-高危車輛。

圖8 分類結果質量評估視圖布局策略示意Fig.8 Schematic diagram of layout strategy for classification result quality measurement view

3 應用案例

隨著社會上汽車保有量的不斷增加，道路交通擁堵、交通事故頻發(fā)等問題日益嚴重。部分車況不佳、司機不遵守交通法規(guī)的車輛更加劇了問題的嚴重性。為便于精準關注和管理高危車輛，提高管理效率，實現(xiàn)基于基本車況、交通違法記錄、交通事故記錄等信息對車輛進行評估，本文算法專用于解決此問題，但也適用于其他領域中蘊含類別與順序信息的數(shù)據(jù)集，如癌癥分期判斷等。

3.1 數(shù)據(jù)來源

本案例中所用數(shù)據(jù)來源于合作公司提供的車輛脫敏數(shù)據(jù)，其中基本車況、交通違法記錄、交通事故記錄等信息經(jīng)整合與處理，最終得到包含9個字段的數(shù)據(jù)，具體如表2所示。

雖然原始數(shù)據(jù)中含148 500條記錄，但其中有大量數(shù)據(jù)相同，通過層次聚類法將數(shù)據(jù)分為98個類簇，從每個類簇中隨機選取1條數(shù)據(jù)構成新的數(shù)據(jù)集，將新數(shù)據(jù)集中的98條數(shù)據(jù)作為案例進行分析。為檢驗方法的有效性，還邀請了2名交通部門的技術專家，分別對該98條數(shù)據(jù)進行標注，對不一致的結果經(jīng)討論統(tǒng)一后標注，最終形成Ground Truth數(shù)據(jù)。

3.2 交互分類過程

在載入數(shù)據(jù)之初，采用t-SNE法將所有數(shù)據(jù)投影至散點圖（如圖9所示），同時根據(jù)2名技術專家提供的經(jīng)驗公式對數(shù)據(jù)進行排序，將初始排序結果顯示在電子表格中（見圖10）。

表2 車輛數(shù)據(jù)各屬性編碼及其含義Table 2 Coding and meaning of each attribute of vehicle data

圖9 初始分類視圖Fig.9 Initial category view

圖10 初始排序視圖Fig.10 Initial sort view

經(jīng)驗公式雖不一定準確，但可提供初步參考。首先，觀察電子表格頂部，將相關數(shù)據(jù)標注為“高危車輛”，類似地，觀察表格的中部和底部，將相關數(shù)據(jù)標注為“中危車輛”和“低危車輛”，表格中所標注的信息可在散點圖中同步顯示。然后，觀察散點圖中被標注數(shù)據(jù)的周邊情況，做進一步標注，最后點擊“更新分類模型”按鈕，便可自動更新數(shù)據(jù)分類結果、選擇候選標注數(shù)據(jù)、評估當前分類結果質量，并刷新相應視圖。中間候選標注數(shù)據(jù)視圖和中間分類結果質量評估視圖分別如圖11和圖12所示。

圖11 中間候選標注數(shù)據(jù)視圖Fig.11 Intermediate candidate annotation data view

圖12 中間分類結果質量評估視圖Fig.12 Quality measurement view of intermediate classification results

由圖12可知，中間分類結果模型一致度僅74%，需進一步優(yōu)化。繼續(xù)觀察候選標注數(shù)據(jù)視圖頂部，調整數(shù)據(jù)對的類別屬性或相對順序關系，選擇性地挑選并標注部分候選標注數(shù)據(jù)，便可更新分類模型和（或）排序模型，如此迭代，直至獲得滿意的分類結果。經(jīng)6輪迭代，合計進行18次類別屬性標注、25次順序關系標注，得到的最終分類結果質量評估視圖如圖13所示。由圖13可知，最終分類結果質量較好。

圖13 最終分類結果質量評估視圖Fig.13 Final classification result quality measurement view

與Ground Truth數(shù)據(jù)對比發(fā)現(xiàn)，98條數(shù)據(jù)中有96條分類結果一致，模型一致度近98%。其中不一致的2條數(shù)據(jù)在Ground Truth中被標注為“高危車輛”，而在本文算法中被分為“中危車輛”。進一步分析發(fā)現(xiàn)，這2條數(shù)據(jù)處于“高危車輛-中危車輛”的邊緣，所以該分類結果可以被理解和接受。

4 結 語

在大數(shù)據(jù)時代，分類是最基本的數(shù)據(jù)分析任務之一，交互分類是解決復雜分類問題最有效的方法之一。在某些分類應用場景中，用戶易于感知數(shù)據(jù)類別間的相對順序關系?；诖?，筆者借助用戶對數(shù)據(jù)間相對順序關系的認知，改進交互分類算法，提出排序支持的交互分類算法。另外，進一步給出了候選標注數(shù)據(jù)的推薦和排序問題、分類結果質量評估問題的相應解決方案，并以包括基本車況、交通違法記錄、交通事故記錄等信息的車輛數(shù)據(jù)集為例，將車輛分為高危車輛、中危車輛、低危車輛3類，分類結果模型一致度達近98%，驗證了本文算法的有效性。

本文算法將散點圖和電子表格作為主要可視化界面，由于視覺遮擋問題難以擴展，且難以應用于更大規(guī)模的數(shù)據(jù)集，未來可進一步探索多尺度可視化、魚眼可視化等技術，以提高視覺空間的利用效率；另外，目前排序模型信息僅用于輔助選擇候選標注數(shù)據(jù)和評估分類結果質量，未來可將排序信息直接融入分類模型，以充分利用排序信息。