趙秦怡，黑韶敏

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

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

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

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

1 相關(guān)定義

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

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

定義1在概念層次樹(shù)T中，結(jié)點(diǎn)node的深度d（node）是指從根結(jié)點(diǎn)到node的路徑長(zhǎng)度。結(jié)點(diǎn)node的高度h（node）是指從node到以node為根結(jié)點(diǎn)的子樹(shù)中的葉結(jié)點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。概念層次樹(shù)T的高度h（T）是指根結(jié)點(diǎn)的高度。結(jié)點(diǎn)node的層次l（node）定義為l（node）=h（T）-d（node）。

例2 關(guān)于氣候?qū)ο蟆皡^(qū)域”屬性的概念層次樹(shù)，如圖1所示。

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

定義2在概念層次樹(shù)T中，設(shè)結(jié)點(diǎn)node1和node2的最近公共祖先是a（node1，node2）。結(jié)點(diǎn)node1和node2的語(yǔ)義距離定義為：

定義3當(dāng)假設(shè)對(duì)象獨(dú)立時(shí)，值不確定性離散對(duì)象ou和ov的屬性值（概率分布向量）ou［Ai］=ou.PAi和ov［Ai］=ov.PAi之間的期望語(yǔ)義距離定義為〔11〕：

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

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

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

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

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

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

例3o1，o2，o3，o44個(gè)氣候?qū)ο蟮摹皡^(qū)域”屬性描述，在該屬性上的值概率分布如表1所示，“區(qū)域”屬性的概念層次樹(shù)見(jiàn)圖1。

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

根據(jù)概念層次樹(shù)，計(jì)算“區(qū)域”屬性值域中的分量之間的語(yǔ)義距離，計(jì)算結(jié)果見(jiàn)表2。

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

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

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

計(jì)算“區(qū)域”屬性值（概率分布向量）的期望語(yǔ)義距離及o1，o2，o3，o44個(gè)氣候?qū)ο笾g的期望語(yǔ)義距離，結(jié)果見(jiàn)表3。

表3 4個(gè)對(duì)象間的期望語(yǔ)義距離

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

2.2 算法描述

輸入：不確定訓(xùn)練數(shù)據(jù)庫(kù)T、待分類對(duì)象集合O、屬性概念層次樹(shù)、k

輸出：待分類對(duì)象所屬類標(biāo)簽

算法偽代碼：

forall attributeAiinN∕∕對(duì)訓(xùn)練集中的每一屬性

{

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

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

}

foralloinO∕∕對(duì)每一個(gè)待分類對(duì)象

{ foralltinT∕∕對(duì)訓(xùn)練集中的每一對(duì)象

{ compute_stribute_instance_distance（o，t）； ∕∕計(jì)算屬性間的語(yǔ)義距離

compute_expected_instance_distance（o，t）；

∕∕計(jì)算對(duì)象間的語(yǔ)義距離

sort（distance）；∕∕語(yǔ)義距離排序

min（k，distance）→objects（C）； ∕∕找出前k個(gè)語(yǔ)義距離最小的對(duì)象

max_class（C）→label； 獲得前k個(gè)最近鄰對(duì)象的最大類

}

}

3 算法分析及實(shí)驗(yàn)

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

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

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

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

（1）取不同k值時(shí)的分類準(zhǔn)確率比較，結(jié)果見(jiàn)表4。

表4 取不同k值的分類準(zhǔn)確率比較

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

表5 算法分類準(zhǔn)確率比較

實(shí)驗(yàn)結(jié)果表明，此算法是一個(gè)分類準(zhǔn)確率好的基于不確定數(shù)據(jù)分類方法。算法中k的取值對(duì)分類結(jié)果有一定的影響，但這種影響是無(wú)規(guī)律的，分類時(shí)，k值可由領(lǐng)域?qū)＜抑付ǎ蛲ㄟ^(guò)實(shí)驗(yàn)數(shù)據(jù)給定。

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

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

〔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ī)〔J〕.自動(dòng)化學(xué)報(bào)，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〕呂艷霞，王翠榮，王聰，等.大數(shù)據(jù)環(huán)境下的不確定數(shù)據(jù)流在線分類算法〔J〕.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，37（9）：1245-1248.

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

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

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