基于張開角測度的數(shù)據(jù)約簡*

李　晨， 王亞茹， 岳士弘

(天津大學(xué) 電氣與自動化工程學(xué)院，天津 300072)

基于張開角測度的數(shù)據(jù)約簡*

李晨， 王亞茹， 岳士弘

(天津大學(xué) 電氣與自動化工程學(xué)院，天津 300072)

摘要:數(shù)據(jù)約簡是包括數(shù)據(jù)壓縮、數(shù)據(jù)調(diào)整和特征提取在內(nèi)的數(shù)據(jù)挖掘技術(shù)中的重要課題，但已有的數(shù)據(jù)約簡方法主要聚焦在特征或者維度的約簡，而針對樣本個數(shù)的約簡方法，往往是針對具體的數(shù)據(jù)集開發(fā)，缺乏一般性。 針對數(shù)據(jù)集中數(shù)據(jù)分布的一般特征，定義一種新的基于張開角的測度。該測度能夠區(qū)分?jǐn)?shù)據(jù)集中核心對象和邊界對象分布的本質(zhì)區(qū)別，實現(xiàn)數(shù)據(jù)集中以核心對象為中心的數(shù)據(jù)壓縮。通過對UCI公共測試平臺上20個具有不同特征的典型樣本集進行數(shù)據(jù)約簡和測試，結(jié)果表明:約簡能夠有效地提取數(shù)據(jù)集中的核心目標(biāo)；通過對約簡前后數(shù)據(jù)集采用經(jīng)典K均值算法聚類，發(fā)現(xiàn)約簡后數(shù)據(jù)集中聚類正確率明顯高于約簡前數(shù)據(jù)集。

關(guān)鍵詞:數(shù)據(jù)約簡； 方向角； 聚類分析

0引言

數(shù)據(jù)約簡是在保持分類和決策能力的前提下，對數(shù)據(jù)中不相關(guān)或者不重要的信息進行去除。冗余的數(shù)據(jù)不僅浪費存儲空間，而且影響分類的精確性和決策的正確性。數(shù)據(jù)約簡包括特征約簡和樣本數(shù)約簡。已有的關(guān)于特征約簡的研究成果已經(jīng)很豐富也很深入，如神經(jīng)網(wǎng)絡(luò)、粗集、主成分分析等[1～3]。目前有關(guān)數(shù)據(jù)約簡的方法主要集中在對樣本屬性的約簡上即特征約簡,而對數(shù)據(jù)集中總的樣本個數(shù)的約簡方法，則主要是對特定數(shù)據(jù)集進行，方法較少且缺乏一般性。 當(dāng)前，隨著信息量呈現(xiàn)出爆炸性的增長，對海量數(shù)據(jù)使用數(shù)據(jù)約簡是不可避免的，目前見諸于報道的包括抽樣和綜合兩種途徑[4,5]。一種抽樣方法是將樣本分成若干子集，然后分別對這些子集進行學(xué)習(xí)，對學(xué)習(xí)結(jié)果進行重新組合；另一種方法是對樣本進行分組，然后反復(fù)選取那些能夠提高學(xué)習(xí)效果的例子加進來[6]。綜合的方法試圖產(chǎn)生適合內(nèi)存大小的數(shù)據(jù)，然后對這些數(shù)據(jù)進行訪問。綜合的數(shù)據(jù)可以由統(tǒng)計得來[7,8]，也可以由壓縮技術(shù)得到[9]。抽樣和綜合可以互為補充，將兩者結(jié)合起來使用。

抽樣是最常用的一種減少樣本數(shù)的方法。通過對數(shù)據(jù)樣本的精選，不僅減少了數(shù)據(jù)的處理量，還節(jié)省了系統(tǒng)資源，并且通過對數(shù)據(jù)的篩選，使其反映的規(guī)律性更加凸顯。但由于通常情況下樣本集中樣本的分布并不可知，故抽樣的代表性難以保證。

對海量數(shù)據(jù)進行數(shù)據(jù)約簡并不是對其進行簡單的比例縮放。傳統(tǒng)方法是發(fā)現(xiàn)數(shù)據(jù)庫中所反映的每一個模型，它們是局部的模式或反模式(異常)。目前，數(shù)據(jù)約簡的研究關(guān)心約簡效率比關(guān)心約簡后泛化能力要多得多。實際上，泛化的合理性和抽取樣本的代表性才是機器學(xué)習(xí)的核心，圍繞該問題的工作十分有意義[10]。

本文提出一種新的基于張開角的測度，從數(shù)據(jù)集樣本的分布特征出發(fā)，區(qū)分核心目標(biāo)和邊界目標(biāo)，通過漸進的迭代優(yōu)化運算,刪除相互之間類別信息模糊的無用數(shù)據(jù)，而這些目標(biāo)對應(yīng)著數(shù)據(jù)集中樣本分布的邊界點。實驗結(jié)果表明：采用本文提出的方法能夠在大幅度縮減原始訓(xùn)練集規(guī)模的同時保持原分類問題的識別精度。事實上，通過使用經(jīng)典的K均值算法聚類到約簡前和約簡后的數(shù)據(jù)集，約簡后的數(shù)據(jù)集中的聚類正確率明顯高于約簡前的數(shù)據(jù)集，這表明本文提出的方法能夠有效地提取數(shù)據(jù)集中的代表點保留數(shù)據(jù)集中有用的信息消除噪聲目標(biāo)的干擾[11,12]。

1基于張開角測度的數(shù)據(jù)約簡

本節(jié)首先提出一個基于張開角測度的數(shù)據(jù)約簡方法，這個方法基于如下觀察。圖1顯示一個包含12個點的數(shù)據(jù)集中數(shù)據(jù)的分布,其中,圖1(a)是原始的數(shù)據(jù)集; 圖1(b)～(d) 分別相應(yīng)于邊界點、中間點和核心點的分布及張開角示意。 從這些點的幾何位置上比較，大致可以分為外側(cè)的邊界點(A,C,H,E,F,G)、中間點(B,L,J,H)和核心點(K,I)。

圖1　一個類中不同點的分布與張開角Fig 1　Distribution and open-angle of different points in a class

邊界點與其它點的一個顯著區(qū)別是，如果從任何一個考察的邊界點與內(nèi)部最近的若干點做連線，則這些連線逐對之間的平均張開角要遠(yuǎn)小于其它中間點和核心點的張開角。實際上，對于每個點選擇離其最近的4個點做連線，則邊界點A,C,H,E,F,G的平均張開角值為67.5°、中間點B,L,J,H為112.3°和核心點K,I為120.4°。一個點離開群聚點越遠(yuǎn)，它的平均張開角越小。另一方面，一個點在當(dāng)前不是邊界點，但是在一個邊界點被去除后卻可能變成邊界點，從而與其它邊界點可以進行比較。如圖1中的B點，在去除A點后變成邊界點。因此，當(dāng)約簡迭代且漸進地進行時，每次約簡的都是一個最靠近邊界的點。

一般設(shè)X={x1,x2,…,xn} 是一個d維空間中包含n個數(shù)據(jù)向量(模式)集合，任取X中第i個向量xi,設(shè)xi1,xi2,…,xi2d是2d個順時針排列的距離其最近的向量，則從xi出發(fā)與xi1,xi2,…,xi2d相連構(gòu)成(2d-1)個向量的張開角(xi,xi1),(xi1,xi2),…,(xi(2d-1),xi(2d))，則定義xi的平均張開角測度如下為

i=1,…,n

(1)

式中Angle( )為一對從xi出發(fā)的一對連接向量之間的夾角; |xsxi|相應(yīng)的連接長度；因此，m(xi)的設(shè)計基于邊界點的兩個特征：較大的張開角和較長的與近鄰點的連接距離。較長的連接距離意味著該點附件其它點分布稀疏，或者說密度較小。另一方面，根據(jù)前面的分析,本文提出的方法不是進行一次性約簡，而是使用一個迭代的約簡過程，按照一定約簡比例逐個刪除樣本實現(xiàn)原始數(shù)據(jù)集的約簡。具體實現(xiàn)過程如下：

1)輸入d維空間數(shù)據(jù)點集X={x1x2,…,xn};

2) 計算X中逐對點之間的距離構(gòu)成一個新的數(shù)據(jù)集D(X);

3)記X=X1∪X2;

4)開始

讓X1=?(空集)且X2=X;

5)重復(fù)

對于任意xi∈X在D(X)中找出連接該點長度最小的2d距離；

6)根據(jù)式(1)計算xi∈X的平均張開角;

7)根據(jù)張開角排序所有X中的點;

8)去除張開角最小的向量;

9)去除該去除向量對應(yīng)的連接距離;

10)重新計算這些相關(guān)向量的張開角;

11)返回步驟(7);

12)在達(dá)到一個約簡比后輸出結(jié)果。

以一個包含80個點的數(shù)據(jù)集為例來說明數(shù)據(jù)約簡過程。圖2顯示了這80個數(shù)據(jù)點在二維坐標(biāo)系下的分布情況，其中,x軸表示點的橫坐標(biāo)，y軸表示點的縱坐標(biāo)。本文后續(xù)約簡圖中的坐標(biāo)表示與圖2相同。當(dāng)約簡比分別設(shè)定為30 %,50 %,80 %時，圖3顯示了30 %,50 %,80 %目標(biāo)被約簡后的數(shù)據(jù)集，其中,實心點表示被保留的點，而空心圓圈表示被約簡的點。從圖中可以看出，隨著迭代的進行，約簡過程始終沿著邊界進行，各個類的幾何中心由于與相鄰點的距離保持較大，因此始終被保留,同時每次去除都是一個邊界點。

圖2　測試的數(shù)據(jù)集Fig 2　Test data set

(a) 30 %的點約簡

(b) 50 %的點約簡

(c) 80 %的點約簡圖3　點約簡后的數(shù)據(jù)集Fig 3　Data sets after points reduction

2實驗

1)實驗環(huán)境:本節(jié)實驗結(jié)果運行在以下條件下:Matlab@6.5,3.2 GHz CPU,512M RAM 和Window 7 系統(tǒng)。

2)測試數(shù)據(jù)集:使用UCI數(shù)據(jù)集中 23 個帶有不同特征的數(shù)據(jù)集進行約簡并進行效果分析，23個數(shù)據(jù)集的主要特征如表1所示。這些數(shù)據(jù)集中正確的類標(biāo)號是先驗給出的?？梢杂糜跈z測任何一個測試的分類或聚類算法的正確性和有效性。

3)聚類算法:聚類實施算法是在Weka2.3軟件平臺上完成的。在該平臺上使用經(jīng)典的K均值算法實施聚類，正確的類數(shù)k都是作為先驗的信息預(yù)先輸入。

4)效果評價:這里的正確率是聚類后的標(biāo)號與先驗的標(biāo)號作對比得到的，而約簡后的正確率是根據(jù)最近鄰原則，在約簡后的樣本集中確定好聚類原型后，再將被約簡的樣本按照距離最近的聚類原型賦予類的標(biāo)號。而運行時間是在Matlab中使用“tic”和“toc”兩個函數(shù)統(tǒng)計計算得出的。

表1　23個UCI中測試數(shù)據(jù)集分布

這些選擇的數(shù)據(jù)集都帶有大量噪聲和雜訊，這將嚴(yán)重影響聚類或分類的正確率。本文使用提出的數(shù)據(jù)約簡方法對數(shù)據(jù)集進行約簡，分別在不同的比例下約簡后的數(shù)據(jù)集使用K均值算法進行聚類分析，其正確率如表格3所示。表2顯示:在23個數(shù)據(jù)集中共有20個數(shù)據(jù)集分類的正確率在數(shù)據(jù)約簡后有顯著提高。而正確率未能上升的數(shù)據(jù)集中，實際上，類的形狀分布是任意的，無法用K均值算法正確聚類[13]。

圖4、圖5、分別顯示了數(shù)據(jù)集IRIS約簡過程中的約簡效果，這里,數(shù)據(jù)集的樣本被投影到第1個和第2個維度所組成的二維空間中。圖4為原始的數(shù)據(jù)集，圖5表示30 %,50 %和60 %目標(biāo)被約簡后的數(shù)據(jù)集，圖中實心點表示被保留的點，而空心圓圈表示被約簡的點。

從圖中可以看出，IRIS數(shù)據(jù)集中的原先樣本在這兩個維度上可分性較差，但是在實施數(shù)據(jù)約簡后，類與類之間的距離變大，可分性明顯增加；事實上，在其它特征或特征組合上，這些數(shù)據(jù)集中也有類似的結(jié)論[14]。

表2　23個UCI測試數(shù)據(jù)集約簡聚類效果

但從時間上看，數(shù)據(jù)約簡需要反復(fù)計算各個點的領(lǐng)域，相當(dāng)于在K均值算法中實施了預(yù)處理，若約簡比例超過50 %，總的運算時間可以減少。這是由于K均值算法的計算復(fù)雜度是O(ktn),k是輸入的類數(shù)，t是迭代次數(shù)，而n是總樣本個數(shù)。數(shù)據(jù)約簡實際上減小了樣本數(shù)n，但是增加了預(yù)處理時間并且是逐次進行的。

圖4　Iris數(shù)據(jù)集Fig 4　Data set of Iris

(a) Iris中30 %的點約簡

(b) Iris中50 %的點約簡

(c) Iris中60 %的點約簡圖5　Iris中的點約簡Fig 5　Reduction of points of Iris

3結(jié)論

本文研究了任意數(shù)據(jù)集中基于數(shù)據(jù)個數(shù)的數(shù)據(jù)約簡，分析了不同樣本的分布特征，據(jù)此提出一個具有一般性的新的測度。以K均值算法為例，實驗表明:本文提出測度的效率明顯提高，其中基于部分特征的 K均值算法分類正確率提高26 %～28 %，基于全部樣本的情況下正確率提高 8～12 %,證明本文提出算法是實用和有效的[15]。

本文方法的主要不足在于時間效率的耗費，由于要計算逐對點的距離，因此,數(shù)據(jù)集的約簡時間要高于已有的基于抽樣的方法，為此，進一步的研究需要在保留該算法優(yōu)勢的基礎(chǔ)上改進計算效率。

參考文獻:

[1]葉施仁.海量數(shù)據(jù)約簡與分類研究[D].北京：中國科學(xué)院計算技術(shù)研究所,2001.

[2]Sanguinetti G.Dimensionality reduction of clustered data set-s[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(3):535-540.

[3]Bochanski J J,Hennawi J F,Simcoe R A,et al.MASE:A new data reduction pipeline for the magellan echellette spectro-graph[J].Publications of the Astronomical Society of the Pacific,2009,121(886):1409-1418.

[4]Wacker L,Christl M,Synal H A.Bats:A new tool for AMS data reduction[J].Nuclear Instruments and Methods in Physics Research Section B:Beam Interactions with Materials and Atoms,2010,268(7):976-979.

[5]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[6]Cool R J,Moustakas J,Blanton M R,et al.The prism multi-object survey (PRIMUS).II.data reduction and red-shift fitting[J].The Astrophysical Journal,2013,767(2):118.

[7]BatchelorBG.Patternrecognition:Ideasinpractice[M].NewYork：SpringerScience&BusinessMedia,2012.

[8]黃治國,王端.基于粗糙集的數(shù)據(jù)約簡方法研究[J].計算機工程與設(shè)計,2009 (18):4284-4286.

[9]鄧少波,關(guān)素潔,黎敏,等.屬性與屬性值合一的數(shù)據(jù)約簡算法[J].模式識別與人工智能,2009 (2):195-201.

[10]Machinelearning:Anartificialintelligenceapproach[M].NewYork：SpringerScience&BusinessMedia,2013.

[11] 張學(xué)工.模式識別[M].北京：清華大學(xué)出版社,2010.

[12] 高新波.模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社,2004.

[13] 謝春麗,劉永闊.概念格理論屬性約簡算法研究[J].傳感器與微系統(tǒng),2012,31(3):116-118.

[14]ZhangZ,ZhangJ,XueH.ImprovedK-meansclusteringalgori-thm[C]∥CongressonImageandSignalProcessing,Cherbourg-Octeville,CISP’08,IEEE,2008:169-172.

[15] 李潔,高新波,焦李成.基于特征加權(quán)的模糊聚類新算法[J].電子學(xué)報,2006,34(1):89-92.

Data reduction based on open-angle measurement*

LI Chen， WANG Ya-ru， YUE Shi-hong

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Abstract:Data reduction has been an important issue of data mining including data compression,data adjustment,feature extraction,and so on,however,existing methods of data reduction mainly focus on reduction of features and dimensions,methods of reduction to the number of samples always limit to specific data sets which lack of generality.Aiming at general feature of data distribution in data sets,define a new kind of measurement based on opening angle.This measurement can distinguish essential difference of distribution between kernel objects and boundary objects,and realize data compression which takes kernel objects as center for data sets.By data reduction and test on 20 typical simple sets which have different features on UCI public test platform,the result demonstrates the proposed method can extract kernel objects in data sets effectively; by using the typical k-means algorithm to cluster the data sets before data reduction,cluster accuracy of reduced data sets is apparently higher than that of original data sets.

Key words:data reduction; direction angle; cluster analysis

DOI:10.13873/J.1000—9787(2016)04—0025—04

收稿日期：2015—07—28

*基金項目：國家自然科學(xué)基金資助項目(61174014)

中圖分類號:TP 391.4

文獻標(biāo)識碼:A

文章編號:1000—9787(2016)04—0025—04

作者簡介:

李晨(1991-)，男，山西運城人，碩士研究生，主要研究領(lǐng)域為模式識別。

岳士弘，通訊作者，E-mail:shyue1999@tju.edu.cn。