第三章數(shù)據(jù)歸約本章目標(biāo)明確基于特征、案例維歸約與技術(shù)歸約的區(qū)別。解釋數(shù)據(jù)挖掘過程的預(yù)處理階段中進(jìn)行數(shù)據(jù)歸約的優(yōu)點(diǎn)應(yīng)用相應(yīng)的統(tǒng)計(jì)方法，理解特征選擇和特征構(gòu)成的基本原則。理解特征等級主成分分析方法。區(qū)別基于增量和平均樣本的案例中的技術(shù)。對數(shù)據(jù)描述，特征的挑選、歸約或轉(zhuǎn)換可能是決定挖掘方案質(zhì)量的最重要的問題。除了影響到數(shù)據(jù)挖掘算法的屬性，它也能決定問題量否可解，或所得到的挖掘模型有多強(qiáng)大。為什么要數(shù)據(jù)歸約：

1.一旦特征數(shù)量達(dá)到數(shù)百，而只有上百條樣本用于分析時，對挖掘是相對不夠的。

2.由高維度引起的數(shù)據(jù)超負(fù)，使一些挖掘算法不適用。3.1大型數(shù)據(jù)集的維度預(yù)處理數(shù)據(jù)集的三個主要維度：列（特征），行（案例或樣本）和特征的值。它們以平面文件的形式出現(xiàn)。數(shù)據(jù)歸約過程３個基本操作：刪除列、刪除行、減少列中值的數(shù)量（平整特征）。例如：用分箱方法減少值的數(shù)量，用特征合并代替原來特征（身體素質(zhì)指標(biāo)代替人的身高和體重特征）數(shù)據(jù)歸約的約定是不要降低結(jié)果的質(zhì)量。在數(shù)據(jù)歸約操作時的目標(biāo)過程：1.計(jì)算時間：較簡單的數(shù)據(jù)，也即經(jīng)過數(shù)據(jù)歸約后的結(jié)果，可減少挖掘所消耗的時間。2.預(yù)測／描述精度：多數(shù)挖掘模型的主要度量標(biāo)準(zhǔn)，它估量了數(shù)據(jù)歸納和慨括為模型的好壞。3.數(shù)據(jù)挖掘模型的描述：簡單的描述通常來自數(shù)據(jù)歸約，意味著模型能得到更好的理解。理想的情況是維歸約后既能減少時間，又能同時提高精度和簡化描述。數(shù)據(jù)歸約算法的特征：1.可測性：已歸約的數(shù)據(jù)集可精確確定近似結(jié)果的質(zhì)量。2.可識別性：挖掘前能執(zhí)行歸約算法時能確定近似結(jié)果的質(zhì)量。3.單調(diào)性：算法是可迭代的，結(jié)果的質(zhì)量是時間和輸入數(shù)據(jù)質(zhì)量的一個非遞減的函數(shù)。4.一致性：結(jié)果的質(zhì)量與時間和輸入數(shù)據(jù)質(zhì)量有關(guān)。5.收益遞增：方案在迭代早期可獲得大的改進(jìn)，但隨時間遞減。6.中斷性：算法可在任何時刻停止并給出答案。7.優(yōu)先權(quán)：算法可以暫停并以最小的開銷新開始。3.2特征歸約在進(jìn)行數(shù)據(jù)歸約時不但要處理干擾數(shù)據(jù)和污染數(shù)據(jù)，而且要處理不相關(guān)、相關(guān)、冗余數(shù)據(jù)。為了提高效率，通常單獨(dú)處理相關(guān)特征，只選擇與挖掘應(yīng)用相關(guān)的數(shù)據(jù)，以達(dá)到用最小的測量和處理量獲得最好的性能。特征歸約的目標(biāo)：更少的數(shù)據(jù)，以便挖掘算法能更快的學(xué)習(xí)。更高的挖掘處理精度，以便更好地從數(shù)據(jù)中歸納出模型。簡單的挖掘處理結(jié)果，以便理解和使用起來更加容易。更少的特征，以便在下一次數(shù)據(jù)收集中，通過去除冗余或不相關(guān)特征做到節(jié)儉。特征歸約的目標(biāo)與任務(wù)：

1.特征選擇－基于應(yīng)用領(lǐng)域的知識和挖掘的目標(biāo)，選擇初始數(shù)據(jù)集中特征的一個子集。

2.特征構(gòu)成－有一些數(shù)據(jù)的轉(zhuǎn)換對挖掘方法的結(jié)果有驚人影響，因此特征構(gòu)成是一個比特殊的挖掘技術(shù)更有決定性因素。特征構(gòu)成依賴于應(yīng)用的知識，交叉學(xué)科知識的應(yīng)用有利于數(shù)據(jù)準(zhǔn)備的改進(jìn)。特征選擇方法：

1.特征排列算法：特征等級列表是根據(jù)特有的評估測量標(biāo)準(zhǔn)進(jìn)行排序的。測量標(biāo)準(zhǔn)基于可用數(shù)據(jù)的精度、一致性、信息內(nèi)容、樣本之間的距離和特征之間的最終統(tǒng)計(jì)相關(guān)性。它僅指出特征間的相關(guān)性，不提供子集。

2.最小子集算法：返回一個最小特征子集，子集中的特征之間沒有等級區(qū)別。子集中的特征與挖掘過程相關(guān)，其余的則是不相關(guān)的。在特征選擇過程中需要建立特征評估方案來確定等級排列或特征子集選擇，這一點(diǎn)很重要。例如，若一個數(shù)據(jù)集有３個特征{A1,A2,A3},特征出現(xiàn)或不出現(xiàn)取值0,1，共有23個歸約的特征子集,

{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},

{1,1,0},{1,1,1}特征選擇的任務(wù)是搜索空間中的每一種狀態(tài)都指定可能特征的一個子集。此問題n=3,空間較小，但大多數(shù)挖掘應(yīng)用，n>20，搜索起點(diǎn)和搜索策略相當(dāng)重要，常常用試探搜索代替窮舉搜索。特征子集選擇的兩種方法1.自底向上方法：從空集開始，然后從初始特征集選擇最相關(guān)的特征來寫入此集。這種方法采用一種基于一些試探式的特征評估標(biāo)準(zhǔn)。2.自頂向下方法：從原始特征的的完整集合開始，然后根據(jù)所選的試探式評估尺度一個一個挑選出不相關(guān)的特征，并將其去除。一種可行的特征選擇技術(shù)是基于均值和方差的比較。它適用于特征的分布是未知的情況，實(shí)際情況也不知道特征的分布，如果假設(shè)分布是正態(tài)，利用統(tǒng)計(jì)學(xué)可獲得好的結(jié)果。這種技術(shù)僅是一種試探式的、不嚴(yán)密的數(shù)學(xué)建模工具。如果一個特征描述了不同種類的實(shí)體，用特征的方差對特征的均值進(jìn)行標(biāo)準(zhǔn)化，進(jìn)行不同類之間的比較。如果均值偏離很遠(yuǎn)，此特征具有分別兩樣本的能力，否則該特征的意義不大?；诰岛头讲畹臋z驗(yàn)公式設(shè)A和B是兩個不同類特征的值的集合，n1和n2是相應(yīng)的樣本數(shù)。上式基于這樣一種假設(shè)，已知特征獨(dú)立于其他特征。主要用于分類問題。例題：下表是一組數(shù)據(jù)集，有兩個輸入特征X和Y，C是把樣本分成兩類的附加特征。假設(shè)檢驗(yàn)閾值為0.5XYC0.30.7A0.20.9B0.60.6A0.50.5A0.70.7B0.40.9BX和Y特征的值的子集：

XA={0.3,0.6,0.5},XB={0.2,0.7,0.4}YA={0.7,0.6,0.5},YB={0.9,0.7,0.9}計(jì)算特征子集的均值和方差：

var(XA)=0.0233,var(XB)=0.6333var(YA)=0.01,var(YB)=0.0133結(jié)果分析：選擇Ｘ進(jìn)行歸約，因它均值接近，檢驗(yàn)結(jié)果小于閾值。Ｙ不需要?dú)w約，它可能是兩類間的區(qū)別特征。上述方法分別檢驗(yàn)特征。當(dāng)分別考慮時，一些特征可能是有用的，但是在預(yù)測能力上它們可能會是冗余的。如果對特征進(jìn)行總體的而不是單個的檢查，我們就可獲得一些關(guān)于它們的特性的額外信息。3.4主成分分析最流行的大型數(shù)據(jù)集維歸約的統(tǒng)計(jì)方法是

Karhunen-Loeve(K-L)方法，也叫主成分分析。主成分分析方法是將以向量樣本表示的初始數(shù)據(jù)集轉(zhuǎn)換為一個新的導(dǎo)出維度的向量樣本集。轉(zhuǎn)換的目標(biāo)是將不同樣本中的信息集中在較小的維度當(dāng)中。主成分分析的基本概念：將一個n維向量樣本集Ｘ={x1,x2,x3,…,xm}轉(zhuǎn)換成一個相同維度的集Ｙ={y1,y2,y3,…,ym}，但數(shù)據(jù)集Ｙ中將大部分信息內(nèi)容存在前幾維中。分析過程：將輸入集維度Ｘ是歸約為只有一個維度Ｙ,通過矩陣計(jì)算將Ｘ轉(zhuǎn)化為Ｙ。

Y=A·Ｘ選擇Ａ以使得Ｙ對已知數(shù)據(jù)集方差最大，轉(zhuǎn)換中獲得一維的Ｙ叫做第一主成分，它是最大方差方向的軸。它是數(shù)據(jù)點(diǎn)之間的距離平方和以及在它們在成分軸上的投影最小。矩陣A是不可能直接確定，在進(jìn)行特征轉(zhuǎn)換時，先計(jì)算協(xié)方差矩陣S。S定義為：通過計(jì)算S來實(shí)現(xiàn)與m個最大的特征值相對應(yīng)的m個特征向量定義了n維空間向m維空間的線性轉(zhuǎn)換,且m個特征相互獨(dú)立。S中的相關(guān)知識：

1.Sn×n的特征值是λ1,λ2,…,λn,其中：

λ1≥λ2≥…λn≥02.特征向量e1,e2,…,en對應(yīng)特征值λ1,λ2,…,λn,稱為主軸。變換后的n維空間，第i個成分的方差等于第i個特征值，數(shù)據(jù)集的大多數(shù)信息集中在少數(shù)主成分中。變換后數(shù)據(jù)集有效維度(m)取值標(biāo)準(zhǔn)：則特征選擇的標(biāo)準(zhǔn)是根據(jù)S的m個最大特征值之和與S的交點(diǎn)比率。（基于Y數(shù)據(jù)集方差最大準(zhǔn)則）主成分分析例子：初始數(shù)據(jù)集是著名的艾里斯數(shù)據(jù)集，有4個特征，每一樣本是一個4維向量。下表標(biāo)準(zhǔn)化的艾里斯數(shù)據(jù)的相關(guān)矩陣(對稱)。Feature1Feature2Feature3Feature4Feature11.0000-0.10940.87180.8180Feature2-0.10941.0000-0.4205-0.3536Feature30.8718-0.42051.00000.9628Feature40.8180-0.35360.96281.0000由相關(guān)矩陣直接計(jì)算特征值，下表所示Feature特征值Feature12.91082Feature20.92122Feature30.14735Feature40.02062設(shè)定閾值R*=0.95,取前兩個特征作為特征子集。

R=(2.91082+0.92122)/(2.91082+0.92122+0.14735+0.02062)=0.958>0.953.5值歸約減少已知特征的離散值的數(shù)目是基于數(shù)據(jù)歸約階段的第二套技術(shù)，這就是特征離散化技術(shù)。則將連續(xù)型特征的值離散化，使之成為少量的區(qū)間，每一個區(qū)間映射到一個離散符號。其優(yōu)點(diǎn)是簡化了數(shù)據(jù)描述并易于理解數(shù)據(jù)和最終挖掘的結(jié)果。例如人的年齡可為兒童、青少年、成人，中年、老年。問題是這種歸約處理存在兩個問題：

1.什么是分割點(diǎn)?2.怎樣選擇區(qū)間表述？離散化可減少計(jì)算的復(fù)雜性。每個特征可以單獨(dú)平整，其過程只執(zhí)行一次，但需要有關(guān)特征的知識。假設(shè)一個特征有一列數(shù)字值，這些值可以用大于小于運(yùn)算符由小到大進(jìn)行排序，可采用分箱的概念將相近的值分組，然后各小組進(jìn)行平整。均值或中位數(shù)，均值或眾數(shù)適用于中等或大量箱數(shù)，邊界平整適用于小箱數(shù)。例如：有一特征f的值集合是：

{3,2,1,5,4,3,1,7,5,3}，通過分類組成一個有序集合：

{1,1,2,3,3,3,4,5,5,7}分為３個箱：｛1,1,2,3,3,3,4,5,5,7｝

BIN1

BIN2

BIN3下面分別眾數(shù)、均值和邊界對其平整。眾數(shù)平整：｛1,1,1,3,3,3,5,5,5,5｝

BIN1

BIN2

BIN3均值平整：｛1.33,1.33,1.33,3,3,3,5.25,5.25,5.25,5.25｝

BIN1

BIN2

BIN3邊界平整：｛1,1,2,3,3,3,4,4,4,7｝

BIN1

BIN2

BIN3主要問題是找到最好的分割點(diǎn)。理論上，分割點(diǎn)不能獨(dú)立其他特征來決定。但很多挖掘應(yīng)用每個特征的試探性決策獨(dú)立地給出了合適的結(jié)果。值歸約問題可表述為一個選擇k個箱的最優(yōu)化問題：給出箱的數(shù)量k，分配箱中的值，使得一個值到它的箱子的均值或中值的平均距離最小。算法可能非常復(fù)雜，通常采用近似最優(yōu)化算法，下面是一個改進(jìn)的試探性程序過程步驟：1.對已知的特征的所有值進(jìn)行分類。2.大概在指定每個箱中分類的相鄰值(vi)的均等數(shù)目，箱子數(shù)已給定。3.當(dāng)減少全局距離誤差(ER)(所有從每個vi到其指定箱子的均值或眾數(shù)的距離之和)時，把邊界元素vi從一個箱中移到下一個(或前一個)箱中。例如：特征f的值集合是{5,1,8,2,2,9,2,1,8,6}分成３個箱(k=3)，采用眾數(shù)平整箱子。第一次迭代計(jì)算：

a)集合排序?yàn)?{1,1,2,2,2,5,6,8,8,9}b)分箱為:{1,1,22,2,5,6,8,8,9}

BIN1

BIN2

BIN3c)(i)3個箱子的眾數(shù)是{1,2,8}，用眾數(shù)的絕對距離計(jì)算總誤差：

ER=0+0+1+0+2+3+2+0+0+1=7(iv)在下面的三次迭代中把兩個元素從BIN2移到BIN1，一個元素從BIN3移到BIN2,得到ER越來越小，新的分布(最終ER=4，再移動ER增大)為：

{1,1,2,2,25,6,8,8,9}

BIN1

BIN2

BIN3另一特征的值歸約算法是用舍入來取得近似值。其算法步驟：

1.整除Y=int(X/10k)2.舍入If(mod(X,10k)≥10k/2)thenY=Y+13.整乘Y=Y*10k

其中k是從最右邊起要舍入的位數(shù)。例如，如果k=1，數(shù)字1450舍入為1450；如果k=2，舍入為1500；如果k=3，舍入為1000。3.7案例歸約如果我們沒有參與數(shù)據(jù)收集過程，那么在挖掘時可看作是二次數(shù)據(jù)分析，挖掘過程與收集數(shù)據(jù)和選擇初始數(shù)據(jù)的樣本集的最優(yōu)方法沒有聯(lián)系，樣本是已知的，質(zhì)量或好或壞，或者沒有先驗(yàn)知識，需要解決案例數(shù)據(jù)集中使用的維數(shù)和樣本數(shù)目，或者說數(shù)據(jù)表中的行數(shù)。因此案例歸約是數(shù)據(jù)歸約中最復(fù)雜的任務(wù)。案例歸約過程實(shí)際上是一個取樣過程，如果取樣已由挖掘技術(shù)來管理，就不需要進(jìn)行案例歸約了。在數(shù)據(jù)分析中出現(xiàn)兩種取樣過程，第一種，有時數(shù)據(jù)集本身不過是來自較大的、未知總體的一個樣本，取樣是數(shù)據(jù)收集過程的一部分，挖掘?qū)@類取樣沒有興趣。第二