基于張開(kāi)角測(cè)度的數(shù)據(jù)約簡(jiǎn)*

李　晨， 王亞茹， 岳士弘

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

基于張開(kāi)角測(cè)度的數(shù)據(jù)約簡(jiǎn)*

李晨， 王亞茹， 岳士弘

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

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

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

0引言

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

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

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

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

1基于張開(kāi)角測(cè)度的數(shù)據(jù)約簡(jiǎn)

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

圖1　一個(gè)類中不同點(diǎn)的分布與張開(kāi)角Fig 1　Distribution and open-angle of different points in a class

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

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

i=1,…,n

(1)

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

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

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

3)記X=X1∪X2;

4)開(kāi)始

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

5)重復(fù)

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

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

7)根據(jù)張開(kāi)角排序所有X中的點(diǎn);

8)去除張開(kāi)角最小的向量;

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

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

11)返回步驟(7);

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

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

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

(a) 30 %的點(diǎn)約簡(jiǎn)

(b) 50 %的點(diǎn)約簡(jiǎn)

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

2實(shí)驗(yàn)

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

2)測(cè)試數(shù)據(jù)集:使用UCI數(shù)據(jù)集中 23 個(gè)帶有不同特征的數(shù)據(jù)集進(jìn)行約簡(jiǎn)并進(jìn)行效果分析，23個(gè)數(shù)據(jù)集的主要特征如表1所示。這些數(shù)據(jù)集中正確的類標(biāo)號(hào)是先驗(yàn)給出的。可以用于檢測(cè)任何一個(gè)測(cè)試的分類或聚類算法的正確性和有效性。

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

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

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

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

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

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

表2　23個(gè)UCI測(cè)試數(shù)據(jù)集約簡(jiǎn)聚類效果

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

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

(a) Iris中30 %的點(diǎn)約簡(jiǎn)

(b) Iris中50 %的點(diǎn)約簡(jiǎn)

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

3結(jié)論

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

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

參考文獻(xiàn):

[1]葉施仁.海量數(shù)據(jù)約簡(jiǎn)與分類研究[D].北京：中國(guó)科學(xué)院計(jì)算技術(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]黃治國(guó),王端.基于粗糙集的數(shù)據(jù)約簡(jiǎn)方法研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009 (18):4284-4286.

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

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

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

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

[13] 謝春麗,劉永闊.概念格理論屬性約簡(jiǎn)算法研究[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é)報(bào),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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61174014)

中圖分類號(hào):TP 391.4

文獻(xiàn)標(biāo)識(shí)碼:A

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

作者簡(jiǎn)介:

李晨(1991-)，男，山西運(yùn)城人，碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別。

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