數(shù)據(jù)預(yù)處理課件

數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典元昌安主編鄧松李文敬劉海濤編著電子工業(yè)出版社數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典第5章數(shù)據(jù)預(yù)處理

本章包括：

數(shù)據(jù)預(yù)處理基本功能數(shù)據(jù)預(yù)處理的方法第5章數(shù)據(jù)預(yù)處理

本章包括：數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但有潛在的有用信息和知識(shí)的過(guò)程。數(shù)據(jù)挖掘：為企業(yè)決策者提供重要的、有價(jià)值的信息或知識(shí)，從而為企業(yè)帶來(lái)不可估量的經(jīng)濟(jì)效益。數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中數(shù)據(jù)挖掘過(guò)程一般包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘以及知識(shí)評(píng)價(jià)和呈現(xiàn)。在一個(gè)完整的數(shù)據(jù)挖掘過(guò)程中，數(shù)據(jù)預(yù)處理要花費(fèi)60%左右的時(shí)間，而后的挖掘工作僅占總工作量的10%左右。

目前對(duì)數(shù)據(jù)挖掘的研究主要集中于挖掘技術(shù)、挖掘算法、挖掘語(yǔ)言等。數(shù)據(jù)挖掘過(guò)程一般包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘以數(shù)據(jù)挖掘的必要性：在海量的原始數(shù)據(jù)中，存在著大量雜亂的、重復(fù)的、不完整的數(shù)據(jù)，嚴(yán)重影響到數(shù)據(jù)挖掘算法的執(zhí)行效率，甚至可能導(dǎo)致挖掘結(jié)果的偏差。數(shù)據(jù)預(yù)處理課件數(shù)據(jù)預(yù)處理分類：從對(duì)不同的源數(shù)據(jù)進(jìn)行預(yù)處理的功能來(lái)分，數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換、數(shù)據(jù)歸約等4個(gè)基本功能。在實(shí)際的數(shù)據(jù)預(yù)處理過(guò)程中，

這4種功能不一定都用到，而且，它們的使用也沒(méi)有先后順序，

某一種預(yù)處理可能先后要多次進(jìn)行。數(shù)據(jù)預(yù)處理分類：從數(shù)據(jù)預(yù)處理所采用的技術(shù)和方法來(lái)分：

基本粗集理論的簡(jiǎn)約方法；復(fù)共線性數(shù)據(jù)預(yù)處理方法；基于Hash函數(shù)取樣的數(shù)據(jù)預(yù)處理方法；基于遺傳算法數(shù)據(jù)預(yù)處理方法；基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)預(yù)處理方法；Web挖掘的數(shù)據(jù)預(yù)處理方法等等。數(shù)據(jù)預(yù)處理課件5.1數(shù)據(jù)預(yù)處理基本功能

在數(shù)據(jù)挖掘整體過(guò)程中,海量的原始數(shù)據(jù)中存在著大量雜亂的、重復(fù)的、不完整的數(shù)據(jù)，嚴(yán)重影響到數(shù)據(jù)挖掘算法的執(zhí)行效率，甚至可能導(dǎo)致挖掘結(jié)果的偏差。為此，在數(shù)據(jù)挖掘算法執(zhí)行之前，必須對(duì)收集到的原始數(shù)據(jù)進(jìn)行預(yù)處理，以改進(jìn)數(shù)據(jù)的質(zhì)量，提高數(shù)據(jù)挖掘過(guò)程的效率、精度和性能。數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換與數(shù)據(jù)歸約等技術(shù)。5.1數(shù)據(jù)預(yù)處理基本功能在數(shù)據(jù)挖掘整體過(guò)程中,海量的原始數(shù)5.1.1數(shù)據(jù)清理

數(shù)據(jù)清理要去除源數(shù)據(jù)集中的噪聲數(shù)據(jù)和無(wú)關(guān)數(shù)據(jù)，處理遺漏數(shù)據(jù)和清洗臟數(shù)據(jù)、空缺值，

識(shí)別刪除孤立點(diǎn)等。5.1.1數(shù)據(jù)清理數(shù)據(jù)清理要去除源數(shù)據(jù)集中的噪聲數(shù)據(jù)和無(wú)5.1.1.1噪聲數(shù)據(jù)處理

噪聲是一個(gè)測(cè)量變量中的隨機(jī)錯(cuò)誤或偏差，包括錯(cuò)誤的值或偏離期望的孤立點(diǎn)值。對(duì)于噪聲數(shù)據(jù)有如下幾種處理方法：分箱法聚類法識(shí)別孤立點(diǎn)回歸

5.1.1.1噪聲數(shù)據(jù)處理噪聲是一個(gè)測(cè)量變量中的隨機(jī)5.1.1.2空缺值的處理

目前最常用的方法是使用最可能的值填充空缺值，

如用一個(gè)全局常量替換空缺值、使用屬性的平均值填充空缺值或?qū)⑺性M按某些屬性分類，

然后用同一類中屬性的平均值填充空缺值。例5.2：一個(gè)公司職員平均工資收入為3000元，則使用該值替換工資中“基本工資”屬性中的空缺值。

5.1.1.2空缺值的處理目前最常用的方法是使用最可能的值5.1.1.3清洗臟數(shù)據(jù)

異構(gòu)數(shù)據(jù)源數(shù)據(jù)庫(kù)中的數(shù)據(jù)并不都是正確的，常常不可避免地存在著不完整、不一致、不精確和重復(fù)的數(shù)據(jù)，這些數(shù)據(jù)統(tǒng)稱為“臟數(shù)據(jù)”。臟數(shù)據(jù)能使挖掘過(guò)程陷入混亂，導(dǎo)致不可靠的輸出。

5.1.1.3清洗臟數(shù)據(jù)異構(gòu)數(shù)據(jù)源數(shù)據(jù)庫(kù)中的數(shù)據(jù)并不都是正清洗臟數(shù)據(jù)可采用下面的方式：手工實(shí)現(xiàn)方式用專門編寫的應(yīng)用程序采用概率統(tǒng)計(jì)學(xué)原理查找數(shù)值異常的記錄對(duì)重復(fù)記錄的檢測(cè)與刪除清洗臟數(shù)據(jù)可采用下面的方式：5.1.2.1實(shí)體識(shí)別問(wèn)題

在數(shù)據(jù)集成時(shí)，來(lái)自多個(gè)數(shù)據(jù)源的現(xiàn)實(shí)世界的實(shí)體有時(shí)并不一定是匹配的，例如：數(shù)據(jù)分析者如何才能確信一個(gè)數(shù)據(jù)庫(kù)中的student_id和另一個(gè)數(shù)據(jù)庫(kù)中的stu_id值是同一個(gè)實(shí)體。通常，可根據(jù)數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)的元數(shù)據(jù)來(lái)區(qū)分模式集成中的錯(cuò)誤。5.1.2.1實(shí)體識(shí)別問(wèn)題在數(shù)據(jù)集成時(shí)，來(lái)自多個(gè)數(shù)據(jù)5.1.2.2冗余問(wèn)題

數(shù)據(jù)集成往往導(dǎo)致數(shù)據(jù)冗余，如同一屬性多次出現(xiàn)、同一屬性命名不一致等，對(duì)于屬性間冗余可以用相關(guān)分析檢測(cè)到，然后刪除。

5.1.2.2冗余問(wèn)題5.1.2.3數(shù)據(jù)值沖突檢測(cè)與處理

對(duì)于現(xiàn)實(shí)世界的同一實(shí)體，來(lái)自不同數(shù)據(jù)源的屬性值可能不同。這可能是因?yàn)楸硎?、比例或編碼、數(shù)據(jù)類型、單位不統(tǒng)一、字段長(zhǎng)度不同。5.1.2.3數(shù)據(jù)值沖突檢測(cè)與處理5.1.3數(shù)據(jù)變換

數(shù)據(jù)變換主要是找到數(shù)據(jù)的特征表示，用維變換或轉(zhuǎn)換方法減少有效變量的數(shù)目或找到數(shù)據(jù)的不變式，包括規(guī)格化、歸約、切換、旋轉(zhuǎn)和投影等操作。規(guī)格化是指將元組集按規(guī)格化條件進(jìn)行合并，也就是屬性值量綱的歸一化處理。5.1.3數(shù)據(jù)變換數(shù)據(jù)變換主要是找到數(shù)據(jù)的特征表示，用維規(guī)格化條件定義了屬性的多個(gè)取值到給定虛擬值的對(duì)應(yīng)關(guān)系。對(duì)于不同的數(shù)值屬性特點(diǎn)，一般可以分為取值連續(xù)和取值分散的數(shù)值屬性規(guī)格化問(wèn)題。規(guī)格化條件定義了屬性的多個(gè)取值到給定虛擬值的對(duì)應(yīng)關(guān)系。對(duì)于不歸約指將元組按語(yǔ)義層次結(jié)構(gòu)合并。語(yǔ)義層次結(jié)構(gòu)定義了元組屬性值之間的語(yǔ)義關(guān)系。規(guī)格化和歸約能大量減少元組個(gè)數(shù)，提高計(jì)算效率。同時(shí)，規(guī)格化和歸約過(guò)程提高了知識(shí)發(fā)現(xiàn)的起點(diǎn)，使得一個(gè)算法能夠發(fā)現(xiàn)多層次的知識(shí)，適應(yīng)不同應(yīng)用的需要。歸約指將元組按語(yǔ)義層次結(jié)構(gòu)合并。語(yǔ)義層次結(jié)構(gòu)定義了元組屬性值5.1.4數(shù)據(jù)歸約

數(shù)據(jù)歸約是將數(shù)據(jù)庫(kù)中的海量數(shù)據(jù)進(jìn)行歸約，歸約之后的數(shù)據(jù)仍接近于保持原數(shù)據(jù)的完整性，但數(shù)據(jù)量相對(duì)小得多，這樣進(jìn)行數(shù)據(jù)挖掘的性能和效率會(huì)得到很大提高。數(shù)據(jù)歸約的策略主要有數(shù)據(jù)立方體聚集、維歸約、數(shù)據(jù)壓縮、數(shù)值壓縮、離散化和概念分層。5.1.4數(shù)據(jù)歸約數(shù)據(jù)歸約是將數(shù)據(jù)庫(kù)中的海量數(shù)據(jù)進(jìn)行歸約5.1.4.1維歸約

通過(guò)刪除不相關(guān)的屬性(或維)減少數(shù)據(jù)量，不僅壓縮了數(shù)據(jù)集，還減少了出現(xiàn)在發(fā)現(xiàn)模式上的屬性數(shù)目，通常采用屬性子集選擇方法找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布。

5.1.4.1維歸約通過(guò)刪除不相關(guān)的屬性(或維)減少5.1.4.2數(shù)據(jù)壓縮

數(shù)據(jù)壓縮分為無(wú)損壓縮和有損壓縮，比較流行和有效的有損數(shù)據(jù)壓縮方法是小波變換和主要成分分析。小波變換對(duì)于稀疏或傾斜數(shù)據(jù)以及具有有序?qū)傩缘臄?shù)據(jù)有很好的壓縮結(jié)果。5.1.4.2數(shù)據(jù)壓縮數(shù)據(jù)壓縮分為無(wú)損壓縮和有損壓縮，比較5.1.4.3數(shù)值歸約

數(shù)值歸約通過(guò)選擇替代的、較小的數(shù)據(jù)表示形式來(lái)減少數(shù)據(jù)量。

數(shù)值歸約技術(shù)可以是有參的，也可以是無(wú)參的。有參方法是使用一個(gè)模型來(lái)評(píng)估數(shù)據(jù)，只需存放參數(shù)，而不需要存放實(shí)際數(shù)據(jù)。有參的數(shù)值歸約技術(shù)有以下兩種，回歸：線性回歸和多元回歸；對(duì)數(shù)線性模型：近似離散屬性集中的多維概率分布。5.1.4.3數(shù)值歸約數(shù)值歸約通過(guò)選擇替代的、較小的數(shù)據(jù)無(wú)參的數(shù)值歸約技術(shù)有3種：直方圖聚類選樣無(wú)參的數(shù)值歸約技術(shù)有3種：5.1.4.4概念分層

概念分層通過(guò)收集并用較高層的概念替換較低層的概念來(lái)定義數(shù)值屬性的一個(gè)離散化。概念分層可以用來(lái)歸約數(shù)據(jù)，通過(guò)這種概化盡管細(xì)節(jié)丟失了，但概化后的數(shù)據(jù)更有意義、更容易理解，并且所需的空間比原數(shù)據(jù)少。對(duì)于數(shù)值屬性，由于數(shù)據(jù)的可能取值范圍的多樣性和數(shù)據(jù)值的更新頻繁，說(shuō)明概念分層是困難的。5.1.4.4概念分層概念分層通過(guò)收集并用較高層的概念數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)的分布分析自動(dòng)地構(gòu)造，如用分箱、直方圖分析、聚類分析、基于熵的離散化和自然劃分分段等技術(shù)生成數(shù)值概念分層。由用戶專家在模式級(jí)顯示地說(shuō)明屬性的部分序或全序，從而獲得概念的分層；只說(shuō)明屬性集，但不說(shuō)明它們的偏序，由系統(tǒng)根據(jù)每個(gè)屬性不同值的個(gè)數(shù)產(chǎn)生屬性序，自動(dòng)構(gòu)造有意義的概念分層。數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)的分布分析自動(dòng)地構(gòu)造，5.2數(shù)據(jù)預(yù)處理的方法

數(shù)據(jù)預(yù)處理方法就是根據(jù)不同的挖掘問(wèn)題采用相應(yīng)的理論和技術(shù)，實(shí)現(xiàn)數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換、數(shù)據(jù)歸約等基本功能。預(yù)處理方法很多，在此介紹常用的幾種方法。5.2數(shù)據(jù)預(yù)處理的方法數(shù)據(jù)預(yù)處理方法就是根據(jù)不同的挖掘問(wèn)題5.2.1基于粗集理論的簡(jiǎn)約方法

粗糙集理論是一種研究不精確、不確定性知識(shí)的數(shù)學(xué)工具，可以對(duì)數(shù)據(jù)屬性進(jìn)行十分有效的精簡(jiǎn)，求出最小約簡(jiǎn)集，是數(shù)據(jù)預(yù)處理一種有效的方法。5.2.1基于粗集理論的簡(jiǎn)約方法粗糙集理論是一種研究不數(shù)據(jù)一般存在信息的含糊性問(wèn)題。粗糙集理論的最大特點(diǎn)是無(wú)需提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息。數(shù)據(jù)一般存在信息的含糊性問(wèn)題。

粗糙集理論的基本思路是利用定義在數(shù)據(jù)集合U上的等價(jià)關(guān)系對(duì)U進(jìn)行劃分，對(duì)于數(shù)據(jù)表來(lái)說(shuō)，這種等價(jià)關(guān)系可以是某個(gè)屬性，或者是幾個(gè)屬性的集合。因此按照不同屬性的組合就把數(shù)據(jù)表劃分成不同的基本類，在這些基本類的基礎(chǔ)上進(jìn)一步求得最小約簡(jiǎn)集。

例如：表5.1優(yōu)秀人才決策表給出了某部門的員工數(shù)據(jù)記錄集，通過(guò)對(duì)員工的政治表現(xiàn)、工作能力、科研能力等確定優(yōu)秀人才人選。論域U

條件屬性（C）

決策屬性

政治表現(xiàn)（C1）工作能力（C2）

科研能力（C3）

優(yōu)秀人才（D）

e1優(yōu)秀強(qiáng)強(qiáng)是e2良好一般一般否e3一般差差否e4一般一般一般否e5良好強(qiáng)一般否e6優(yōu)秀強(qiáng)強(qiáng)是其中：條件屬性集為C＝{政治表現(xiàn)，工作能力，科研能力}，決策屬性集為D＝{優(yōu)秀人才}。

例如：表5.1優(yōu)秀人才決策表給出了某部門的員工數(shù)據(jù)記錄集，根據(jù)粗糙集理論對(duì)表5.1進(jìn)行離散化后再進(jìn)行數(shù)據(jù)預(yù)處理。處理過(guò)程分兩個(gè)步驟進(jìn)行，一是對(duì)決策表?xiàng)l件屬性集進(jìn)行約簡(jiǎn)求核；二是對(duì)條件屬性值進(jìn)行約簡(jiǎn)。具體求解步驟可見(jiàn)第11章相關(guān)內(nèi)容。根據(jù)粗糙集理論對(duì)表5.1進(jìn)行離散化后再進(jìn)行數(shù)據(jù)預(yù)處理?；诖植诩碚摰臄?shù)據(jù)預(yù)處理具有優(yōu)點(diǎn)：第一，數(shù)據(jù)挖掘的對(duì)象一般都是通過(guò)觀測(cè)、試驗(yàn)、調(diào)查得到的數(shù)據(jù)，通過(guò)觀測(cè)、試驗(yàn)、調(diào)查等得到的數(shù)據(jù)存在著冗余、雜亂、不完整等因素，采用粗糙集理論進(jìn)行數(shù)據(jù)預(yù)處理，不需要預(yù)先知道額外的信息，有利于集中精力解決問(wèn)題；基于粗糙集理論的數(shù)據(jù)預(yù)處理具有優(yōu)點(diǎn)：第二，算法簡(jiǎn)單。對(duì)于給定的決策表，預(yù)處理過(guò)程所使用的算法可以是分辨矩陣或逐個(gè)屬性、逐條規(guī)則進(jìn)行檢驗(yàn)，算法簡(jiǎn)單，易于計(jì)算機(jī)的實(shí)現(xiàn)，方便挖掘系統(tǒng)的自動(dòng)操作；第三，可以有效地去除冗余的屬性或?qū)傩缘闹?。第二，算法?jiǎn)單。對(duì)于給定的決策表，預(yù)處理過(guò)程所使用的算法可以5.2.2復(fù)共線性數(shù)據(jù)的預(yù)處理方法

常規(guī)方法進(jìn)行函數(shù)發(fā)現(xiàn)時(shí)一般要作出一個(gè)假設(shè)：數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)。而傳統(tǒng)的函數(shù)發(fā)現(xiàn)算法中，常常忽略對(duì)數(shù)據(jù)是否滿足該假設(shè)的檢驗(yàn)。若數(shù)據(jù)不滿足統(tǒng)計(jì)不相關(guān)的假設(shè)（也稱數(shù)據(jù)變量之間存在復(fù)共線性），在這種情況下，函數(shù)發(fā)現(xiàn)算法挖掘出來(lái)的函數(shù)關(guān)系表達(dá)式可能會(huì)存在系統(tǒng)誤差，該表達(dá)式將不是我們要發(fā)現(xiàn)的理想函數(shù)。5.2.2復(fù)共線性數(shù)據(jù)的預(yù)處理方法常規(guī)方法進(jìn)行函數(shù)發(fā)現(xiàn)時(shí)一為解決該問(wèn)題，本節(jié)給出ε－復(fù)共線性的概念，然后給出不滿足不相關(guān)假設(shè)的情況下進(jìn)行數(shù)據(jù)預(yù)處理的算法ε－MDPA（ε－MulticollinearityDataPreprocessingAlgorithm復(fù)共線性數(shù)據(jù)預(yù)處理算法）。為解決該問(wèn)題，本節(jié)給出ε－復(fù)共線性的概念，然后給出不滿足不相5.2.2.1.相關(guān)概念假定給定的樣本數(shù)據(jù)為Y、X，其中因變量樣本數(shù)據(jù)矩陣Y=(y1,y2,…,yn)是p×n樣本矩陣，即p個(gè)因變量，n個(gè)樣本；自變量樣本數(shù)據(jù)矩陣X是q×n矩陣，即q個(gè)自變量，n個(gè)樣本。在實(shí)際計(jì)算時(shí)，X一般是將原始數(shù)據(jù)中心化后得到的樣本矩陣，即：X×1n＝0。5.2.2.1.相關(guān)概念假定給定的樣本數(shù)據(jù)為Y、X，其中因變?cè)谝话愕暮瘮?shù)發(fā)現(xiàn)算法中，自變量樣本數(shù)據(jù)矩陣X需要數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，也即X各行之間不能存在線性關(guān)系。而實(shí)際上，只要矩陣X的行向量之間存在近似線性關(guān)系時(shí)，函數(shù)發(fā)現(xiàn)算法就有可能達(dá)不到實(shí)用的效果。為此，下面我們給出ε－復(fù)共線性的定義，并對(duì)滿足這一定義的數(shù)據(jù)給出數(shù)據(jù)預(yù)處理的算法(ε－MDPA)。在一般的函數(shù)發(fā)現(xiàn)算法中，自變量樣本數(shù)據(jù)矩陣X需要數(shù)據(jù)滿足統(tǒng)計(jì)定義5.1（ε－復(fù)共線性）給定矩陣X，設(shè)X′為X的轉(zhuǎn)置矩陣，設(shè)矩陣（XX′）n×n的特征根為λ1,λ2,…,λn,若對(duì)預(yù)設(shè)的正數(shù)ε，0＜ε＜0.1，有max(λi,i=1,…,n)/min(λi,i=1,…,n)>1/ε，則稱矩陣X滿足ε－復(fù)共線性。定義5.1（ε－復(fù)共線性）給定矩陣X，設(shè)X′為X的轉(zhuǎn)置矩陣，ε－復(fù)共線性描述了最大特征根和最小特征根之間的差距，當(dāng)ε足夠小時(shí)，XX′至少有一個(gè)特征根接近于0，這時(shí)，X的行向量之間存在著近似的線性關(guān)系，從而描述了數(shù)據(jù)之間的相關(guān)程度。ε用于控制X各行向量之間的相關(guān)程度，當(dāng)其線性關(guān)系達(dá)到用戶指定的程度，那么，該組數(shù)據(jù)在進(jìn)行函數(shù)發(fā)現(xiàn)之前應(yīng)該進(jìn)行轉(zhuǎn)換預(yù)處理。ε－復(fù)共線性描述了最大特征根和最小特征根之間的差距，當(dāng)ε足夠5.2.2.2.ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法

本小節(jié)主要討論存在著ε－復(fù)共線性的數(shù)據(jù)矩陣X數(shù)據(jù)預(yù)處理的方法。5.2.2.2.ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法本小節(jié)主要討論存算法思路：為消除數(shù)據(jù)的復(fù)共線性使數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，需對(duì)矩陣X作主成分分析，計(jì)算出主向量矩陣Z，矩陣Z的各行向量之間是滿足統(tǒng)計(jì)不相關(guān)假設(shè)的。于是，在后繼的函數(shù)發(fā)現(xiàn)算法中，將挖掘Y與Z的關(guān)系，然后再利用X與Z的關(guān)系，得到Y(jié)與X之間的關(guān)系表達(dá)式。算法思路：為消除數(shù)據(jù)的復(fù)共線性使數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，需對(duì)下面的ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法描述了存在ε－復(fù)共線性數(shù)據(jù)的轉(zhuǎn)換方法。數(shù)據(jù)預(yù)處理課件算法5-1

ε－MDPA(ε－MulticollinearityDataPreprocessingAlgorithm)輸入：q×n矩陣

X，控制值ε輸出：Z(轉(zhuǎn)換后消除復(fù)共線性的數(shù)據(jù)矩陣)步驟：BeginStep1計(jì)算XX′的特征值λ1,λ2,…,λq，并按從大到小順序排序；Step2判斷數(shù)據(jù)矩陣X具有ε－復(fù)共線性。End.

算法的偽代碼如下：EC（X）//計(jì)算XX′的特征值λ1,λ2,…,λq，并按從大到小順序排序；IFλ1/λq>1/ε//數(shù)據(jù)矩陣X具有ε－復(fù)共線性

PCMC(Xq×n，λ1,λ2,…,λq，t)//主分量矩陣計(jì)算ELSEZ=X；ENDIF算法5-1ε－MDPA(ε－Multicollineari算法3-1的計(jì)算代價(jià)主要在第1行計(jì)算特征值過(guò)程和第3行主分量矩陣計(jì)算過(guò)程，分別由下面的算法5-2和算法5-3實(shí)現(xiàn)。算法3-1的計(jì)算代價(jià)主要在第1行計(jì)算特征值過(guò)程和第3行主分量算法5-2

EC(EigenvalueCompute特征值計(jì)算子程序)輸入：q×n矩陣

X輸出：特征值λ1，λ2，…，λq，并按從大到小順序排序和特征向量矩陣Eigenvalue(q,q)步驟：BeginStep1

計(jì)算相關(guān)系數(shù)矩陣CorMatrix（q,q）；Step2利用雅可比法計(jì)算矩陣CorMatrix（q,q）的特征值；Step3判斷上三角元素是否全部滿足設(shè)定值；Step4將特征值、特征向量按照特征值的大小進(jìn)行排序得到特征值向量lpt[q]和特征向量矩陣EigenVector[q,q]。End.算法5-2EC(EigenvalueCompute特征值算法的偽代碼如下：Begin計(jì)算相關(guān)系數(shù)矩陣CorMatrix（q,q）；利用雅可比法計(jì)算矩陣CorMatrix（q,q）的特征值；Eigenvalue[i,j]=CorMatrix[i,j],(i,j=1,2,…,q)；l=0;//定義計(jì)數(shù)變量while(l<(q*(q-1))/2)//判斷上三角元素是否全部滿足設(shè)定值,滿足跳出循環(huán)，否則繼續(xù)循環(huán){l=0;求在Eigenvalue[q,q]矩陣上三角元素中的最大值及其位置pos1,pos2根據(jù)pos1,pos2進(jìn)行一輪特征值、特征向量的計(jì)算if((abs(Eigenvalue[i,j])<),(i=0,1,…,q,j=i+1,…,q)//判斷上三角元素是否滿足條件l++;//滿足計(jì)數(shù)器l加1}Lpt[i]=Eigenvalue[i,i];(i=1,2,…,q);//將特征值放入一維數(shù)組中將特征值、特征向量按照特征值的大小進(jìn)行排序得到特征值向量lpt[q]和特征向量矩陣EigenVector[q,q]End.算法的偽代碼如下：說(shuō)明：算法中把特征值存放在Lpt數(shù)組，特征向量存放在Eigenvalue數(shù)組中。一般q<<n，所以算法的主要計(jì)算代價(jià)在第一步計(jì)算相關(guān)系數(shù)矩陣中，計(jì)算量為q*n=O(n)下面的算法描述了主分量矩陣的計(jì)算過(guò)程。

說(shuō)明：算法5-3

PCMC(PrincipleComponentMatrixCompute主分量矩陣計(jì)算子程序)輸入：矩陣Xq×n，λ1,λ2,…,λq，特征向量矩陣EigenVector[q,q]，t(t<=1為確定主分量個(gè)數(shù)時(shí)所需特征值之和對(duì)總和貢獻(xiàn)率的臨界值)輸出：所需主分量矩陣Zk×n步驟：

BeginStep1計(jì)算所需主分量個(gè)數(shù)k；Step2根據(jù)特征向量矩陣Eigenvalue(q,q)計(jì)算出所需特征向量矩陣Pk×q；Step3計(jì)算主分量矩陣Zk×n(=P×X)。End.算法5-3PCMC(PrincipleComponent算法的偽代碼如下：Begin計(jì)算所需主分量個(gè)數(shù)k(<=q)即滿足（λ1＋λ2＋…＋λk）/（λ1＋λ2＋…＋λq）>=t根據(jù)特征向量矩陣Eigenvalue(q,q)計(jì)算出所需特征向量矩陣Pk×q計(jì)算主分量矩陣Zk×n(=P×X)End.顯然，算法3-3的計(jì)算代價(jià)主要在第2行，第3行，它們的計(jì)算復(fù)雜度在下面的命題中將進(jìn)行分析。下面的命題描述了算法ε－MDPA的復(fù)雜度。算法的偽代碼如下：命題5.1ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法ε－MDPA的總計(jì)算量為O(n)。證明：

注意，算法中的p,q的值一般較小，相對(duì)于n的值可計(jì)為O(1)，算法計(jì)算代價(jià)主要有：（1）計(jì)算特征值：計(jì)算量為O(n)（2）計(jì)算主分量個(gè)數(shù)：計(jì)算量為O(1)（3）計(jì)算特征向量矩陣：計(jì)算量為O(1)（4）計(jì)算主分量矩陣：計(jì)算量為O(1)

因此，ε－MDPA的總計(jì)算量為O(n)。命題5.1ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法ε－MDPA的總計(jì)算量在目前常規(guī)的數(shù)據(jù)挖掘系統(tǒng)中，其數(shù)據(jù)分析功能模塊中，一般有主成分分析模塊，因此，ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法在海量數(shù)據(jù)計(jì)算中，可使用這些模塊計(jì)算的中間結(jié)果，或者使用抽樣方法估算主成分分析模塊的一些參數(shù)，以減少運(yùn)算量。因此，ε－MDPA在沒(méi)有明顯增加計(jì)算量的情況下，將一些函數(shù)發(fā)現(xiàn)算法的應(yīng)用推廣到數(shù)據(jù)不滿足統(tǒng)計(jì)不相關(guān)假設(shè)的情況，大大地拓寬了統(tǒng)計(jì)學(xué)及數(shù)據(jù)挖掘中的一些方法應(yīng)用

在目前常規(guī)的數(shù)據(jù)挖掘系統(tǒng)中，其數(shù)據(jù)分析功能模塊中，一般有主成5.2.2.3.實(shí)驗(yàn)

本實(shí)驗(yàn)的目的在于讓讀者理解ε－MDPA算法的運(yùn)算過(guò)程，所以，實(shí)驗(yàn)數(shù)據(jù)樣本數(shù)較小。實(shí)驗(yàn)針對(duì)以下數(shù)據(jù)進(jìn)行，見(jiàn)表5.2。表5.2某地區(qū)森林植被與引起洪澇災(zāi)害的降雨量的關(guān)系序號(hào)變量

12345678910X182.988.099.9105.3117.7131.0168.2161.8174.2184.7X292.093.096.094.0110.0101.0105.0112.0112.0112.0X317.121.325.129.034.040.044.049.051.053.0X494.096.097.097.0100.0101.0104.0109.0111.0111.0

y8.49.610.411.412.214.215.817.919.620.85.2.2.3.實(shí)驗(yàn)本實(shí)驗(yàn)的目的在于讓讀者理解ε－MDPA該例中：p=1，q=4，n=10運(yùn)行ε－MDPA應(yīng)用程序，并選擇ε＝0.001,t=0.90計(jì)算得：

CorMatrix（q,q）=

λ1＝3.827,λ2=0.138,λ3=0.032,λ4=0.003λ1/λ4=1276>1/ε=1000,該例中：p=1，q=4，n=10數(shù)據(jù)矩陣X存在復(fù)共線性，執(zhí)行PCMC子程序，計(jì)算主分量矩陣。由λ1/∑λi＝0.957>t，k=1,即主分量只需取一個(gè)，即λ1＝3.827對(duì)應(yīng)的評(píng)分量。計(jì)算得P1＊4=(0.259,0.257,0.258,0.258)計(jì)算消除復(fù)共線性后的數(shù)據(jù)矩陣Z：Z1＊10＝P×X＝(73.8,76.9,82.0,83.9,93.3,96.3,103.6,111.5,115.7,118.9)然后，就可以使用新的數(shù)據(jù)矩陣挖掘其與因變量Y之間的函數(shù)關(guān)系，最終將結(jié)果再代回到自變量X即可。

數(shù)據(jù)矩陣X存在復(fù)共線性，執(zhí)行PCMC子程序，計(jì)算主分量矩陣。5.2.3基于Hash函數(shù)取樣的抽樣技術(shù)數(shù)據(jù)預(yù)處理

在函數(shù)發(fā)現(xiàn)算法處理海量數(shù)據(jù)時(shí)，由于實(shí)時(shí)的需要（例如針對(duì)數(shù)據(jù)流的處理），常需要先進(jìn)行抽樣。要使抽樣取得好的效果，最重要的是要使樣本的代表性能真正反映總體的統(tǒng)計(jì)特性。傳統(tǒng)的抽樣方法一般采取簡(jiǎn)單隨機(jī)抽樣，但這種方法反映的是數(shù)據(jù)編號(hào)的統(tǒng)計(jì)特性，沒(méi)有真正反映出其數(shù)據(jù)分布的統(tǒng)計(jì)特性；特別是當(dāng)數(shù)據(jù)傾斜時(shí)，樣本不具有對(duì)總體數(shù)據(jù)統(tǒng)計(jì)分布的代表性。5.2.3基于Hash函數(shù)取樣的抽樣技術(shù)數(shù)據(jù)預(yù)處理傳統(tǒng)的分層抽樣需要有關(guān)層次概念的知識(shí)，然后根據(jù)層的知識(shí)來(lái)進(jìn)行分層，因而傳統(tǒng)方法在沒(méi)有層知識(shí)的情況下就顯得無(wú)能為力。傳統(tǒng)的分層抽樣需要有關(guān)層次概念的知識(shí)，然后根據(jù)層的知識(shí)來(lái)進(jìn)行新的基于Hash函數(shù)取樣技術(shù)SHF(SamplingBasedonHashFunction)模型，新方法注意到傳統(tǒng)分層抽樣需要預(yù)先知道關(guān)于層的知識(shí)，因此引入Hash函數(shù)技術(shù)，在對(duì)總體數(shù)據(jù)沒(méi)有層知識(shí)的情形下，利用Hash桶進(jìn)行分層，即將m維超立方體按等概率空間進(jìn)行分桶，使得每層（Hash桶）的數(shù)據(jù)個(gè)數(shù)相近，以較小的計(jì)算代價(jià)獲得分層的效果，然后進(jìn)行分層抽樣，使所抽樣本能充分反映數(shù)據(jù)的統(tǒng)計(jì)特性。新的基于Hash函數(shù)取樣技術(shù)SHF(SamplingBa算法保證了樣本具有對(duì)總體數(shù)據(jù)的充分的統(tǒng)計(jì)代表性并從理論上可證明新算法復(fù)雜度為O（n）。算法保證了樣本具有對(duì)總體數(shù)據(jù)的充分的統(tǒng)計(jì)代表性并從理論上可證總體的分布函數(shù)構(gòu)造Hash函數(shù)，由于以下原因：

完全地計(jì)算總體數(shù)據(jù)去得到精確分布的計(jì)算量太大；即使處理完整個(gè)總體的數(shù)據(jù)，由于數(shù)據(jù)噪聲，得到總體的分布也只是近似的。所以，SHF利用隨機(jī)抽樣的一些性質(zhì)，使用總體的估計(jì)分布函數(shù)來(lái)代替其精確分布。5.2.3.1SHF模型中的概念

總體的分布函數(shù)構(gòu)造Hash函數(shù)，由于以下原因：5.2.3.1設(shè)總體數(shù)據(jù)為：X＝（Xij）n×m，即共有m個(gè)變量，n行數(shù)據(jù)。為了簡(jiǎn)化問(wèn)題且不失一般性，本節(jié)作下列兩項(xiàng)假定：(1)假定m個(gè)變量中有下列幾種類型：

l

連續(xù)型，如重量和高度等。其距離計(jì)算方法一般用歐氏距離或曼哈坦距離。l

二元型，即變量取值只有2個(gè)狀態(tài)，如性別。l

標(biāo)稱型，二元型的推廣，其狀態(tài)多于2個(gè)，如顏色。其它類型均可以看作上述三種類型的特例。設(shè)總體數(shù)據(jù)為：X＝（Xij）n×m，即共有m個(gè)變量，n行數(shù)據(jù)(2)假定m個(gè)變量中，x1，…，xm1為連續(xù)型變量，xm1+1，…，xm1+m2為二元變量，

xm1+m2+1，…，xm1+m2+m3為標(biāo)稱變量。

m1+m2+m3＝m，即m1個(gè)連續(xù)變量，m2個(gè)二元變量，m3個(gè)標(biāo)稱變量。關(guān)于二元變量，兩個(gè)對(duì)象i，j之間的距離常用它們的匹配系數(shù)來(lái)表示：d(i,j)=f/m2，其中f為m2個(gè)二元變量中，兩個(gè)對(duì)象取不同狀態(tài)的個(gè)數(shù)。關(guān)于標(biāo)稱變量，兩個(gè)對(duì)象i，j之間的距離也常用它們的匹配系數(shù)來(lái)表示：d(i,j)=m3－g/m3，其中g(shù)為m3個(gè)標(biāo)稱變量中，兩個(gè)對(duì)象取相同狀態(tài)的個(gè)數(shù)。

(2)假定m個(gè)變量中，x1，…，xm1為連續(xù)型變量，xm15.2.3.2各類型變量分布函數(shù)的估計(jì)

對(duì)于分布函數(shù)的估計(jì)采用簡(jiǎn)單隨機(jī)取樣，設(shè)簡(jiǎn)單隨機(jī)樣本數(shù)據(jù)為ssimp。為了針對(duì)各類型變量給出各分布函數(shù)的估計(jì)，根據(jù)文獻(xiàn)[13]，有下列三條性質(zhì)：

性質(zhì)5.1（無(wú)偏估計(jì)性）（1）樣本均值xmean是總體均值Xmean的無(wú)偏估計(jì)量。（2）xtotal＝nxmean是總體總值Xtotal的無(wú)偏估計(jì)量。（3）樣本方差＝(xi-xmean)2/(ssimp-1)是總體方差：S＝(Xi-Xmean)2/(n-1)的無(wú)偏估計(jì)量。5.2.3.2各類型變量分布函數(shù)的估計(jì)對(duì)于分布函數(shù)的估計(jì)性質(zhì)5.2（關(guān)于各類型變量的近似分布性）(1)對(duì)于連續(xù)隨機(jī)變量x，其估計(jì)分布函數(shù)為近似正態(tài)分布N(xmena,sx2)。分布函數(shù)為：F（x）＝

性質(zhì)5.2（關(guān)于各類型變量的近似分布性）(2)對(duì)于二元變量x，設(shè)其狀態(tài)為0,1。所抽ssimp個(gè)樣本中，0狀態(tài)的個(gè)數(shù)為ssimp0，1狀態(tài)的個(gè)數(shù)為ssimp1。令p=ssimp0/ssimp,則其估計(jì)分布函數(shù)為：F（x）=(2)對(duì)于二元變量x，設(shè)其狀態(tài)為0,1。所抽ssimp個(gè)樣(3)對(duì)于標(biāo)稱變量x，設(shè)狀態(tài)為sta1,sta2,…,stat，分別被標(biāo)記為1,2，…,t。所抽樣本中各狀態(tài)出現(xiàn)的個(gè)數(shù)分別為ksta1,ksta2,…kstat，令pi=kstai/ssimp(i=1,2,…,t)。則其估計(jì)分布函數(shù)為：F(x)＝(3)對(duì)于標(biāo)稱變量x，設(shè)狀態(tài)為sta1,sta2,…,st性質(zhì)5.3

(抽樣數(shù)的確定)估計(jì)分布函數(shù)的簡(jiǎn)單隨機(jī)抽樣樣本個(gè)數(shù)ssimp由以下方法確定：ssimp=其中為標(biāo)準(zhǔn)正態(tài)分布的雙側(cè)分位數(shù)，r為相對(duì)誤差。性質(zhì)5.3(抽樣數(shù)的確定)估計(jì)分布函數(shù)的簡(jiǎn)單隨機(jī)抽樣樣本5.2.3.3Hash函數(shù)的構(gòu)造

SHF模型按如下步驟構(gòu)造Hash函數(shù)：對(duì)總體進(jìn)行簡(jiǎn)單隨機(jī)抽樣，抽樣針對(duì)每維變量進(jìn)行。按（5.1）（5.2）（5.3）式得到每維變量的近似分布，構(gòu)造Hash函數(shù)如下：H(x1,x2,…,xm)＝F(x1)F(x2)…F(xm)

（5.4）5.2.3.3Hash函數(shù)的構(gòu)造SHF模型按如下步驟構(gòu)以上方法實(shí)際上假定了各變量之間相互獨(dú)立。對(duì)于總體數(shù)據(jù)，若各變量之間存在復(fù)共線性情形，可采取因子分析法先將數(shù)據(jù)進(jìn)行轉(zhuǎn)化，消除其復(fù)共線性。其計(jì)算量為O（n）。命題5.2

x1,x2,…,xm

相互獨(dú)立時(shí)，H(x1,x2,…,xm)為變量X=(x1,x2,…,xm)的聯(lián)合分布函數(shù)。證明：由獨(dú)立隨機(jī)變量的聯(lián)合分布函數(shù)的性質(zhì)即知。以上方法實(shí)際上假定了各變量之間相互獨(dú)立。對(duì)于總體數(shù)據(jù)，若各變5.2.3.4分層取樣

SHF模型利用Hash函數(shù)對(duì)總體數(shù)據(jù)進(jìn)行分桶，亦即將數(shù)據(jù)進(jìn)行分層，然后針對(duì)各桶進(jìn)行簡(jiǎn)單隨機(jī)抽樣，從而實(shí)現(xiàn)分層抽樣。設(shè)按函數(shù)發(fā)現(xiàn)技術(shù)要求所需抽取的樣本數(shù)為slayer，將[0,1]slayer等分，slayer個(gè)等分點(diǎn)如下：0=i0,i1,i2,…,islayer-1,islayer=1，則iq-iq-1=1/slayer(q=1,2,…,slayer)將n個(gè)數(shù)據(jù)分到slayer個(gè)桶，分法如下：若第j行數(shù)據(jù)滿足：iq-1<=H(xj1,xj2,…,xjm)<iq(q=1,2,…slayer-1)iq-1<=H(xj1,xj2,…,xjm)<=iq(q=slayer)（5.5）則第j行屬于第q個(gè)桶。5.2.3.4分層取樣SHF模型利用Hash函數(shù)對(duì)總體數(shù)命題5.3（各桶中數(shù)據(jù)分布的特點(diǎn)）按上述分桶方法，各桶中數(shù)據(jù)的個(gè)數(shù)以概率1相同。證明：由命題5.2知，

H(x1,x2,…,xm)為變量X=(x1,x2,…,xm)的聯(lián)合分布函數(shù)，將n個(gè)點(diǎn)看作是分布在維數(shù)為m的超幾何體中。由于桶的劃分是按分布函數(shù)等概率來(lái)劃分的（注意，不是按超幾何體等體積劃分），即超幾何體被劃分為slayer個(gè)等概率空間，即slayer個(gè)等概率Hash桶，由概率函數(shù)的頻率意義知，各桶落入點(diǎn)的頻率應(yīng)該均為，因此，各桶中數(shù)據(jù)的個(gè)數(shù)以概率1相同。命題5.3（各桶中數(shù)據(jù)分布的特點(diǎn)）按上述分桶方法，各桶中數(shù)命題5.3保證了后面的基于Hash函數(shù)取樣技術(shù)在分層時(shí)，各層中數(shù)據(jù)個(gè)數(shù)接近，為保證抽樣質(zhì)量提供了理論依據(jù)。性質(zhì)5.4分層抽樣的精度優(yōu)于簡(jiǎn)單隨機(jī)抽樣，即分層抽樣的估計(jì)量方差小于簡(jiǎn)單隨機(jī)抽樣。命題5.3保證了后面的基于Hash函數(shù)取樣技術(shù)在分層時(shí)，各層5.2.3.5基于Hash函數(shù)取樣的數(shù)據(jù)預(yù)處理算法

SHF模型中的HSDPA(HashSamplingBasedDataPreprocessingAlgorithm)算法首先進(jìn)行簡(jiǎn)單隨機(jī)抽樣，估計(jì)分布函數(shù)，構(gòu)造出Hash函數(shù)，然后進(jìn)行基于Hash函數(shù)的分層抽樣，得到具有充分統(tǒng)計(jì)代表性的樣本。下面的算法5-4給出了計(jì)算過(guò)程的細(xì)節(jié)：5.2.3.5基于Hash函數(shù)取樣的數(shù)據(jù)預(yù)處理算法SHF算法5-4HSDPA算法輸入：n行m列混合類型數(shù)據(jù)，樣本個(gè)體數(shù)為slayer輸出：slayer行m列混合類型數(shù)據(jù)步驟：

BeginStep1針對(duì)各列進(jìn)行簡(jiǎn)單隨機(jī)抽樣；Step2根據(jù)（5.1）（5.2）（5.3）式估計(jì)各列分布函數(shù)；Step3根據(jù)（5.4）式構(gòu)造Hash函數(shù)H；Step4根據(jù)（5.5）式將n個(gè)個(gè)體分成slayer個(gè)桶；Stpe5隨機(jī)地從各桶抽取一個(gè)個(gè)體，組成一個(gè)樣本數(shù)為slayer的樣本；Step6End.算法5-4HSDPA算法命題5.4HSDPA算法的復(fù)雜度為O（n），即為關(guān)于n的線性時(shí)間。證明：顯然，HSDPA算法中m,k,ssimp,slayer<<n第1步代價(jià)為O(1)第2步代價(jià)為O(1)第3步代價(jià)為O(1)第4步代價(jià)為n第5代價(jià)為O(1)所以整個(gè)算法的代價(jià)為：O(n)即整個(gè)算法的復(fù)雜度是關(guān)于n的線性時(shí)間。HSDPA算法已被成功應(yīng)用于聚類分析方法中，參見(jiàn)文獻(xiàn)[15]。該文實(shí)驗(yàn)表明，HSPDA算法在聚類質(zhì)量下降很小的情況下，在數(shù)據(jù)集個(gè)數(shù)接近10000時(shí)，聚類效率比傳統(tǒng)算法提高2個(gè)數(shù)量級(jí)。命題5.4HSDPA算法的復(fù)雜度為O（n），即為關(guān)于n的5.2.3基于遺傳算法的預(yù)處理方法

遺傳算法是從某一隨機(jī)產(chǎn)生的或是特定的初始群體出發(fā)(父本)，進(jìn)行選擇、復(fù)制、交叉、變異等，不斷地進(jìn)行迭代計(jì)算，并根據(jù)每一個(gè)個(gè)體的適應(yīng)度值，優(yōu)勝劣汰，引導(dǎo)搜索過(guò)程向解逼近。遺傳算法的優(yōu)點(diǎn)：它直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，無(wú)需函數(shù)可導(dǎo)或連續(xù)，具有內(nèi)在的隱并行性和較好的全局尋優(yōu)能力，它以一定的概率進(jìn)行交叉和變異，采用了概率化的尋優(yōu)方法，能自動(dòng)獲取搜索過(guò)程中的有關(guān)知識(shí)并用于指導(dǎo)優(yōu)化，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。5.2.3基于遺傳算法的預(yù)處理方法

遺傳算法是從某一隨機(jī)產(chǎn)生遺傳算法的高效搜索能力可以用來(lái)進(jìn)行數(shù)據(jù)的聚類預(yù)處理，即把一條具有n個(gè)屬性的記錄看作是n維空間中的一個(gè)點(diǎn)，數(shù)據(jù)庫(kù)中的數(shù)據(jù)記錄就成為n維空間中的一組點(diǎn)群，這樣對(duì)樣本的聚類問(wèn)題就轉(zhuǎn)化為對(duì)點(diǎn)群的劃分或歸類問(wèn)題。遺傳算法的高效搜索能力可以用來(lái)進(jìn)行數(shù)據(jù)的聚類預(yù)處理，即把一條在用遺傳算法求解之前，有必要先對(duì)問(wèn)題的解空間進(jìn)行編碼。以交易數(shù)據(jù)庫(kù)為例，經(jīng)過(guò)預(yù)處理的目標(biāo)子集，由0，1形成了相應(yīng)的屬性值，所以可采用通常的二進(jìn)制編碼方法，編碼長(zhǎng)度取決于向量的維數(shù)，這是一個(gè)長(zhǎng)度固定的染色體編碼。遺傳算法中，自然選擇過(guò)程的模擬通常是采用評(píng)估函數(shù)和適應(yīng)度函數(shù)來(lái)實(shí)現(xiàn)的。在用遺傳算法求解之前，有必要先對(duì)問(wèn)題的解空間進(jìn)行編碼。以交易評(píng)估函數(shù)主要通過(guò)染色體優(yōu)劣的絕對(duì)值來(lái)評(píng)估，而適應(yīng)度則用來(lái)評(píng)估一個(gè)染色體相對(duì)于整個(gè)群體優(yōu)劣的相對(duì)值的大小。評(píng)估函數(shù)主要通過(guò)染色體優(yōu)劣的絕對(duì)值來(lái)評(píng)估，而適應(yīng)度則用來(lái)評(píng)估通常的遺傳算子主要有選擇、交叉和變異。

其中，選擇算子指按照一定的策略從父代中選出個(gè)體進(jìn)入中間群體；交叉算子指隨機(jī)地從群體中抽取兩個(gè)個(gè)體，并按照某種交叉策略使兩個(gè)個(gè)體互相交換部分染色體碼串，形成兩個(gè)新的個(gè)體，可采用兩點(diǎn)交叉或多點(diǎn)交叉策略；變異算子指按一定的概率，改變?nèi)旧w中的某些位的值。數(shù)據(jù)預(yù)處理課件標(biāo)準(zhǔn)遺傳算法的形式化描述為

，SGA是一個(gè)八元組SGA=(C,E,P0,M,Φ,Γ,Ψ,T)，其中，C為個(gè)體的編碼方法，E為個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，P0為初始群體，M為群體規(guī)模，Φ

為選擇算子，Γ為交叉算子，Ψ

為變異算子，T為遺傳算法的終止條件。遺傳算法一般分為兩個(gè)階段，首先從初始群體開(kāi)始，通過(guò)選擇生成中間群體，然后在中間群體上進(jìn)行交叉與變異，以形成下一代的群體。標(biāo)準(zhǔn)遺傳算法的形式化描述為，SGA是一個(gè)八元組SGA=(算法5-5基于遺傳算法的特征子集選取算法

輸入：置迭代次數(shù)為0,隨機(jī)生成初始群體；輸出：優(yōu)化的特征子集，優(yōu)化的子群體。步驟：

BeginStep1置迭代次數(shù)為0,隨機(jī)生成初始群體；Step2IFT終止條件滿足

ThenEnd；Step3計(jì)算當(dāng)前群體中各個(gè)體的適應(yīng)度；Step4由各個(gè)體適應(yīng)度選擇生成中間群體；Step5以概率Pc選擇個(gè)體進(jìn)行交叉，產(chǎn)生的新個(gè)體替換老個(gè)體，加入到中間群體中；Step6以概率Pm選擇個(gè)體對(duì)其某一位進(jìn)行變異，產(chǎn)生新個(gè)體替換老個(gè)體，并加入到中間群體中；Step7轉(zhuǎn)Step2。End.算法5-5基于遺傳算法的特征子集選取算法5.2.4基于神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理方法

人工神經(jīng)網(wǎng)絡(luò)（artificialneuralnetwork，簡(jiǎn)稱ANN）是在對(duì)大腦的生理研究的基礎(chǔ)上，用模擬生物神經(jīng)元的某些基本功能元件（即人工神經(jīng)元），按各種不同的聯(lián)結(jié)方式組成的一個(gè)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)(NeuralNetwork)的學(xué)習(xí)結(jié)果為目標(biāo)函數(shù)，根據(jù)這個(gè)目標(biāo)函數(shù)的輸出作為分類的依據(jù)。輸入即為文本在各個(gè)特征上的各分量值。5.2.4基于神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理方法人工神經(jīng)網(wǎng)絡(luò)（arti神經(jīng)網(wǎng)絡(luò)實(shí)際上是一組連接的輸入/輸出單元，其中每一個(gè)連接都具有一定的權(quán)值。通過(guò)訓(xùn)練集來(lái)訓(xùn)練的過(guò)程就是調(diào)整這些權(quán)值的過(guò)程，使得神經(jīng)網(wǎng)絡(luò)可以正確的預(yù)測(cè)類別。神經(jīng)網(wǎng)絡(luò)的訓(xùn)練是針對(duì)訓(xùn)練例逐個(gè)進(jìn)行的，所以神經(jīng)網(wǎng)絡(luò)的訓(xùn)練集可以隨時(shí)添加，不需要重新進(jìn)行訓(xùn)練就可完成網(wǎng)絡(luò)的調(diào)整。神經(jīng)網(wǎng)絡(luò)實(shí)際上是一組連接的輸入/輸出單元，其中每一個(gè)連接都具同時(shí)有實(shí)驗(yàn)結(jié)果表明，在訓(xùn)練例過(guò)少的情況下，神經(jīng)網(wǎng)絡(luò)的分類準(zhǔn)確率較低。因?yàn)榭赏ㄟ^(guò)訓(xùn)練來(lái)針對(duì)特征取一定的合適的權(quán)值，神經(jīng)網(wǎng)絡(luò)可以較好地抵御噪音的干擾。

因此有必要建立“白化”機(jī)制，用規(guī)則解釋網(wǎng)絡(luò)的權(quán)值矩陣，為決策支持和數(shù)據(jù)挖掘提供說(shuō)明。同時(shí)有實(shí)驗(yàn)結(jié)果表明，在訓(xùn)練例過(guò)少的情況下，神經(jīng)網(wǎng)絡(luò)的分類準(zhǔn)確通常有兩種解決方法：方法一，建立一個(gè)基于規(guī)則的系統(tǒng)輔助。神經(jīng)網(wǎng)絡(luò)運(yùn)行的同時(shí)，將其輸入和輸出模式給基于規(guī)則的系統(tǒng)，然后用反向關(guān)聯(lián)完成網(wǎng)絡(luò)的推理過(guò)程，這種方法把網(wǎng)絡(luò)的運(yùn)行過(guò)程和解釋過(guò)程用兩套系統(tǒng)實(shí)現(xiàn)，開(kāi)銷大，不夠靈活；方法二，直接從訓(xùn)練好的網(wǎng)絡(luò)中提取(分類)規(guī)則。這是當(dāng)前數(shù)據(jù)挖掘使用得比較多的方法。通常有兩種解決方法：網(wǎng)絡(luò)中的采掘規(guī)則，主要有兩種：網(wǎng)絡(luò)結(jié)構(gòu)分解的規(guī)則提取和由神經(jīng)網(wǎng)絡(luò)的非線性映射關(guān)系提取規(guī)則。其中，網(wǎng)絡(luò)結(jié)構(gòu)分解的規(guī)則提取以神經(jīng)網(wǎng)絡(luò)的隱層結(jié)點(diǎn)和輸出層結(jié)點(diǎn)為研究對(duì)象，把整個(gè)網(wǎng)絡(luò)分解為許多單層子網(wǎng)的組合。研究較簡(jiǎn)單的子網(wǎng)，便于從中挖掘知識(shí)。網(wǎng)絡(luò)中的采掘規(guī)則，主要有兩種：對(duì)于大規(guī)模網(wǎng)絡(luò)，在提取規(guī)則前，需要對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行剪枝和刪除冗余結(jié)點(diǎn)等預(yù)處理工作。而由神經(jīng)網(wǎng)絡(luò)的非線性映射關(guān)系提取規(guī)則直接從網(wǎng)絡(luò)輸入和輸出層數(shù)據(jù)入手，不考慮網(wǎng)絡(luò)的隱層結(jié)構(gòu)，避免基于結(jié)構(gòu)分解的規(guī)則提取算法的不足。對(duì)于大規(guī)模網(wǎng)絡(luò)，在提取規(guī)則前，需要對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行剪枝和刪除冗組織特征映射神經(jīng)網(wǎng)絡(luò)(SOFM)

自組織特征映射神經(jīng)網(wǎng)絡(luò)(SOFM)是一種典型的自適應(yīng)聚類分析技術(shù)。SOFM是一個(gè)動(dòng)態(tài)系統(tǒng)，它利用低維空間的表示學(xué)習(xí)拓?fù)浣Y(jié)構(gòu)并提取高維輸入向量中的結(jié)構(gòu)。這種表示代替了輸入向量的全局的概率密度。設(shè)有n個(gè)樣本，SOFM網(wǎng)絡(luò)訓(xùn)練算法如下：組織特征映射神經(jīng)網(wǎng)絡(luò)(SOFM)算法5-6

SOFM算法

輸入：初始化輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)的連接權(quán)值,并置時(shí)間t=0,i=0；輸入模式向量。輸出：輸出結(jié)點(diǎn)

所連接的權(quán)向量及幾何鄰域

內(nèi)結(jié)點(diǎn)所連接的權(quán)值:

算法5-6SOFM算法步驟：BeginStep1初始化輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)的連接權(quán)值,并置時(shí)間t=0,i=0。Step2輸入模式向量；Step3計(jì)算輸入與全部輸出結(jié)點(diǎn)所連接權(quán)向量

的距離:Step4具有最小距離的結(jié)點(diǎn)為競(jìng)爭(zhēng)獲勝結(jié)點(diǎn)

Step5調(diào)整輸出結(jié)點(diǎn)

所連接的權(quán)向量及幾何鄰域

內(nèi)結(jié)點(diǎn)所連接的權(quán)值:Step6i=i+1，t=t+1,IF

i≤nThenStep2

End步驟：算法中，

表示學(xué)習(xí)速度是可變的，隨時(shí)間而衰減，即隨著訓(xùn)練次數(shù)的增加，權(quán)值調(diào)整幅度逐漸減小，以使獲勝結(jié)點(diǎn)所連接的權(quán)向量能代表模式的本質(zhì)屬性。借助SOFM網(wǎng)絡(luò)，可將歸納數(shù)據(jù)庫(kù)中的樣本數(shù)據(jù)(一般仍為高維數(shù)據(jù))按數(shù)據(jù)分布聚類到低維空間，這也體現(xiàn)了一種數(shù)據(jù)降維操作，可以形成相應(yīng)的目標(biāo)數(shù)據(jù)子集。

算法中，表示學(xué)習(xí)速度是可變的，隨時(shí)間而5.2.5Web挖掘數(shù)據(jù)預(yù)處理方法

Web使用挖掘由3個(gè)階段構(gòu)成:數(shù)據(jù)預(yù)處理模式發(fā)現(xiàn)模式分析5.2.5Web挖掘數(shù)據(jù)預(yù)處理方法Web使用挖掘由3個(gè)階段算法5-7

WLP會(huì)話識(shí)別算法輸入：給出θ的會(huì)話溢出時(shí)間和會(huì)話總數(shù)；輸出：會(huì)話集si。步驟：

Begin(1)θ表示會(huì)話的溢出時(shí)間。算法5-7WLP會(huì)話識(shí)別算法(2)fori=1tondoA、；//確定使用者活動(dòng)列表Li的會(huì)話總數(shù)；B、；

C、form=1todo//m表示第m個(gè)會(huì)話；i.；//找出最接近閾值的請(qǐng)求時(shí)間函數(shù)；ii.將tm加入到ti；iii.tstart=tm；D、

依據(jù)將

Li轉(zhuǎn)存為會(huì)話列表si；

End(2)fori=1tondo函數(shù)中的代表已知列表的起始點(diǎn)，為已知列表的終點(diǎn)，表示要查找的記錄參考時(shí)間，即等于它或小于它的最近的記錄。其結(jié)果是返回一條記錄的位置，標(biāo)示出會(huì)話的終點(diǎn)，或下一會(huì)話的起點(diǎn)。函數(shù)例如：從某實(shí)驗(yàn)室的Web服務(wù)器3天的日志作為會(huì)話的數(shù)據(jù)，數(shù)據(jù)大小是145MB。其中，θ的會(huì)話溢出時(shí)間為30min，會(huì)話總數(shù)47631,原始Web日志中項(xiàng)數(shù)為572614，數(shù)據(jù)清洗后項(xiàng)數(shù)為85892例如：從某實(shí)驗(yàn)室的Web服務(wù)器3天的日志作為會(huì)話的數(shù)據(jù)，數(shù)據(jù)

謝謝

數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典元昌安主編鄧松李文敬劉海濤編著電子工業(yè)出版社數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典第5章數(shù)據(jù)預(yù)處理

本章包括：

數(shù)據(jù)預(yù)處理基本功能數(shù)據(jù)預(yù)處理的方法第5章數(shù)據(jù)預(yù)處理

本章包括：數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但有潛在的有用信息和知識(shí)的過(guò)程。數(shù)據(jù)挖掘：為企業(yè)決策者提供重要的、有價(jià)值的信息或知識(shí)，從而為企業(yè)帶來(lái)不可估量的經(jīng)濟(jì)效益。數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中數(shù)據(jù)挖掘過(guò)程一般包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘以及知識(shí)評(píng)價(jià)和呈現(xiàn)。在一個(gè)完整的數(shù)據(jù)挖掘過(guò)程中，數(shù)據(jù)預(yù)處理要花費(fèi)60%左右的時(shí)間，而后的挖掘工作僅占總工作量的10%左右。

目前對(duì)數(shù)據(jù)挖掘的研究主要集中于挖掘技術(shù)、挖掘算法、挖掘語(yǔ)言等。數(shù)據(jù)挖掘過(guò)程一般包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘以數(shù)據(jù)挖掘的必要性：在海量的原始數(shù)據(jù)中，存在著大量雜亂的、重復(fù)的、不完整的數(shù)據(jù)，嚴(yán)重影響到數(shù)據(jù)挖掘算法的執(zhí)行效率，甚至可能導(dǎo)致挖掘結(jié)果的偏差。數(shù)據(jù)預(yù)處理課件數(shù)據(jù)預(yù)處理分類：從對(duì)不同的源數(shù)據(jù)進(jìn)行預(yù)處理的功能來(lái)分，數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換、數(shù)據(jù)歸約等4個(gè)基本功能。在實(shí)際的數(shù)據(jù)預(yù)處理過(guò)程中，

這4種功能不一定都用到，而且，它們的使用也沒(méi)有先后順序，

某一種預(yù)處理可能先后要多次進(jìn)行。數(shù)據(jù)預(yù)處理分類：從數(shù)據(jù)預(yù)處理所采用的技術(shù)和方法來(lái)分：

基本粗集理論的簡(jiǎn)約方法；復(fù)共線性數(shù)據(jù)預(yù)處理方法；基于Hash函數(shù)取樣的數(shù)據(jù)預(yù)處理方法；基于遺傳算法數(shù)據(jù)預(yù)處理方法；基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)預(yù)處理方法；Web挖掘的數(shù)據(jù)預(yù)處理方法等等。數(shù)據(jù)預(yù)處理課件5.1數(shù)據(jù)預(yù)處理基本功能

在數(shù)據(jù)挖掘整體過(guò)程中,海量的原始數(shù)據(jù)中存在著大量雜亂的、重復(fù)的、不完整的數(shù)據(jù)，嚴(yán)重影響到數(shù)據(jù)挖掘算法的執(zhí)行效率，甚至可能導(dǎo)致挖掘結(jié)果的偏差。為此，在數(shù)據(jù)挖掘算法執(zhí)行之前，必須對(duì)收集到的原始數(shù)據(jù)進(jìn)行預(yù)處理，以改進(jìn)數(shù)據(jù)的質(zhì)量，提高數(shù)據(jù)挖掘過(guò)程的效率、精度和性能。數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換與數(shù)據(jù)歸約等技術(shù)。5.1數(shù)據(jù)預(yù)處理基本功能在數(shù)據(jù)挖掘整體過(guò)程中,海量的原始數(shù)5.1.1數(shù)據(jù)清理

數(shù)據(jù)清理要去除源數(shù)據(jù)集中的噪聲數(shù)據(jù)和無(wú)關(guān)數(shù)據(jù)，處理遺漏數(shù)據(jù)和清洗臟數(shù)據(jù)、空缺值，

識(shí)別刪除孤立點(diǎn)等。5.1.1數(shù)據(jù)清理數(shù)據(jù)清理要去除源數(shù)據(jù)集中的噪聲數(shù)據(jù)和無(wú)5.1.1.1噪聲數(shù)據(jù)處理

噪聲是一個(gè)測(cè)量變量中的隨機(jī)錯(cuò)誤或偏差，包括錯(cuò)誤的值或偏離期望的孤立點(diǎn)值。對(duì)于噪聲數(shù)據(jù)有如下幾種處理方法：分箱法聚類法識(shí)別孤立點(diǎn)回歸

5.1.1.1噪聲數(shù)據(jù)處理噪聲是一個(gè)測(cè)量變量中的隨機(jī)5.1.1.2空缺值的處理

目前最常用的方法是使用最可能的值填充空缺值，

如用一個(gè)全局常量替換空缺值、使用屬性的平均值填充空缺值或?qū)⑺性M按某些屬性分類，

然后用同一類中屬性的平均值填充空缺值。例5.2：一個(gè)公司職員平均工資收入為3000元，則使用該值替換工資中“基本工資”屬性中的空缺值。

5.1.1.2空缺值的處理目前最常用的方法是使用最可能的值5.1.1.3清洗臟數(shù)據(jù)

異構(gòu)數(shù)據(jù)源數(shù)據(jù)庫(kù)中的數(shù)據(jù)并不都是正確的，常常不可避免地存在著不完整、不一致、不精確和重復(fù)的數(shù)據(jù)，這些數(shù)據(jù)統(tǒng)稱為“臟數(shù)據(jù)”。臟數(shù)據(jù)能使挖掘過(guò)程陷入混亂，導(dǎo)致不可靠的輸出。

5.1.1.3清洗臟數(shù)據(jù)異構(gòu)數(shù)據(jù)源數(shù)據(jù)庫(kù)中的數(shù)據(jù)并不都是正清洗臟數(shù)據(jù)可采用下面的方式：手工實(shí)現(xiàn)方式用專門編寫的應(yīng)用程序采用概率統(tǒng)計(jì)學(xué)原理查找數(shù)值異常的記錄對(duì)重復(fù)記錄的檢測(cè)與刪除清洗臟數(shù)據(jù)可采用下面的方式：5.1.2.1實(shí)體識(shí)別問(wèn)題

在數(shù)據(jù)集成時(shí)，來(lái)自多個(gè)數(shù)據(jù)源的現(xiàn)實(shí)世界的實(shí)體有時(shí)并不一定是匹配的，例如：數(shù)據(jù)分析者如何才能確信一個(gè)數(shù)據(jù)庫(kù)中的student_id和另一個(gè)數(shù)據(jù)庫(kù)中的stu_id值是同一個(gè)實(shí)體。通常，可根據(jù)數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)的元數(shù)據(jù)來(lái)區(qū)分模式集成中的錯(cuò)誤。5.1.2.1實(shí)體識(shí)別問(wèn)題在數(shù)據(jù)集成時(shí)，來(lái)自多個(gè)數(shù)據(jù)5.1.2.2冗余問(wèn)題

數(shù)據(jù)集成往往導(dǎo)致數(shù)據(jù)冗余，如同一屬性多次出現(xiàn)、同一屬性命名不一致等，對(duì)于屬性間冗余可以用相關(guān)分析檢測(cè)到，然后刪除。

5.1.2.2冗余問(wèn)題5.1.2.3數(shù)據(jù)值沖突檢測(cè)與處理

對(duì)于現(xiàn)實(shí)世界的同一實(shí)體，來(lái)自不同數(shù)據(jù)源的屬性值可能不同。這可能是因?yàn)楸硎?、比例或編碼、數(shù)據(jù)類型、單位不統(tǒng)一、字段長(zhǎng)度不同。5.1.2.3數(shù)據(jù)值沖突檢測(cè)與處理5.1.3數(shù)據(jù)變換

數(shù)據(jù)變換主要是找到數(shù)據(jù)的特征表示，用維變換或轉(zhuǎn)換方法減少有效變量的數(shù)目或找到數(shù)據(jù)的不變式，包括規(guī)格化、歸約、切換、旋轉(zhuǎn)和投影等操作。規(guī)格化是指將元組集按規(guī)格化條件進(jìn)行合并，也就是屬性值量綱的歸一化處理。5.1.3數(shù)據(jù)變換數(shù)據(jù)變換主要是找到數(shù)據(jù)的特征表示，用維規(guī)格化條件定義了屬性的多個(gè)取值到給定虛擬值的對(duì)應(yīng)關(guān)系。對(duì)于不同的數(shù)值屬性特點(diǎn)，一般可以分為取值連續(xù)和取值分散的數(shù)值屬性規(guī)格化問(wèn)題。規(guī)格化條件定義了屬性的多個(gè)取值到給定虛擬值的對(duì)應(yīng)關(guān)系。對(duì)于不歸約指將元組按語(yǔ)義層次結(jié)構(gòu)合并。語(yǔ)義層次結(jié)構(gòu)定義了元組屬性值之間的語(yǔ)義關(guān)系。規(guī)格化和歸約能大量減少元組個(gè)數(shù)，提高計(jì)算效率。同時(shí)，規(guī)格化和歸約過(guò)程提高了知識(shí)發(fā)現(xiàn)的起點(diǎn)，使得一個(gè)算法能夠發(fā)現(xiàn)多層次的知識(shí)，適應(yīng)不同應(yīng)用的需要。歸約指將元組按語(yǔ)義層次結(jié)構(gòu)合并。語(yǔ)義層次結(jié)構(gòu)定義了元組屬性值5.1.4數(shù)據(jù)歸約

數(shù)據(jù)歸約是將數(shù)據(jù)庫(kù)中的海量數(shù)據(jù)進(jìn)行歸約，歸約之后的數(shù)據(jù)仍接近于保持原數(shù)據(jù)的完整性，但數(shù)據(jù)量相對(duì)小得多，這樣進(jìn)行數(shù)據(jù)挖掘的性能和效率會(huì)得到很大提高。數(shù)據(jù)歸約的策略主要有數(shù)據(jù)立方體聚集、維歸約、數(shù)據(jù)壓縮、數(shù)值壓縮、離散化和概念分層。5.1.4數(shù)據(jù)歸約數(shù)據(jù)歸約是將數(shù)據(jù)庫(kù)中的海量數(shù)據(jù)進(jìn)行歸約5.1.4.1維歸約

通過(guò)刪除不相關(guān)的屬性(或維)減少數(shù)據(jù)量，不僅壓縮了數(shù)據(jù)集，還減少了出現(xiàn)在發(fā)現(xiàn)模式上的屬性數(shù)目，通常采用屬性子集選擇方法找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布。

5.1.4.1維歸約通過(guò)刪除不相關(guān)的屬性(或維)減少5.1.4.2數(shù)據(jù)壓縮

數(shù)據(jù)壓縮分為無(wú)損壓縮和有損壓縮，比較流行和有效的有損數(shù)據(jù)壓縮方法是小波變換和主要成分分析。小波變換對(duì)于稀疏或傾斜數(shù)據(jù)以及具有有序?qū)傩缘臄?shù)據(jù)有很好的壓縮結(jié)果。5.1.4.2數(shù)據(jù)壓縮數(shù)據(jù)壓縮分為無(wú)損壓縮和有損壓縮，比較5.1.4.3數(shù)值歸約

數(shù)值歸約通過(guò)選擇替代的、較小的數(shù)據(jù)表示形式來(lái)減少數(shù)據(jù)量。

數(shù)值歸約技術(shù)可以是有參的，也可以是無(wú)參的。有參方法是使用一個(gè)模型來(lái)評(píng)估數(shù)據(jù)，只需存放參數(shù)，而不需要存放實(shí)際數(shù)據(jù)。有參的數(shù)值歸約技術(shù)有以下兩種，回歸：線性回歸和多元回歸；對(duì)數(shù)線性模型：近似離散屬性集中的多維概率分布。5.1.4.3數(shù)值歸約數(shù)值歸約通過(guò)選擇替代的、較小的數(shù)據(jù)無(wú)參的數(shù)值歸約技術(shù)有3種：直方圖聚類選樣無(wú)參的數(shù)值歸約技術(shù)有3種：5.1.4.4概念分層

概念分層通過(guò)收集并用較高層的概念替換較低層的概念來(lái)定義數(shù)值屬性的一個(gè)離散化。概念分層可以用來(lái)歸約數(shù)據(jù)，通過(guò)這種概化盡管細(xì)節(jié)丟失了，但概化后的數(shù)據(jù)更有意義、更容易理解，并且所需的空間比原數(shù)據(jù)少。對(duì)于數(shù)值屬性，由于數(shù)據(jù)的可能取值范圍的多樣性和數(shù)據(jù)值的更新頻繁，說(shuō)明概念分層是困難的。5.1.4.4概念分層概念分層通過(guò)收集并用較高層的概念數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)的分布分析自動(dòng)地構(gòu)造，如用分箱、直方圖分析、聚類分析、基于熵的離散化和自然劃分分段等技術(shù)生成數(shù)值概念分層。由用戶專家在模式級(jí)顯示地說(shuō)明屬性的部分序或全序，從而獲得概念的分層；只說(shuō)明屬性集，但不說(shuō)明它們的偏序，由系統(tǒng)根據(jù)每個(gè)屬性不同值的個(gè)數(shù)產(chǎn)生屬性序，自動(dòng)構(gòu)造有意義的概念分層。數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)的分布分析自動(dòng)地構(gòu)造，5.2數(shù)據(jù)預(yù)處理的方法

數(shù)據(jù)預(yù)處理方法就是根據(jù)不同的挖掘問(wèn)題采用相應(yīng)的理論和技術(shù)，實(shí)現(xiàn)數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換、數(shù)據(jù)歸約等基本功能。預(yù)處理方法很多，在此介紹常用的幾種方法。5.2數(shù)據(jù)預(yù)處理的方法數(shù)據(jù)預(yù)處理方法就是根據(jù)不同的挖掘問(wèn)題5.2.1基于粗集理論的簡(jiǎn)約方法

粗糙集理論是一種研究不精確、不確定性知識(shí)的數(shù)學(xué)工具，可以對(duì)數(shù)據(jù)屬性進(jìn)行十分有效的精簡(jiǎn)，求出最小約簡(jiǎn)集，是數(shù)據(jù)預(yù)處理一種有效的方法。5.2.1基于粗集理論的簡(jiǎn)約方法粗糙集理論是一種研究不數(shù)據(jù)一般存在信息的含糊性問(wèn)題。粗糙集理論的最大特點(diǎn)是無(wú)需提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息。數(shù)據(jù)一般存在信息的含糊性問(wèn)題。

粗糙集理論的基本思路是利用定義在數(shù)據(jù)集合U上的等價(jià)關(guān)系對(duì)U進(jìn)行劃分，對(duì)于數(shù)據(jù)表來(lái)說(shuō)，這種等價(jià)關(guān)系可以是某個(gè)屬性，或者是幾個(gè)屬性的集合。因此按照不同屬性的組合就把數(shù)據(jù)表劃分成不同的基本類，在這些基本類的基礎(chǔ)上進(jìn)一步求得最小約簡(jiǎn)集。

例如：表5.1優(yōu)秀人才決策表給出了某部門的員工數(shù)據(jù)記錄集，通過(guò)對(duì)員工的政治表現(xiàn)、工作能力、科研能力等確定優(yōu)秀人才人選。論域U

條件屬性（C）

決策屬性

政治表現(xiàn)（C1）工作能力（C2）

科研能力（C3）

優(yōu)秀人才（D）

e1優(yōu)秀強(qiáng)強(qiáng)是e2良好一般一般否e3一般差差否e4一般一般一般否e5良好強(qiáng)一般否e6優(yōu)秀強(qiáng)強(qiáng)是其中：條件屬性集為C＝{政治表現(xiàn)，工作能力，科研能力}，決策屬性集為D＝{優(yōu)秀人才}。

例如：表5.1優(yōu)秀人才決策表給出了某部門的員工數(shù)據(jù)記錄集，根據(jù)粗糙集理論對(duì)表5.1進(jìn)行離散化后再進(jìn)行數(shù)據(jù)預(yù)處理。處理過(guò)程分兩個(gè)步驟進(jìn)行，一是對(duì)決策表?xiàng)l件屬性集進(jìn)行約簡(jiǎn)求核；二是對(duì)條件屬性值進(jìn)行約簡(jiǎn)。具體求解步驟可見(jiàn)第11章相關(guān)內(nèi)容。根據(jù)粗糙集理論對(duì)表5.1進(jìn)行離散化后再進(jìn)行數(shù)據(jù)預(yù)處理?；诖植诩碚摰臄?shù)據(jù)預(yù)處理具有優(yōu)點(diǎn)：第一，數(shù)據(jù)挖掘的對(duì)象一般都是通過(guò)觀測(cè)、試驗(yàn)、調(diào)查得到的數(shù)據(jù)，通過(guò)觀測(cè)、試驗(yàn)、調(diào)查等得到的數(shù)據(jù)存在著冗余、雜亂、不完整等因素，采用粗糙集理論進(jìn)行數(shù)據(jù)預(yù)處理，不需要預(yù)先知道額外的信息，有利于集中精力解決問(wèn)題；基于粗糙集理論的數(shù)據(jù)預(yù)處理具有優(yōu)點(diǎn)：第二，算法簡(jiǎn)單。對(duì)于給定的決策表，預(yù)處理過(guò)程所使用的算法可以是分辨矩陣或逐個(gè)屬性、逐條規(guī)則進(jìn)行檢驗(yàn)，算法簡(jiǎn)單，易于計(jì)算機(jī)的實(shí)現(xiàn)，方便挖掘系統(tǒng)的自動(dòng)操作；第三，可以有效地去除冗余的屬性或?qū)傩缘闹?。第二，算法?jiǎn)單。對(duì)于給定的決策表，預(yù)處理過(guò)程所使用的算法可以5.2.2復(fù)共線性數(shù)據(jù)的預(yù)處理方法

常規(guī)方法進(jìn)行函數(shù)發(fā)現(xiàn)時(shí)一般要作出一個(gè)假設(shè)：數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)。而傳統(tǒng)的函數(shù)發(fā)現(xiàn)算法中，常常忽略對(duì)數(shù)據(jù)是否滿足該假設(shè)的檢驗(yàn)。若數(shù)據(jù)不滿足統(tǒng)計(jì)不相關(guān)的假設(shè)（也稱數(shù)據(jù)變量之間存在復(fù)共線性），在這種情況下，函數(shù)發(fā)現(xiàn)算法挖掘出來(lái)的函數(shù)關(guān)系表達(dá)式可能會(huì)存在系統(tǒng)誤差，該表達(dá)式將不是我們要發(fā)現(xiàn)的理想函數(shù)。5.2.2復(fù)共線性數(shù)據(jù)的預(yù)處理方法常規(guī)方法進(jìn)行函數(shù)發(fā)現(xiàn)時(shí)一為解決該問(wèn)題，本節(jié)給出ε－復(fù)共線性的概念，然后給出不滿足不相關(guān)假設(shè)的情況下進(jìn)行數(shù)據(jù)預(yù)處理的算法ε－MDPA（ε－MulticollinearityDataPreprocessingAlgorithm復(fù)共線性數(shù)據(jù)預(yù)處理算法）。為解決該問(wèn)題，本節(jié)給出ε－復(fù)共線性的概念，然后給出不滿足不相5.2.2.1.相關(guān)概念假定給定的樣本數(shù)據(jù)為Y、X，其中因變量樣本數(shù)據(jù)矩陣Y=(y1,y2,…,yn)是p×n樣本矩陣，即p個(gè)因變量，n個(gè)樣本；自變量樣本數(shù)據(jù)矩陣X是q×n矩陣，即q個(gè)自變量，n個(gè)樣本。在實(shí)際計(jì)算時(shí)，X一般是將原始數(shù)據(jù)中心化后得到的樣本矩陣，即：X×1n＝0。5.2.2.1.相關(guān)概念假定給定的樣本數(shù)據(jù)為Y、X，其中因變?cè)谝话愕暮瘮?shù)發(fā)現(xiàn)算法中，自變量樣本數(shù)據(jù)矩陣X需要數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，也即X各行之間不能存在線性關(guān)系。而實(shí)際上，只要矩陣X的行向量之間存在近似線性關(guān)系時(shí)，函數(shù)發(fā)現(xiàn)算法就有可能達(dá)不到實(shí)用的效果。為此，下面我們給出ε－復(fù)共線性的定義，并對(duì)滿足這一定義的數(shù)據(jù)給出數(shù)據(jù)預(yù)處理的算法(ε－MDPA)。在一般的函數(shù)發(fā)現(xiàn)算法中，自變量樣本數(shù)據(jù)矩陣X需要數(shù)據(jù)滿足統(tǒng)計(jì)定義5.1（ε－復(fù)共線性）給定矩陣X，設(shè)X′為X的轉(zhuǎn)置矩陣，設(shè)矩陣（XX′）n×n的特征根為λ1,λ2,…,λn,若對(duì)預(yù)設(shè)的正數(shù)ε，0＜ε＜0.1，有max(λi,i=1,…,n)/min(λi,i=1,…,n)>1/ε，則稱矩陣X滿足ε－復(fù)共線性。定義5.1（ε－復(fù)共線性）給定矩陣X，設(shè)X′為X的轉(zhuǎn)置矩陣，ε－復(fù)共線性描述了最大特征根和最小特征根之間的差距，當(dāng)ε足夠小時(shí)，XX′至少有一個(gè)特征根接近于0，這時(shí)，X的行向量之間存在著近似的線性關(guān)系，從而描述了數(shù)據(jù)之間的相關(guān)程度。ε用于控制X各行向量之間的相關(guān)程度，當(dāng)其線性關(guān)系達(dá)到用戶指定的程度，那么，該組數(shù)據(jù)在進(jìn)行函數(shù)發(fā)現(xiàn)之前應(yīng)該進(jìn)行轉(zhuǎn)換預(yù)處理。ε－復(fù)共線性描述了最大特征根和最小特征根之間的差距，當(dāng)ε足夠5.2.2.2.ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法

本小節(jié)主要討論存在著ε－復(fù)共線性的數(shù)據(jù)矩陣X數(shù)據(jù)預(yù)處理的方法。5.2.2.2.ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法本小節(jié)主要討論存算法思路：為消除數(shù)據(jù)的復(fù)共線性使數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，需對(duì)矩陣X作主成分分析，計(jì)算出主向量矩陣Z，矩陣Z的各行向量之間是滿足統(tǒng)計(jì)不相關(guān)假設(shè)的。于是，在后繼的函數(shù)發(fā)現(xiàn)算法中，將挖掘Y與Z的關(guān)系，然后再利用X與Z的關(guān)系，得到Y(jié)與X之間的關(guān)系表達(dá)式。算法思路：為消除數(shù)據(jù)的復(fù)共線性使數(shù)據(jù)滿足統(tǒng)計(jì)不相關(guān)假設(shè)，需對(duì)下面的ε－復(fù)共線性數(shù)據(jù)預(yù)處理算法描述了存在ε－復(fù)共線性數(shù)據(jù)的轉(zhuǎn)換方法。數(shù)據(jù)預(yù)處理課件算法5-1

ε－MDPA(ε－MulticollinearityDataPreprocessingAlgorithm)輸入：q×n矩陣

X，控制值ε輸出：Z(轉(zhuǎn)換后消除復(fù)共線性的數(shù)據(jù)矩陣)步驟：BeginStep1計(jì)算XX′的特征值λ1,λ2,…,λq，并按從大到小順序排序；Step2判斷數(shù)據(jù)矩陣X具有ε－復(fù)共線性。End.

算法的偽代碼如下：EC（X）//計(jì)算XX′的特征值λ1,λ2,…,λq，并按從大到小順序排序；IFλ1/λq>1/ε//數(shù)據(jù)矩陣X具有ε－復(fù)共線性

PCMC(Xq×n，λ1,λ2,…,λq，t)//主分量矩陣計(jì)算ELSEZ=X；ENDIF算法5-1ε－MDPA(ε－Multicollineari算法3-1的計(jì)算代價(jià)主要在第1行計(jì)算特征值過(guò)程和第3行主分量矩陣計(jì)算過(guò)程，分別由下面的算法5-2和算法5-3實(shí)現(xiàn)。算法3-1的計(jì)算代價(jià)主要在第1行計(jì)算特征值過(guò)程和第3行主分量算法5-2

EC(EigenvalueCompute特征值計(jì)算子程序)輸入：q×n矩陣

X輸出：特征值λ1，λ2，…，λq，并按從大到小順序排序和特征向量矩陣Eigenvalue(q,q)步驟：BeginStep1

計(jì)算相關(guān)系數(shù)矩陣CorMatrix（q,q）；Step2利用雅可比法計(jì)算矩陣CorMatrix（q,q）的特征值；Step3判斷上三角元素是否全部滿足設(shè)定值；Step4將特征值、特征向量按照特征值的大小進(jìn)行排序得到特征值向量lpt[q]和特征向量矩陣EigenVector[q,q]。End.算法5-2EC(EigenvalueCompute特征值算法的偽代碼如下：Begin計(jì)算相關(guān)系數(shù)矩陣CorMatrix（q,q）；利用雅可比法計(jì)算矩陣CorMatrix（q,q）的特征值；Eigenvalue[i,j]=CorMatrix[i,j],(i,j=1,2,…,q)；l=0;//定義計(jì)數(shù)變量while(l<(q*(q-1))/2)//判斷上三角元素是否全部滿足設(shè)定值,滿足跳出循環(huán)，否則繼續(xù)循環(huán){l=0;求在Eigenvalue[q,q]矩陣上三角元素中的最大值及其位置pos1,pos2根據(jù)pos1,pos2進(jìn)行一輪特征值、特征向量的計(jì)算if((abs(Eigenvalue[i,j])<),(i=0,1,…,q,j=i+1,…,q)//判斷上三角元素是否滿足條件l++;//滿足計(jì)數(shù)器l加1}Lpt[i]=Eigenvalue[i,i];(i=1,2,…,q);//將特征值放入一維數(shù)組中將特征值、特征向量按照特征值的大小進(jìn)行排序得到特征值向量lpt[q]和特征向量矩陣EigenVector[q,q]End.算法的偽代碼如下：說(shuō)明：算法中把特征值存放在Lpt數(shù)組，特征向量存放在Eigenvalue數(shù)組中。一般q<<n，所以算法的主要計(jì)算代價(jià)在第一步計(jì)算相關(guān)系數(shù)矩陣中，計(jì)算量為q*n=O(n)下面的算法描述了主分量矩陣的計(jì)算過(guò)程。

說(shuō)明：算法5-3

PCMC(PrincipleComponentMatrixCompute主分量矩陣計(jì)算子程序)輸入：矩陣Xq×n，λ1,λ2,…,λq，特征向量矩陣EigenVector[q,q]，t(t<=1為確定主分量個(gè)數(shù)時(shí)所需特征值之和對(duì)總和貢獻(xiàn)率的臨界值)輸出：所需主分量矩陣Zk×n步驟：

BeginStep1計(jì)算所需主分量個(gè)數(shù)k；Step2根據(jù)特征向量矩陣Eigenvalue(q,q)計(jì)算出所需特征向量矩陣Pk×q；Step3計(jì)算主分量矩陣Zk×n(=P×X)。End.算法5-3PCMC(PrincipleComponent算法的偽代碼如下：Begin計(jì)算所需主分量個(gè)數(shù)k(<=q)即滿足（λ1＋λ2＋…＋λk）/（λ1＋λ2＋…＋λq）>=t根據(jù)特征向量矩陣Eigenvalue(q,q)計(jì)算出所需特征向量矩陣Pk×q計(jì)算主分量矩陣Zk×n(=P×X)End.顯然，算法3-3的計(jì)算代價(jià)主要在第2行，第3行，它們的計(jì)算復(fù)雜度在下面的命題中將進(jìn)行分析。下面的命題描述了算法ε－MDPA的復(fù)雜度。算法的偽代碼如下：命題