數(shù)據(jù)挖掘：概念與技術(shù)-課件

第3章數(shù)據(jù)預(yù)處理2014-111PPT課件目錄3.1數(shù)據(jù)預(yù)處理：概覽3.2數(shù)據(jù)清洗3.3數(shù)據(jù)聚合3.4數(shù)據(jù)刪減3.5數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)離散化3.6總結(jié)2PPT課件數(shù)據(jù)預(yù)處理

真實(shí)世界中的數(shù)據(jù)庫(kù)對(duì)噪聲、缺失、以及不一致的數(shù)據(jù)是高度敏感的，因?yàn)檫@些數(shù)據(jù)常常容量很大，并且很可能是多來(lái)源的異質(zhì)數(shù)據(jù)。

數(shù)據(jù)的低質(zhì)量會(huì)導(dǎo)致低質(zhì)量的數(shù)據(jù)挖掘結(jié)果?！叭绾翁幚頂?shù)據(jù)，以有助于提到數(shù)據(jù)的質(zhì)量和數(shù)據(jù)挖掘的效果呢？數(shù)據(jù)被如何處理能夠提高挖掘過(guò)程的高效性和簡(jiǎn)易型呢？”

這里有幾種數(shù)據(jù)預(yù)處理的技術(shù)，包括：數(shù)據(jù)清洗，數(shù)據(jù)聚合，數(shù)據(jù)刪減，數(shù)據(jù)轉(zhuǎn)換。這些技術(shù)能提升挖掘算法的精確性和效率。它們并非相對(duì)獨(dú)立，是共同工作的。比如，數(shù)據(jù)清洗也包含數(shù)據(jù)轉(zhuǎn)化以去除錯(cuò)誤數(shù)據(jù)。3PPT課件3.1數(shù)據(jù)預(yù)處理：概覽3.1.1數(shù)據(jù)質(zhì)量：為什么做數(shù)據(jù)預(yù)處理？

如果數(shù)據(jù)滿(mǎn)足了人們的預(yù)期用途的需求，則數(shù)據(jù)質(zhì)量好。數(shù)據(jù)質(zhì)量包含很多因素，如：精確性、完整性、一致性、時(shí)效性、可信性以及可解釋性。

數(shù)據(jù)的不精確、不完整以及不一致是大型真實(shí)世界數(shù)據(jù)庫(kù)以及數(shù)據(jù)倉(cāng)庫(kù)的常見(jiàn)特點(diǎn)。

4PPT課件數(shù)據(jù)的不精確性不精確數(shù)據(jù)有很多可能的原因：數(shù)據(jù)收集工具可能錯(cuò)誤，數(shù)據(jù)記錄中很多人為的或計(jì)算機(jī)導(dǎo)致的的錯(cuò)誤。用戶(hù)也可能在值當(dāng)他們不愿意暴露個(gè)人資料的時(shí)候在一些強(qiáng)制必須填寫(xiě)的欄目故意提交了錯(cuò)誤的資料（如生日直接用默認(rèn)值1月1日）。這是一些偽裝缺失的數(shù)據(jù)。數(shù)據(jù)在傳輸時(shí)也可能出錯(cuò)。一些技術(shù)上的限制，例如并行同步數(shù)據(jù)的傳輸和計(jì)算時(shí)緩沖區(qū)間的有限性。不正確的數(shù)據(jù)也可能因?yàn)槊?xí)慣或者數(shù)據(jù)編碼的不一致性，或者輸入域的格式不一致。重復(fù)的元組也需要進(jìn)行數(shù)據(jù)清洗。5PPT課件數(shù)據(jù)的不完整性導(dǎo)致數(shù)據(jù)的不完整性的原因也有很多：感興趣的屬性并不能總是可獲得，比如銷(xiāo)售交易數(shù)據(jù)中的客戶(hù)資料信息。另外，很可能因?yàn)樵诋?dāng)時(shí)的條目中，該屬性被認(rèn)為是不重要的。相關(guān)聯(lián)的數(shù)據(jù)沒(méi)有被記錄可能因?yàn)檎`解或者設(shè)備故障的原因。6PPT課件不一致的數(shù)據(jù)

和其他數(shù)據(jù)記錄不一致的數(shù)據(jù)應(yīng)該被被刪掉。另外，數(shù)據(jù)歷史和修改可能被忽視。缺失的數(shù)據(jù)，特別是缺失了某些屬性值的元組，值可能需要被推斷。

數(shù)據(jù)質(zhì)量依賴(lài)于人們對(duì)數(shù)據(jù)的預(yù)期使用。兩個(gè)不同的用戶(hù)可能對(duì)一個(gè)給定的數(shù)據(jù)庫(kù)的質(zhì)量有不同的評(píng)估。

比如，一個(gè)市場(chǎng)分析員獲得了一個(gè)由顧客地址列表的數(shù)據(jù)庫(kù)。一些地址是過(guò)期或錯(cuò)誤的，總體上有80%是精確的。市場(chǎng)分析員認(rèn)為這是一個(gè)針對(duì)目標(biāo)市場(chǎng)的很大的客戶(hù)數(shù)據(jù)庫(kù)，對(duì)數(shù)據(jù)的精確性很滿(mǎn)意。但是，銷(xiāo)售經(jīng)理可能認(rèn)為數(shù)據(jù)是不精確的。7PPT課件數(shù)據(jù)的時(shí)效性

時(shí)效性也可能影響數(shù)據(jù)質(zhì)量：

比如你在瀏覽AllElectronics公式的每月銷(xiāo)售獎(jiǎng)金的數(shù)據(jù)分布。一些銷(xiāo)售代表在月末的時(shí)候沒(méi)有及時(shí)的提交他們的銷(xiāo)售記錄。在月末之后可能有一些數(shù)據(jù)的更正和調(diào)整。從每個(gè)月的時(shí)間周期來(lái)看，數(shù)據(jù)庫(kù)中存放的數(shù)據(jù)是不完整的。因?yàn)樵履┑臄?shù)據(jù)沒(méi)有被及時(shí)的更新導(dǎo)致了數(shù)據(jù)質(zhì)量的負(fù)面性影響。8PPT課件數(shù)據(jù)的可信性和可解釋性

另外的兩個(gè)影響數(shù)據(jù)質(zhì)量的因素是可信性和可解釋性。

可信性反映用戶(hù)有多相信這些數(shù)據(jù)，可解釋性反應(yīng)數(shù)據(jù)有多容易被理解。

例如一個(gè)數(shù)據(jù)庫(kù)在某一時(shí)刻有一些錯(cuò)誤，然后都被更正了。過(guò)去的錯(cuò)誤導(dǎo)致了銷(xiāo)售部門(mén)用戶(hù)的大量問(wèn)題，因此他們不再相信這些數(shù)據(jù)。這些數(shù)據(jù)可能使用了很多會(huì)計(jì)代碼，銷(xiāo)售部門(mén)不懂如何解釋。即使這些數(shù)據(jù)是精確完整一致和有時(shí)效性的，但是仍然被銷(xiāo)售部門(mén)用戶(hù)認(rèn)為是低質(zhì)量的。9PPT課件3.1.2數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)預(yù)處理的主要步驟是：數(shù)據(jù)清洗數(shù)據(jù)聚合數(shù)據(jù)刪減數(shù)據(jù)轉(zhuǎn)換10PPT課件數(shù)據(jù)清洗

數(shù)據(jù)清洗的工作是清洗數(shù)據(jù)，通過(guò)填寫(xiě)缺失的數(shù)據(jù)，平滑噪音數(shù)據(jù)，識(shí)別需要去除的離群點(diǎn)，以及解決不一致性。

如果用戶(hù)相信數(shù)據(jù)是臟數(shù)據(jù)，便不可能信任數(shù)據(jù)挖掘的結(jié)果。另外，臟數(shù)據(jù)可能導(dǎo)致挖掘過(guò)程中的混亂，導(dǎo)致不可靠的輸出結(jié)果。

即使絕大多數(shù)的挖掘方法都有處理數(shù)據(jù)不完整和噪聲的步驟，但仍然不夠健壯。通常，這些算法集中避免建模的函數(shù)對(duì)數(shù)據(jù)的過(guò)度擬合。

因此，有用的預(yù)處理的步驟是把你的數(shù)據(jù)通過(guò)一些數(shù)據(jù)清洗的例程工作來(lái)完成。11PPT課件數(shù)據(jù)聚合

如果你的分析中數(shù)據(jù)是多來(lái)源的，則需要進(jìn)行數(shù)據(jù)聚合工作，即聚合多種數(shù)據(jù)庫(kù)，數(shù)據(jù)立方，以及文件。

一個(gè)給定概念的屬性在不同數(shù)據(jù)庫(kù)中可能有不同的命名，導(dǎo)致了不一致性和冗余。

例如，顧客的主鍵屬性在一個(gè)數(shù)據(jù)庫(kù)中是custom_id,在另外的數(shù)據(jù)庫(kù)卻是cust_id。命名的不一致性也可能發(fā)生在屬性值的上面。

例如，一個(gè)數(shù)據(jù)庫(kù)中人名的第一個(gè)名字是”Bill”，在另一個(gè)中是”William”,第三個(gè)中是”B”.12PPT課件

同時(shí)，你懷疑一些屬性值是由其他屬性值計(jì)算的（比如年收入）。有大量的冗余數(shù)據(jù)會(huì)讓知識(shí)發(fā)現(xiàn)過(guò)程速度降低以及產(chǎn)生混亂。

因此，除了數(shù)據(jù)清洗，必須采取步驟來(lái)避免在數(shù)據(jù)聚合中出現(xiàn)冗余。通常，數(shù)據(jù)清洗和數(shù)據(jù)聚合在為數(shù)據(jù)倉(cāng)庫(kù)準(zhǔn)備數(shù)據(jù)時(shí)被整合成一個(gè)預(yù)處理步驟。在數(shù)據(jù)清洗之外，在鑒別和去除因聚合導(dǎo)致的冗余數(shù)據(jù)的步驟。13PPT課件數(shù)據(jù)刪減

“我被選做分析的數(shù)據(jù)集非常大，這確信無(wú)疑的會(huì)減慢挖掘過(guò)程。是否有一個(gè)方法能夠在不影響數(shù)據(jù)挖掘的效果的情況下減小數(shù)據(jù)集呢？”這就是數(shù)據(jù)刪減。數(shù)據(jù)刪減能得到一個(gè)數(shù)據(jù)集的刪減集，比原來(lái)的數(shù)據(jù)小很多，但是能產(chǎn)生相同的（或幾乎相同的）分析結(jié)果。

數(shù)據(jù)刪減包括維度刪減和數(shù)據(jù)塊刪減。14PPT課件維度刪減：維度刪減是一種獲得原有數(shù)據(jù)的刪減或者壓縮集的數(shù)據(jù)編碼方案。比如，數(shù)據(jù)壓縮技術(shù)（小波分析、主成分分析）屬性子集選擇（去除不相關(guān)屬性），以及屬性構(gòu)造（如從原有數(shù)據(jù)集中建立小的更有用的屬性）數(shù)據(jù)塊刪減：數(shù)據(jù)被可選的更小的數(shù)據(jù)替換，使用參數(shù)模型（如回歸和對(duì)數(shù)-線(xiàn)性模型）或者非參數(shù)模型（直方圖，聚類(lèi)，抽樣和數(shù)據(jù)聚集）。15PPT課件數(shù)據(jù)轉(zhuǎn)換

在神經(jīng)網(wǎng)絡(luò)、最近鄰分類(lèi)以及聚類(lèi)分析中，你可能使用一個(gè)基于距離的挖掘算法。

如果將數(shù)據(jù)標(biāo)準(zhǔn)化，按比例縮小到一個(gè)更小的范圍，如[0.0，1.0]中，可能會(huì)得到更好的效果。

你的顧客數(shù)據(jù)中可能包含年齡屬性和年薪屬性。年薪屬性會(huì)使用一個(gè)比年齡大得多的值范圍。因此，如果屬性是左非規(guī)范的，距離測(cè)量會(huì)在年薪上產(chǎn)生更大的距離權(quán)重。16PPT課件

離散化和概念層次生成也很有效。用于將原始數(shù)據(jù)值替換成范圍區(qū)間或者高層概念層級(jí)。例如，原始的年齡值被高層級(jí)的概念：年輕人，成年人和老年人替換。

離散化和概念層次生成是數(shù)據(jù)挖掘的強(qiáng)大工具，因?yàn)樗麄冊(cè)试S數(shù)據(jù)挖掘在更多抽象級(jí)別上進(jìn)行。

標(biāo)準(zhǔn)化、離散化和概念層次生成是數(shù)據(jù)轉(zhuǎn)換的幾種形式。17PPT課件多種預(yù)處理的形式18PPT課件預(yù)處理的作用

總之，真實(shí)世界中的數(shù)據(jù)更可能是臟的、不完整和不一致的。數(shù)據(jù)預(yù)處理技術(shù)可以提升數(shù)據(jù)質(zhì)量，因而提升接下來(lái)的挖掘過(guò)程的精確性和有效性。

數(shù)據(jù)預(yù)處理是知識(shí)發(fā)現(xiàn)過(guò)程的一個(gè)重要步驟，因?yàn)楹玫馁|(zhì)量抉擇基于好的質(zhì)量的數(shù)據(jù)。發(fā)現(xiàn)數(shù)據(jù)的異常，在早期進(jìn)行修正，減少被分析的數(shù)據(jù)會(huì)給決策制定帶來(lái)巨大的回報(bào)。19PPT課件3.2數(shù)據(jù)清洗3.2.1缺失值假設(shè)你需要分析AllElectronics的銷(xiāo)售和顧客數(shù)據(jù)。你注意到許多元組在一些屬性例如顧客收入上沒(méi)有記錄值。如何能填寫(xiě)這些屬性的缺失值呢？有如下方法：1.忽略元組。常常在類(lèi)別標(biāo)簽（假定是分類(lèi)任務(wù)）缺失時(shí)這樣做。這種方法不是非常有效，除非元組包含若干缺失值的屬性。當(dāng)每個(gè)屬性上缺失的值占的比例變化很大時(shí)，這種方法特別糟糕。通過(guò)忽略這些元組，也不會(huì)使用這些元組剩下的屬性值。本來(lái)這些數(shù)據(jù)可以很有用的。20PPT課件2手工填寫(xiě)缺失值。通常，這種方法耗時(shí)，并且對(duì)一個(gè)有很多缺失值的大型數(shù)據(jù)集來(lái)說(shuō)并非可行。3使用一個(gè)全局常數(shù)來(lái)填寫(xiě)缺失值。可以將所有缺失的屬性值用同一個(gè)常數(shù)，例如標(biāo)簽“Unknown”或者”-∞”來(lái)表示。如果缺失值被“Unknown”替換，挖掘算法可能錯(cuò)誤的認(rèn)為形成了一個(gè)有趣的概念，因?yàn)樗麄兌加幸粋€(gè)共同的值”Unknown”.因此，即使這種方法很簡(jiǎn)單，卻也并非不會(huì)出錯(cuò)。4使用一個(gè)屬性的中心性測(cè)量來(lái)填寫(xiě)缺失值。對(duì)于標(biāo)準(zhǔn)（對(duì)稱(chēng)的）數(shù)據(jù)分布，可以使用平均值，對(duì)偏斜數(shù)據(jù)分布可以使用中值。21PPT課件5.使用給定元組的類(lèi)別相同的所有樣本的均值或者中值。例如，如果根據(jù)顧客的信用風(fēng)險(xiǎn)來(lái)分類(lèi)顧客，可以計(jì)算和該顧客的信用風(fēng)險(xiǎn)類(lèi)別相同的所有顧客的收入均值，來(lái)填寫(xiě)給定元組的缺失的收入屬性。如果對(duì)于給定類(lèi)別數(shù)據(jù)分布是偏斜的，則使用中值。6.使用缺失值的最可能的值來(lái)填寫(xiě)。值可以由回歸、使用Bayes公式的基于推理的工具，或者決策樹(shù)推理。如，使用你的數(shù)據(jù)集中的其他顧客的屬性，可以建立一個(gè)預(yù)測(cè)顧客缺失的收入值的決策樹(shù)。方法3-6改變了數(shù)據(jù)，即填寫(xiě)的值可能是不正確的。其中，方法6是一種流行的策略。22PPT課件

需要重點(diǎn)指出的是，在某些情形，一個(gè)缺失的值并非意味著數(shù)據(jù)的錯(cuò)誤！例如，當(dāng)申請(qǐng)信用卡時(shí)，申請(qǐng)者被要求提供駕駛證號(hào)碼。沒(méi)有駕駛證的自然就會(huì)在這一項(xiàng)不填寫(xiě)。表格應(yīng)當(dāng)允許回答者做詳細(xì)說(shuō)明，例如“不適合”。

軟件例程可能被使用來(lái)發(fā)現(xiàn)其他的空值（例如，“不知道？”或者“空”）。理想情況是，每一個(gè)屬性有一個(gè)或者多個(gè)針對(duì)空值情形的規(guī)則。這些規(guī)則可以詳細(xì)指明空值是否被允許或者種類(lèi)值如何被處理和轉(zhuǎn)換。屬性域可以被留作空白，如果在隨后的商業(yè)過(guò)程中能夠被提供。

因此，即使在數(shù)據(jù)被獲取之后，我們能夠盡力去清洗，好的數(shù)據(jù)庫(kù)和數(shù)據(jù)表過(guò)程設(shè)計(jì)能在第一時(shí)間最小化缺失值和錯(cuò)誤的數(shù)目。23PPT課件3.2.2噪聲數(shù)據(jù)

“什么是噪聲？”噪聲是度量變量的隨機(jī)錯(cuò)誤或者偏差。

第2章中介紹的基本統(tǒng)計(jì)描述技術(shù)（箱子圖、散點(diǎn)圖）、數(shù)據(jù)可視化的技術(shù)科用來(lái)識(shí)別離群點(diǎn)，這些可能代表噪聲。給定一個(gè)數(shù)值屬性，例如價(jià)格，如何來(lái)平滑數(shù)據(jù)以去除噪聲呢？有如下技術(shù)：1、裝箱

裝箱方法通過(guò)參考數(shù)據(jù)值的“鄰居”（即該值周?chē)臄?shù)據(jù)）來(lái)平滑排好序的數(shù)據(jù)。24PPT課件排好序的數(shù)據(jù)被分布到一系列的“桶”,或箱子中。因?yàn)檠b箱方法參考值的鄰居，所以使用的是局部平滑。有若干種裝箱技術(shù)：1）等頻裝箱。例如，價(jià)格屬性先被排序，然后被分割到箱子的大小為3的等頻箱子中。2）箱子均值平滑。箱子中的每個(gè)值被箱子的均值替代。3）箱子中值平滑。每個(gè)箱子值被箱子中值取代。4）箱子邊界平滑。箱子值被最靠近的邊界值（最大值或最小值）取代。箱子的寬度也大，平滑效果也越顯著。另外，等寬度的箱子，即每個(gè)箱子間隔是個(gè)相同的常數(shù)也常被使用。箱子技術(shù)也是一種數(shù)據(jù)離散化的技術(shù)。25PPT課件2、回歸：數(shù)據(jù)平滑也可以使用回歸的方法，即將數(shù)據(jù)值通過(guò)一個(gè)函數(shù)來(lái)表達(dá)。線(xiàn)性回歸是尋找兩個(gè)屬性（或變量）的最好的直線(xiàn)來(lái)通過(guò)一個(gè)屬性預(yù)測(cè)另外一個(gè)。多元線(xiàn)性回歸是線(xiàn)性回歸的擴(kuò)展。超過(guò)兩個(gè)的屬性被包含在其中，數(shù)據(jù)被擬合成一個(gè)高維超平面。3、離群點(diǎn)分析：通過(guò)聚類(lèi)的方法可以檢測(cè)離群點(diǎn)。例如，相似的值被分組，或“簇”。值落在簇之外的被認(rèn)為是離群點(diǎn)。26PPT課件4、其他方法：

很多數(shù)據(jù)平滑技術(shù)也適用于數(shù)據(jù)離散化和數(shù)據(jù)削減。例如，裝箱技術(shù)削減了每個(gè)屬性的不同值的個(gè)數(shù)。在基于邏輯的數(shù)據(jù)挖掘方法例如決策樹(shù)中，因?yàn)樾枰粩嘀貜?fù)的在排序數(shù)據(jù)上做值的比較，因此這相當(dāng)于是數(shù)據(jù)削減。

概念分層是數(shù)據(jù)離散化的一種，可以用來(lái)做數(shù)據(jù)平滑。一個(gè)概念分層例如價(jià)格，可以映射真實(shí)的價(jià)格值到便宜、中等、昂貴上。這樣削減了挖掘過(guò)程需要處理的數(shù)據(jù)值的個(gè)數(shù)。一些分類(lèi)方法有內(nèi)置的數(shù)據(jù)平滑機(jī)制。27PPT課件3.2.3數(shù)據(jù)清洗作為一個(gè)過(guò)程

“數(shù)據(jù)清洗是一個(gè)巨大的工作。數(shù)據(jù)清洗作為一個(gè)過(guò)程怎么樣呢？在處理這個(gè)任務(wù)是人如何精確的進(jìn)行呢？有任何可用的工具嗎？”

數(shù)據(jù)清洗作為一個(gè)過(guò)程的第一步是不一致性檢測(cè)。不一致性可能由多種原因?qū)е拢涸O(shè)計(jì)很差的數(shù)據(jù)表人為的輸入錯(cuò)誤故意的錯(cuò)誤（不希望泄露個(gè)人信息的回答者），以及數(shù)據(jù)延遲（如過(guò)期的地址）還可能因?yàn)椴灰恢碌臄?shù)據(jù)表達(dá)和編碼的不一致使用其他的來(lái)源例如測(cè)量設(shè)備的錯(cuò)誤導(dǎo)致的記錄數(shù)據(jù)和系統(tǒng)錯(cuò)誤錯(cuò)誤也可能發(fā)生在被用于和預(yù)期不同的目的時(shí)還有一些不一致性是因?yàn)閿?shù)據(jù)聚合導(dǎo)致的（一個(gè)給定的屬性在不同數(shù)據(jù)庫(kù)中使用不同的名稱(chēng)）28PPT課件

“那么，如何進(jìn)行不一致檢測(cè)呢？”

使用任何你事先已經(jīng)知道的關(guān)于數(shù)據(jù)的相應(yīng)屬性的知識(shí)，這種知識(shí)被稱(chēng)為“元數(shù)據(jù)”。

例如，數(shù)據(jù)的類(lèi)型和每個(gè)屬性的域是什么？每個(gè)屬性的可接受的值是什么？基本的統(tǒng)計(jì)數(shù)據(jù)描述（Section2.2）對(duì)于獲取數(shù)據(jù)趨勢(shì)和鑒別異常很有用。例如，尋找均值，中值和眾數(shù)。

數(shù)據(jù)是對(duì)稱(chēng)還是偏斜的？值的取值范圍是？所有的值都落在期望的區(qū)間嗎？每個(gè)屬性的標(biāo)準(zhǔn)差是多少？值在距離均值兩倍標(biāo)準(zhǔn)差的范圍外的屬性值可能是潛在離群值。屬性之間有已知的依賴(lài)關(guān)系嗎？

在這個(gè)步驟，你可能需要寫(xiě)下你自己的腳本或者使用后面將要討論的一些工具。通過(guò)這樣的方式，你可以找到噪聲，離群點(diǎn)，需要察覺(jué)的異常值。29PPT課件

作為一個(gè)數(shù)據(jù)分析師，你需要尋找不一致的編碼以及任何不一致的數(shù)據(jù)表達(dá)（比如，2010/12/25和25/12/2010)。

字段過(guò)載是另一個(gè)錯(cuò)誤源，常常是設(shè)計(jì)者將新屬性的定義擠進(jìn)一個(gè)已經(jīng)定義好的屬性未使用的位（bit)。（例如，一個(gè)屬性的值范圍是32位二進(jìn)制中的31位，剩1個(gè)位未使用）。

數(shù)據(jù)還需要使用唯一性規(guī)則，連續(xù)性規(guī)則和空值規(guī)則來(lái)檢查。唯一值規(guī)則是給定屬性的每一個(gè)值必須和該屬性的其他所有值不同。連續(xù)性規(guī)則是在屬性的最小值和最大值之間不能有缺失值（例如，檢查號(hào)碼）?？罩狄?guī)則指明了空白、提問(wèn)標(biāo)記、特殊字符或其他的字符串可能指代空值條件（如一個(gè)給定屬性的值不可獲得），以及這樣的值如何被處理。30PPT課件

空值規(guī)則應(yīng)當(dāng)指明如何記錄空值條件，例如，存儲(chǔ)數(shù)值屬性的0值，字符屬性的空白，或者其他可能使用的習(xí)慣（如，像“不知道”或者“？”的輸入應(yīng)當(dāng)被轉(zhuǎn)換成空白）。

有一系列不同的商業(yè)工具可以用來(lái)做不一致性檢測(cè)。數(shù)據(jù)洗擦工具使用簡(jiǎn)單的領(lǐng)域知識(shí)（如郵政地址和拼音檢查的知識(shí)）來(lái)檢測(cè)和修正數(shù)據(jù)中的錯(cuò)誤。這些工具在清洗多種來(lái)源的數(shù)據(jù)時(shí)依賴(lài)于語(yǔ)法解析和模糊匹配技術(shù)。

數(shù)據(jù)審核工具通過(guò)分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和關(guān)系來(lái)尋找不一致性，以及檢查違反了條件的數(shù)據(jù)。

它們是數(shù)據(jù)挖掘工具的變體。它們可能使用統(tǒng)計(jì)分析來(lái)發(fā)現(xiàn)關(guān)聯(lián)，或者聚類(lèi)發(fā)現(xiàn)離群點(diǎn)。也可能利用2.2節(jié)介紹的基本統(tǒng)計(jì)數(shù)據(jù)描述方法。31PPT課件

一些數(shù)據(jù)不一致性可以通過(guò)使用外部參考來(lái)人工改正。例如，數(shù)據(jù)輸入的錯(cuò)誤可以通過(guò)紙上跟蹤的方式來(lái)改正。

絕大部分的輸錯(cuò)，都需要進(jìn)行數(shù)據(jù)轉(zhuǎn)換。即一旦我們發(fā)現(xiàn)了不一致性，常常需要定義和應(yīng)用轉(zhuǎn)換來(lái)修正。

商業(yè)工具在數(shù)據(jù)轉(zhuǎn)換步驟可以起到作用。數(shù)據(jù)遷移工具允許做簡(jiǎn)單的轉(zhuǎn)換例如將字符串“gender”變?yōu)椤眘ex”.

ETL(抽取/轉(zhuǎn)換/加載工具）允許用戶(hù)規(guī)定使用圖形用戶(hù)接口（GUI)來(lái)轉(zhuǎn)換。

這些工具常常只支持有限的轉(zhuǎn)換集，因此，我們還常常選擇編寫(xiě)定制的腳本來(lái)做數(shù)據(jù)清洗的工作。32PPT課件不一致性的兩個(gè)步驟即不一致性檢測(cè)和數(shù)據(jù)轉(zhuǎn)換是迭代的過(guò)程。這個(gè)過(guò)程是修剪錯(cuò)誤，很耗時(shí)。33PPT課件3.3數(shù)據(jù)聚合數(shù)據(jù)挖掘經(jīng)常需要數(shù)據(jù)聚合——合并多個(gè)數(shù)據(jù)庫(kù)中的數(shù)據(jù)。細(xì)致的聚合能幫助減少和避免結(jié)果數(shù)據(jù)集中的冗余和不一致性。并在隨后的數(shù)據(jù)挖掘過(guò)程中提高準(zhǔn)確率和速度。34PPT課件3.3.1實(shí)體識(shí)別問(wèn)題

數(shù)據(jù)聚合是將多種數(shù)據(jù)來(lái)源結(jié)合到一個(gè)數(shù)據(jù)庫(kù)中，如數(shù)據(jù)倉(cāng)庫(kù)。這些來(lái)源包含多種數(shù)據(jù)庫(kù)，數(shù)據(jù)立方以及文件。

模式聚合和對(duì)象匹配可能比較復(fù)雜。如何將真實(shí)世界中的實(shí)體等價(jià)地匹配到多個(gè)數(shù)據(jù)源中？這就是實(shí)體識(shí)別問(wèn)題。

35PPT課件

例如，數(shù)據(jù)分析師或者計(jì)算機(jī)如何確信一個(gè)數(shù)據(jù)庫(kù)中的customer_id和另一個(gè)庫(kù)中的cust_number指的是同一個(gè)屬性？包含名稱(chēng)，含義，數(shù)據(jù)類(lèi)型，屬性的取值范圍，以及控制規(guī)則的元數(shù)據(jù)在3.2節(jié)被探討過(guò)。這種元數(shù)據(jù)能幫助避免模式聚合中的錯(cuò)誤。

元素?fù)?jù)還可以用來(lái)幫助數(shù)據(jù)轉(zhuǎn)換（例如，數(shù)據(jù)編碼pay_type在一個(gè)數(shù)據(jù)庫(kù)中可能是”H”、“S”,在一個(gè)中可能是”1”和“2”).因此，這個(gè)步驟和數(shù)據(jù)清洗也互相關(guān)聯(lián)。36PPT課件

將一個(gè)數(shù)據(jù)庫(kù)中的屬性匹配到另一個(gè)數(shù)據(jù)庫(kù)時(shí)，需要特別注意數(shù)據(jù)的結(jié)構(gòu)。

必須保證源系統(tǒng)中的任何屬性的功能性依賴(lài)關(guān)系以及參考限制與目標(biāo)系統(tǒng)匹配。例如，在一個(gè)系統(tǒng)中，discount可能被按次序被應(yīng)用，在另一個(gè)系統(tǒng)中則按每一個(gè)單個(gè)的項(xiàng)目?jī)?nèi)部的次序被應(yīng)用。如果在聚合之前沒(méi)有發(fā)現(xiàn)這個(gè)，目標(biāo)系統(tǒng)中的商品則會(huì)有錯(cuò)誤的discount信息。37PPT課件3.3.2冗余和關(guān)聯(lián)性分析

冗余是數(shù)據(jù)聚合的另外一個(gè)重要的問(wèn)題。一個(gè)屬性（例如年收入）是冗余的，如果它能從其他的屬性或?qū)傩约贤茖?dǎo)得到。屬性的不一致或者維度命名也會(huì)導(dǎo)致相應(yīng)數(shù)據(jù)集中的冗余。

這種冗余可以使用關(guān)聯(lián)性分析來(lái)檢測(cè)。給出兩個(gè)屬性，這種分析能基于可獲得的數(shù)據(jù)測(cè)量一個(gè)屬性在多強(qiáng)的程度上暗含了另一個(gè)。對(duì)于名詞數(shù)據(jù)，可以使用卡方檢驗(yàn)。對(duì)數(shù)值型數(shù)據(jù)，使用關(guān)聯(lián)系數(shù)和協(xié)方差。38PPT課件名詞數(shù)據(jù)的卡方關(guān)聯(lián)檢驗(yàn)

對(duì)名詞數(shù)據(jù)，兩個(gè)屬性A和B之間的關(guān)聯(lián)關(guān)系可以使用卡方檢驗(yàn)來(lái)發(fā)現(xiàn)。

假設(shè)A有c個(gè)不同的值，a1,a2,….ac.

B有r個(gè)不同的值，b1,b2,…br.

則包含屬性A和屬性B的元組可以使用一個(gè)列聯(lián)表來(lái)表示，其中A屬性的c個(gè)不同值構(gòu)成表的列，B屬性的r個(gè)不同值構(gòu)成表的行。令(Ai,Bj)表示屬性A取ai而屬性B取bj的聯(lián)合事件，即（A=ai,B=bj).39PPT課件

在表中每一個(gè)可能的(Ai,Bj)聯(lián)合事件都有一個(gè)單元?？ǚ街档墓绞牵浩渲?，oij表示觀察到的（Ai,Bj)聯(lián)合事件的頻率（實(shí)際次數(shù)）。而eij表示(Ai,Bj)事件的期望頻率，計(jì)算公式是：其中，n是數(shù)據(jù)元組的個(gè)數(shù)。40PPT課件

公式3.1計(jì)算全部r*c個(gè)單元的值。那些實(shí)際的次數(shù)和期望值相差最大的是對(duì)卡方值貢獻(xiàn)最大的。

卡方統(tǒng)計(jì)檢驗(yàn)假定屬性A和屬性B是互相獨(dú)立的，即這兩個(gè)屬性之間沒(méi)有關(guān)聯(lián)?；陲@著性水平，自由度是(r-1)*(c-1)。如果假設(shè)被拒絕，則A和B統(tǒng)計(jì)相關(guān)。41PPT課件卡方檢驗(yàn)舉例——例3.1假設(shè)調(diào)查了1500個(gè)人，按性別分成男和女。每個(gè)人投票是否喜歡閱讀小說(shuō)。這樣，就有了兩個(gè)屬性：gender和preferred_reading.觀察到的每個(gè)可能的聯(lián)合事件的次數(shù)在表3.1中。圓括號(hào)中的表示事件的期望次數(shù)，按照公式3.2計(jì)算出來(lái)的。42PPT課件可以注意到，每一行中，期望次數(shù)的總和必須和這一行的觀察次數(shù)的總和相等；每一列中，期望次數(shù)的和等于這一列的觀察次數(shù)的和。利用公式3.1，計(jì)算卡方值為：對(duì)于2*2的表，自由度為(2-1)*(2-1)=1.在自由度為1時(shí)，卡方值為10.828則可以在0.001的顯著性水平上拒絕值原假設(shè)。因?yàn)橛?jì)算出的值大于這個(gè)值，所以能以更小的顯著性水平拒絕原假設(shè)，即性別和是否喜歡讀小說(shuō)之間存在強(qiáng)相關(guān)關(guān)系。43PPT課件數(shù)值型數(shù)據(jù)的相關(guān)系數(shù)

44PPT課件

相關(guān)系數(shù)rAB的值在-1到+1之間。如果rAB>0，則稱(chēng)A和B正相關(guān)。表示A的值隨著B(niǎo)的值的增大而增大。值越大，相關(guān)性越強(qiáng)。因此，一個(gè)很大的值意味著A（或B)需要被作為冗余刪除。

如果rAB=0,則A和B相互獨(dú)立，它們之間沒(méi)有任何關(guān)系。如果值<0,則A和B負(fù)相關(guān)，表示一個(gè)屬性的值隨著另一個(gè)值的降低而增大。散點(diǎn)圖可以用來(lái)可視化屬性之間的關(guān)聯(lián)關(guān)系。45PPT課件

注意：關(guān)聯(lián)并不表示因果。即如果A和B相關(guān)，但并不意味著A導(dǎo)致B或者B導(dǎo)致A。

例如，在分析一個(gè)人口統(tǒng)計(jì)數(shù)據(jù)庫(kù)時(shí)，我們發(fā)現(xiàn)表示醫(yī)院數(shù)目的屬性和盜車(chē)數(shù)目相關(guān)。但這并不表示一個(gè)屬性導(dǎo)致了另外一個(gè)。兩個(gè)屬性實(shí)際上都是因?yàn)槿丝跀?shù)這第三個(gè)屬性導(dǎo)致的。46PPT課件數(shù)值型數(shù)據(jù)的協(xié)方差

在概率理論和統(tǒng)計(jì)學(xué)中，相關(guān)性和協(xié)方差是評(píng)價(jià)兩個(gè)屬性是否一起發(fā)生變化的兩種相似的測(cè)量?？紤]兩個(gè)數(shù)值型屬性A和B,n個(gè)觀察{(a1,b1),…(an,bn)}.屬性A和屬性B的均值，即期望值為：和47PPT課件則屬性A和B的協(xié)方差為：如果利用公式3.3來(lái)計(jì)算相關(guān)系數(shù)rA,B,則：其中分母是屬性A和B的標(biāo)準(zhǔn)差?？梢钥吹剑?8PPT課件

49PPT課件協(xié)方差舉例——例3.2考慮下表，這是一個(gè)觀察到的5次AllElectronics和Hightech公式的股票價(jià)格。如果股票是被同一個(gè)公司的趨勢(shì)影響，那么它們的價(jià)格是否一起漲落呢？50PPT課件計(jì)算均值：則協(xié)方差為：協(xié)方差值為正，因此，我們可以說(shuō)兩個(gè)公司的股票是一起漲的。51PPT課件方差是協(xié)方差的特例，是兩個(gè)屬性相等，即屬性自身的協(xié)方差。52PPT課件3.3.3元組復(fù)制

除了檢測(cè)屬性間的冗余，元組級(jí)別的冗余也需要被檢測(cè)。不規(guī)范表的使用（一般是為了避免連接提高性能）是另一種數(shù)據(jù)冗余的來(lái)源。在不同的復(fù)制之間常常產(chǎn)生不一致性。因?yàn)椴痪_的數(shù)據(jù)輸入或者更新了一部分而非全部的數(shù)據(jù)。

例如，一個(gè)購(gòu)買(mǎi)訂單數(shù)據(jù)庫(kù)包含購(gòu)買(mǎi)者的姓名和地址屬性，而非這個(gè)信息的主鍵信息。不一致性就可能產(chǎn)生，比如在購(gòu)買(mǎi)訂單數(shù)據(jù)庫(kù)中同樣的購(gòu)買(mǎi)者姓名卻是不同的地址。53PPT課件3.3.4數(shù)據(jù)值和檢測(cè)與解析的沖突

數(shù)據(jù)聚合還包含數(shù)據(jù)值沖突的檢測(cè)和解析。例如，對(duì)于同一個(gè)真實(shí)世界實(shí)體，不同來(lái)源的屬性值可能不同?？赡苁且?yàn)楸磉_(dá)、刻度或者編碼的不同。

比如，體重屬性在一個(gè)系統(tǒng)中可能以公制單位存放而在另一個(gè)中以英帝單位存放。

學(xué)校之間交換信息的時(shí)候，每個(gè)學(xué)校有自己的課程設(shè)置和等級(jí)模式。一個(gè)大學(xué)可能采用一個(gè)季度系統(tǒng)，一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)中3門(mén)課程，等級(jí)從A+到F。另一個(gè)可能采用學(xué)期值，數(shù)據(jù)庫(kù)中提供2門(mén)課程，等級(jí)從1到10.很難制定兩所大學(xué)精確的課程——等級(jí)轉(zhuǎn)換規(guī)則，交換信息很困難。54PPT課件

屬性的抽象級(jí)別也可能不同。在一個(gè)抽象級(jí)別更低的系統(tǒng)中，同一個(gè)屬性的級(jí)別比另一個(gè)系統(tǒng)中同樣的值更低。

比如，total_sales在一個(gè)數(shù)據(jù)庫(kù)中指AllElectronics的一個(gè)部門(mén)的總體銷(xiāo)售，而同樣名稱(chēng)的屬性在另一個(gè)數(shù)據(jù)庫(kù)中指的是一個(gè)給定地區(qū)的總體銷(xiāo)售。55PPT課件3.4數(shù)據(jù)刪減3.4.1數(shù)據(jù)刪減策略概覽數(shù)據(jù)刪減策略包含減少維度，減少數(shù)據(jù)塊以及數(shù)據(jù)壓縮。維度刪減是減少考慮的隨機(jī)變量或?qū)傩缘膫€(gè)數(shù)。維度刪減方法包括小波轉(zhuǎn)換，主成分分析，即將原有數(shù)據(jù)轉(zhuǎn)換或者投影到一個(gè)更小的空間。屬性子集選擇是檢測(cè)和刪除不相關(guān)的、弱相關(guān)的、冗余的屬性和維度的減少維度的方法。56PPT課件刪減數(shù)據(jù)塊是將原有數(shù)據(jù)以可選的、更小的表格替換。分參數(shù)和非參數(shù)兩種技術(shù)。參數(shù)的方法是，使用一個(gè)模型來(lái)評(píng)估數(shù)據(jù)，常常只有數(shù)據(jù)參數(shù)被存儲(chǔ)，而非實(shí)際的數(shù)據(jù)。回歸和對(duì)數(shù)——線(xiàn)性模型是兩個(gè)參數(shù)技術(shù)的例子。非參數(shù)技術(shù)存放以直方圖、聚類(lèi)、抽樣以及數(shù)據(jù)立方的形式表示的刪減數(shù)據(jù)。57PPT課件數(shù)據(jù)壓縮中，應(yīng)用轉(zhuǎn)換來(lái)得到一個(gè)原有數(shù)據(jù)的刪減或壓縮的表達(dá)。如果原有數(shù)據(jù)能從壓縮數(shù)據(jù)中被重構(gòu)而沒(méi)有任何信息損失，則數(shù)據(jù)刪減是無(wú)損的。如果只能重構(gòu)原有數(shù)據(jù)的近似集，則數(shù)據(jù)刪減是有損的。有一些字符串壓縮的無(wú)丟失的算法，這些通常只允許有限制的數(shù)據(jù)處理。減少維度和減少數(shù)據(jù)塊也能被看成是數(shù)據(jù)壓縮的形式。還有許多其他數(shù)據(jù)刪減的方法。花在數(shù)據(jù)刪減上的時(shí)間復(fù)雜度不應(yīng)當(dāng)超過(guò)或等于挖掘一個(gè)刪減的數(shù)據(jù)集節(jié)省的時(shí)間。58PPT課件3.4.2小波轉(zhuǎn)換

離散小波轉(zhuǎn)換（DWT)是一個(gè)線(xiàn)性信號(hào)處理技術(shù)。對(duì)一個(gè)數(shù)據(jù)向量X,使用小波系數(shù)，轉(zhuǎn)換成一個(gè)不同的數(shù)值向量X’。

這兩個(gè)向量的長(zhǎng)度相同。當(dāng)應(yīng)用這種數(shù)據(jù)刪減的技術(shù)時(shí)，將每個(gè)元組看成一個(gè)n維的數(shù)據(jù)向量，X=(x1,x2,…,xn)，表示數(shù)據(jù)庫(kù)的n個(gè)屬性的n個(gè)測(cè)量。

“如果小波轉(zhuǎn)換的數(shù)據(jù)和原有數(shù)據(jù)的長(zhǎng)度相同，這種數(shù)據(jù)刪減技術(shù)如何有效呢？”59PPT課件

有效性在于小波轉(zhuǎn)換的數(shù)據(jù)能夠被截短。數(shù)據(jù)的被壓縮的近似集被保留，只存放了小波系數(shù)最強(qiáng)的一小部分?jǐn)?shù)據(jù)。

例如，所有比一些用戶(hù)指定閥值更大的小波系數(shù)被保留。其他的系數(shù)被設(shè)置為0.得到的數(shù)據(jù)表達(dá)因此非常稀疏，操作就可以利用數(shù)據(jù)的稀疏性，在小波空間計(jì)算將非?？?。

這個(gè)技術(shù)還能被用于去除噪聲，而不需要消除數(shù)據(jù)的主要特征，像數(shù)據(jù)清洗一樣有效。

給定一系列系數(shù)，原有數(shù)據(jù)的近似能應(yīng)用逆DWT被重構(gòu)。60PPT課件 DWT和離散傅里葉轉(zhuǎn)換（DFT)關(guān)聯(lián)性很強(qiáng)。DFT是一種包含正弦余弦的信號(hào)處理技術(shù)。一般情況下，DWT能得到更好的無(wú)損壓縮。即如果在給定數(shù)據(jù)向量上應(yīng)用DWT和DFT，DWT能得到原有數(shù)據(jù)更好的近似集。因此，得到一個(gè)相同的近似集，DWT需要更少的空間。

只有一種DFT，但DWT有不同的系列。流行的小波轉(zhuǎn)換包含Harr-2,Daubechies-4,以及Daubechies-6.應(yīng)用一個(gè)離散小波轉(zhuǎn)換的一般步驟是使用一個(gè)層次化的金字塔算法，每次迭代將數(shù)據(jù)減半，這是非常快的計(jì)算速度。61PPT課件DWT的步驟：1、輸入數(shù)據(jù)向量的長(zhǎng)度L必須是2的整數(shù)次冪。這個(gè)條件可以在必要時(shí)以0填充數(shù)據(jù)向量來(lái)滿(mǎn)足。2、每個(gè)轉(zhuǎn)換包含應(yīng)用兩個(gè)函數(shù)。第一個(gè)應(yīng)用一些數(shù)據(jù)平滑，例如求和或者加權(quán)平均。第二個(gè)使用一個(gè)加權(quán)差，為了表達(dá)數(shù)據(jù)的具體特征。3、這兩個(gè)函數(shù)被應(yīng)用到向量X的每一個(gè)對(duì)（x2i,x2i+1).這會(huì)得到兩個(gè)長(zhǎng)度為L(zhǎng)/2的數(shù)據(jù)集。一般情況下，它們一個(gè)表達(dá)的是平滑的或者低頻的輸入數(shù)據(jù)的版本，另一個(gè)是高頻的內(nèi)容。4、這兩個(gè)函數(shù)被遞歸的應(yīng)用到前一個(gè)循環(huán)得到的數(shù)據(jù)集上，直到數(shù)據(jù)集的長(zhǎng)度變成2.5、從前一次迭代的數(shù)據(jù)集中選擇值，將其指明為轉(zhuǎn)換數(shù)據(jù)的小波系數(shù)。62PPT課件63PPT課件

一個(gè)矩陣被應(yīng)用在輸入數(shù)據(jù)上，以便于得到小波系數(shù)。矩陣依賴(lài)于給定的DWT。矩陣必須是正交的，即列是單位向量，相互正交的，因此矩陣的逆是它的轉(zhuǎn)置。

通過(guò)將矩陣分解為幾個(gè)稀疏矩陣，得到的快速DWT算法具有O(n)的時(shí)間復(fù)雜度。

小波轉(zhuǎn)換能被應(yīng)用于高維數(shù)據(jù)如數(shù)據(jù)立方上。方法是首先應(yīng)用轉(zhuǎn)換到第一個(gè)維度上，然后第二個(gè)，以此類(lèi)推。計(jì)算復(fù)雜度視立方的單元數(shù)目而定。

小波轉(zhuǎn)換對(duì)于稀疏或偏斜的數(shù)據(jù)有很好的效果，以及次序?qū)傩缘臄?shù)據(jù)上。小波變換的有損壓縮據(jù)說(shuō)比JPEG好。它有很多實(shí)際的應(yīng)用，包括指紋圖像、計(jì)算機(jī)視覺(jué)的壓縮，時(shí)間序列數(shù)據(jù)分析以及數(shù)據(jù)清洗。64PPT課件3.4.3主成分分析

假定要?jiǎng)h減的數(shù)據(jù)包含n個(gè)屬性或維度。主成分分析（PCA)尋找K個(gè)n維正交向量，這些向量能最好的表達(dá)數(shù)據(jù)，k<n.原有的數(shù)據(jù)因此被投影到一個(gè)更小的空間，得到刪減的維度。

不同于屬性子集選擇，PCA通過(guò)創(chuàng)建一個(gè)可選的更好的變量集，得到重要屬性的聯(lián)合。PCA常常揭示之前沒(méi)有察覺(jué)的關(guān)系，因此得到通常沒(méi)有的解釋。aproductofafewsparsematrices65PPT課件PCA的基本步驟：1、將輸入數(shù)據(jù)標(biāo)準(zhǔn)化，每個(gè)屬性落在相同的值區(qū)間。確保屬性在更大范圍的不會(huì)占有更大權(quán)重。2、計(jì)算K個(gè)正交向量，提供標(biāo)準(zhǔn)輸入數(shù)據(jù)的基礎(chǔ)。這是一些單位向量。每個(gè)點(diǎn)在方向上與其他的垂直。這些向量被稱(chēng)為主要成分。輸入數(shù)據(jù)是主成分的線(xiàn)性組合。3、主成分按重要性或者長(zhǎng)度遞減的次序存放。主成分作為數(shù)據(jù)的新的坐標(biāo)軸的集合，提供重要的方差信息。即，排序的坐標(biāo)軸中，第一個(gè)軸表示數(shù)據(jù)的最大方差，第二個(gè)表示次高的方差，以此類(lèi)推。例如圖3.5表示了兩個(gè)主成分Y1和Y2。66PPT課件67PPT課件4、因?yàn)橹鞒煞职粗匾缘慕敌蚺帕?，?shù)據(jù)尺寸可以通過(guò)去除次要成分來(lái)減少，即具有更小方差信息的。使用最強(qiáng)的主成分，得到原有數(shù)據(jù)的很好的近似集的重構(gòu)是可能的。PCA能被應(yīng)用于次序或者非次序?qū)傩浴Ｄ芴幚硐∈韬推钡臄?shù)據(jù)。高維數(shù)據(jù)能被減少為2個(gè)。相比于小波轉(zhuǎn)換，PCA能更好的處理稀疏數(shù)據(jù)，而小波轉(zhuǎn)換更適合處理高維數(shù)據(jù)。68PPT課件3.4.4屬性子集選擇

用來(lái)做分析的數(shù)據(jù)集可能包含成百個(gè)屬性，許多屬性和挖掘任務(wù)并不相關(guān)或者是冗余的。

例如，挖掘任務(wù)是對(duì)顧客進(jìn)行分類(lèi)，判斷他們是否會(huì)購(gòu)買(mǎi)一個(gè)流行的新CD，像顧客的電話(huà)號(hào)碼很可能是不相關(guān)的，不像年齡和音樂(lè)類(lèi)型這類(lèi)屬性是相關(guān)的。領(lǐng)域?qū)＜姨暨x一些有用的屬性是可能的，但這是一個(gè)困難和耗時(shí)的工作，特別是在數(shù)據(jù)的行為并不已知的時(shí)候。去掉了相關(guān)的屬性，或者保留了不相關(guān)的屬性都是有害的。導(dǎo)致挖掘算法的困惑以及低質(zhì)量的模式發(fā)現(xiàn)。并且，增加的不相關(guān)和冗余屬性也會(huì)讓挖掘過(guò)程變慢。69PPT課件

屬性子集選擇通過(guò)減少不相關(guān)和冗余的屬性來(lái)減少數(shù)據(jù)集的大小。屬性子集選擇的目標(biāo)是尋找一個(gè)相應(yīng)的數(shù)據(jù)類(lèi)別分布概率盡可能接近使用所有屬性的原始分布的最小屬性集合。在刪減的屬性集上挖掘具有特別的好處：使挖掘出的模式更容易被理解。

“如何尋找一個(gè)原有屬性的好的子集合呢？”

對(duì)于n個(gè)屬性，有2n個(gè)子集合，對(duì)優(yōu)化子集的窮舉搜索是代價(jià)很大的，特別是在n和數(shù)據(jù)類(lèi)別增加的時(shí)候。因此，剪枝式的啟發(fā)式方法通常被用于屬性子集選擇。這些方法通常是貪心式的，策略是做一個(gè)局部最優(yōu)的選擇用以得到一個(gè)全局優(yōu)化的解。70PPT課件

“最好的”（以及“最差的”）屬性常常是使用統(tǒng)計(jì)顯著性檢驗(yàn)來(lái)決定，假定屬性之間是互相獨(dú)立的。許多其他的屬性評(píng)估方法如決策樹(shù)分類(lèi)中的信息增益。

基本的屬性子集選擇的啟發(fā)式技術(shù)如下：

1、逐步向前選擇。該方法從一個(gè)屬性的空集合開(kāi)始作為刪減集合。然后確定一個(gè)原有屬性的最好屬性，加入到刪減集合中。每一次迭代，都把剩余屬性集中最好的屬性加入到該集合。

2、逐步向后刪除。該方法從全體屬性集開(kāi)始，每一次從中去除剩余屬性集合中最差的屬性。

3、結(jié)合向前選擇和向后刪除的方法。71PPT課件屬性子集選擇的貪心式方法72PPT課件4、決策樹(shù)推導(dǎo)。決策樹(shù)算法（如ID3，C4.5，和CART)最初被用于分類(lèi)。決策樹(shù)推導(dǎo)是創(chuàng)建一個(gè)流程圖結(jié)構(gòu)，每一個(gè)內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）表示一個(gè)屬性的檢驗(yàn)，每一個(gè)分支對(duì)應(yīng)于一個(gè)檢驗(yàn)的結(jié)果，每一個(gè)外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)）表示一個(gè)類(lèi)別預(yù)測(cè)。在一個(gè)節(jié)點(diǎn)，算法選擇最好的屬性去將數(shù)據(jù)分割成單個(gè)的類(lèi)別。當(dāng)決策樹(shù)用于屬性子集選擇時(shí)，給定數(shù)據(jù)的樹(shù)被創(chuàng)建。所有沒(méi)有出現(xiàn)在樹(shù)中的屬性被認(rèn)為是不相關(guān)的。出現(xiàn)在樹(shù)中的屬性構(gòu)成了刪減屬性子集。在某些情形下，可能需要基于一些屬性創(chuàng)建一些新的屬性。這類(lèi)屬性構(gòu)造能幫助提高對(duì)高維數(shù)據(jù)的精確性和結(jié)構(gòu)的理解。比如，基于屬性height和width創(chuàng)建area屬性。通過(guò)結(jié)合屬性，屬性構(gòu)造能發(fā)現(xiàn)數(shù)據(jù)屬性之間的缺失信息，有利于知識(shí)發(fā)現(xiàn)。73PPT課件3.4.5回歸和對(duì)數(shù)——線(xiàn)性模型：參數(shù)數(shù)據(jù)刪減

線(xiàn)性回歸中，數(shù)據(jù)被擬合成一條直線(xiàn)。

例如，隨機(jī)變量y(也稱(chēng)為響應(yīng)變量），被建模成另一個(gè)隨機(jī)變量x(稱(chēng)為預(yù)測(cè)變量）的線(xiàn)性函數(shù)，公式為：y=wx+b

在數(shù)據(jù)挖掘環(huán)境中，x和y都是數(shù)值型的屬性，系數(shù)w和b稱(chēng)為回歸系數(shù)，定義了直線(xiàn)的斜率和y-截距。系數(shù)的求解可以使用最小二乘法，最小化實(shí)際直線(xiàn)分割數(shù)據(jù)和估計(jì)值之間的錯(cuò)誤。

多元線(xiàn)性回歸是線(xiàn)性回歸的擴(kuò)展，將相應(yīng)變量y建模成2個(gè)或更多的預(yù)測(cè)變量的線(xiàn)性函數(shù)。74PPT課件

對(duì)數(shù)——線(xiàn)性模型近似于離散高維概率分布。

給定一系列包含n維屬性的元組，將每一個(gè)元組當(dāng)成n維空間中的一個(gè)點(diǎn)。

對(duì)數(shù)——線(xiàn)性模型基于一個(gè)更小的維度聯(lián)合的子集，來(lái)估計(jì)每個(gè)點(diǎn)在高維空間的概率。這樣就能從低維空間構(gòu)建高維數(shù)據(jù)空間。因此，模型可以用于維度刪減（因?yàn)榈途S點(diǎn)常常比原有數(shù)據(jù)點(diǎn)占有更少的空間）以及數(shù)據(jù)平滑（因?yàn)榈途S空間的聚合估計(jì)比高維空間的估計(jì)對(duì)抽樣變化主觀度更?。?5PPT課件

回歸和對(duì)數(shù)——線(xiàn)性模型都能用在稀疏數(shù)據(jù)上，即使應(yīng)用比較有限。兩種方法都能處理偏斜數(shù)據(jù)，回歸做的更好。對(duì)高維數(shù)據(jù)，回歸的計(jì)算復(fù)雜度很高，而對(duì)數(shù)——線(xiàn)性模型對(duì)高于10維的數(shù)據(jù)有更好的可擴(kuò)展性。

一些軟件包中有回歸問(wèn)題的解決方法。如SAS,SPSS,S-Plus.76PPT課件3.4.6直方圖

直方圖使用箱子來(lái)近似數(shù)據(jù)分布，是一種流行的數(shù)據(jù)刪減的形式。

直方圖是將一個(gè)屬性A劃分成不相交的子集，稱(chēng)為桶或者箱子。

如果每個(gè)桶只表示一個(gè)單個(gè)的屬性值/頻率對(duì)，則桶稱(chēng)為單例桶。如圖3.7.通常，桶表示給定屬性的連續(xù)范圍?！叭绾未_定桶和屬性值的劃分呢？”有如下劃分的技術(shù)：等寬度：每個(gè)桶的范圍都是相同的。如圖3.8.等頻率：每個(gè)桶的頻數(shù)相同（即裝了個(gè)數(shù)幾乎相同的數(shù)據(jù)樣本）77PPT課件單例桶舉例78PPT課件等寬度裝箱79PPT課件

直方圖對(duì)于稀疏和稠密數(shù)據(jù)都很高效，對(duì)高度偏斜或者均勻分布的數(shù)據(jù)也是一樣。

單個(gè)屬性的直方圖可以被擴(kuò)展到多個(gè)屬性。多維直方圖能捕獲屬性間的依賴(lài)關(guān)系，最多能對(duì)5維數(shù)據(jù)有效。進(jìn)一步的研究高維數(shù)據(jù)的有效直方圖是有必要的。80PPT課件3.4.7聚類(lèi)

聚類(lèi)技術(shù)將數(shù)據(jù)元組當(dāng)成對(duì)象。將對(duì)象劃分成分組，或簇，在同一個(gè)簇中對(duì)象是相似的，跟其他簇中的對(duì)象是不相似的。相似性一般是基于距離函數(shù)，以對(duì)象在空間上的距離有多接近來(lái)定義。

聚類(lèi)的質(zhì)量可以用它的直徑來(lái)表示，即簇中兩個(gè)對(duì)象的最大距離。幾何中心距離是聚類(lèi)質(zhì)量的一個(gè)可選的測(cè)量，定義為每個(gè)聚類(lèi)對(duì)象到聚類(lèi)中心的平均距離。

圖3.3展示了一個(gè)顧客數(shù)據(jù)的2-D散點(diǎn)圖，點(diǎn)的位置是在一個(gè)城市中的顧客位置?？梢钥匆?jiàn)3個(gè)數(shù)據(jù)簇。81PPT課件82PPT課件3.4.8抽樣

抽樣也可以作為一種數(shù)據(jù)刪減的技術(shù)，因?yàn)樗试S從一個(gè)大數(shù)據(jù)集中抽取小得多的隨機(jī)數(shù)據(jù)（子集）來(lái)表示。假定一個(gè)大數(shù)據(jù)集D包含N個(gè)元組，最常用的數(shù)據(jù)刪減的抽樣技術(shù)包括：1、無(wú)置換的簡(jiǎn)單隨機(jī)抽樣（SRSWOR)。方法是從N個(gè)元組中以概率1/N從D中抽樣s個(gè)數(shù)據(jù)，每個(gè)元組被抽樣的概率都相等。2、有置換的簡(jiǎn)單隨機(jī)抽樣（SRSWR)。類(lèi)似于SPSWOR,除了每次從D中抽樣一個(gè)元組之后，記錄它然后替換。即元組被抽樣之后，再放回D中下次還可以被繼續(xù)抽到。83PPT課件3、聚類(lèi)樣本。如果D中的元組被分成M個(gè)互不相交的簇，然后就可以抽樣得到s個(gè)簡(jiǎn)單隨機(jī)抽樣簇，s<M.例如，元組在一個(gè)數(shù)據(jù)庫(kù)中通常被一次檢索一頁(yè)，每一頁(yè)可以被看做一個(gè)簇。然后使用SRSWOR到頁(yè)面上，便可以得到刪減數(shù)據(jù)的代表，即元組的聚類(lèi)抽樣。其他的一些包含豐富語(yǔ)義信息的聚類(lèi)規(guī)則也可以使用。例如，在空間數(shù)據(jù)庫(kù)中，基于不同地區(qū)在地理位置上的接近程度來(lái)圖形化地定義簇。84PPT課件4、分層抽樣：如果D被分成互不相交的層，分層抽樣可以通過(guò)對(duì)每個(gè)層進(jìn)行簡(jiǎn)單隨機(jī)抽樣來(lái)生成。這能在數(shù)據(jù)偏斜的時(shí)候，選出具有代表性的樣本。例如，從顧客數(shù)據(jù)中進(jìn)行分層抽樣。將每個(gè)顧客按年齡分組，然后對(duì)分組抽樣。在這種方式下，有最小個(gè)數(shù)的顧客年齡層也被保證會(huì)被抽取。85PPT課件

使用抽樣的方法進(jìn)行數(shù)據(jù)刪減的優(yōu)點(diǎn)在于，得到一個(gè)樣本的代價(jià)和樣本的大小成比例，即s與N的比例。因此，抽樣復(fù)雜度是亞線(xiàn)性比于數(shù)據(jù)尺寸。其他的數(shù)據(jù)刪減技術(shù)的復(fù)雜度至少是O(N)。

給定一個(gè)固定的樣本大小，抽樣復(fù)雜度隨著數(shù)據(jù)維度的個(gè)數(shù)增加而增加。如果用直方圖技術(shù)，復(fù)雜度則是n的指數(shù)級(jí)別。

抽樣是最常用的用來(lái)估計(jì)一個(gè)集合查詢(xún)的答案的方法。86PPT課件3.4.9數(shù)據(jù)立方聚合

假設(shè)你在為你的分析收集數(shù)據(jù)。這些數(shù)據(jù)包括AllElectronics公司每個(gè)季度的銷(xiāo)售，從2008年至2010年。你感興趣的是每年的銷(xiāo)售額，而不是每個(gè)季度的總體銷(xiāo)售額。因此，數(shù)據(jù)需要被聚合，得到每年的銷(xiāo)售總額而非季度銷(xiāo)售額。

圖3.10是聚合的情況。得到的數(shù)據(jù)集尺寸更小，對(duì)分析任務(wù)來(lái)說(shuō)沒(méi)有必要的信息損失。87PPT課件舉例88PPT課件

數(shù)據(jù)立方存儲(chǔ)的是高維聚合信息。如圖3.11是一個(gè)銷(xiāo)售數(shù)據(jù)的高維分析的數(shù)據(jù)立方，包含AllElectronics公司所有分部的每年的每種商品類(lèi)型的銷(xiāo)售額。每個(gè)單元是一個(gè)聚合的數(shù)據(jù)值，對(duì)應(yīng)于高維空間中的數(shù)據(jù)點(diǎn)。每個(gè)屬性有一個(gè)概念層級(jí)，允許對(duì)數(shù)據(jù)的多層抽象級(jí)別的分析。比如，對(duì)于子公司的層級(jí)允許將子公司基于位置分組為不同的地區(qū)。

數(shù)據(jù)立方提供對(duì)預(yù)先計(jì)算，數(shù)據(jù)摘要的快速訪(fǎng)問(wèn)，因此有利用在線(xiàn)分析處理以及數(shù)據(jù)挖掘。89PPT課件3.5數(shù)據(jù)轉(zhuǎn)換和離散化3.5.1數(shù)據(jù)轉(zhuǎn)換策略概覽數(shù)據(jù)轉(zhuǎn)換把數(shù)據(jù)轉(zhuǎn)換或合并成適合數(shù)據(jù)挖掘的形式。數(shù)據(jù)轉(zhuǎn)換的策略包括：1、平滑。用于去除數(shù)據(jù)中的噪聲。技術(shù)包括裝箱，回歸和聚類(lèi)。2、屬性構(gòu)造（或特征構(gòu)造）。從給定屬性中構(gòu)造或增加新屬性以便于挖掘過(guò)程。3、聚合。在數(shù)據(jù)上應(yīng)用聚合或者概括操作。例如，聚合每日銷(xiāo)售數(shù)據(jù)以計(jì)算每月和每年的總體數(shù)據(jù)。通常這個(gè)步驟用在構(gòu)造用于多層抽象級(jí)別數(shù)據(jù)分析的數(shù)據(jù)立方。90PPT課件4、規(guī)范化。屬性被按比例縮放到一個(gè)更小的范圍，如-1.0到1.0，或0.0到1.0之間。5、離散化。數(shù)值屬性的原始值被區(qū)間標(biāo)簽或概念標(biāo)簽置換。標(biāo)簽?zāi)鼙贿f歸的組織成高層概念。形成一個(gè)數(shù)值屬性的概念層級(jí)。圖3.12是一個(gè)價(jià)格屬性的概念層級(jí)的例子。超過(guò)一個(gè)的概念層級(jí)可以被用來(lái)滿(mǎn)足不同用戶(hù)的需求。6、名詞數(shù)據(jù)的概念層級(jí)生成。例如steet屬性可以擴(kuò)展成高層概念，如city和country.許多名詞屬性的層次是隱藏在數(shù)據(jù)庫(kù)模式中的，可以在模式定義級(jí)別自動(dòng)定義。91PPT課件離散化

離散化技術(shù)可以基于離散化方法的不同來(lái)分類(lèi)，例如是使用類(lèi)別信息還是處理方向（自底向上和自頂向下）。

如果離散化過(guò)程使用類(lèi)別信息，稱(chēng)為有監(jiān)督的離散化；否則是無(wú)監(jiān)督的。

如果過(guò)程先尋找一個(gè)活若干點(diǎn)來(lái)分割整個(gè)屬性范圍，然后對(duì)每個(gè)區(qū)間遞歸重復(fù)這個(gè)步驟，則稱(chēng)為自頂向下的離散化或分割。自底向上的離散化或合并先把所有的連續(xù)值作為潛在的分割點(diǎn)，通過(guò)合并相鄰的值移除某些點(diǎn)來(lái)形成區(qū)間，然后再遞歸的應(yīng)用這個(gè)過(guò)程到每一個(gè)區(qū)間。92PPT課件

數(shù)據(jù)離散化和概念層級(jí)生成也是數(shù)據(jù)刪減的形式。原始數(shù)據(jù)被一個(gè)數(shù)目更小的區(qū)間或者概念標(biāo)簽置換。這簡(jiǎn)化了原有數(shù)據(jù)，使挖掘更高效。挖掘出的模式通常更易于被理解。概念層級(jí)在對(duì)多層抽象級(jí)別挖掘上也十分有效。93PPT課件3.5.2數(shù)據(jù)標(biāo)準(zhǔn)化

使用的度量單位會(huì)影響數(shù)據(jù)分析。例如，將身高的度量單位從米變成英寸，或體重從公斤變?yōu)榘?，?huì)導(dǎo)致非常不同的結(jié)果。

通常，用更小的單位表達(dá)的屬性會(huì)有一個(gè)更大的屬性取值范圍，傾向于給這類(lèi)屬性更大的效應(yīng)或“權(quán)重”。為了避免對(duì)度量單位的依賴(lài)，數(shù)據(jù)需要被標(biāo)準(zhǔn)化。

這會(huì)將數(shù)據(jù)按比例縮放在一個(gè)更小或更常見(jiàn)的區(qū)間，如[-1,1]或[0,1]。94PPT課件

標(biāo)準(zhǔn)化數(shù)據(jù)會(huì)給所有屬性相同權(quán)重。在分類(lèi)算法包括神經(jīng)網(wǎng)絡(luò)或最近令分類(lèi)以及聚類(lèi)中，標(biāo)準(zhǔn)化特別有效。如果在神經(jīng)網(wǎng)絡(luò)反向傳播算法中，對(duì)每個(gè)訓(xùn)練元組的每個(gè)屬性的輸入值進(jìn)行標(biāo)準(zhǔn)化，則會(huì)加速學(xué)習(xí)的速度。對(duì)于基于距離的方法，標(biāo)準(zhǔn)化可以避免屬性在初始時(shí)具有大的范圍？在沒(méi)有給定數(shù)據(jù)的先驗(yàn)知識(shí)時(shí)也很有用。有許多數(shù)據(jù)標(biāo)準(zhǔn)化的方法，如：最小——最大值標(biāo)準(zhǔn)化Z-分?jǐn)?shù)標(biāo)準(zhǔn)化十進(jìn)制換算標(biāo)準(zhǔn)化95PPT課件令A(yù)是一個(gè)數(shù)值屬性，有n個(gè)觀察到的值v1,v2,…,vn.最小——最大值標(biāo)準(zhǔn)化：令minA和maxA表示屬性A的最小值和最大值，最小——最大值標(biāo)準(zhǔn)化將值vi映射為vi’(范圍是[new_minA,new_maxA]:最小——最大值標(biāo)準(zhǔn)化保留了原有數(shù)據(jù)值的關(guān)系。如果后來(lái)的輸入的標(biāo)準(zhǔn)化的數(shù)據(jù)落在了原有數(shù)據(jù)區(qū)間的外面，將會(huì)發(fā)生過(guò)界的錯(cuò)誤。96PPT課件Min_max

normarlization舉例假定收入屬性的最小值和最大值分別是$12,000和$98,000.將收入屬性映射到范圍[0.0,1.0]上。則一個(gè)值為$73,600的收入標(biāo)準(zhǔn)化為：97PPT課件Z-分?jǐn)?shù)標(biāo)準(zhǔn)化

98PPT課件Z-scorenormarlization舉例假定income屬性的均值和標(biāo)準(zhǔn)差是$54,000和$16,000。使用z-分?jǐn)?shù)標(biāo)準(zhǔn)化，則$73,600被轉(zhuǎn)換為：99PPT課件Z-分?jǐn)?shù)標(biāo)準(zhǔn)化的變體是使用屬性A的平均絕對(duì)偏差來(lái)替換標(biāo)準(zhǔn)差。平均絕對(duì)偏差sA的計(jì)算公式為：用sA替換σA即可。平均絕對(duì)偏差比標(biāo)準(zhǔn)差對(duì)離群點(diǎn)更健壯，因?yàn)闆](méi)有平方。即離群點(diǎn)的效應(yīng)被減弱。100PPT課件十進(jìn)制換算標(biāo)準(zhǔn)化

十進(jìn)制換算標(biāo)準(zhǔn)化通過(guò)移動(dòng)屬性A的值的十進(jìn)制小數(shù)點(diǎn)來(lái)標(biāo)準(zhǔn)化。移動(dòng)的數(shù)目依賴(lài)于屬性A的絕對(duì)值的最大值。轉(zhuǎn)換公式為：其中，j是使max(|vi’|)<1的最小整數(shù)。101PPT課件Decimalscalingnormarlization舉例

假設(shè)屬性A的記錄值的范圍是-986到917.則A的絕對(duì)值的最大值為986.通過(guò)十進(jìn)制換算標(biāo)準(zhǔn)化，將每個(gè)值除以1000（因?yàn)閖=3)，所以-986標(biāo)準(zhǔn)化為：-0.986.917標(biāo)準(zhǔn)化為0.917.102PPT課件

注意標(biāo)準(zhǔn)化會(huì)小部分的改變?cè)袛?shù)據(jù)，特別是在用z-分?jǐn)?shù)標(biāo)準(zhǔn)化和十進(jìn)制換算標(biāo)準(zhǔn)化時(shí)。

將標(biāo)準(zhǔn)化參數(shù)存儲(chǔ)起來(lái)是有必要的，因?yàn)閷?lái)的數(shù)據(jù)可以使用同一方式進(jìn)行標(biāo)準(zhǔn)化。103PPT課件3.5.3裝箱離散化技術(shù)

裝箱技術(shù)在3.2.2節(jié)已被討論過(guò)。

裝箱技術(shù)沒(méi)有使用分類(lèi)信息，因此是無(wú)監(jiān)督的離散化技術(shù)。它對(duì)人為指定的箱子個(gè)數(shù)以及離群點(diǎn)比較敏感。104PPT課件3.5.4直方圖分析的離散化技術(shù)

直方圖也是一種無(wú)監(jiān)督的離散化技術(shù)。在2.2.3節(jié)已被討論過(guò)。

最小的區(qū)間尺寸可以被用來(lái)控制遞歸分割的步驟。這可以指明分割的最小寬度，或者每個(gè)分割的最小值數(shù)目。直方圖還可以基于數(shù)據(jù)分布的聚類(lèi)分析來(lái)分割。105PPT課件3.5.5聚類(lèi)、決策樹(shù)以及關(guān)聯(lián)分析離散化技術(shù)

聚類(lèi)分析是一種流行的數(shù)據(jù)離散化方法。一個(gè)聚類(lèi)算法可以應(yīng)用到數(shù)值屬性上，將屬性A的值分割成簇或分組。聚類(lèi)考慮屬性A的分布，和數(shù)據(jù)點(diǎn)的緊密度，因此會(huì)產(chǎn)生高質(zhì)量的離散化結(jié)果。

聚類(lèi)可以被用來(lái)生成屬性A的概念層次，使用自頂向下的分割策略或者自底向上的合并策略。106PPT課件

決策樹(shù)分類(lèi)技術(shù)也可以用來(lái)做數(shù)據(jù)的離散化。這種技術(shù)采用自頂向下的分割方法。不同于其他的前面提到的方法，這是一種有監(jiān)督的離散化方法，即使用分類(lèi)標(biāo)簽的信息。

例如，我們有一個(gè)數(shù)據(jù)集，包括病人的癥狀（屬性）以及病人的相應(yīng)診斷類(lèi)別標(biāo)簽。在計(jì)算和確定分割點(diǎn)時(shí)使用到分類(lèi)分布信息。直觀地，主要思想是選擇分割點(diǎn)，使一個(gè)給定的分割包含同類(lèi)別的盡可能多的元組。熵是在這種情況適用的最普遍的測(cè)量。離散化數(shù)值屬性A時(shí)，選擇有最小熵的屬性A作為分割點(diǎn)，然后遞歸的分割結(jié)果區(qū)間，以得到一個(gè)層次的離散化結(jié)果。最終形成一個(gè)屬性A的概念層次。

因?yàn)闆Q策樹(shù)離散化適用分類(lèi)信息，區(qū)間界限定義的地方更可能提高分類(lèi)的精確性。107PPT課件

關(guān)聯(lián)分析也可以用于數(shù)據(jù)離散化。ChiMerge是一種基于卡方分布的離散化方法。之前的離散化方法中，都是采用一種自頂向下的分割策略。這種ChiMerge的方法是采用自底向上的方法，通過(guò)尋找最優(yōu)的鄰