第3章數(shù)據(jù)預(yù)處理3.1數(shù)據(jù)質(zhì)量3.2數(shù)據(jù)預(yù)處理概述3.3數(shù)據(jù)清洗3.4數(shù)據(jù)集成與轉(zhuǎn)換3.5數(shù)據(jù)約簡(jiǎn)本章小結(jié)

3.1數(shù)據(jù)質(zhì)量

在統(tǒng)計(jì)學(xué)實(shí)驗(yàn)設(shè)計(jì)或調(diào)查中,所收集的數(shù)據(jù)在質(zhì)量上都達(dá)到了一定的要求,其原因有兩點(diǎn):一是數(shù)據(jù)收集的目標(biāo)十分明確,可在源頭上對(duì)數(shù)據(jù)質(zhì)量進(jìn)行有效的控制;二是數(shù)據(jù)規(guī)模小,便于操作與分析。數(shù)據(jù)預(yù)處理技術(shù)涉及兩方面的問(wèn)題:一是數(shù)據(jù)質(zhì)量問(wèn)題的檢測(cè)和糾正;二是使用可以容忍低質(zhì)量數(shù)據(jù)的算法。

3.1.1誤差與噪聲

期望數(shù)據(jù)完美是不現(xiàn)實(shí)的,人為誤差、測(cè)量設(shè)備的局限或數(shù)據(jù)收集過(guò)程的漏洞都可能導(dǎo)致數(shù)據(jù)質(zhì)量低的問(wèn)題。數(shù)據(jù)屬性值乃至整個(gè)數(shù)據(jù)對(duì)象都可能會(huì)丟失。在某些情況下,會(huì)出現(xiàn)不真實(shí)的、重復(fù)的數(shù)據(jù)對(duì)象,即對(duì)應(yīng)于單個(gè)“實(shí)際”對(duì)象出現(xiàn)了多個(gè)數(shù)據(jù)對(duì)象。

1.測(cè)量誤差和數(shù)據(jù)收集錯(cuò)誤

測(cè)量誤差(MeasurementError)是指測(cè)量過(guò)程中出現(xiàn)的數(shù)據(jù)質(zhì)量問(wèn)題。一個(gè)常見(jiàn)的問(wèn)題是在某種程度上記錄值與實(shí)際值不同。對(duì)于連續(xù)屬性,測(cè)量值與實(shí)際值的差稱(chēng)為誤差(Error)。術(shù)語(yǔ)數(shù)據(jù)收集錯(cuò)誤(DataCollectionError)是指諸如遺漏數(shù)據(jù)對(duì)象或?qū)傩灾?或者包含了不恰當(dāng)?shù)钠渌麛?shù)據(jù)對(duì)象等錯(cuò)誤。

測(cè)量誤差和數(shù)據(jù)收集錯(cuò)誤可能是系統(tǒng)性的,也可能是隨機(jī)性的。

2.噪聲和偽像

噪聲是測(cè)量誤差的隨機(jī)部分,涉及數(shù)值的扭曲或噪聲的加入。圖3-1顯示被隨機(jī)噪聲干擾前后的時(shí)間序列,如果在時(shí)間序列上添加更多的噪聲,形狀將會(huì)消失。圖3-1時(shí)間序列數(shù)據(jù)噪聲

“噪聲”通常用于包含時(shí)間或空間分量的數(shù)據(jù)。在這些情況下,常常可以使用信號(hào)或圖像處理技術(shù)降低噪聲,從而幫助發(fā)現(xiàn)可能“淹沒(méi)在噪聲中”的模式(信號(hào))。盡管如此,完全

消除噪聲通常是困難的,而許多數(shù)據(jù)挖掘工作都關(guān)注設(shè)計(jì)魯棒算法(RobustAlgorithm),即在噪聲干擾下也能產(chǎn)生可以接受的結(jié)果。數(shù)據(jù)錯(cuò)誤可能是更確定性現(xiàn)象的結(jié)果,如一組照片在同一地方出現(xiàn)條紋。數(shù)據(jù)的這種確定性失真常稱(chēng)作偽像(Artifact)。

3.精度、偏倚和準(zhǔn)確率

定義3.1(精度,Precision)同一個(gè)量的重復(fù)測(cè)量值之間的接近程度。

定義3.2(偏倚,Bias)測(cè)量值與真實(shí)值之間的偏離。

定義3.3(準(zhǔn)確率,Accuracy)被測(cè)量的測(cè)量值與實(shí)際值之間的接近程度。

4.離群點(diǎn)

離群點(diǎn)(Outlier)是在某種意義上具有不同于數(shù)據(jù)集中其他大部分?jǐn)?shù)據(jù)對(duì)象的數(shù)據(jù)對(duì)象,或是相對(duì)于該屬性的典型值來(lái)說(shuō)不尋常的屬性值,也稱(chēng)之為異常對(duì)象或異常值(Anomaly)。有許多定義離群點(diǎn)的方法,并且統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘領(lǐng)域已經(jīng)提出了很多不同的定義。此外,區(qū)別噪聲和離群點(diǎn)這兩個(gè)概念是非常重要的。需要指出的是,離群點(diǎn)可以是合法的數(shù)據(jù)對(duì)象或值。因此,不同于噪聲,離群點(diǎn)是人們感興趣的對(duì)象。

5.缺失值

數(shù)據(jù)對(duì)象遺漏一個(gè)或多個(gè)屬性值的情況并不少見(jiàn),導(dǎo)致信息收集不全,例如有的人拒絕透露年齡或體重。

針對(duì)數(shù)據(jù)值缺失的問(wèn)題,現(xiàn)有許多處理策略,每種策略可能適用于特定的情況,典型的方法包括以下兩種:

(1)刪除策略。

(2)估計(jì)缺失值。

6.不一致的值

數(shù)據(jù)可能包含不一致的值。比如地址字段列出了郵政編碼和城市名,但是有的郵政編碼所對(duì)應(yīng)的城市并不包含在對(duì)應(yīng)的城市中?？赡苁侨斯ぽ斎朐撔畔r(shí)顛倒了兩個(gè)數(shù)字,或是在手寫(xiě)體掃描時(shí)錯(cuò)讀了一個(gè)數(shù)字。無(wú)論導(dǎo)致不一致值的原因是什么,重要的是能檢測(cè)出來(lái),并且如果可能的話,糾正這種錯(cuò)誤。

檢測(cè)到不一致后,有時(shí)可以對(duì)數(shù)據(jù)進(jìn)行更正。產(chǎn)品代碼可能有“校驗(yàn)”數(shù)字,或者可以通過(guò)一個(gè)備案的已知產(chǎn)品代碼列表,復(fù)核產(chǎn)品代碼。如果發(fā)現(xiàn)它不正確但接近一個(gè)已知代碼,則糾正它。糾正不一致,需要額外的或冗余的信息。

7.重復(fù)數(shù)據(jù)

數(shù)據(jù)可能包含重復(fù)或近似重復(fù)的數(shù)據(jù)對(duì)象,例如,許多人都收到過(guò)重復(fù)的郵件。為了檢測(cè)并刪除這種重復(fù),必須處理兩種情況:一是如果兩個(gè)對(duì)象實(shí)際代表同一個(gè)對(duì)象,則對(duì)

應(yīng)的屬性值不同,必須解決這些不一致的值;二是需要避免意外地將兩個(gè)相似但并非重復(fù)的數(shù)據(jù)對(duì)象(如兩個(gè)人具有相同的姓名)合并在一起。去重復(fù)(Deduplication)通常用來(lái)表示

處理這些問(wèn)題的過(guò)程,在某些情況下,兩個(gè)或多個(gè)對(duì)象在數(shù)據(jù)庫(kù)的屬性度量上是相同的,但是仍然代表不同的對(duì)象。這種重復(fù)是合法的。但是如果某些算法設(shè)計(jì)中沒(méi)有專(zhuān)門(mén)考慮這

些屬性可能相同的對(duì)象,可能還會(huì)導(dǎo)致問(wèn)題。

3.1.2應(yīng)用問(wèn)題

數(shù)據(jù)質(zhì)量問(wèn)題也可以從應(yīng)用角度考慮。特別是對(duì)工業(yè)、商業(yè)等領(lǐng)域,數(shù)據(jù)質(zhì)量是至關(guān)重要的,甚至影響到整個(gè)市場(chǎng)的走勢(shì)。類(lèi)似的觀點(diǎn)也出現(xiàn)在統(tǒng)計(jì)學(xué)和實(shí)驗(yàn)科學(xué)中,它們強(qiáng)調(diào)精心設(shè)計(jì)實(shí)驗(yàn)來(lái)收集與特定假設(shè)相關(guān)的數(shù)據(jù),這與測(cè)量和收集數(shù)據(jù)一樣。許多數(shù)據(jù)質(zhì)量問(wèn)題與特定的應(yīng)用和領(lǐng)域有關(guān),這里仍然只考慮一些一般性問(wèn)題。需要指出的是,在特定條件下,數(shù)據(jù)的時(shí)效性也極為重要,有些數(shù)據(jù)收集后就開(kāi)始老化,例如顧客的購(gòu)買(mǎi)行為或Web瀏覽模式,而快照只代表有限時(shí)間內(nèi)的真實(shí)情況。

3.2數(shù)據(jù)預(yù)處理概述

數(shù)據(jù)預(yù)處理是數(shù)據(jù)挖掘(知識(shí)發(fā)現(xiàn))過(guò)程中的一個(gè)重要步驟,尤其是在對(duì)包含有噪聲、不完整、不一致數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘時(shí),更需要進(jìn)行數(shù)據(jù)預(yù)處理,以提高數(shù)據(jù)挖掘?qū)ο蟮馁|(zhì)量,并最終達(dá)到提高數(shù)據(jù)挖掘質(zhì)量的目的。

典型的數(shù)據(jù)預(yù)處理技術(shù)包括數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)約簡(jiǎn)等。

(1)數(shù)據(jù)清洗(DataCleaning):主要處理數(shù)據(jù)缺失、噪聲、異常點(diǎn)問(wèn)題,通過(guò)計(jì)算與分析手段填補(bǔ)遺漏的數(shù)據(jù)值、平滑有噪聲數(shù)據(jù)、識(shí)別或除去異常值(Outlier),以及解決不一致問(wèn)題。

(2)數(shù)據(jù)集成(DataIntegration):旨在將多源(如數(shù)據(jù)庫(kù)、文件等)數(shù)據(jù)進(jìn)行合并。由于描述同一個(gè)概念的屬性在不同數(shù)據(jù)庫(kù)取不同的名字,在進(jìn)行數(shù)據(jù)集成時(shí)就常常會(huì)引起數(shù)據(jù)的不一致或冗余。

(3)數(shù)據(jù)轉(zhuǎn)換(DataTransformation):對(duì)數(shù)據(jù)進(jìn)行規(guī)范化(Normalization)操作,以滿(mǎn)足數(shù)據(jù)挖掘下游分析的需求。在正式進(jìn)行數(shù)據(jù)挖掘之前,尤其是使用基于對(duì)象距離(Distance-Based)的挖掘算法時(shí),比如神經(jīng)網(wǎng)絡(luò)、K最近鄰分類(lèi)(NearestNeighborClassifier)等,必須進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化,即將其縮至特定的范圍之內(nèi),如[0,1]。

(4)數(shù)據(jù)約簡(jiǎn)(DataReduction):在不影響挖掘結(jié)果的前提下縮小所挖掘數(shù)據(jù)規(guī)模的操作/過(guò)程。當(dāng)然,完全不影響挖掘結(jié)果是不可能的,所以數(shù)據(jù)約簡(jiǎn)的目標(biāo)是盡可能減少信

息的丟失?，F(xiàn)有的數(shù)據(jù)約簡(jiǎn)包括:

①數(shù)據(jù)聚合(DataAggregation),如構(gòu)造數(shù)據(jù)立方(Cube);

②維數(shù)約簡(jiǎn)(DimensionReduction),如通過(guò)相關(guān)分析消除多余屬性;

③數(shù)據(jù)壓縮(DataRompression),如利用編碼方法(最小編碼長(zhǎng)度或小波等);

④數(shù)據(jù)塊約簡(jiǎn)

(NumerosityReduction),如利用聚類(lèi)或參數(shù)模型替代原有數(shù)據(jù)。

這里需要強(qiáng)調(diào)的是,以上所提及的各種數(shù)據(jù)預(yù)處理方法并不是相互獨(dú)立的,而是相互關(guān)聯(lián)的。例如,消除數(shù)據(jù)冗余既可以看成是一種數(shù)據(jù)清洗,也可以認(rèn)為是一種數(shù)據(jù)約簡(jiǎn)。由于現(xiàn)實(shí)世界中的數(shù)據(jù)常常是含有噪聲的、不完全的和不一致的,數(shù)據(jù)預(yù)處理能夠幫助改善數(shù)據(jù)的質(zhì)量,進(jìn)而幫助提高數(shù)據(jù)挖掘進(jìn)程的有效性和準(zhǔn)確性。高質(zhì)量的決策來(lái)自高質(zhì)量的數(shù)據(jù)。因此,數(shù)據(jù)預(yù)處理是整個(gè)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)過(guò)程中的一個(gè)重要步驟。

3.3-數(shù)據(jù)清洗

數(shù)據(jù)清洗旨在通過(guò)填補(bǔ)缺失數(shù)據(jù)、消除異常數(shù)據(jù)、平滑噪聲數(shù)據(jù),以糾正不一致的數(shù)據(jù)。

3.3.1缺失數(shù)據(jù)處理

假設(shè)在分析一個(gè)商場(chǎng)銷(xiāo)售數(shù)據(jù)時(shí),發(fā)現(xiàn)有多個(gè)記錄中的屬性值為空(如顧客的收入屬性),對(duì)于為空的屬性值,可以采用以下方法進(jìn)行缺失數(shù)據(jù)(MissingData)處理。

(1)忽略該條記錄。

(2)手工填補(bǔ)缺失值。

(3)利用缺省值填補(bǔ)缺失值。

(4)利用均值填補(bǔ)缺失值。

(5)利用同類(lèi)別均值填補(bǔ)缺失值。

(6)利用預(yù)估值填補(bǔ)缺失值。

3.3.2噪聲數(shù)據(jù)處理

噪聲是指被測(cè)變量的一個(gè)隨機(jī)錯(cuò)誤和變化,常用的去噪方法有以下四種:

(1)桶平滑方法(Bin方法)。該方法利用周?chē)c(diǎn)(近鄰)對(duì)數(shù)據(jù)進(jìn)行去噪處理,首先對(duì)一組數(shù)據(jù)進(jìn)行排序,排序后將數(shù)據(jù)分配到若干桶。例如,首先對(duì)商品價(jià)格數(shù)據(jù)進(jìn)行排序,然后將其劃分為若干等高度的桶(兩種典型桶平滑方法示意描述如圖3-2所示)。圖3-2兩種典型桶平滑方法

(2)聚類(lèi)方法。通過(guò)聚類(lèi)分析可幫助發(fā)現(xiàn)異常數(shù)據(jù)(Outliers),如圖3-3所示。圖3-3-基于聚類(lèi)分析的異常數(shù)據(jù)監(jiān)測(cè)

(3)人機(jī)結(jié)合檢查方法。通過(guò)人與計(jì)算機(jī)檢查相結(jié)合的方法,可以幫助發(fā)現(xiàn)異常數(shù)據(jù)。

(4)回歸方法。可以利用擬合函數(shù)對(duì)數(shù)據(jù)進(jìn)行平滑。許多數(shù)據(jù)平滑方法,同時(shí)也是數(shù)據(jù)約簡(jiǎn)方法。

3.3.3-不一致數(shù)據(jù)處理

現(xiàn)實(shí)世界的數(shù)據(jù)庫(kù)中常出現(xiàn)數(shù)據(jù)記錄內(nèi)容不一致的情況,其中一些數(shù)據(jù)可以利用它們與外部的關(guān)聯(lián)手工加以解決。例如,數(shù)據(jù)錄入錯(cuò)誤一般可以通過(guò)與原稿進(jìn)行對(duì)比來(lái)加以糾正。此外,還有一些例程可以幫助糾正使用編碼時(shí)所發(fā)生的不一致問(wèn)題。知識(shí)工程工具也可以幫助發(fā)現(xiàn)違反數(shù)據(jù)約束條件的情況。由于同一屬性在不同數(shù)據(jù)庫(kù)中的取名不規(guī)范,使得在進(jìn)行數(shù)據(jù)集成時(shí),不一致的情況時(shí)有發(fā)生。

3.4數(shù)據(jù)集成與轉(zhuǎn)換

數(shù)據(jù)挖掘任務(wù)常常涉及數(shù)據(jù)集成操作,即將來(lái)自多個(gè)數(shù)據(jù)源(如數(shù)據(jù)庫(kù)、數(shù)據(jù)立方(DataCubic)、普通文件等)的數(shù)據(jù)結(jié)合在一起并形成一個(gè)統(tǒng)一的數(shù)據(jù)集合,以便為數(shù)據(jù)挖掘工作的順利完成提供完整的數(shù)據(jù)基礎(chǔ)。

3.4.1數(shù)據(jù)集成處理

在數(shù)據(jù)集成過(guò)程中,需要考慮解決以下幾個(gè)問(wèn)題:

(1)模式集成(SchemaIntegration)問(wèn)題,即如何使來(lái)自多個(gè)數(shù)據(jù)源的實(shí)體相互匹配,涉及實(shí)體識(shí)別問(wèn)題(EntityIdentificationProblem)。

(2)數(shù)據(jù)冗余問(wèn)題(Redundancy),是指相似的數(shù)據(jù)或者特征重復(fù)出現(xiàn)的現(xiàn)象,這是數(shù)據(jù)集成中經(jīng)常發(fā)生的另一個(gè)問(wèn)題。若一個(gè)屬性完全可以從其他屬性中推演出來(lái),那這個(gè)屬性就是冗余屬性。

利用相關(guān)分析可以幫助發(fā)現(xiàn)一些數(shù)據(jù)冗余情況。例如,給定兩個(gè)屬性A、B,則根據(jù)這兩個(gè)屬性的數(shù)值,可以分析出這兩個(gè)屬性間的相互關(guān)系:

(3)數(shù)值沖突檢測(cè)與消除。對(duì)于一個(gè)現(xiàn)實(shí)世界實(shí)體,其來(lái)自不同數(shù)據(jù)源的屬性值或許不同,產(chǎn)生這樣問(wèn)題的原因可能是表示的差異、比例尺度的不同或編碼的差異等。

3.4.2數(shù)據(jù)轉(zhuǎn)換處理

數(shù)據(jù)轉(zhuǎn)換就是將數(shù)據(jù)轉(zhuǎn)換或歸并,使得其描述形式適合數(shù)據(jù)挖掘的要求。數(shù)據(jù)轉(zhuǎn)換包含以下處理內(nèi)容:

(1)平滑處理,用以幫助除去數(shù)據(jù)中的噪聲,主要技術(shù)方法有桶平滑方法、聚類(lèi)方法和回歸方法等。

(2)歸并處理,即對(duì)數(shù)據(jù)進(jìn)行總結(jié)或合計(jì)操作。

(3)數(shù)據(jù)泛化處理,即用更抽象(更高層次)的概念來(lái)取代低層次或數(shù)據(jù)層的數(shù)據(jù)對(duì)象。

(4)標(biāo)準(zhǔn)化,即將有關(guān)屬性數(shù)據(jù)按比例投射到特定范圍之中。

對(duì)于基于距離計(jì)算的挖掘,標(biāo)準(zhǔn)化方法可以幫助消除因?qū)傩匀≈捣秶煌绊懲诰蚪Y(jié)果的公正性。下面介紹三種標(biāo)準(zhǔn)化方法。

①最大最小標(biāo)準(zhǔn)化方法。該方法對(duì)初始數(shù)據(jù)進(jìn)行一種線性轉(zhuǎn)換。設(shè)minA和maxA為屬性A的最小值和最大值,最大最小標(biāo)準(zhǔn)化方法將屬性A的一個(gè)值v映射為v',且有v'∈[new_minA,new_maxA]。具體映射計(jì)算公式為

例3.1假設(shè)收入屬性的最小、最大值分別是12000元和98000元,若要利用最大最小標(biāo)準(zhǔn)化方法將屬性收入的值映射到0~1的范圍內(nèi),則收入73600元將被轉(zhuǎn)化為

②零均值標(biāo)準(zhǔn)化方法。該方法是根據(jù)屬性A的均值和偏差來(lái)對(duì)A進(jìn)行標(biāo)準(zhǔn)化。屬性A的v值可以通過(guò)以下計(jì)算公式獲得其映射值:

例3.2假設(shè)屬性收入的均值與方差分別為54000元和16000元,使用零均值標(biāo)準(zhǔn)化方法將73600元的屬性收入值映射為

③十基數(shù)變換標(biāo)準(zhǔn)化方法。該方法通過(guò)移動(dòng)屬性A值的小數(shù)位置來(lái)達(dá)到標(biāo)準(zhǔn)化的目的。所移動(dòng)的小數(shù)位數(shù)取決于屬性A絕對(duì)值的最大值。屬性A的v值可以通過(guò)以下計(jì)算

公式計(jì)算新值v':

3.4.3-離散化和二進(jìn)制化

1.特征賦權(quán)的原因

在數(shù)據(jù)挖掘算法中,尤其是分類(lèi)算法中,對(duì)于數(shù)據(jù)類(lèi)別屬性(CategoricalAttributes)是有具體的格式要求的。同樣的,關(guān)聯(lián)規(guī)則挖掘算法對(duì)交易事務(wù)數(shù)據(jù)的要求是二進(jìn)制形式(BinaryAttributes)。因此,常常需要將連續(xù)屬性ContinuousAttributes)轉(zhuǎn)變成類(lèi)別屬性(CategoricalAttributes),即離散化(Discretization)。而連續(xù)屬性或者類(lèi)別屬性則可能需要進(jìn)行二進(jìn)制化。此外,如果類(lèi)別屬性有太多的值,或者當(dāng)一些值出現(xiàn)的頻率很小時(shí),需要?dú)w并一些值以減少類(lèi)別的數(shù)目。

2.典型方法

(1)二進(jìn)制(Binarization)。一個(gè)簡(jiǎn)單的二進(jìn)制例子是:如果類(lèi)別有m個(gè)值,給每個(gè)原始的值賦予唯一的整數(shù),其值域是{0,1,…,m-1}。如果屬性是順序的,則賦值也是順序的。需要注意的是,即便原始屬性值是整數(shù)類(lèi)型的,這一步也是必需的,因?yàn)樵嫉膶傩灾悼赡懿辉趝0,1,…,m-1}集合中。下一步是將每個(gè)整數(shù)轉(zhuǎn)化成二進(jìn)制形式。由于n=lb(m)個(gè)二進(jìn)位制可以代表這些整數(shù),因此表示這些數(shù)據(jù)需要有n位二進(jìn)制字符長(zhǎng)度,如表3-1所示。

但是,這種轉(zhuǎn)變會(huì)帶來(lái)復(fù)雜性。如屬性x2和x3-會(huì)產(chǎn)生聯(lián)系,因?yàn)镚ood這個(gè)屬性的編碼同時(shí)用到了這兩個(gè)屬性。此外,關(guān)聯(lián)分析需要非對(duì)稱(chēng)的二進(jìn)制屬性,只有那些值為1的屬性

才是重要的。因此,對(duì)于關(guān)聯(lián)問(wèn)題,有必要給每個(gè)類(lèi)別值引入一個(gè)二進(jìn)制屬性,如表3-2所示。

(2)連續(xù)屬性離散化(DiscretizationofContinuousAttributes)。離散化通常在分類(lèi)和關(guān)聯(lián)分析中使用。一般情況下,最好的離散化依賴(lài)于使用的算法,也要考慮到其他屬性。然而,一個(gè)屬性的離散化通常是單獨(dú)考慮的。連續(xù)屬性轉(zhuǎn)變成類(lèi)別屬性通常涉及兩個(gè)子任務(wù),一是如何確定類(lèi)別數(shù)量,二是如何確定映射關(guān)系,即第一步通過(guò)指定n-1個(gè)分割點(diǎn)(SplitPoints)將原來(lái)的值域分割成n個(gè)區(qū)間,第二步將位于同一區(qū)間內(nèi)的值映射到相同的類(lèi)別值上。因此,離散化的問(wèn)題主要是確定選擇多少個(gè)分割點(diǎn)并在哪里分割,其結(jié)果可以表示成一個(gè)區(qū)間的集合{(x0,x1],(x1,x2],…,(xn-1,xn)},其中x0和xn可能分別代表-∞或者+∞,且x0<x≤x1,…,xn-1<x<xn,如圖3-4所示。圖3-4離散化示意圖

(3)非監(jiān)督離散化(UnsupervisedDiscretization)。分類(lèi)問(wèn)題中離散化方法有可能使用類(lèi)別信息,使用了類(lèi)別信息的方法稱(chēng)之為監(jiān)督式(Supervised)離散化方法,沒(méi)有使用類(lèi)別信息的方法稱(chēng)之為非監(jiān)督(Unsupervised)離散化方法。典型的非監(jiān)督離散化方法包括等寬法(EqualWidth)與等頻法(EqualFrequency),其中等寬法將范圍內(nèi)的屬性劃分成一個(gè)用

戶(hù)指定的區(qū)間數(shù)量,每個(gè)區(qū)間都有相同的寬度(Width),這類(lèi)方法的缺陷是受離群值影響很大。等頻法是將相同數(shù)量的對(duì)象分到每個(gè)區(qū)間中。

(4)監(jiān)督式離散化(SupervisedDiscretization)。使用額外信息(如類(lèi)標(biāo)簽)通常會(huì)產(chǎn)生更好的結(jié)果,而離散化所構(gòu)造的區(qū)間通常會(huì)包含類(lèi)別與非類(lèi)別標(biāo)簽。

(5)極端情況。有太多值的類(lèi)別屬性(CategoricalAttributeswithTooManyValues)

有時(shí)會(huì)產(chǎn)生很多極端情況。如果類(lèi)別屬性是順序的,則可以利用類(lèi)似連續(xù)屬性離散化的方法;如果類(lèi)別屬性是分類(lèi)的,則要利用一些領(lǐng)域知識(shí)。

3.5數(shù)據(jù)約簡(jiǎn)

對(duì)大規(guī)模的數(shù)據(jù)庫(kù)內(nèi)容進(jìn)行復(fù)雜的數(shù)據(jù)分析通常需要耗費(fèi)大量時(shí)間,這使得大數(shù)據(jù)挖掘通常變得不現(xiàn)實(shí)和不可行。解決這些問(wèn)題通常有兩類(lèi)方法:一是在不改變數(shù)據(jù)的條件下通過(guò)并行處理技術(shù)提高計(jì)算效率,例如Hadoop平臺(tái)等;二是通過(guò)算法在盡量保持?jǐn)?shù)據(jù)信息不變的條件下降低數(shù)據(jù)規(guī)模。

數(shù)據(jù)約簡(jiǎn)的主要策略包括:

①數(shù)據(jù)立方歸并(Aggregation),這類(lèi)合計(jì)操作主要用于

構(gòu)造數(shù)據(jù)立方;

②維數(shù)約簡(jiǎn),主要用于檢測(cè)和消除無(wú)關(guān)或冗余的屬性;

③數(shù)據(jù)壓縮,利用編碼技術(shù)壓縮數(shù)據(jù)集的規(guī)模大小;

④數(shù)據(jù)塊約簡(jiǎn),利用更簡(jiǎn)單的數(shù)據(jù)表達(dá)形式,如參數(shù)模

型、非參數(shù)模型(聚類(lèi)、采樣、直方圖等),來(lái)取代原有的數(shù)據(jù)。

3.5.1數(shù)據(jù)立方歸并

圖3-5是對(duì)某公司三年銷(xiāo)售額進(jìn)行歸并處理的示意圖,其特點(diǎn)是針對(duì)單個(gè)維度進(jìn)行歸并。實(shí)際上,通過(guò)需要?dú)w并的維度遠(yuǎn)遠(yuǎn)超過(guò)一個(gè)維度。圖3-6是一個(gè)三維數(shù)據(jù)立方從時(shí)間(年代)、公司分支和商品類(lèi)型三個(gè)角度(維度)描述相應(yīng)(時(shí)空)的銷(xiāo)售額(對(duì)應(yīng)一個(gè)小立方塊)。每個(gè)屬性都可對(duì)應(yīng)一個(gè)概念層次樹(shù),以幫助進(jìn)行多抽象層次的數(shù)據(jù)分析。圖3-5數(shù)據(jù)合計(jì)描述示意圖圖3-6數(shù)據(jù)立方合計(jì)描述示意圖

3.5.2維數(shù)約簡(jiǎn)

維數(shù)約簡(jiǎn)可通過(guò)計(jì)算消除多余和無(wú)關(guān)屬性,從而有效地降低數(shù)據(jù)屬性的規(guī)模。屬性子集選擇方法(AttributeSubsetSelection)是在確保新數(shù)據(jù)子集概率分布盡可能接近原始數(shù)據(jù)集概率分布的前提下,尋找出最小的屬性子集,再利用篩選后的屬性集進(jìn)行數(shù)據(jù)挖掘與下游分析。由于使用了屬性子集,從而使得用戶(hù)更加容易理解挖掘結(jié)果。

從原始數(shù)據(jù)的屬性集中提取最優(yōu)屬性子集是一個(gè)枚舉搜索的過(guò)程,但是枚舉方式最大的困難在于搜索空間的大小。

一般利用統(tǒng)計(jì)重要性的測(cè)試來(lái)幫助選擇“最優(yōu)”或“最差”屬性,這里假設(shè)各屬性之間是相互獨(dú)立的。此外,還有許多評(píng)估屬性的方法,如用于構(gòu)造決策樹(shù)的信息增益方法。構(gòu)造屬性子集的基本啟發(fā)式方法有以下幾種:

(1)逐步添加。

(2)逐步約簡(jiǎn)。

(3)約簡(jiǎn)與添加相結(jié)合。

(4)決策樹(shù)歸納。

3.5.3-數(shù)據(jù)壓縮

數(shù)據(jù)壓縮就是利用數(shù)據(jù)編碼或數(shù)據(jù)轉(zhuǎn)換等方式將原始數(shù)據(jù)進(jìn)行壓縮。如果利用壓縮后的數(shù)據(jù)可以完全恢復(fù)原始數(shù)據(jù),稱(chēng)之為無(wú)損壓縮,否則就稱(chēng)為有損壓縮。由于無(wú)損壓縮的壓縮比例相對(duì)較低,因此在數(shù)據(jù)挖掘領(lǐng)域通常使用有損壓縮,典型的有損數(shù)據(jù)壓縮方法是小波變換(WaveletTransforms)和主成分分析(PrincipalComponentsAnalysis,PCA)。

1.小波變換

離散小波變換是一種線性信號(hào)處理技術(shù),其將一個(gè)數(shù)據(jù)向量D轉(zhuǎn)換為另一個(gè)數(shù)據(jù)向量D',且兩個(gè)向量具有相同長(zhǎng)度。但是對(duì)后者而言,可以舍棄一些小波相關(guān)系數(shù),僅保留所有大于用戶(hù)指定閾值的小波系數(shù),而將其他小波系數(shù)置為0,以幫助提高數(shù)據(jù)處理的運(yùn)算效率。

離散小波變換與離散傅里葉變換相近,后者也是信號(hào)處理的關(guān)鍵技術(shù)之一。一般來(lái)說(shuō),離散小波變換具有更好的有損壓縮性能。也就是說(shuō),給定同一組數(shù)據(jù)向量(相關(guān)系數(shù)),利用離散小波變換所獲得的數(shù)據(jù)比利用離散傅里葉變換所獲得的數(shù)據(jù)更接近原始數(shù)據(jù)。

應(yīng)用離散小波變換進(jìn)行數(shù)據(jù)轉(zhuǎn)換時(shí),通常采用通用層次算法,其中每次循環(huán)將要處理的數(shù)據(jù)一分為二進(jìn)行處理,以獲得更快的運(yùn)算性能。

其主要步驟說(shuō)明如下:

(1)L為所輸入數(shù)據(jù)向量的長(zhǎng)度(2次方),必要時(shí),需用0補(bǔ)齊數(shù)據(jù)向量以確保向量長(zhǎng)度滿(mǎn)足要求。

(2)設(shè)計(jì)兩個(gè)函數(shù),其中一個(gè)負(fù)責(zé)進(jìn)行初步的數(shù)據(jù)平滑,而另外一個(gè)負(fù)責(zé)完成差值計(jì)算以獲得數(shù)據(jù)的主要特征。

(3)將數(shù)據(jù)向量一分為二,分別代表輸入數(shù)據(jù)的低頻部分和輸入數(shù)據(jù)的高頻部分,然后采用步驟(2)中兩個(gè)函數(shù)分別對(duì)兩部分?jǐn)?shù)據(jù)進(jìn)行處理。

(4)對(duì)所輸入的數(shù)據(jù)向量循環(huán)使用(3)中的處理步驟,直到所有劃分的子數(shù)據(jù)向量的長(zhǎng)度均為2為止。

(5)提出步驟(3)與(4)的結(jié)果即為小波相關(guān)系數(shù)。

2.主成分分析

主成分分析方法的主要處理步驟如下:

(1)對(duì)輸入數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化,以確保各屬性取值均落入相同的數(shù)值范圍。

(2)根據(jù)已標(biāo)準(zhǔn)化的數(shù)據(jù)計(jì)算c個(gè)向量,其中所輸入數(shù)據(jù)均可以表示為這c個(gè)向量的線性組合。

(3)對(duì)c個(gè)主要向量按其重要性(計(jì)算所得變化量)進(jìn)行遞減排序。

(4)根據(jù)所給定的用戶(hù)閾值,消去重要性較低的向量,以便最終獲得約簡(jiǎn)后的數(shù)據(jù)集合。

此外,利用最主要的主要素也可以較好地近似恢復(fù)原來(lái)的數(shù)據(jù)。

3.5.4數(shù)據(jù)塊約簡(jiǎn)

數(shù)據(jù)塊約簡(jiǎn)主要包含參數(shù)與非參數(shù)兩種基本方法,其中參數(shù)方法利用數(shù)學(xué)模型來(lái)幫助通過(guò)計(jì)算獲得原來(lái)的數(shù)據(jù),只需要存儲(chǔ)模型的參數(shù)即可(當(dāng)然,異常數(shù)據(jù)也需要存儲(chǔ))。

1.回歸與線性對(duì)數(shù)模型

回歸與線性對(duì)數(shù)模型可對(duì)給定數(shù)據(jù)進(jìn)行擬合,線性回歸方法是利用直線對(duì)數(shù)據(jù)進(jìn)行擬合。例如,利用自變量X的一個(gè)線性函數(shù)可以擬合因變量Y的輸出,其線性函數(shù)模型為

2.直方圖

直方圖是利用插值方法對(duì)數(shù)據(jù)分布情況進(jìn)行近似,一個(gè)屬性A的直方圖就是根據(jù)屬性的數(shù)據(jù)分布將其劃分為若干不相交的子集(稱(chēng)之為桶,Bucket)。這些子集沿水平軸顯示,

其高度(或面積)與該桶中數(shù)據(jù)的平均(出現(xiàn))頻率成正比。通常,桶代表某個(gè)屬性的一段連續(xù)值,若桶中僅代表一個(gè)屬性值或頻率,則這一桶就稱(chēng)為單桶。

例3.3-以下是一個(gè)商場(chǎng)所銷(xiāo)售商品的價(jià)格清單(按遞增順序排列,括號(hào)中的數(shù)表示前面數(shù)字出現(xiàn)的次數(shù)):1(2),5(5),8(2),10(4),12(1),14(3),15(5),18(8),20(7),21(4),

25(5),28(2),30(3),上述數(shù)據(jù)所形成的屬性值/頻率對(duì)的直方圖如圖3-7所示。圖3-7數(shù)據(jù)直方圖描述示意圖

構(gòu)造直方圖所涉及的數(shù)據(jù)集劃分方法有:

(1)等寬方法:在一個(gè)等寬的直方圖中,每個(gè)桶的寬度(范圍)是相同的(如圖3-7所示)。

(2)等高方法:在一個(gè)等高的直方圖中,每個(gè)桶中的數(shù)據(jù)個(gè)數(shù)是相同的。

(3)V最優(yōu)直方圖方法:若對(duì)指定桶個(gè)數(shù)的所有可能直方圖進(jìn)行考慮,該方法所獲得的直方圖在這些直方圖中的變化最小。

(4)最大差異測(cè)量法:即讓受訪者從一組對(duì)象中指出能表明最大差異偏好的對(duì)象。例如,在幾個(gè)對(duì)象中指出“最好的”和“最差的”。

3.聚類(lèi)

聚類(lèi)技術(shù)將數(shù)據(jù)對(duì)象進(jìn)行分組,使得隸屬于同一組的數(shù)據(jù)對(duì)象具有以下性質(zhì):同一組或類(lèi)中的對(duì)象彼此相似,而不同組或類(lèi)中