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

本章包括：

數據預處理基本功能數據預處理的方法第5章數據預處理

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

目前對數據挖掘的研究主要集中于挖掘技術、挖掘算法、挖掘語言等。數據挖掘過程一般包括數據采集、數據預處理、數據挖掘以數據挖掘的必要性：在海量的原始數據中，存在著大量雜亂的、重復的、不完整的數據，嚴重影響到數據挖掘算法的執行效率，甚至可能導致挖掘結果的偏差。數據預處理課件數據預處理分類：從對不同的源數據進行預處理的功能來分，數據預處理主要包括數據清理、數據集成、數據變換、數據歸約等4個基本功能。在實際的數據預處理過程中，

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

某一種預處理可能先后要多次進行。數據預處理分類：從數據預處理所采用的技術和方法來分：

基本粗集理論的簡約方法；復共線性數據預處理方法；基于Hash函數取樣的數據預處理方法；基于遺傳算法數據預處理方法；基于神經網絡的數據預處理方法；Web挖掘的數據預處理方法等等。數據預處理課件5.1數據預處理基本功能

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

數據清理要去除源數據集中的噪聲數據和無關數據，處理遺漏數據和清洗臟數據、空缺值，

識別刪除孤立點等。5.1.1數據清理數據清理要去除源數據集中的噪聲數據和無5.1.1.1噪聲數據處理

噪聲是一個測量變量中的隨機錯誤或偏差，包括錯誤的值或偏離期望的孤立點值。對于噪聲數據有如下幾種處理方法：分箱法聚類法識別孤立點回歸

5.1.1.1噪聲數據處理噪聲是一個測量變量中的隨機5.1.1.2空缺值的處理

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

如用一個全局常量替換空缺值、使用屬性的平均值填充空缺值或將所有元組按某些屬性分類，

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

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

異構數據源數據庫中的數據并不都是正確的，常常不可避免地存在著不完整、不一致、不精確和重復的數據，這些數據統稱為“臟數據”。臟數據能使挖掘過程陷入混亂，導致不可靠的輸出。

5.1.1.3清洗臟數據異構數據源數據庫中的數據并不都是正清洗臟數據可采用下面的方式：手工實現方式用專門編寫的應用程序采用概率統計學原理查找數值異常的記錄對重復記錄的檢測與刪除清洗臟數據可采用下面的方式：5.1.2.1實體識別問題

在數據集成時，來自多個數據源的現實世界的實體有時并不一定是匹配的，例如：數據分析者如何才能確信一個數據庫中的student_id和另一個數據庫中的stu_id值是同一個實體。通常，可根據數據庫或數據倉庫的元數據來區分模式集成中的錯誤。5.1.2.1實體識別問題在數據集成時，來自多個數據5.1.2.2冗余問題

數據集成往往導致數據冗余，如同一屬性多次出現、同一屬性命名不一致等，對于屬性間冗余可以用相關分析檢測到，然后刪除。

5.1.2.2冗余問題5.1.2.3數據值沖突檢測與處理

對于現實世界的同一實體，來自不同數據源的屬性值可能不同。這可能是因為表示、比例或編碼、數據類型、單位不統一、字段長度不同。5.1.2.3數據值沖突檢測與處理5.1.3數據變換

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

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

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

5.1.4.1維歸約通過刪除不相關的屬性(或維)減少5.1.4.2數據壓縮

數據壓縮分為無損壓縮和有損壓縮，比較流行和有效的有損數據壓縮方法是小波變換和主要成分分析。小波變換對于稀疏或傾斜數據以及具有有序屬性的數據有很好的壓縮結果。5.1.4.2數據壓縮數據壓縮分為無損壓縮和有損壓縮，比較5.1.4.3數值歸約

數值歸約通過選擇替代的、較小的數據表示形式來減少數據量。

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

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

數據預處理方法就是根據不同的挖掘問題采用相應的理論和技術，實現數據清理、數據集成、數據變換、數據歸約等基本功能。預處理方法很多，在此介紹常用的幾種方法。5.2數據預處理的方法數據預處理方法就是根據不同的挖掘問題5.2.1基于粗集理論的簡約方法

粗糙集理論是一種研究不精確、不確定性知識的數學工具，可以對數據屬性進行十分有效的精簡，求出最小約簡集，是數據預處理一種有效的方法。5.2.1基于粗集理論的簡約方法粗糙集理論是一種研究不數據一般存在信息的含糊性問題。粗糙集理論的最大特點是無需提供問題所需處理的數據集合之外的任何先驗信息。數據一般存在信息的含糊性問題。

粗糙集理論的基本思路是利用定義在數據集合U上的等價關系對U進行劃分，對于數據表來說，這種等價關系可以是某個屬性，或者是幾個屬性的集合。因此按照不同屬性的組合就把數據表劃分成不同的基本類，在這些基本類的基礎上進一步求得最小約簡集。

例如：表5.1優秀人才決策表給出了某部門的員工數據記錄集，通過對員工的政治表現、工作能力、科研能力等確定優秀人才人選。論域U

條件屬性（C）

決策屬性

政治表現（C1）工作能力（C2）

科研能力（C3）

優秀人才（D）

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

例如：表5.1優秀人才決策表給出了某部門的員工數據記錄集，根據粗糙集理論對表5.1進行離散化后再進行數據預處理。處理過程分兩個步驟進行，一是對決策表條件屬性集進行約簡求核；二是對條件屬性值進行約簡。具體求解步驟可見第11章相關內容。根據粗糙集理論對表5.1進行離散化后再進行數據預處理。基于粗糙集理論的數據預處理具有優點：第一，數據挖掘的對象一般都是通過觀測、試驗、調查得到的數據，通過觀測、試驗、調查等得到的數據存在著冗余、雜亂、不完整等因素，采用粗糙集理論進行數據預處理，不需要預先知道額外的信息，有利于集中精力解決問題；基于粗糙集理論的數據預處理具有優點：第二，算法簡單。對于給定的決策表，預處理過程所使用的算法可以是分辨矩陣或逐個屬性、逐條規則進行檢驗，算法簡單，易于計算機的實現，方便挖掘系統的自動操作；第三，可以有效地去除冗余的屬性或屬性的值。第二，算法簡單。對于給定的決策表，預處理過程所使用的算法可以5.2.2復共線性數據的預處理方法

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

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

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

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

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

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

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

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

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

說明：算法5-3

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

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

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

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

在目前常規的數據挖掘系統中，其數據分析功能模塊中，一般有主成5.2.2.3.實驗

本實驗的目的在于讓讀者理解ε－MDPA算法的運算過程，所以，實驗數據樣本數較小。實驗針對以下數據進行，見表5.2。表5.2某地區森林植被與引起洪澇災害的降雨量的關系序號變量

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.實驗本實驗的目的在于讓讀者理解ε－MDPA該例中：p=1，q=4，n=10運行ε－MDPA應用程序，并選擇ε＝0.001,t=0.90計算得：

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數據矩陣X存在復共線性，執行PCMC子程序，計算主分量矩陣。由λ1/∑λi＝0.957>t，k=1,即主分量只需取一個，即λ1＝3.827對應的評分量。計算得P1＊4=(0.259,0.257,0.258,0.258)計算消除復共線性后的數據矩陣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)然后，就可以使用新的數據矩陣挖掘其與因變量Y之間的函數關系，最終將結果再代回到自變量X即可。

數據矩陣X存在復共線性，執行PCMC子程序，計算主分量矩陣。5.2.3基于Hash函數取樣的抽樣技術數據預處理

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

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

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

l

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

二元型，即變量取值只有2個狀態，如性別。l

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

xm1+m2+1，…，xm1+m2+m3為標稱變量。

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

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

對于分布函數的估計采用簡單隨機取樣，設簡單隨機樣本數據為ssimp。為了針對各類型變量給出各分布函數的估計，根據文獻[13]，有下列三條性質：

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

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

(抽樣數的確定)估計分布函數的簡單隨機抽樣樣本個數ssimp由以下方法確定：ssimp=其中為標準正態分布的雙側分位數，r為相對誤差。性質5.3(抽樣數的確定)估計分布函數的簡單隨機抽樣樣本5.2.3.3Hash函數的構造

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

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

x1,x2,…,xm

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

SHF模型利用Hash函數對總體數據進行分桶，亦即將數據進行分層，然后針對各桶進行簡單隨機抽樣，從而實現分層抽樣。設按函數發現技術要求所需抽取的樣本數為slayer，將[0,1]slayer等分，slayer個等分點如下：0=i0,i1,i2,…,islayer-1,islayer=1，則iq-iq-1=1/slayer(q=1,2,…,slayer)將n個數據分到slayer個桶，分法如下：若第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個桶。5.2.3.4分層取樣SHF模型利用Hash函數對總體數命題5.3（各桶中數據分布的特點）按上述分桶方法，各桶中數據的個數以概率1相同。證明：由命題5.2知，

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

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

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

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

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

其中，選擇算子指按照一定的策略從父代中選出個體進入中間群體；交叉算子指隨機地從群體中抽取兩個個體，并按照某種交叉策略使兩個個體互相交換部分染色體碼串，形成兩個新的個體，可采用兩點交叉或多點交叉策略；變異算子指按一定的概率，改變染色體中的某些位的值。數據預處理課件標準遺傳算法的形式化描述為

，SGA是一個八元組SGA=(C,E,P0,M,Φ,Γ,Ψ,T)，其中，C為個體的編碼方法，E為個體適應度評價函數，P0為初始群體，M為群體規模，Φ

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

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

輸入：置迭代次數為0,隨機生成初始群體；輸出：優化的特征子集，優化的子群體。步驟：

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

ThenEnd；Step3計算當前群體中各個體的適應度；Step4由各個體適應度選擇生成中間群體；Step5以概率Pc選擇個體進行交叉，產生的新個體替換老個體，加入到中間群體中；Step6以概率Pm選擇個體對其某一位進行變異，產生新個體替換老個體，并加入到中間群體中；Step7轉Step2。End.算法5-5基于遺傳算法的特征子集選取算法5.2.4基于神經網絡數據預處理方法

人工神經網絡（artificialneuralnetwork，簡稱ANN）是在對大腦的生理研究的基礎上，用模擬生物神經元的某些基本功能元件（即人工神經元），按各種不同的聯結方式組成的一個網絡。神經網絡(NeuralNetwork)的學習結果為目標函數，根據這個目標函數的輸出作為分類的依據。輸入即為文本在各個特征上的各分量值。5.2.4基于神經網絡數據預處理方法人工神經網絡（arti神經網絡實際上是一組連接的輸入/輸出單元，其中每一個連接都具有一定的權值。通過訓練集來訓練的過程就是調整這些權值的過程，使得神經網絡可以正確的預測類別。神經網絡的訓練是針對訓練例逐個進行的，所以神經網絡的訓練集可以隨時添加，不需要重新進行訓練就可完成網絡的調整。神經網絡實際上是一組連接的輸入/輸出單元，其中每一個連接都具同時有實驗結果表明，在訓練例過少的情況下，神經網絡的分類準確率較低。因為可通過訓練來針對特征取一定的合適的權值，神經網絡可以較好地抵御噪音的干擾。

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

自組織特征映射神經網絡(SOFM)是一種典型的自適應聚類分析技術。SOFM是一個動態系統，它利用低維空間的表示學習拓撲結構并提取高維輸入向量中的結構。這種表示代替了輸入向量的全局的概率密度。設有n個樣本，SOFM網絡訓練算法如下：組織特征映射神經網絡(SOFM)算法5-6

SOFM算法

輸入：初始化輸入結點到輸出結點的連接權值,并置時間t=0,i=0；輸入模式向量。輸出：輸出結點

所連接的權向量及幾何鄰域

內結點所連接的權值:

算法5-6SOFM算法步驟：BeginStep1初始化輸入結點到輸出結點的連接權值,并置時間t=0,i=0。Step2輸入模式向量；Step3計算輸入與全部輸出結點所連接權向量

的距離:Step4具有最小距離的結點為競爭獲勝結點

Step5調整輸出結點

所連接的權向量及幾何鄰域

內結點所連接的權值:Step6i=i+1，t=t+1,IF

i≤nThenStep2

End步驟：算法中，

表示學習速度是可變的，隨時間而衰減，即隨著訓練次數的增加，權值調整幅度逐漸減小，以使獲勝結點所連接的權向量能代表模式的本質屬性。借助SOFM網絡，可將歸納數據庫中的樣本數據(一般仍為高維數據)按數據分布聚類到低維空間，這也體現了一種數據降維操作，可以形成相應的目標數據子集。

算法中，表示學習速度是可變的，隨時間而5.2.5Web挖掘數據預處理方法

Web使用挖掘由3個階段構成:數據預處理模式發現模式分析5.2.5Web挖掘數據預處理方法Web使用挖掘由3個階段算法5-7

WLP會話識別算法輸入：給出θ的會話溢出時間和會話總數；輸出：會話集si。步驟：

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

C、form=1todo//m表示第m個會話；i.；//找出最接近閾值的請求時間函數；ii.將tm加入到ti；iii.tstart=tm；D、

依據將

Li轉存為會話列表si；

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

謝謝

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

本章包括：

數據預處理基本功能數據預處理的方法第5章數據預處理

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

目前對數據挖掘的研究主要集中于挖掘技術、挖掘算法、挖掘語言等。數據挖掘過程一般包括數據采集、數據預處理、數據挖掘以數據挖掘的必要性：在海量的原始數據中，存在著大量雜亂的、重復的、不完整的數據，嚴重影響到數據挖掘算法的執行效率，甚至可能導致挖掘結果的偏差。數據預處理課件數據預處理分類：從對不同的源數據進行預處理的功能來分，數據預處理主要包括數據清理、數據集成、數據變換、數據歸約等4個基本功能。在實際的數據預處理過程中，

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

某一種預處理可能先后要多次進行。數據預處理分類：從數據預處理所采用的技術和方法來分：

基本粗集理論的簡約方法；復共線性數據預處理方法；基于Hash函數取樣的數據預處理方法；基于遺傳算法數據預處理方法；基于神經網絡的數據預處理方法；Web挖掘的數據預處理方法等等。數據預處理課件5.1數據預處理基本功能

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

數據清理要去除源數據集中的噪聲數據和無關數據，處理遺漏數據和清洗臟數據、空缺值，

識別刪除孤立點等。5.1.1數據清理數據清理要去除源數據集中的噪聲數據和無5.1.1.1噪聲數據處理

噪聲是一個測量變量中的隨機錯誤或偏差，包括錯誤的值或偏離期望的孤立點值。對于噪聲數據有如下幾種處理方法：分箱法聚類法識別孤立點回歸

5.1.1.1噪聲數據處理噪聲是一個測量變量中的隨機5.1.1.2空缺值的處理

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

如用一個全局常量替換空缺值、使用屬性的平均值填充空缺值或將所有元組按某些屬性分類，

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

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

異構數據源數據庫中的數據并不都是正確的，常常不可避免地存在著不完整、不一致、不精確和重復的數據，這些數據統稱為“臟數據”。臟數據能使挖掘過程陷入混亂，導致不可靠的輸出。

5.1.1.3清洗臟數據異構數據源數據庫中的數據并不都是正清洗臟數據可采用下面的方式：手工實現方式用專門編寫的應用程序采用概率統計學原理查找數值異常的記錄對重復記錄的檢測與刪除清洗臟數據可采用下面的方式：5.1.2.1實體識別問題

在數據集成時，來自多個數據源的現實世界的實體有時并不一定是匹配的，例如：數據分析者如何才能確信一個數據庫中的student_id和另一個數據庫中的stu_id值是同一個實體。通常，可根據數據庫或數據倉庫的元數據來區分模式集成中的錯誤。5.1.2.1實體識別問題在數據集成時，來自多個數據5.1.2.2冗余問題

數據集成往往導致數據冗余，如同一屬性多次出現、同一屬性命名不一致等，對于屬性間冗余可以用相關分析檢測到，然后刪除。

5.1.2.2冗余問題5.1.2.3數據值沖突檢測與處理

對于現實世界的同一實體，來自不同數據源的屬性值可能不同。這可能是因為表示、比例或編碼、數據類型、單位不統一、字段長度不同。5.1.2.3數據值沖突檢測與處理5.1.3數據變換

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

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

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

5.1.4.1維歸約通過刪除不相關的屬性(或維)減少5.1.4.2數據壓縮

數據壓縮分為無損壓縮和有損壓縮，比較流行和有效的有損數據壓縮方法是小波變換和主要成分分析。小波變換對于稀疏或傾斜數據以及具有有序屬性的數據有很好的壓縮結果。5.1.4.2數據壓縮數據壓縮分為無損壓縮和有損壓縮，比較5.1.4.3數值歸約

數值歸約通過選擇替代的、較小的數據表示形式來減少數據量。

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

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

數據預處理方法就是根據不同的挖掘問題采用相應的理論和技術，實現數據清理、數據集成、數據變換、數據歸約等基本功能。預處理方法很多，在此介紹常用的幾種方法。5.2數據預處理的方法數據預處理方法就是根據不同的挖掘問題5.2.1基于粗集理論的簡約方法

粗糙集理論是一種研究不精確、不確定性知識的數學工具，可以對數據屬性進行十分有效的精簡，求出最小約簡集，是數據預處理一種有效的方法。5.2.1基于粗集理論的簡約方法粗糙集理論是一種研究不數據一般存在信息的含糊性問題。粗糙集理論的最大特點是無需提供問題所需處理的數據集合之外的任何先驗信息。數據一般存在信息的含糊性問題。

粗糙集理論的基本思路是利用定義在數據集合U上的等價關系對U進行劃分，對于數據表來說，這種等價關系可以是某個屬性，或者是幾個屬性的集合。因此按照不同屬性的組合就把數據表劃分成不同的基本類，在這些基本類的基礎上進一步求得最小約簡集。

例如：表5.1優秀人才決策表給出了某部門的員工數據記錄集，通過對員工的政治表現、工作能力、科研能力等確定優秀人才人選。論域U

條件屬性（C）

決策屬性

政治表現（C1）工作能力（C2）

科研能力（C3）

優秀人才（D）

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

例如：表5.1優秀人才決策表給出了某部門的員工數據記錄集，根據粗糙集理論對表5.1進行離散化后再進行數據預處理。處理過程分兩個步驟進行，一是對決策表條件屬性集進行約簡求核；二是對條件屬性值進行約簡。具體求解步驟可見第11章相關內容。根據粗糙集理論對表5.1進行離散化后再進行數據預處理。基于粗糙集理論的數據預處理具有優點：第一，數據挖掘的對象一般都是通過觀測、試驗、調查得到的數據，通過觀測、試驗、調查等得到的數據存在著冗余、雜亂、不完整等因素，采用粗糙集理論進行數據預處理，不需要預先知道額外的信息，有利于集中精力解決問題；基于粗糙集理論的數據預處理具有優點：第二，算法簡單。對于給定的決策表，預處理過程所使用的算法可以是分辨矩陣或逐個屬性、逐條規則進行檢驗，算法簡單，易于計算機的實現，方便挖掘系統的自動操作；第三，可以有效地去除冗余的屬性或屬性的值。第二，算法簡單。對于給定的決策表，預處理過程所使用的算法可以5.2.2復共線性數據的預處理方法

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

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

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

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

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

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

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

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

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

說明：算法5-3

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

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