趙秦怡，黑韶敏

（大理大學數學與計算機學院，云南大理 671003）

分類是數據挖掘一個重要的研究方向，國內外諸多學者進行了大量的研究工作，提出了如決策樹分類、貝葉斯分類、基于規(guī)則的分類、神經網絡分類、支持向量機等各具特色的分類算法，傳統(tǒng)的分類算法都是針對確定性數據提出的。在大數據環(huán)境下，不確定數據是普遍存在的，如原始數據不準確、使用粗粒度數據集合、處理缺失值、數據集成中引入的不確定性等都會導致數據的不確定。

近年來，不確定性數據在數據挖掘領域的研究得到越來越多的關注，不確定數據分類研究是其中重要的研究分支。BI J B等〔1〕提出了一種面向不確定數據的基于支持向量機分類方法。楊志民等〔2〕利用未確知理論，建立離散型屬性不確定性數據模型，將其引入到支持向量機分類模型中。CHENG R等〔3〕提出一種屬性級不確定數據的樸素貝葉斯分類方法，方法采用了基于均值和基于分布的類條件概率密度函數。QIN B等〔4〕提出了兩種針對區(qū)間不確定數據的樸素貝葉斯分類方法，方法基于不確定數據在區(qū)間上滿足高斯分布的假設，通過不確定數據類條件概率密度函數上的積分預測未知類別樣本的類別標簽。QIN B等〔5〕提出了一種基于規(guī)則的不確定分類方法。QIN B等〔6〕提出了一種不確定決策樹分類算法，決策樹中不確定數據的屬性分裂度量準則是基于概率勢的思想。呂艷霞等〔7〕提出了一種大數據環(huán)境下的不確定數據流在線分類算法，其決策樹的葉子節(jié)點利用加權貝葉斯分類算法提高分類準確率，算法可以快速高效地分析不確定數據流。

不確定性數據主要分為元組存在不確定和元組屬性值不確定兩種類型。本文針對元組屬性值不確定提出了一種基于期望語義距離的k近鄰（KNN）分類方法，對象的不確定屬性值用概率分布向量描述，對象間的距離用期望語義距離計算。

1 相關定義

值不確定性是指一個對象的某個屬性可能取這個值，也可能取另一個值。在概率論方法中，對于不確定性連續(xù)屬性，采用概率密度函數表達數據對象的屬性值，而對于不確定性離散屬性，可以采用概率分布向量表達數據對象的屬性值〔8-10〕。在基于不確定性數據的KNN分類中，需要建立描述對象間期望語義距離關系的數學模型〔11〕。期望語義距離計算模型基于離散型屬性，對于連續(xù)值屬性來說，只需用攀升概念層次樹的方法將其離散化〔12〕。

例1對象o1、o2、o3由不確定性離散屬性“成績”描述，“成績”的值域為{優(yōu)秀、良好、及格、不及格}，o1的“成績”屬性值的概率分布向量o1.P=（0.9，0.1，0，0），o2.P=（0，0，0.9，0.1），o3.P=（0，0，0.1，0.9）。從語義的角度，可以判斷出o2離o1較近。

定義1在概念層次樹T中，結點node的深度d（node）是指從根結點到node的路徑長度。結點node的高度h（node）是指從node到以node為根結點的子樹中的葉結點的最長路徑長度。概念層次樹T的高度h（T）是指根結點的高度。結點node的層次l（node）定義為l（node）=h（T）-d（node）。

例2 關于氣候對象“區(qū)域”屬性的概念層次樹，如圖1所示。

圖1 “區(qū)域”屬性的概念層次樹

定義2在概念層次樹T中，設結點node1和node2的最近公共祖先是a（node1，node2）。結點node1和node2的語義距離定義為：

定義3當假設對象獨立時，值不確定性離散對象ou和ov的屬性值（概率分布向量）ou［Ai］=ou.PAi和ov［Ai］=ov.PAi之間的期望語義距離定義為〔11〕：

定義4值不確定性離散對象ou和ov之間的期望語義距離定義為〔11〕：

其中，當q=1時，求出的語義距離是曼哈頓距離，當q=2時，求出的語義距離是歐幾里得距離，當q＞2時，求出的語義距離是閔可夫斯基距離。在該方法計算語義距離時，設不確定離散屬性的值域有n個值，則屬性的不確定語義距離最多有n（n-1）∕2個。

定義5設不確定離散屬性Ai有nsdAi個不同值的語義距離，這些語義距離從小到大排列為當假設對象獨立時，值不確定性離散對象ou和ov的屬性值（概率分布向量）o［uA］i=ou.PAi和o［vA］i=ov.PAi之間的期望語義距離定義為〔11〕：

2 基于期望語義距離的不確定k近鄰分類法

2.1 算法思想在眾多的分類算法中，KNN分類法有難得的優(yōu)點，如易于編程，不需要優(yōu)化和訓練，在某些問題上具有很高的分類精確度，并且隨著設計樣本容量的增大估計出的概率偏差會降低等優(yōu)點〔12〕。KNN分類法的基本形式為：要分類一個輸入的新對象y，可在訓練數據集合中找出與y距離最近的k個對象，然后把這k個對象中大多數對象所屬的類賦給新對象y。

對象間的語義距離反映了對象間的相似性，語義距離越小，對象之間相似度越高，反之亦然。在不確定數據環(huán)境下，訓練集中對象的屬性取值具有不確定性，對于離散型屬性可用概率分布向量描述屬性的可能取值概率，向量中的分量表示屬性取某個值域可能的概率。離散型不確定性屬性值間的距離實際上是指兩個概率分布向量之間的距離，用傳統(tǒng)的距離計算方法不適用，算法中用了期望語義距離計算。由式（1）根據屬性的概念層次樹計算對象屬性值概率分布向量中所有分量間的期望語義距離，由式（2）計算不確定屬性間期望語義距離，但此方法計算耗費較大，由式（4）定義可知，根據不同的語義距離值建立屬性值分量語義距離索引表，可簡化值不確定性屬性之間期望語義距離的計算。待分類對象和訓練集中對象間期望語義距離的計算由式（3）定義。

例3o1，o2，o3，o44個氣候對象的“區(qū)域”屬性描述，在該屬性上的值概率分布如表1所示，“區(qū)域”屬性的概念層次樹見圖1。

表1 4種氣候在“區(qū)域”屬性上的概率分布（概率向量）

根據概念層次樹，計算“區(qū)域”屬性值域中的分量之間的語義距離，計算結果見表2。

表2 “區(qū)域”屬性值域中分量之間的語義距離

根據定義5，建立“區(qū)域”屬性值域語義距離的索引表，見圖2。

圖2 “區(qū)域”屬性值概率分布向量語義距離索引表

計算“區(qū)域”屬性值（概率分布向量）的期望語義距離及o1，o2，o3，o44個氣候對象之間的期望語義距離，結果見表3。

表3 4個對象間的期望語義距離

由表3可知，距離o1最近的對象是o3，距離o2最近的對象是o4。

2.2 算法描述

輸入：不確定訓練數據庫T、待分類對象集合O、屬性概念層次樹、k

輸出：待分類對象所屬類標簽

算法偽代碼：

forall attributeAiinN∕∕對訓練集中的每一屬性

{

compute_elements_SD（Ai）； ∕∕計算屬性值概率分布向量中分量值間的語義距離

create_attribute_index（Ai）；∕∕建立屬性值概率分布向量語義距離索引表

}

foralloinO∕∕對每一個待分類對象

{ foralltinT∕∕對訓練集中的每一對象

{ compute_stribute_instance_distance（o，t）； ∕∕計算屬性間的語義距離

compute_expected_instance_distance（o，t）；

∕∕計算對象間的語義距離

sort（distance）；∕∕語義距離排序

min（k，distance）→objects（C）； ∕∕找出前k個語義距離最小的對象

max_class（C）→label； 獲得前k個最近鄰對象的最大類

}

}

3 算法分析及實驗

本算法的時間耗費主要集中在屬性間語義距離的計算階段，設訓練集有n個對象，每個對象m個屬性，每個屬性最多有k個概率分布分量，則算法的時間復雜度為O（nmk2）。由于KNN分類法是基于要求的學習法，當需要與待分類對象比較距離的近鄰對象數量很大時，算法可能招致高的計算開銷，且當數據中存在大量與分類不相關屬性時，分類準確率會產生誤差。在數據預處理階段，對訓練集進行屬性相關分析，可以去除與分類任務不相關的屬性，降低訓練集的維度，提高分類的精確度。屬性相關分析可采用計算屬性信息增益的方法實現〔12〕，信息增益較大的屬性與類屬性相關較大，計算各屬性的不確定因子U（A）。

定義6 屬性的不確定U（A）定義如下：

其中Gain（A）為屬性A的信息增益，I（s1，s2，…，sm）為待分類對象集的信息熵。由公式可知屬性A的不確定因子在0和1之間變化，U（A）為0說明屬性A與類屬性之間統(tǒng)計無關，U（A）為1說明屬性A與類屬性之間最大相關。相關分析的目的就在訓練數據庫中保留前n個相關程度高的屬性或不確定因子大于閾值的屬性。

本次實驗采用合成數據，訓練集中含2 000個對象，10個屬性，每個屬性值概率分布向量含5個分量，期望語義距離計算采用歐氏距離。實驗環(huán)境：intel core（TM）i7-7500U 的 CPU，2.7 GHz主頻，8 GB內存，Windows 10操作系統(tǒng)，編程環(huán)境為Vc++6.0，數據庫管理系統(tǒng)為SQL Server 2008。

（1）取不同k值時的分類準確率比較，結果見表4。

表4 取不同k值的分類準確率比較

（2）將本算法與文獻〔3〕中的屬性值不確定貝葉斯分類方法比較，結果見表5。

表5 算法分類準確率比較

實驗結果表明，此算法是一個分類準確率好的基于不確定數據分類方法。算法中k的取值對分類結果有一定的影響，但這種影響是無規(guī)律的，分類時，k值可由領域專家指定，或通過實驗數據給定。

4 結束語

在關系數據庫的眾多分類算法中，KNN分類法有難得的優(yōu)點，但如果訓練集較大時，算法的時間耗費也增大〔12〕。在本算法中，在期望語義距離計算階段進行合理剪枝，降低算法的時間耗費，是今后的努力方法。

〔1〕BI J B，ZHANG T.Support Vector Classification with input Data Uncertainty〔J〕.IN Advances in Neural In?formation Processing Systems，2005（17）：161-168.

〔2〕楊志民，紹元海，梁靜.未知支持向量機〔J〕.自動化學報，2013，6（30）：895-901.

〔3〕CHENG R，REN J，LEE S D，et al.Na?ve bayes classi?fication ofuncertain data〔C〕∕∕Data Mining，2009，ICDM’09，Ninth IEEE InternationalConferenceon.2009：944-949.

〔4〕 QIN B，XIA Y，WANG S，et al.A novel Bayesian classification foruncertain data〔J〕.Knowledage-Based Systems，2011，24（8）：1151-1158.

〔5〕 QIN B，XIA Y，PRABHAKAR S， et al.A Rule-Based Classification Algorithm for Uncertain Data〔C〕∕∕Data Engineering，ICDE 2009，IEEE International Con?ference on.2009：1633-1640.

〔6〕QIN B，XIA Y，LI F.Dtu：A decision tree for uncer?tain data〔C〕∕∕In Proceedings of the 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining，PAKDD.2009：4-15.

〔7〕呂艷霞，王翠榮，王聰，等.大數據環(huán)境下的不確定數據流在線分類算法〔J〕.東北大學學報（自然科學版），2016，37（9）：1245-1248.

〔8〕高世健，王麗珍，肖清.一種基于U-AHC的不確定空間co-location模式挖掘算法〔J〕.計算機研究與發(fā)展，2011，48（S）：60-66 ．

〔9〕陸葉，王麗珍，陳紅梅，等.基于可能世界的不確定空間co-location模式挖掘研究〔J〕.計算機研究與發(fā)展，2010，47（S）：215-221．

〔10〕肖清，陳紅梅，王麗珍.基于DS理論的不確定空間co-location模式挖掘〔J〕.云南大學學報（自然科學版），