帶你讀《資料挖掘導論（原書第2版）》之二：資料

點選檢視第一章 點選檢視第三章

第2章 數　　據

本章讨論一些與資料相關的問題，它們對于資料挖掘的成敗至關重要。

資料類型　資料集的不同表現在多方面。例如，用來描述資料對象的屬性可以具有不同的類型——定量的或定性的，并且資料集通常具有特定的性質，例如，某些資料集包含時間序列或彼此之間具有明顯聯系的對象。毫不奇怪，資料的類型決定我們應使用何種工具和技術來分析資料。此外，資料挖掘研究常常是為了适應新的應用領域和新的資料類型的需要而展開的。

資料的品質　資料通常遠非完美。盡管大部分資料挖掘技術可以忍受某種程度的資料不完美，但是注重了解和提高資料品質将改進分析結果的品質。通常必須解決的資料品質問題包括存在噪聲和離群點，資料遺漏、不一緻或重複，資料有偏差或者不能代表它應該描述的現象或總體情況。

使資料适合挖掘的預處理步驟　通常，原始資料必須加以處理才能适合分析。處理一方面是要提高資料的品質，另一方面要讓資料更好地适應特定的資料挖掘技術或工具。例如，有時需要将連續值屬性（如長度）轉換成離散的分類值的屬性（如短、中、長），23以便應用特定的技術。又如，資料集屬性的數目常常需要減少，因為屬性較少時許多技術用起來更加有效。

根據資料聯系分析資料　資料分析的一種方法是找出資料對象之間的聯系，之後使用這些聯系而不是資料對象本身來進行其餘的分析。例如，我們可以計算對象之間的相似度或距離，然後根據這種相似度或距離進行分析——聚類、分類或異常檢測。諸如此類的相似性或距離度量很多，要根據資料的類型和特定的應用做出正确的選擇。

例2.1 與資料相關的問題　為了進一步解釋這些問題的重要性，考慮下面的假想情況。你收到某個醫學研究者發來的電子郵件，是關于你想要研究的一個項目的。郵件的内容如下：

盡管有些疑慮，你還是開始着手分析這些資料。檔案的前幾行如下：

粗略觀察這些資料并未發現什麼不對。你抛開疑慮，并開始分析。資料檔案隻有1000行，比你希望的小，24兩天之後你認為你已經取得一些進展。你去參加會議，在等待其他人時，你開始與一位參與該項目工作的統計人員交談。當聽說你正在分析該項目的資料時，她請你向她簡略介紹你的結果。

盡管這一場景代表一種極端情況，但它強調了“了解資料”的重要性。為此，本章将讨論上面提到的4個問題，列舉一些基本難點和标準解決方法。

2.1　資料類型

通常，資料集可以看作資料對象的集合。資料對象有時也叫作記錄、點、向量、模式、事件、案例、樣本、執行個體、觀測或實體。資料對象用一組刻畫對象的特性（如物體品質或事件發生時間）的屬性描述。屬性有時也叫作變量、特性、字段、特征或維。

例2.2 學生資訊　通常，資料集是一個檔案，其中對象是檔案的記錄（或行），而每個字段（或列）對應于一個屬性。例如，表2.1顯示了包含學生資訊的資料集。每行對應一個學生，而每列是一個屬性，描述學生的某一方面，如平均績點（GPA）或辨別号（ID）。

基于記錄的資料集在平展檔案或關系資料庫系統中是最常見的，但是還有其他類型的資料集和存儲資料的系統。在2.1.2節，我們将讨論資料挖掘中經常遇到的其他類型的資料集。然而，我們先考慮屬性。

2.1.1　屬性與度量

本小節考慮使用何種類型的屬性描述資料對象。首先定義屬性，然後考慮屬性類型的含義，最後介紹經常遇到的屬性類型。

1.什麼是屬性

我們先更詳細地定義屬性。

定義2.1 屬性（attribute）　對象的性質或特性，它因對象而異，或随時間而變化。例如，眼球顔色因人而異，而物體的溫度随時間而變。注意：眼球顔色是一種符号屬性，具有少量可能的值{棕色，黑色，藍色，綠色，淡褐色，…}；而溫度是數值屬性，可以取無窮多個值。

追根溯源，屬性并非數字或符号。然而，為了讨論和精細地分析對象的特性，我們為它們賦予了數字或符号。為了用一種明确定義的方式做到這一點，我們需要測量标度。

定義2.2測量标度（measurement scale）　将數值或符号值與對象的屬性相關聯的規則（函數）。形式上，測量過程是使用測量标度将一個值與一個特定對象的特定屬性相關聯。這看上去有點抽象，但是任何時候，我們總在進行這樣的測量過程。例如，踏上體重秤稱體重；将人分為男女；清點會議室的椅子數量，确定是否能夠為所有與會者提供足夠的座位。在所有這些情況下，對象屬性的“實體值”都被映射到數值或符号值。

有了這些背景，我們就可以讨論屬性類型，這對于确定特定的資料分析技術是否适用于某種具體的屬性是非常重要的。

2.屬性類型

我們通常将屬性的類型稱為測量标度的類型。從前面的讨論顯而易見，屬性可以用不同的測量标度來描述，并且屬性的性質不必與用來度量它的值的性質相同。換句話說，用來代表屬性的值可能具有不同于屬性本身的性質，反之亦然。我們用兩個例子來解釋。

例2.3 雇員年齡和ID号　與雇員有關的兩個屬性是ID和年齡，這兩個屬性都可以用整數表示。然而，談論雇員的平均年齡是有意義的，但是談論雇員的平均ID卻毫無意義。的确，我們希望ID屬性所表達的唯一方面是它們互不相同。因而，對雇員ID的唯一合法操作就是判定它們是否相等。但在使用整數表示雇員ID時，并沒暗示有此限制。對于年齡屬性而言，用來表示年齡的整數的性質與該屬性的性質大同小異。盡管如此，這種對應仍不完備，例如，年齡有最大值，而整數沒有。

例2.4 線段長度　考慮圖2.1，它展示了一些線段對象和如何用兩種不同的方法将這些對象的長度屬性映射到整數。從上到下，每條後繼線段都是通過最上面的線段自我添加而形成的。這樣，第二條線段是最上面的線段兩次相連形成的，第三條線段是最上面的線段三次相連形成的，以此類推。從實體意義上講，所有的線段都是第一條線段的倍數。這個事實由圖右邊的測量捕獲，但未被左邊的測量捕獲。更準确地說，左邊的測量标度僅僅捕獲長度屬性的序，而右邊的标度同時捕獲序和可加性的性質。是以，屬性可以用一種不描述屬性全部性質的方式測量。

知道屬性的類型很重要，因為它告訴我們測量值的哪些性質與屬性的基本性質一緻，進而使得我們可以避免諸如計算雇員的平均ID這樣的愚蠢行為。

3.屬性的不同類型

一種指定屬性類型的有用（和簡單）的辦法是，确定對應屬性基本性質的數值的性質。例如，長度的屬性可以有數值的許多性質。按照長度比較對象，确定對象的排序，以及談論長度的差和比例都是有意義的。數值的如下性質（操作）常常用來描述屬性。

1) 相異性：=和≠。

2) 序：<、≤、>和≥。

3) 加法：+和-。

4) 乘法：*和/。

給定這些性質，我們可以定義四種屬性類型：标稱（nominal）、序數（ordinal）、區間（interval）和比率（ratio）。表2.2給出這些類型的定義，以及每種類型上有哪些合法的統計操作等資訊。每種屬性類型擁有其上方屬性類型上的所有性質和操作。是以，對于标稱、序數和區間屬性合法的任何性質或操作，對于比率屬性也合法。換句話說，屬性類型的定義是累積的。29當然，對于某種屬性類型合适的統計操作，對其上方的屬性類型就不一定合适。

标稱和序數屬性統稱分類的（categorical）或定性的（qualitative）屬性。顧名思義，定性屬性（如雇員ID）不具有數的大部分性質。即便使用數（即整數）表示，也應當像對待符号一樣對待它們。其餘兩種類型的屬性，即區間和比率屬性，統稱定量的（quantitative）或數值的（numeric）屬性。定量屬性用數表示，并且具有數的大部分性質。注意：定量屬性可以是整數值或連續值。

屬性的類型也可以30用不改變屬性意義的變換來描述。實際上，心理學家S.Smith Stevens最先用允許的變換（permissible transformation）定義了表2.2所示的屬性類型。例如，如果長度分别用米和英尺度量，其屬性的意義并未改變。

對特定的屬性類型有意義的統計操作是：當使用保持屬性意義的變換對屬性進行變換時，它們産生的結果相同。例如，用米和英尺為機關進行度量時，同一組對象的平均長度數值是不同的，但是兩個平均值都代表相同的長度。表2.3給出表2.2中四種屬性類型的允許的（保持意義的）變換。

例2.5 溫度标度　溫度可以很好地解釋前面介紹的一些概念。首先，溫度可以是區間屬性或比率屬性，這取決于其測量标度。當溫度用開爾文溫标測量時，從實體意義上講，2度的溫度是1度的兩倍；當溫度用華氏或攝氏标度測量時則并非如此，因為這時1度溫度與2度溫度相差并不太多。31問題是從實體意義上講，華氏和攝氏标度的零點是硬性規定的，是以，華氏或攝氏溫度的比率并無實體意義。

4.用值的個數描述屬性

區分屬性的一種獨立方法是根據屬性可能取值的個數來判斷。

• 離散的（discrete）　離散屬性具有有限個值或無限可數個值。這樣的屬性可以是分類的（如郵政編碼或ID号），也可以是數值的（如計數）。通常，離散屬性用整數變量表示。二進制屬性（binary attribute）是離散屬性的一種特殊情況，并隻接受兩個值，如真/假、是/否、男/女或0/1。通常，二進制屬性用布爾變量表示，或者用隻取兩個值0或1的整型變量表示。
• 連續的（continuous）　連續屬性是取實數值的屬性，如溫度、高度或重量等屬性。通常，連續屬性用浮點變量表示。實踐中，實數值能可以有限的精度測量和表示。

從理論上講，任何測量标度類型（标稱的、序數的、區間的和比率的）都可以與基于屬性值個數的任意類型（二進制的、離散的和連續的）組合。然而，有些組合并不常出現，或者沒有什麼意義。例如，很難想象一個實際資料集包含連續的二進制屬性。通常，标稱和序數屬性是二進制的或離散的，而區間和比率屬性是連續的。然而，計數屬性（count attribute）是離散的，也是比率屬性。

5.非對稱的屬性

對于非對稱的屬性（asymmetric attribute），出現非零屬性值才是重要的。考慮這樣一個資料集，其中每個對象是一個學生，而每個屬性記錄學生是否選修大學的某個課程。對于某個學生，如果他選修了對應某屬性的課程，該屬性取值1，否則取值0。由于學生隻選修所有可選課程中的很小一部分，這種資料集的大部分值為0，是以，關注非零值将更有意義、32更有效。否則，如果在學生不選修的課程上做比較，則大部分學生都非常相似。隻有非零值才重要的二進制屬性是非對稱的二進制屬性。這類屬性對于關聯分析特别重要。關聯分析将在第5章讨論。也可能有離散的或連續的非對稱特征。例如，如果記錄每門課程的學分，則結果資料集将包含非對稱的離散屬性或連續屬性。

6.度量水準的總體評價

正如本章其餘部分所描述的，資料有許多不同的類型。先前關于測量标度的讨論雖然有用，但并不完整，仍有一些局限。是以我們給出如下見解和指引。

• 相異性、有序性和有意義的區間及比率隻是資料的四個屬性——其他許多屬性都是可能的。舉例來講，一些資料本質上是周期性的，例如地球表面上的位置或時間。再如，考慮值為集合的屬性，其中每個屬性值是一組元素的集合，例如去年看過的所有電影。如果第二個集合是第一個集合的子集，則定義第一個元素（電影）集合比第二個集合更大（包含）。但是，這種關系隻是定義了一個與剛才定義的任何屬性類型都不比對的偏序。
• 用于表示屬性值的數字或符号可能無法蘊含屬性的所有性質，或者所蘊含的性質并不存在。例2.3給出了關于整數的說明，即ID的平均值和超出範圍的年齡。
• 為分析目的資料經常進行轉換——參見2.3.7節。通常将觀測變量的分布改變為更容易分析的分布，例如高斯（正态）分布。這種轉換隻保留了原始值的順序，其他的性質将會丢失。盡管如此，如果期望的結果是一個差異的統計檢驗或預測模型，那這種轉換是合理的。
• 對任何資料分析的最終評估，包括對屬性的操作，都是從專業領域的角度分析結果是否有意義。

總之，确定哪些操作可以在特定的屬性或屬性集合上執行，而不影響分析的完整性是十分具有挑戰性的。幸運的是，既定的做法往往是一個可靠的指南，而有時候标準做法也有可能是錯誤的或有局限性的。

2.1.2　資料集的類型

資料集的類型有多種，并且随着資料挖掘的發展與成熟，還會有更多類型的資料集用于分析。本小節介紹一些很常見的類型。為友善起見，我們将資料集的類型分成三組：記錄資料、基于圖形的資料和有序資料。這些分類不能涵蓋所有的可能性，肯定還存在其他的分組。

1.資料集的一般特性

在提供特定類型資料集的細節之前，我們先讨論适用于許多資料集的三個特性，即次元、分布和分辨率，它們對資料挖掘技術具有重要影響。

次元（dimensionality）　資料集的次元是資料集中的對象具有的屬性數目。低次元資料往往與中、高次元資料有質的不同。事實上，分析高維資料有時會陷入所謂的維災難（curse of dimensionality）。正因如此，資料預處理的一個重要動機就是減少次元，稱為維歸約（dimensionality reduction）。這些問題将在本章後面和附錄B中更深入地讨論。

分布（distribution）　資料集的分布是構成資料對象的屬性的各種值或值的集合出現的頻率。同樣，資料集的分布可以看作對資料空間各個區域中對象集中程度的描述。統計學家列舉了許多分布的類型，如高斯分布（正态分布)，并描述了它們的性質（見附錄C）。雖然描述分布的統計方法可以産生強大的分析技術，但是許多資料集的分布并沒有被标準的統計分布很好地解釋。

是以許多資料挖掘算法并沒有為其分析的資料假定某個特定的統計分布。然而，分布的一般特性通常具有強烈的影響。例如，假設将類别屬性用作類變量，其中一個類别在95％的情況下出現，而其他類别隻在5%的情況下發生。正如4.11節所讨論的那樣，這種分布的傾斜度（skewness）會使分類變得困難（傾斜度對資料分析有其他影響，這裡不做讨論）。

傾斜資料的一個特例是稀疏性（sparsity）。對于稀疏的二進制、計數或連續資料，一個對象的大多數屬性值為0。在許多情況下，非零項還不到1%。實際上，稀疏性是一個優點，因為通常隻有非零值才需要存儲和處理。這将節省大量的計算時間和存儲空間。事實上，有些資料挖掘算法，如第5章介紹的關聯規則挖掘算法，僅适合處理稀疏資料。最後，請注意稀疏資料集中的屬性通常是非對稱屬性。

分辨率（resolution）　經常可以在不同的分辨率下得到資料，并且在不同的分辨率下資料的性質不同。例如，在幾米的分辨率下，地球表面看上去很不平坦，但在數十公裡的分辨率下卻相對平坦。資料的模式也依賴于分辨率。如果分辨率太高，模式可能看不出，或者掩埋在噪聲中；如果分辨率太低，模式可能不出現。例如，幾小時記錄一下氣壓變化可以反映出風暴等天氣系統的移動；而在月的标度下，這些現象就檢測不到。

2.記錄資料

許多資料挖掘任務都假定資料集是記錄（資料對象）的彙集，每個記錄包含固定的資料字段（屬性）集，如圖2.2a所示。對于記錄資料的大部分基本形式，記錄之間或資料字段之間沒有明顯的聯系，并且每個記錄（對象）具有相同的屬性集。記錄資料通常存放在平展檔案或關系資料庫中。關系資料庫當然不僅僅是記錄的彙集，它還包含更多的資訊，但是資料挖掘一般并不使用關系資料庫的這些資訊。35更确切地說，資料庫是查找記錄的友善場所。下面介紹不同類型的記錄資料，并用圖2.2加以說明。

事務資料或購物籃資料　事務資料（transaction data）是一種特殊類型的記錄資料，其中每個記錄（事務）涉及一系列的項。考慮一個雜貨店。顧客一次購物所購買的商品的集合就構成一個事務，而購買的商品是項。這種類型的資料稱為購物籃資料（market basket data），因為記錄中的項是顧客“購物籃”中的商品。事務資料是項的集合的集族，但是也可以将它視為記錄的集合，其中記錄的字段是非對稱的屬性。這些屬性常常是二進制的，指出商品是否已買。36更一般地，這些屬性還可以是離散的或連續的，例如表示購買的商品數量或購買商品的花費。圖2.2b展示了一個事務資料集，每一行代表一位顧客在特定時間購買的商品。

資料矩陣　如果一個資料集族中的所有資料對象都具有相同的數值屬性集，則資料對象可以看作多元空間中的點（向量），其中每個維代表對象的一個不同屬性。這樣的資料對象集可以用一個m×n的矩陣表示，其中，有m行（一個對象一行）n列（一個屬性一列），也可以用清單示資料對象，用行表示屬性。這種矩陣稱作資料矩陣（data matrix）或模式矩陣（pattern matrix）。資料矩陣是記錄資料的變體，但是，由于它由數值屬性組成，可以使用标準的矩陣操作對資料進行變換和處理，是以，對于大部分統計資料，資料矩陣是一種标準的資料格式。圖2.2c展示了一個樣本資料矩陣。

稀疏資料矩陣　稀疏資料矩陣是資料矩陣的一種特殊情況，其中屬性的類型相同并且是非對稱的，即隻有非零值才是重要的。事務資料是僅含0和1元素的稀疏資料矩陣的例子。另一個常見的例子是文檔資料。特别地，如果忽略文檔中詞（術語）的次序——“詞袋”法——則文檔可以用詞向量表示，其中每個詞是向量的一個分量（屬性），而每個分量的值是對應詞在文檔中出現的次數。文檔集合的這種表示通常稱作文檔詞矩陣（document-term matrix）。圖2.2d顯示了一個文檔詞矩陣。文檔是該矩陣的行，而詞是矩陣的列。實踐應用時，僅存放稀疏資料矩陣的非零項。

3.基于圖的資料

有時，圖形可以友善而有效地表示資料。我們考慮兩種特殊情況：（1）圖捕獲資料對象之間的聯系；（2）資料對象本身用圖表示。

帶有對象之間聯系的資料　對象之間的聯系常常攜帶重要資訊。在這種情況下，資料常常用圖表示。一般把資料對象映射到圖的結點，而對象之間的聯系用對象之間的鍊和諸如方向、權值等鍊性質表示。考慮網際網路上的網頁，頁面上包含文本和指向其他頁面的連結。為了處理搜尋查詢，Web搜尋引擎收集并處理網頁，提取它們的内容。然而，衆所周知，指向或出自每個頁面的連結包含大量該頁面與查詢相關程度的資訊，因而必須考慮。

圖2.3a顯示了互相連結的網頁集。圖資料的另一個重要例子是社交網絡，其中的資料對象是人，人與人之間的聯系是他們通過社交媒體進行的互動。

具有圖對象的資料　如果對象具有結構，即對象包含具有聯系的子對象，則這樣的對象常常用圖表示。例如，化合物的結構可以用圖表示，其中結點是原子，結點之間的鍊是化學鍵。圖2.3b給出化合物苯的分子結構示意圖，其中包含碳原子（黑色）和氫原子（灰色）。圖表示可以确定何種子結構頻繁地出現在化合物的集合中，并且弄清楚這些子結構中是否有某種子結構與諸如熔點或生成熱等特定的化學性質有關。頻繁圖挖掘是資料挖掘中分析這類資料的一個分支，将在6.5節讨論。

4.有序資料

對于某些資料類型，屬性具有涉及時間或空間序的聯系。下面介紹各種類型的有序資料，如圖2.4所示。圖2.3　不同的圖形資料

時序事務資料　時序事務資料（sequential transaction data）可以看作事務資料的擴充，其中每個事務包含一個與之相關聯的時間。考慮帶有事務發生時間的零售事務資料。時間資訊可以幫助我們發現“萬聖節前夕糖果銷售達到高峰”之類的模式。時間也可以與每個屬性相關聯，例如，每個記錄可以是一位顧客的購物曆史，包含不同時間購買的商品清單。使用這些資訊，就有可能發現“購買DVD播放機的人趨向于在其後不久購買DVD”之類的模式。

圖2.4a展示了一些時序事務資料。有5個不同的時間——t1、t2、t3、t4和t5，3位不同的顧客——C1、C2和C3，5種不同的商品——A、B、C、D和E。在圖a上面的表中，每行對應一位顧客在特定的時間購買的商品。例如，在時間t3，顧客C2購買了商品A和D。下面的表顯示相同的資訊，但每行對應一位顧客。每行包含涉及該顧客的所有事務資訊，其中每個事務包含一些商品和購買這些商品的時間，例如，顧客C3在時間t2購買了商品A和C。

時間序列資料　時間序列資料（time series data）是一種特殊的有序資料類型，其中每條記錄都是一個時間序列（time series），即一段時間以來的測量序列。例如，金融資料集可能包含各種股票每日價格的時間序列對象。再例如，考慮圖2.4c，該圖顯示明尼阿波利斯市從1982年到1994年的月平均氣溫的時間序列。在分析諸如時間序列的時間資料時，重要的是要考慮時間自相關（temporal autocorrelation），即如果兩個測量的時間很接近，則這些測量的值通常非常相似。

序列資料　序列資料（sequence data）是一個38　～40資料集合，它是各個實體的序列，如詞或字母的序列。除沒有時間戳之外，它與時序資料非常相似，隻是有序序列考慮項的位置。例如，動植物的遺傳資訊可以用稱作基因的核苷酸的序清單示，與遺傳序列資料有關的許多問題都涉及由核苷酸序列的相似性預測基因結構和功能的相似性。圖2.4b顯示用4種核苷酸表示的一段人類基因碼。所有的DNA都可以由A、T、G和C四種核苷酸構造。

空間和時空資料　有些對象除了其他類型的屬性之外，還具有空間屬性，如位置或區域。空間資料的一個例子是從不同的地理位置收集的氣象資料（降水量、氣溫、氣壓）。這些測量通常是随時間收集的，是以，這些資料由不同位置的時間序列組成。在這種情況下，我們将資料稱為時空資料。雖然可以對每個特定的時間或位置分别進行分析，但對時空資料更完整的分析需要考慮資料的時間和空間兩個方面。

空間資料的一個重要方面是空間自相關性（spatial autocorrelation），即實體上靠近的對象趨于在其他方面也相似。是以，地球上兩個互相靠近的點通常具有相近的氣溫和降水量。值得注意的是，空間自相關性類似于時間自相關性。

空間和時空資料的重要例子是科學和工程資料集，其資料取自二維或三維網格上規則或不規則分布的點上的測量或模型輸出結果。例如，地球科學資料集記錄在各種分辨率（如每度）下經緯度球面網格點（網格單元）上測量的溫度和氣壓，如經緯度都為1°。另一個例子是，在瓦斯氣流模拟中，可以針對模拟中的每個網格點記錄不同時刻的流速和方向。還有一種不同類型的時空資料來自在時間和空間中追蹤物體（例如車輛）的軌迹。

5.處理非記錄資料

大部分資料挖掘算法都是為記錄資料或其變體（如事務資料和資料矩陣）設計的。通過從資料對象中提取特征，并使用這些特征建立對應于每個對象的記錄，針對記錄資料的技術也可以用于非記錄資料。考慮前面介紹的化學結構資料。給定一個常見的子結構集合，每個化合物都可以用一個具有二進制屬性的記錄表示，這些二進制屬性指出化合物是否包含特定的子結構。41這樣的表示實際上是事務資料集，其中事務是化合物，而項是子結構。

在某些情況下，容易用記錄形式表示資料，但是這類表示并不能捕獲資料中的所有資訊。考慮這樣的時空資料，它由空間網格每一點上的時間序列組成。通常，這種資料存放在資料矩陣中，其中每行代表一個位置，而每列代表一個特定的時間點。然而，這種表示并不能明确地表示屬性之間存在的時間聯系以及對象之間存在的空間聯系。但并不是說這種表示不合适，而是說分析時必須考慮這些聯系。例如，在使用資料挖掘技術時，忽略屬性的時間自相關性或資料對象的空間自相關性（即空間網格上的位置）并不是一個好主意。

2.2　資料品質

資料挖掘算法通常用于為其他目的收集的資料，或者在收集時未明确其目的。是以，資料挖掘常常不能“在資料源頭控制品質”。相比之下，統計學的實驗設計或調查中，其資料品質往往都達到了一定的要求。由于無法避免資料品質問題，是以資料挖掘着眼于兩個方面：（1）資料品質問題的檢測和糾正；（2）使用可以容忍低品質資料的算法。第一步的檢測和糾正，通常稱作資料清理（data cleaning）。

下面幾小節讨論資料品質。盡管也讨論某些與應用有關的問題，但是關注的焦點是測量和資料收集問題。

2.2.1　測量和資料收集問題

期望資料完美是不現實的。人類的錯誤、測量裝置的限制或資料收集過程中的漏洞都可能導緻問題。資料的值乃至整個資料對象都可能會丢失。在有些情況下，可能有不真實或重複的對象，即對應于單個“實際”對象出現了多個資料對象。例如，對于一個最近住過兩個不同地方的人，42可能有兩個不同的記錄。即使所有的資料都不缺，并且“看上去很好”，也可能存在不一緻，如一個人身高2m，但體重隻有2kg。

下面我們關注資料測量和收集方面的資料品質問題。我們先定義測量誤差和資料收集錯誤，然後考慮涉及測量誤差的各種問題：噪聲、僞像、偏置、精度和準确率。最後讨論同時涉及測量和資料收集的資料品質問題：離群點、遺漏和不一緻的值、重複資料。

1.測量誤差和資料收集錯誤

術語測量誤差（measurement error）是指測量過程中産生的問題。一個常見的問題是：在某種程度上，記錄的值與實際值不同。對于連續屬性，測量值與實際值的差稱為誤差（error）。術語資料收集錯誤（data collection error）是指諸如遺漏資料對象或屬性值，或者不當地包含了其他資料對象等錯誤。例如，一種特定種類動物研究可能包含了相關種類的其他動物，它們隻是表面上與要研究的種類相似。測量誤差和資料收集錯誤可能是系統的也可能是随機的。

我們隻考慮一般的錯誤類型。在特定的領域中，總有某些類型的錯誤是常見的，并且通常存在很好的技術，能檢測并糾正這些錯誤。例如，人工輸入資料時，鍵盤錄入錯誤是常見的，是以許多資料輸入程式具有檢測技術，并通過人工幹預糾正這類錯誤。

2.噪聲和僞像

噪聲是測量誤差的随機部分。這通常涉及值被扭曲或加入了謬誤對象。圖2.5顯示了被随機噪聲幹擾前後的時間序列。如果在時間序列上添加更多的噪聲，形狀将會消失。圖2.6顯示了三組添加一些噪聲點（用“+”表示）前後的資料點集。注意，有些噪聲點與非噪聲點混在一起。

術語“噪聲”通常用于包含時間或空間分量的資料。在這些情況下，常常可以使用信号或圖像處理技術降低噪聲，進而幫助發現可能“淹沒在噪聲中”的模式（信号）。盡管如此，完全消除噪聲通常是困難的，而許多資料挖掘工作都關注設計魯棒算法（robust algorithm），即在噪聲幹擾下也能産生可以接受的結果。

資料錯誤可能是更确定性現象的結果，如一組照片在同一地方出現條紋。資料的這種确定性失真常稱作僞像（artifact）。

3.精度、偏置和準确率

在統計學和實驗科學中，測量過程和結果資料是用精度和偏置度量的。我們給出标準的定義，随後簡略加以讨論。對于下面的定義，我們假定對相同的基本量進行重複測量。

定義2.3 精度（precision）　（同一個量的）重複測量值之間的接近程度。

定義2.4 偏置（bias）　測量值與被測量之間的系統的變化。精度通常用值集合的标準差度量，而偏置用值集合的均值與測出的已知值之間的差度量。隻有那些通過外部手段能夠得到測量值的對象，偏置才是可确定的。假定我們有1g品質的标準實驗室重量，并且想評估實驗室的新天平的精度和偏置。我們稱重5次，得到下列值：{1.015，0.990，1.013，1.001，0.986}。這些值的均值是1.001，是以偏置是0.001。用标準差度量，精度是0.013。

通常使用更一般的術語準确率表示資料測量誤差的程度。

定義2.5準确率（accuracy）　被測量的測量值與實際值之間的接近度。

準确率依賴于精度和偏置，但是沒有用這兩個量表達準确率的公式。

準确率的一個重要方面是有效數字（significant digit）的使用。其目标是僅使用資料精度所能确定的數字位數表示測量或計算結果。例如，對象的長度用最小刻度為毫米的米尺測量，則我們隻能記錄最接近毫米的長度資料，這種測量的精度為±0.5mm。這裡不再詳細地讨論有效數字，因為大部分讀者應當在先前的課程中接觸過，并且在理工科和統計學教材中讨論得相當深入。

諸如有效數字、精度、偏置和準确率問題常常被忽視，但是對于資料挖掘、統計學和自然科學，它們都非常重要。通常，資料集并不包含資料精度資訊，用于分析的程式傳回的結果也沒有這方面的資訊。45但是，缺乏對資料和結果準确率的了解，分析者将可能出現嚴重的資料分析錯誤。

4.離群點

離群點（outlier）是在某種意義上具有不同于資料集中其他大部分資料對象的特征的資料對象，或是相對于該屬性的典型值來說不尋常的屬性值。我們也稱其為異常（anomalous）對象或異常值。有許多定義離群點的方法，并且統計學和資料挖掘界已經提出了很多不同的定義。此外，差別噪聲和離群點這兩個概念是非常重要的。與噪聲不同，離群點可以是合法的資料對象或值。例如，在欺詐和網絡入侵檢測中，目标就是在大量的正常對象或事件中找到異常對象或事件。第9章會更詳細地讨論異常檢測。

5.遺漏值

一個對象遺漏一個或多個屬性值的情況并不少見。有時可能會出現資訊收集不全的情況，例如有的人拒絕透露年齡或體重。還有些情況下，某些屬性并不能用于所有對象，例如表格常常有條件選擇部分，僅當填表人以特定的方式回答前面的問題時，條件選擇部分才需要填寫，但為簡單起見存儲了表格的所有字段。無論何種情況，在資料分析時都應當考慮遺漏值。

有許多處理遺漏值的政策（和這些政策的變種），每種政策适用于特定的情況。這些政策在下面列出，同時我們指出它們的優缺點。

删除資料對象或屬性　一種簡單而有效的政策是刪除具有遺漏值的資料對象。然而，即使不完整的資料對象也包含一些有用的資訊，并且，如果許多對象都有遺漏值，則很難甚至不可能進行可靠的分析。盡管如此，如果某個資料集隻有少量的對象具有遺漏值，則忽略它們可能是合算的。一種與之相關的政策是删除具有遺漏值的屬性。然而，做這件事要小心，46因為被删除的屬性可能對分析是至關重要的。

估計遺漏值　有時，遺漏值可以可靠地估計。例如，在考慮以大緻平滑的方式變化的、具有少量但分散的遺漏值的時間序列時，遺漏值可以使用其他值來估計（插值）。另舉一例，考慮一個具有許多相似資料點的資料集，與具有遺漏值的點鄰近的點的屬性值常常可以用來估計遺漏的值。如果屬性是連續的，則可以使用最近鄰的平均屬性值；如果屬性是分類的，則可以取最近鄰中最常出現的屬性值。為了更具體地解釋，考慮地面站記錄的降水量，對于未設地面站的區域，降水量可以使用鄰近地面站的觀測值估計。

在分析時忽略遺漏值　許多資料挖掘方法都可以修改，以忽略遺漏值。例如，假定正在對資料對象聚類，需要計算各對資料對象間的相似性。如果某對資料對象的一個對象或兩個對象的某些屬性有遺漏值，則可以僅使用沒有遺漏值的屬性來計算相似性。當然，這種相似性隻是近似的，但是除非整個屬性數目很少，或者遺漏值的數量很大，否則這種誤差影響不大。同樣，許多分類方法都可以修改，以便于處理遺漏值。

6.不一緻的值

資料可能包含不一緻的值。比如位址字段列出了郵政編碼和城市名，但是有的郵政編碼區域并不包含在對應的城市中。這可能是人工輸入該資訊時颠倒了兩個數字，或許是在掃描手寫體時錯讀了一個數字。無論導緻不一緻值的原因是什麼，重要的是能檢測出來，并且如果可能的話，糾正這種錯誤。

有些不一緻類型容易檢測，例如人的身高不應當是負的。另一些情況下，可能需要查閱外部資訊源，例如當保險公司處理賠償要求時，它将對照顧客資料庫核對賠償單上的姓名與位址。

檢測到不一緻後，有時可以對資料進行更正。産品代碼可能有“校驗”數字，或者可以通過一個備案的已知産品代碼清單複核産品代碼，如果發現它不正确但接近一個已知代碼，則糾正它。糾正不一緻需要額外的或備援的資訊。

例2.6 不一緻的海洋表面溫度　該例解釋實際的時間序列資料中的不一緻性。這些資料是在海洋的不同點測量的海洋表面溫度（SST）。最初人們利用船或浮标使用海洋測量方法收集SST資料，而最近開始使用衛星來收集這些資料。為了建立長期的資料集，需要使用這兩種資料源。然而，由于資料來自不同的資料源，兩部分資料存在微妙的不同。這種差異顯示在圖2.7中，該圖顯示了各年度之間SST值的相關性。如果某兩個年度的SST值是正相關的，則對應于這兩年的位置為白色，否則為黑色。（季節性的變化從資料中删除，否則所有的年都是高度相關的。）資料彙集在一起的地方（1983年）有一個明顯的變化。在1958～1982年和1983～1999年兩組中，每組内的年互相之間趨向于正相關，但與另一組的年負相關。這并不意味着該資料不能用，但是分析者應當考慮這種差異對資料挖掘分析的潛在影響。

7.重複資料

資料集可以包含重複或幾乎重複的資料對象。許多人都收到過重複的郵件，因為它們以稍微不相同的名字多次出現在資料庫中。為了檢測并删除這種重複，必須處理兩個主要問題。首先，如果兩個對象實際代表同一個對象，則對應的屬性值必然不同，必須解決這些不一緻的值；其次，需要避免意外地将兩個相似但并非重複的資料對象（如兩個人具有相同姓名）合并在一起。術語去重複（deduplication）通常用來表示處理這些問題的過程。

在某些情況下，兩個或多個對象在資料庫的屬性度量上是相同的，但是仍然代表不同的對象。這種重複是合法的。但是，如果某些算法設計中沒有專門考慮這些屬性可能相同的對象，就還是會導緻問題。本章習題13就是這樣的一個例子。

2.2.2　關于應用的問題

資料品質問題也可以從應用角度考慮，表達為“資料是高品質的，如果它适合預期的應用”。特别是對工商界，資料品質的這種提議非常有用。類似的觀點也出現在統計學和實驗科學中，那裡強調精心設計實驗來收集與特定假設相關的資料。與測量和資料收集一樣，許多資料品質問題與特定的應用和領域有關。我們這裡仍然隻考慮一些一般性問題。

時效性　有些資料在收集後就開始老化。比如說，如果資料提供正在發生的現象或過程的快照，如顧客的購買行為或Web浏覽模式，則快照隻代表有限時間内的真實情況。如果資料已經過時，則基于它的模型和模式也已經過時。49

相關性　可用的資料必須包含應用所需要的資訊。考慮構造一個模型，預測交通事故發生率。如果忽略了駕駛員的年齡和性别資訊，那麼除非這些資訊可以間接地通過其他屬性得到，否則模型的準确率可能是有限的。

確定資料集中的對象相關不太容易。一個常見問題是抽樣偏置（sampling bias），指樣本包含的不同類型的對象與它們在總體中的出現情況不成比例。例如調查資料隻反映對調查做出響應的那些人的意見。（抽樣的其他問題将在2.3.2節進一步讨論。）由于資料分析的結果隻能反映現有的資料，抽樣偏置通常會導緻不正确的分析。

關于資料的知識　理想情況下，資料集附有描述資料的文檔。文檔的品質好壞決定它是支援還是幹擾其後的分析。例如，如果文檔标明若幹屬性是強相關的，則說明這些屬性可能提供了高度備援的資訊，我們通常隻保留一個屬性。（考慮銷售稅和銷售價格。）然而，如果文檔很糟糕，例如，沒有告訴我們某特定字段上的遺漏值用-9999表示，則我們的資料分析就可能出問題。其他應該說明的重要特性是資料精度、特征的類型（标稱的、序數的、區間的、比率的）、測量的刻度（如長度用米還是英尺）和資料的來源。

2.3　資料預處理

本節我們考慮應當采用哪些預處理步驟，讓資料更加适合挖掘。資料預處理是一個廣泛的領域，包含大量以複雜的方式相關聯的不同政策和技術。我們将讨論一些最重要的思想和方法，并試圖指出它們之間的互相聯系。具體地說，我們将讨論如下主題。

• 聚集
• 抽樣
• 維歸約50
• 特征子集選擇
• 特征建立
• 離散化和二進制化
• 變量變換

粗略地說，這些主題分為兩類，即選擇分析所需要的資料對象和屬性，以及建立/改變屬性。這兩種情況的目标都是改善資料挖掘分析工作，減少時間，降低成本，提高品質。細節參見以下幾小節。

術語注記：在下面的内容中，我們有時根據習慣用法，使用特征（feature）或變量（variable）指代屬性（attribute）。

2.3.1　聚集

有時，“少就是多”，而聚集就是如此。聚集（aggregation）将兩個或多個對象合并成單個對象。考慮一個由事務（資料對象）組成的資料集，它記錄一年中不同日期在各地（Minneapolis Chicago……）商店的商品日銷售情況，見表2.4。對該資料集的事務進行聚集的一種方法是，用一個商店的事務替換該商店的所有事務。這把每天出現在一個商店的成百上千個事務記錄歸約成單個日事務，而每天的資料對象的個數減少為商店的個數。

在這裡，一個顯而易見的問題是如何建立聚集事務，即在建立代表單個商店或日期的聚集事務時，如何合并所有記錄的每個屬性的值。定量屬性（如價格）通常通過求和或求平均值進行聚集。定性屬性（如商品）可以忽略，也可以用更高層次的類别來概括，例如電視和電子産品。

表2.4中的資料也可以看作多元數組，其中每個屬性是一個維。從這個角度，聚集是删除屬性（如商品類型）的過程，或者是壓縮特定屬性不同值個數的過程，如将日期的可能值從365天壓縮到12個月。這種類型的聚集通常用于聯機分析處理（OnLine Analytical Processing，OLAP），OLAP的引用在參考文獻中給出。

51聚集的動機有多種。首先，資料歸約導緻的較小資料集需要較少的記憶體和處理時間，是以可以使用開銷更大的資料挖掘算法。其次，通過高層而不是低層資料視圖，聚集起到了範圍或标度轉換的作用。在前面的例子中，在商店位置和月份上的聚集給出資料按月、按商店，而不是按天、按商品的視圖。最後，對象或屬性群的行為通常比單個對象或屬性的行為更加穩定。這反映了統計學事實：相對于被聚集的單個對象，諸如平均值、總數等聚集量具有較小的變異性。對于總數，實際變差大于單個對象的（平均）變差，但是變差的百分比較小；而對于均值，實際變差小于單個對象的（平均）變差。聚集的缺點是可能丢失有趣的細節。在商店的例子中，按月的聚集就丢失了星期幾具有最高銷售額的資訊。

例2.7 澳洲降水量　該例基于澳洲從1982年到1993年的降水量。我們把澳洲國土按經緯度0.5°乘以0.5°大小分成3030個網格。圖2.8a的直方圖顯示了這些網格單元上的平均月降水量的标準差。而圖2.8b的直方圖顯示了相同位置的平均年降水量的标準差。可見，平均年降水量比平均月降水量的變異性小。所有降水量的測量（以及它們的标準差）都以厘米（cm）為機關。

2.3.2　抽樣

抽樣是一種選擇資料對象子集進行分析的常用方法。在統計學中，抽樣長期用于資料的事先調查和最終的資料分析。52在資料挖掘中，抽樣也非常有用。然而，在統計學和資料挖掘中，抽樣的動機并不相同。統計學家使用抽樣的原因是擷取感興趣的整個資料集的代價太高并且太費時間，而資料挖掘人員進行抽樣，通常是因為處理所有資料所需的記憶體或時間方面的計算成本太高。在某些情況下，使用抽樣的算法可以壓縮資料量，以便可以使用更好但開銷較大的資料挖掘算法。

有效抽樣的主要原理如下：如果樣本是有代表性的，則使用樣本與使用整個資料集的效果幾乎一樣。反過來說，若樣本近似地具有與原資料集相同的（感興趣的）性質，則稱樣本是有代表性的。如果資料對象的均值（平均值）是感興趣的性質，而樣本具有近似于原資料集的均值，則樣本就是有代表性的。由于抽樣是一個統計過程，特定樣本的代表性是不一樣的，是以最好能做的就是選擇一個抽樣方案，以確定以很高的機率得到有代表性的樣本。如下所述，這涉及選擇适當的樣本容量以及抽樣技術。

1.抽樣方法

有許多抽樣技術，但是這裡隻介紹少量最基本的抽樣技術及其變種。最簡單的抽樣是簡單随機抽樣（simple random sampling）。53對于這種抽樣，選取任何特定項的機率相等。随機抽樣有兩種變種（其他抽樣技術也一樣）：（1）無放回抽樣——每個選中項立即從構成總體的所有對象集中删除；（2）有放回抽樣——對象被選中時不從總體中删除。在有放回抽樣中，相同的對象可能被多次抽出。當樣本與資料集相比相對較小時，兩種方法産生的樣本差别不大。但是對于分析，有放回抽樣較為簡單，因為在抽樣過程中，每個對象被選中的機率保持不變。

當總體由不同類型的對象組成并且每種類型的對象數量差别很大時，簡單随機抽樣不能充分地代表不太頻繁出現的對象類型。在分析需要所有類型的代表時，這可能出現問題。例如，當為稀有類建構分類模型時，樣本中适當地提供稀有類是至關重要的，是以需要提供具有不同頻率的感興趣的項的抽樣方案。分層抽樣（stratified sampling）就是這樣的方法，它從預先指定的組開始抽樣。在最簡單的情況下，盡管每組的大小不同，但是從每組抽取的對象個數相同。另一種變種是從每一組對象抽取的樣本數量正比于該組的大小。

例2.8 抽樣與資訊損失　一旦標明抽樣技術，就需要選擇樣本容量。較大的樣本容量增大了樣本具有代表性的機率，但也抵消了抽樣帶來的許多好處。反過來，使用較小容量的樣本，可能丢失模式或檢測出錯誤的模式。圖2.9a顯示了包含8000個二維點的資料集，而圖2.9b和圖2.9c顯示了從該資料集抽取的容量分别為2000和500的樣本。該資料集的大部分結構都出現在2000個點的樣本中，但是許多結構在500個點的樣本中丢失了。

例2.9 确定合适的樣本容量　為了說明确定合适的樣本容量需要系統的方法，考慮下面的任務。

使用抽樣可以有效地解決該問題。一種方法是取資料點的一個小樣本，逐對計算點之間的相似性，然後形成高度相似的點組。從每個點組取一個點，則可以得到具有代表性的點的集合。然而，按照該方法，我們需要确定樣本的容量，它以很高的機率確定得到期望的結果，即從每個簇至少找出一個代表點。圖2.10b顯示了随着樣本容量從10變化到60，從10個組的每一個組中得到一個對象的機率。有趣的是，使用容量為20的樣本，隻有很小的機會（20%)得到包含所有10個組的樣本。即便使用容量為30的樣本，得到不包含所有10個組中對象的樣本的機率也很高（幾乎40%）。該問題将在第7章習題4讨論聚類時進一步考察。

2.漸進抽樣

由于可能很難确定合适的樣本容量，是以有時需要使用自适應（adaptive）或漸進抽樣（progressive sampling）方法。這些方法從一個小樣本開始，然後增加樣本容量直至得到足夠容量的樣本。盡管這種技術不需要在一開始就确定正确的樣本容量，但是需要評估樣本的方法，确定它是否足夠大。

例如，假定使用漸進抽樣來學習一個預測模型。盡管預測模型的準确率随樣本容量的增加而增加，但是在某一點準确率的增加趨于穩定。我們希望在穩定點停止增加樣本容量。通過掌握模型準确率随樣本逐漸增大的變化情況，并通過選取接近于目前容量的其他樣本，我們可以估計出與穩定點的接近程度，進而停止抽樣。

2.3.3　維歸約

資料集可能包含大量特征。考慮一個文檔的集合，其中每個文檔是一個向量，其分量是文檔中每個詞出現的頻率。在這種情況下，通常有成千上萬的屬性（分量），每個代表詞彙表中的一個詞。再看一個例子，考慮包含過去30年各種股票日收盤價的時間序列資料集。在這種情況下，屬性是特定日期的價格，也數以千計。

維歸約有多方面的好處。關鍵的好處是，如果次元（資料屬性的個數）較低，許多資料挖掘算法的效果就會更好。部分是因為維歸約可以删除不相關的特征并降低噪聲，另一部分是因為維災難。（維災難在下面解釋。）還有一個好處是維歸約可以使模型更容易了解，因為模型可能隻涉及較少的屬性。此外，維歸約也可以更容易讓資料可視化。即使維歸約沒有将資料歸約到二維或三維，資料也可以通過觀察屬性對或三元組屬性達到可視化，并且這種組合的數目也會大大減少。最後，使用維歸約降低了資料挖掘算法的時間和記憶體需求。

術語“維歸約”通常用于這樣的技術：通過建立新屬性，将一些舊屬性合并在一起以降低資料集的次元。通過選擇舊屬性的子集得到新屬性，這種維歸約稱為特征子集選擇或特征選擇。特征選擇将在2.3.4節讨論。

下面簡單介紹兩個重要的主題：維災難和基于線性代數方法（如主成分分析）的維歸約技術。更多關于維歸約的内容可檢視附錄B。

1.維災難

維災難是指這樣的現象：随着資料次元的增加，許多資料分析變得非常困難。特别是随着次元增加，資料在它所占據的空間中越來越稀疏。是以，我們觀測到的資料對象很可能不是總體資料對象的代表性樣本。對于分類，這可能意味着沒有足夠的資料對象來建立模型，将所有可能的對象可靠地指派到一個類。對于聚類，點之間的密度和距離的定義（對聚類是至關重要的）失去了意義。（8.1.2節、8.4.6節和8.4.8節會進一步讨論。）結果是，對于高維資料，許多分類和聚類算法（以及其他的資料分析算法）都麻煩纏身——分類準确率降低，聚類品質下降。

2.維歸約的線性代數技術

維歸約的一些最常用的方法是使用線性代數技術，将資料由高維空間投影到低維空間，特别是對于連續資料。主成分分析（Principal Component Analysis，PCA）是一種用于連續屬性的線性代數技術，它找出新的屬性（主成分），這些屬性是原屬性的線性組合，是互相正交的（orthogonal），并且捕獲了資料的最大變差。例如，前兩個主成分是兩個正交屬性，是原屬性的線性組合，盡可能多地捕獲了資料的變差。奇異值分解（Singular Value Decomposition，SVD）是一種線性代數技術，它與PCA有關，并且也用于維歸約。請參考附錄A和B擷取更多細節。

2.3.4　特征子集選擇

降低次元的另一種方法是僅使用特征的一個子集。這種方法盡管看起來可能丢失資訊，但是在存在備援或不相關的特征的時候，情況并非如此。備援特征重複了包含在一個或多個其他屬性中的許多或所有資訊。例如，一種産品的購買價格和所支付的銷售稅額包含許多相同的資訊。不相關特征包含對于手頭的資料挖掘任務幾乎完全沒用的資訊，例如學生的ID号碼對于預測學生的總平均成績是不相關的。備援和不相關的特征可能降低分類的準确率，影響所發現的聚類的品質。

盡管使用常識或領域知識可以立即消除一些不相關的和備援的屬性，但是選擇最佳的特征子集通常需要系統的方法。特征選擇的理想方法是：将所有可能的特征子集作為感興趣的資料挖掘算法的輸入，然後選取能産生最好結果的子集。這種方法的優點是反映了最終使用的資料挖掘算法的目的和偏愛。然而，由于涉及n個屬性的子集多達2n個，這種方法在大部分情況下行不通，是以需要其他政策。有三種标準的特征選擇方法：嵌入、過濾和包裝。

嵌入方法（embedded approach）　特征選擇作為資料挖掘算法的一部分是理所當然的。特别是在資料挖掘算法運作期間，算法本身決定使用哪些屬性和忽略哪些屬性。構造決策樹分類器的算法（在第3章讨論）通常以這種方式運作。

過濾方法（filter approach）　使用某種獨立于資料挖掘任務的方法，在資料挖掘算法運作前進行特征選擇，例如我們可以選擇屬性的集合，它的屬性對之間的相關度盡可能低。

包裝方法（wrapper approach）　這些方法将目标資料挖掘算法作為黑盒，使用類似于前面介紹的理想算法，但通常并不枚舉所有可能的子集來找出最佳屬性子集。

由于嵌入方法與具體的算法有關，這裡我們隻進一步讨論過濾和包裝方法。

1.特征子集選擇體系結構

可以将過濾和包裝方法放到一個共同的體系結構中。特征選擇過程可以看作由四部分組成：子集評估度量、控制新的特征子集産生的搜尋政策、停止搜尋判斷和驗證過程。過濾方法和包裝方法的唯一不同是它們使用了不同的特征子集評估方法。對于包裝方法，子集評估使用目标資料挖掘算法；對于過濾方法，子集評估技術不同于目标資料挖掘算法。下面的讨論提供了該方法的一些細節，彙總在圖2.11中。

從概念上講，特征子集選擇是搜尋所有可能的特征子集的過程。可以使用許多不同類型的搜尋政策，但是搜尋政策的計算花費應當較低，并且應當找到最優或近似最優的特征子集。通常不可能同時滿足這兩個要求，是以需要折中。

搜尋的一個不可缺少的組成部分是評估步驟，根據已經考慮的子集評價目前的特征子集。這需要一種評估度量，針對諸如分類或聚類等資料挖掘任務，确定屬性特征子集的品質。對于過濾方法，這種度量試圖預測實際的資料挖掘算法在給定的屬性集上執行的效果如何；對于包裝方法，評估包括實際運作目标資料挖掘應用，子集評估函數就是通常用于度量資料挖掘結果的評判标準。

因為子集的數量可能很大，考察所有的子集可能不現實，是以需要某種停止搜尋判斷。其政策通常基于如下一個或多個條件：疊代次數，子集評估的路徑成本是否最優或超過給定的門檻值，一個特定大小的子集是否已經得到，使用搜尋政策得到的選擇是否可以實作改進。

最後，一旦標明特征子集，就要驗證目标資料挖掘算法在標明子集上的結果。一種直截了當的評估方法是用全部特征的集合運作算法，并将使用全部特征得到的結果與使用該特征子集得到的結果進行比較。如果順利的話，使用特征子集産生的結果将比使用所有特征産生的結果更好，或者至少幾乎一樣好。另一個驗證方法是使用一些不同的特征選擇算法得到特征子集，然後比較資料挖掘算法在每個子集上的運作結果。

2.特征權重

特征權重是另一種保留或删除特征的辦法。特征越重要，賦予它的權值越大，而對于不太重要的特征，賦予它的權值較小。有時，這些權值可以根據特征的相對重要性的領域知識确定，也可以自動确定。例如，有些分類方法，如支援向量機（見第4章），産生分類模型，其中每個特征都賦予一個權值。具有較大權值的特征在模型中所起的作用更加重要。在計算餘弦相似度時進行的對象規範化（2.4.5節）也可以看作一類特征權重。

2.3.5　特征建立

經常可以由原來的屬性建立新的屬性集，以更有效地捕獲資料集中的重要資訊。此外，新屬性的數目可能比原屬性少，使得我們可以獲得前面介紹的維歸約帶來的所有好處。下面介紹兩種建立新屬性的相關方法：特征提取和映射資料到新的空間。

1.特征提取

由原始資料建立新的特征集稱作特征提取（feature extraction)。考慮照片的集合，按照照片是否包含人臉分類。原始資料是像素的集合，是以對于許多分類算法都不适合。然而，如果對資料進行處理，提供一些較高層次的特征，諸如與人臉高度相關的某些類型的邊和區域等，則會有更多的分類技術可以用于該問題。

可是，最常使用的特征提取技術都是高度針對具體領域的。對于特定的領域，如圖像處理，在過去一段時間已經開發了各種提取特征的技術，但是這些技術在其他領域的應用卻是有限的。因而，一旦将資料挖掘用于一個相對較新的領域，一個關鍵任務就是開發新的特征和特征提取方法。

雖然特征提取通常很複雜，但例2.10說明了它也可以相對簡單。

例2.10 密度　考慮一個包含曆史文物資訊的資料集。該資料集包含每個文物的體積和品質，以及其他資訊。為簡單起見，假定這些文物使用少量材料（木材、陶土、銅、黃金）制造，并且我們希望根據制造材料對它們分類。在此情況下，由品質和體積特征構造的密度特征（即密度=品質/體積）可以很直接地産生準确的分類。盡管有一些人試圖通過考察已有特征的簡單數學組合來自動地進行特征提取，但是最常見的方法還是使用專家的意見構造特征。

2.映射資料到新的空間

使用一種完全不同的視角挖掘資料可能揭示出重要和有趣的特征。例如，考慮時間序列資料，它們常常包含周期模式。如果隻有單個周期模式，并且噪聲不多，則容易檢測到該模式；另一方面，如果有大量周期模式，并且存在大量噪聲，則很難檢測這些模式。盡管如此，通過對該時間序列實施傅裡葉變換（Fourier transform)，将它轉換成頻率資訊明顯的表示，就能檢測到這些模式。在例2.11中，不必知道傅裡葉變換的細節，隻需要知道對于時間序列，傅裡葉變換産生屬性與頻率有關的新資料對象就足夠了。

例2.11 傅裡葉分析　圖2.12b中的時間序列是其他三個時間序列的和，其中兩個顯示在圖2.12a中，其頻率分别是每秒7個和17個周期，第三個時間序列是随機噪聲。圖2.12c顯示功率頻譜。在對原時間序列施加傅裡葉變換後，可以計算功率頻譜。（非正式地看，功率頻譜正比于每個頻率屬性的平方。）盡管有噪聲，圖中有兩個尖峰，對應于兩個原來的、無噪聲的時間序列的周期。值得注意的是，本例的要點是：好的特征可以揭示資料的重要性質。

也可以采用許多其他類型的變換。除傅裡葉變換外，對于時間序列和其他類型的資料，經證明小波變換（wavelet transform)也是非常有用的。

2.3.6　離散化和二進制化

有些資料挖掘算法，特别是某些分類算法，要求資料是分類屬性形式。發現關聯模式的算法要求資料是二進制屬性形式。這樣，常常需要将連續屬性變換成分類屬性（離散化，discretization），并且連續和離散屬性可能都需要變換成一個或多個二進制屬性（二進制化（binarization）)。此外，如果一個分類屬性具有大量不同值（類别），或者某些值出現不頻繁，則對于某些資料挖掘任務，通過合并某些值減少類别的數目可能是有益的。

與特征選擇一樣，最佳的離散化和二進制化方法是“對于用來分析資料的資料挖掘算法，産生最好結果”的方法。直接使用這種判别标準通常是不實際的。是以，離散化和二進制化一般要滿足這樣一種判别标準，它與所考慮的資料挖掘任務的性能好壞直接相關。一般來說，63最佳的離散化取決于所使用的算法，以及其他被考慮的屬性。然而，通常情況下，每個屬性的離散化是互相獨立的。

1.二進制化

一種分類屬性二進制化的簡單技術如下：如果有m個分類值，則将每個原始值唯一地賦予區間［0，m-1］中的一個整數。如果屬性是有序的，則指派必須保持序關系。（注意，即使屬性原來就用整數表示，但如果這些整數不在區間［0，m-1］中，則該過程也是必需的。）然後，将這m個整數的每一個都變換成一個二進制數。由于需要n=log2m個二進位表示這些整數，是以要使用n個二進制屬性表示這些二進制數。例如，一個具有5個值{awful，poor，OK，good，great}的分類變量需要3個二進制變量x1、x2、x3。變換見表2.5。

這樣的變換可能導緻複雜化，如無意之中建立了變換後的屬性之間的聯系。例如，在表2.5中，屬性x2和x3是相關的，因為good值使用這兩個屬性表示。此外，關聯分析需要非對稱的二進制屬性，其中隻有屬性的出現（值為1）才是重要的。是以，對于關聯問題，需要為每一個分類值引入一個二進制屬性，如表2.6所示。如果得到的屬性的個數太多，則可以在二進制化之前使用下一節介紹的技術減少分類值的個數。

同樣，對于關聯問題，可能需要用兩個非對稱的二進制屬性替換單個二進制屬性。考慮記錄人的性别（男、女）的二進制屬性，對于傳統的關聯規則算法，該資訊需要變換成兩個非對稱的二進制屬性，其中一個僅當是男性時為1，而另一個僅當是女性時為1。（對于非對稱的二進制屬性，由于其提供一個二進制位資訊需要占用存儲器的兩個二進制位，因而在資訊的表示上不太有效。)

2.連續屬性離散化

通常，離散化應用于在分類或關聯分析中使用到的屬性上。連續屬性變換成分類屬性涉及兩個子任務：決定需要多少個分類值n，以及确定如何将連續屬性值映射到這些分類值。在第一步中，将連續屬性值排序後，通過指定n-1個分割點（split point)把它們分成n個區間。在頗為平凡的第二步中，将一個區間中的所有值映射到相同的分類值。是以，離散化問題就是決定選擇多少個分割點和确定分割點位置的問題。結果可以用區間集合{（x0，x1］，（x1，x2］，…，（xn-1，xn)}表示，其中x0和xn可以分别為-∞或+∞，或者用一系列不等式x0＜x≤x1,…，xn-1＜x＜xn表示。

無監督離散化　用于分類的離散化方法之間的根本差別在于使用類資訊（監督（supervised）)還是不使用類資訊（無監督（unsupervised））。如果不使用類資訊，則常使用一些相對簡單的方法。例如，等寬（equal width）方法将屬性的值域劃分成具有相同寬度的區間，而區間的個數由使用者指定。這種方法可能受離群點的影響而性能不佳，是以等頻率（equal frequency）或等深（equal depth）方法通常更為可取。等頻率方法試圖将相同數量的對象放進每個區間。作為無監督離散化的另一個例子，可以使用諸如K均值（見第7章）等聚類方法。最後，目測檢查資料有時也可能是一種有效的方法。

例2.12 離散化技術　本例解釋如何對實際資料集使用這些技術。圖2.13a顯示了屬于4個不同組的資料點，以及兩個離群點——位于兩邊的大點。可以使用上述技術将這些資料點的x值離散化成4個分類值。（資料集中的點具有随機的y分量，可以更容易地看出每組有多少個點。）盡管目測檢查該資料的方法的效果很好，但不是自動的，是以我們主要讨論其他三種方法。使用等寬、等頻率和K均值技術産生的分割點分别如圖2.13b、圖2.13c和圖2.13d所示，圖中分割點用虛線表示。

在這個特定的例子中，如果用不同組的不同對象被指派到相同分類值的程度來度量離散化技術的性能，則K均值性能最好，其次是等頻率，最後是等寬。更一般地說，最好的離散化将取決于應用場景并且通常涉及領域特定的離散化方法。例如，将人們的收入離散化為低收入、中等收入、高收入是基于經濟因素的。

監督離散化　以分類為例，若某些資料對象的類标确定，那麼根據類标對資料進行離散化通常能取得更好的分類結果。這并不奇怪，因為未使用類标号知識構造的區間常常包含混合的類标号。有一種概念上的簡單方法是以極大化區間純度的方式确定分割點，例如區間包含單個類别标簽的程度。然而，實踐中這種方法可能需要人為确定區間的純度和最小的區間大小。

為了解決這一問題，一些基于統計學的方法用每個屬性值來分隔區間，并通過合并類似于根據統計檢驗得出的相鄰區間來建立較大的區間。這種自下而上的方法的替代方案是自上而下的方法，如平分初始值得到兩個區間并得到最小熵。該技術隻需要把每個值看作可能的分割點即可，因為假定區間包含有序值的集合。然後，取一個區間，通常選取具有最大（小）熵的區間，重複此分割過程，直到區間的個數達到使用者指定的個數，或者滿足終止條件。

無論是自下而上或是自上而下的政策，基于熵的方法是最有前途的離散化方法之一。首先，需要定義熵（entropy)。設k是不同的類标号數，mi是某劃分的第i個區間中值的個數，而mij是區間i中類j的值的個數。第i個區間的熵ei由如下等式給出：

其中，Pij=mij/mi是第i個區間中類j的機率（值的比例）。該劃分的總熵e是每個區間的熵的權重平均，即

其中，m是值的個數，wi=mi/m是第i個區間的值的比例，而n是區間個數。直覺上，區間的熵是區間純度的度量。如果一個區間隻包含一個類的值（該區間非常純），則其熵為0并且不影響總熵。如果一個區間中的值類出現的頻率相等（該區間盡可能不純），則其熵最大。

例2.13 兩個屬性離散化　基于熵的自上而下的方法用來獨立地離散化圖2.14所示的二維資料的屬性x和y。在圖2.14a所示的第一個離散化中，屬性x和y被劃分成三個區間。（虛線訓示分割點。）在圖2.14b所示的第二個離散化中，屬性x和y被劃分成五個區間。

這個簡單的例子解釋了離散化的兩個特點。首先，在二維中，點類是很好分開的，但在一維中的情況并非如此。一般而言，分别離散化每個屬性通常隻能保證次最優的結果。其次，五個區間比三個好，但是，至少從熵的角度看，六個區間對離散化的改善不大。（沒有給出六個區間的熵值和結果。）因而需要有一個終止标準，自動地發現劃分的正确個數。

3.具有過多值的分類屬性

分類屬性有時可能具有太多的值。如果分類屬性是序數屬性，則可以使用類似于處理連續屬性的技術，以減少分類值的個數。然而，如果分類屬性是标稱的，就需要使用其他方法。考慮一所大學，它有許多系，68因而系名屬性可能具有數十個不同的值。在這種情況下，我們可以使用系之間聯系的知識，将系合并成較大的組，如工程學、社會科學或生物科學。如果領域知識不能提供有用的指導，或者這樣的方法會導緻很差的分類性能，則需要使用更為經驗性的方法，如僅當分組結果能提高分類準确率或達到某種其他資料挖掘目标時，才将值聚集到一起。

2.3.7　變量變換

變量變換（variable transformation）是指用于變量的所有值的變換。（盡管我們偶爾也用屬性變換這個術語，但是遵循習慣用法，我們使用變量指代屬性。）換言之，對于每個對象，變換都作用于該對象的變量值。例如，如果隻考慮變量的量級，則可以通過取絕對值對變量進行變換。接下來的部分，我們讨論兩種重要的變量變換類型：簡單函數變換和規範化。69

1.簡單函數

對于這種類型的變量變換，一個簡單的數學函數分别作用于每一個值。如果x是變量，這種變換的例子包括

在統計學中，變量變換（特别是平方根、對數和倒數變換）常用來将不具有高斯（正态）分布的資料變換成具有高斯（正态）分布的資料。盡管這可能很重要，但是在資料挖掘中，其他理由可能更重要。假定感興趣的變量是一次會話中的資料位元組數，并且位元組數的值域範圍為1到10^9。這是一個很大的值域，使用常用對數變換将其進行壓縮可能是有益的。這樣的話，傳輸10^8和10^9位元組的會話比傳輸10位元組和1000位元組的會話更為相似（9-8=1對3-1=2)。對于某些應用，如網絡入侵檢測，可能需要如此，因為前兩個會話多半表示傳輸兩個大檔案，而後兩個會話可能是兩個完全不同的類型。

使用變量變換時需要小心，因為它們改變了資料的特性。盡管有時需要這樣做，但是如果沒有深入了解變換的特性，則可能出現問題。例如，變換1/x雖然壓縮了大于1的值，但是卻放大了0和1之間的值，舉例來說，{1，2，3}變換成1，1/2，1/3，但是1，1/2，1/3變換成{1，2，3}，這樣，對于所有的值集，變換1/x逆轉了序。為了幫助弄清楚一個變換的效果，重要的是問如下問題：想要什麼樣的變換性質？需要保序嗎？變換作用于所有的值，特别是負值和0嗎？變換對0和1之間的值有何特别影響？本章習題17考察了變量變換的其他方面。

2.規範化或标準化

标準化或規範化的目标是使整個值的集合具有特定的性質。一個傳統的例子是統計學中的“對變量标準化”。如果x是屬性值的均值（平均值），而sx是它們的标準差，則變換

建立一個新的變量，它具有均值0和标準差1。如果要以某種方法組合不同的變量，70則為了避免具有較大值域的變量左右分析結果，這種變換常常是必要的。例如，考慮使用年齡和收入兩個變量對人進行比較。對于任意兩個人，收入之差的絕對值（數百或數千元）多半比年齡之差的絕對值（小于150）大很多。如果沒有考慮到年齡和收入值域的差别，則對人的比較将被收入之差所左右。例如，如果兩個人之間的相似性或相異性使用本章後面的相似性或相異性度量來計算，則在很多情況下（如歐幾裡得距離）收入值将左右計算結果。

均值和标準差受離群點的影響很大，是以通常需要修改上述變換。首先，用中位數（median）（即中間值）取代均值。其次，用絕對标準差（absolute standard deviation）取代标準差。例如，如果x是變量，則x的絕對标準差為

，其中xi是變量x的第i個值，m是對象的個數，而μ是均值或中位數。存在離群點時，計算值集的位置（中心）和發散估計的其他方法可以參考統計學書籍。這些更加穩健的方法也可以用來定義标準化變換。

2.4　相似性和相異性的度量

相似性和相異性是重要的概念，因為它們被許多資料挖掘技術所使用，如聚類、最近鄰分類和異常檢測等。在許多情況下，一旦計算出相似性或相異性，就不再需要原始資料了。這種方法可以看作将資料變換到相似性（相異性）空間，然後進行分析。的确，核方法（Kernel method）是實作這種思想的強大方法。我們将在2.4.7節簡單介紹這些核方法，并在4.9.4節的分類中對其進行更全面地讨論。

首先，我們讨論基本要素——相似性和相異性的高層定義，并讨論它們之間的聯系。為友善起見，我們使用術語鄰近度（proximity）表示相似性或相異性。由于兩個對象之間的鄰近度是兩個對象對應屬性之間的鄰近度的函數，是以首先介紹如何度量僅包含一個簡單屬性的對象之間的鄰近度。

然後考慮具有多個屬性的對象的鄰近度度量。這包括Jaccard和餘弦相似性度量，這二者适用于像文檔這樣的稀疏資料，以及相關性和歐幾裡得距離度量，後二者适用于時間序列這樣的稠密資料或多元點。我們也考慮互資訊，它可以應用于多種類型的資料，并且适用于檢測非線性關系。在本次讨論中，我們隻考慮具有相對同類屬性的對象，通常為二進制值或者連續值。

接下來，我們考慮與鄰近度度量相關的若幹重要問題。這包括如何在物體具有不同類型的屬性時計算物體之間的鄰近度，以及在計算數值對象之間的距離時如何解決變量之間的規模差異和相關性。本節最後簡略讨論如何選擇正确的鄰近度度量。

雖然本節重點介紹資料對象之間的鄰近度計算，但也可以在屬性之間計算鄰近度。例如，對于圖2.2d所示的文檔項矩陣，可以用餘弦方法來計算兩個文檔或兩個項（詞）之間的相似度。知道兩個變量強相關有助于消除備援。具體而言，後面讨論的相關性和互資訊度量常常用于此目的。

2.4.1　基礎

1.定義

兩個對象之間的相似度（similarity）的非正式定義是這兩個對象相似程度的數值度量。因而，兩個對象越相似，它們的相似度就越高。通常，相似度是非負的，并常常在0（不相似）和1（完全相似）之間取值。

兩個對象之間的相異度（dissimilarity）是這兩個對象差異程度的數值度量。對象越類似，它們的相異度就越低。通常，術語距離（distance）用作相異度的同義詞，正如我們将介紹的，距離常常用來表示特定類型的相異度。有時，相異度在區間［0，1］中取值，但是相異度在0和∞之間取值也很常見。

2.變換

通常使用變換把相似度轉換成相異度或反之，或者把鄰近度變換到一個特定區間，如［0,1］。例如，我們可能有相似度，其值域從1到10，但是我們打算使用的特定算法或軟體包隻能處理相異度，或隻能處理［0，1］區間的相似度。之是以在這裡讨論這些問題，是因為在稍後讨論鄰近度時，我們将使用這種變換。此外，這些問題相對獨立于特定的鄰近度度量。

通常，鄰近度度量（特别是相似度）被定義為或變換到區間［0,1］中的值。這樣做的動機是使用一種适當的尺度，由鄰近度的值表明兩個對象之間的相似（或相異）程度。這種變換通常是比較直截了當的。例如，如果對象之間的相似度在1（一點也不相似）和10（完全相似）之間變化，則我們可以使用如下變換将它變換到［0，1］區間：

，其中s和s′分别是相似度的原值和新值。一般來說，相似度到［0，1］區間的變換由如下表達式給出：

，其中max_s和min_s分别是相似度的最大值和最小值。類似地，具有有限值域的相異度也能用

映射到［0,1］區間。這是一個線性變換的例子，它保留了點之間的相對距離。換句話說，如果點x1和x2的距離是x3與x4距離的兩倍，那麼線上性變換之後也是如此。

然而，将鄰近度映射到［0，1］區間可能非常複雜。例如，如果鄰近度度量原來在區間［0，∞］上取值，則需要使用非線性變換，并且在新的尺度上，值之間不再具有相同的聯系。對于從0變化到∞的相異度度量，考慮變換

，相異度0、0.5、2、10、100和1000分别被變換到0、0.33、0.67、0.90、0.99和0.999。在原來相異性尺度上較大的值被壓縮到1附近，但是否希望如此取決于應用。

請注意，将鄰近度度量映射到區間［0，1］也可能改變鄰近度度量的含義。例如，相關性（稍後讨論）是一種相似性度量，在區間［-1,1］上取值，通過取絕對值将這些值映射到［0，1］區間丢失了符号資訊，而對于某些應用，符号資訊可能是重要的（見本章習題22)。

将相似度變換成相異度或反之也是比較直截了當的，盡管我們可能再次面臨保持度量的含義問題和将線性尺度改變成非線性尺度的問題。如果相似度（相異度）落在［0，1］區間，則相異度（相似度）可以定義為d=1-s（或s=1-d)。73另一種簡單的方法是定義相似度為負的相異度（或相反）。例如，相異度0,1,10和100可以分别變換成相似度0,-1,-10和-100。

負變換産生的相似度結果不必局限于［0，1］區間，但是，如果希望的話，則可以使用變換

，s=e^-d或

。對于變換

，相異度0，1，10，100分别被變換到1，0.5，0.09，0.01；對于s=e-d，它們分别被變換到1.00，0.37，0.00，0.00；對于

，它們分别被變換到1.00，0.99，0.90，0.00。在這裡的讨論中，我們關注将相異度變換到相似度。相反方向的轉換見本章習題23。

一般來說，任何單調減函數都可以用來将相異度轉換到相似度（或相反）。當然，在将相似度變換到相異度（或相反），或者在将鄰近度的值變換到新的尺度時，也必須考慮一些其他因素。我們提到過一些問題，涉及保持意義、擾亂标度和資料分析工具的需要，但是肯定還有其他問題。

2.4.2　簡單屬性之間的相似度和相異度

通常，具有若幹屬性的對象之間的鄰近度用單個屬性的鄰近度的組合來定義，是以我們首先讨論具有單個屬性的對象之間的鄰近度。考慮由一個标稱屬性描述的對象，對于兩個這樣的對象，相似意味什麼呢？由于标稱屬性隻攜帶了對象的相異性資訊，是以我們隻能說兩個對象有相同的值，或者沒有。因而在這種情況下，如果屬性值比對，則相似度定義為1，否則為0；相異度用相反的方法定義：如果屬性值比對，相異度為0,否則為1。

對于具有單個序數屬性的對象，情況更為複雜，因為必須考慮序資訊。考慮一個在标度{poor，fair，OK，good，wonderful}上測量産品（例如，糖塊）品質的屬性。一個評定為wonderful的産品P1與一個評定為good的産品P2應當比它與一個評定為OK的産品P3更接近。為了量化這種觀察，序數屬性的值常常映射到從0或1開始的連續整數，例如，{poor=0，fair=1，OK=2，good=3，wonderful=4}。于是，P1與P2之間的相異度d（Pl，P2)=3-2=1，或者，如果希望相異度在0和1之間取值d（P1，P2)=（3-2)/4=0.25；序數屬性的相似度可以定義為s=1-d。

序數屬性相似度（相異度）的這種定義可能使讀者感到有點擔心，因為這裡假設了屬性的連續值之間的間隔相等，而事實并非如此。如果根據實際情況，我們應該計算出區間或比率屬性。值fair與good的差真的和OK與wonderful的差相同嗎？可能不相同，但是在實踐中，我們的選擇是有限的，并且在缺乏更多資訊的情況下，這是定義序數屬性之間鄰近度的标準方法。

對于區間或比率屬性，兩個對象之間的相異性的自然度量是它們的值之差的絕對值。例如，我們可能将現在的體重與一年前的體重相比較，說：“我重了10磅。”在這類情況下，相異度通常在0和∞之間，而不是在0和1之間取值。如前所述，區間或比率屬性的相似度通常轉換成相異度。

表2.7總結了這些讨論。其中，x和y是兩個對象，它們具有一個指明類型的屬性，d（x，y)和s（x，y)分别是x和y之間的相異度和相似度（分别用d和s表示）。盡管其他方法也是可能的，但是表中的這些是最常用的。

下面兩節介紹更複雜的涉及多個屬性的對象之間的鄰近度度量：（1）資料對象之間的相異度；（2）資料對象之間的相似度。這樣分節可以更自然地展示使用各種鄰近度度量的基本動機。然而，我們要強調的是使用上述技術，相似度可以變換成相異度，反之亦然。

2.4.3　資料對象之間的相異度

本節讨論各種不同類型的相異度。我們從讨論距離（距離是具有特定性質的相異度）開始，然後給出一些更一般的相異度類型的例子。

距離

首先給出一些例子，然後使用距離的常見性質更正式地介紹距離。一維、二維、三維或高維空間中兩個點x和y之間的歐幾裡得距離（Euclidean distance)d由如下熟悉的公式定義：

其中，n是維數，而xk和yk分别是x和y的第k個屬性值（分量）。用圖2.15、表2.8和表2.9解釋該公式，它們展示了這個點集、這些點的x和y坐标以及包含這些點之間距離的距離矩陣（distance matrix）。

式（2.1）給出的歐幾裡得距離可以用式（2.2）的闵可夫斯基距離（Minkowski distance)來推廣：

其中，r是參數。下面是闵可夫斯基距離的三個最常見的例子。

• r=1，城市街區（也稱曼哈頓、計程車、L1範數）距離。一個常見的例子是漢明距離（Hamming distance)，它是兩個具有二進制屬性的對象（即兩個二進制向量）之間不同的二進制位的個數。
• r=2，歐幾裡得距離（L2範數）。
• r=∞，上确界（Lmax或L∞範數）距離。這是對象屬性之間的最大距離。更正式地，L∞距離由式（2.3）定義：

  

注意不要将參數r與維數（屬性數）n混淆。歐幾裡得距離、曼哈頓距離和上确界距離是對n的所有值（1，2，3，…）定義的，并且指定了将每個維（屬性）上的差組合成總距離的不同方法。

表2.10和表2.11分别給出表2.8中資料的L1距離和L∞距離的鄰近度矩陣。注意，所有的距離矩陣都是對稱的，即第ij個項與第ji個項相同，例如，在表2.9中，第4行第1列和第1行第4列都包含值5.1。

距離（如歐幾裡得距離）具有一些衆所周知的性質。如果d（x,y）是兩個點x和y之間的距離，則如下性質成立：

1） 非負性。（a）對于所有x和y，d（x，y）≥0；（b）僅當x=y時d（x，y)=0。

2） 對稱性。對于所有x和y，d（x，y)=d（y，x)。

3） 三角不等式。對于所有x、y和z，d（x，z)≤d（x，y)+d（y，z)。

滿足以上三個性質的測度稱為度量（metric)。有些人隻對滿足這三個性質的相異性度量使用術語距離，但在實踐中常常違反這一約定。這裡介紹的三個性質是有用的，數學上也是令人滿意的。此外，如果三角不等式成立，則該性質可以用來提高依賴于距離的技術（包括聚類）的效率（見本章習題25)。盡管如此，許多相異度都不滿足一個或多個度量性質。

例2.14給出相關測度的例子。

例2.14 非度量的相異度：集合差　基于集合論中定義的兩個集合差的概念舉例。設有兩個集合A和B，A-B是不在B中的A中元素的集合。例如，如果A={1，2，3，4}，而B={2，3，4}，則A－B={1}，而B－A=，即空集。我們可以将集合A和B之間的距離定義為d（A，B)=size（A-B），其中size是一個函數，它傳回集合元素的個數。該距離測度是大于或等于零的整數值，但不滿足非負性的第二部分，也不滿足對稱性，同時還不滿足三角不等式。然而，如果将相異度修改為d（A，B)=size（A-B)+size（B-A)，則這些性質都可以成立（見本章習題21)。

2.4.4　資料對象之間的相似度

對于相似度，三角不等式（或類似的性質）通常不成立，但是對稱性和非負性通常成立。更明确地說，如果s（x，y)是資料點x和y之間的相似度，則相似度具有如下典型性質。

1） 僅當x=y時s（x，y)=1。（0≤s≤1)

2） 對于所有x和y，s（x，y)=s（y,x)。（對稱性)

對于相似度，沒有與三角不等式對應的一般性質。然而，有時可以将相似度簡單地變換成一種度量距離。稍後讨論的餘弦相似性度量和Jaccard相似性度量就是兩個例子。此外，對于特定的相似性度量，還可能在兩個對象相似性上導出本質上與三角不等式類似的數學限制。

例2.15 非對稱相似性度量　考慮一個實驗，實驗中要求人們對螢幕上快速閃過的一小組字元進行分類。該實驗的混淆矩陣（confusion matrix）記錄每個字元被分類為自己的次數和被分類為另一個字元的次數。使用混淆矩陣，我們可以将字元x和字元y之間的相似性度量定義為x被錯誤分類為y的次數，但請注意，此度量不是對稱的。例如，假定“0”出現了200次，它被分類為“0”160次，而被分類為“o”40次。類似地，“o”出現200次并且被分類為“o”170次，但是分類為“0”隻有30次。如果取這些計數作為兩個字元之間相似性的度量，則得到一種相似性度量，但這種相似性度量不是對稱的。在這種情況下，通過選取

，相似性度量可以轉換成對稱的，其中s′是新的相似性度量。

2.4.5　鄰近度度量的例子

本節給出一些相似性和相異性度量的具體例子。

1.二進制資料的相似性度量

兩個僅包含二進制屬性的對象之間的相似性度量也稱為相似系數（similarity coefficient），并且通常在0和1之間取值，值為1表明兩個對象完全相似，而值為0表明對象一點也不相似。有許多理由表明在特定情形下，一種系數為何比另一種好。

設x和y是兩個對象，都由n個二進制屬性組成。這樣的兩個對象（即兩個二進制向量）的比較可生成如下四個量（頻率)：

• f00=x取0并且y取0的屬性個數；
• f01=x取0并且y取1的屬性個數；
• f10=x取1并且y取0的屬性個數；
• f11=x取1并且y取1的屬性個數。

簡單比對系數（Simple Matching Coefficient，SMC)　一種常用的相似性系數是簡單比對系數，定義如下：

該度量對出現和不出現都進行計數。是以，SMC可以在一個僅包含是非題的測驗中用來發現問題回答相似的學生。

Jaccard系數（Jaccard Coefficient）　假定x和y是兩個資料對象，代表一個事務矩陣（見2.1.2節）的兩行（兩個事務）。如果每個非對稱的二進制屬性對應于商店的一種商品，則1表示該商品被購買，而0表示該商品未被購買。由于未被顧客購買的商品數遠大于被購買的商品數，因而像SMC這樣的相似性度量将會判定所有的事務都是類似的。這樣，常常使用Jaccard系數來處理僅包含非對稱的二進制屬性的對象。Jaccard系數通常用符号J表示，由如下等式定義：

例2.16 SMC和Jaccard相似性系數　為了解釋這兩種相似性度量之間的差别，我們對如下二進制向量計算SMC和J：

x=（1,0,0,0,0,0,0,0,0,0)

y=（0,0,0,0,0,0,1,0,0,1)

• f01=2　x取0并且y取1的屬性個數
• f10=1　x取1并且y取0的屬性個數
• f00=7　x取0并且y取0的屬性個數
• f11=0　x取1并且y取1的屬性個數

2.餘弦相似度

通常，文檔用向量表示，向量的每個元件（屬性）代表一個特定的詞（術語）在文檔中出現的頻率。盡管文檔具有數以百千計或數以萬計的屬性（詞），但是每個文檔向量都是稀疏的，因為它具有相對較少的非零屬性值。（文檔規範化并不對零詞目建立非零詞目，即文檔規範化保持稀疏性。）這樣，與事務資料一樣，相似性不能依賴共享0的個數，因為任意兩個文檔多半都不會包含許多相同的詞，進而如果統計0-0比對，則大多數文檔都與其他大部分文檔非常類似。是以，文檔的相似性度量不僅應當像Jaccard度量一樣需要忽略0-0比對，而且還必須能夠處理非二進制向量。下面定義的餘弦相似度（cosine similarity）就是文檔相似性最常用的度量之一。如果x和y是兩個文檔向量，則

其中′表示向量或者矩陣的轉置，表示兩個向量的内積：

且||x||是向量x的長度，

。

兩個向量的内積适用于非對稱屬性，因為它隻依賴于兩個向量中非零的分量。是以，兩個文檔之間的相似性隻取決于它們中出現的單詞。

例2.17 兩個文檔向量的餘弦相似度　該例計算下面兩個資料對象的餘弦相似度，這些資料對象可能代表文檔向量：

x=（3,2,0,5,0,0,0,2,0,0)

y=（1,0,0,0,0,0,0,1,0,2)

〈x,y〉=3×1＋2×0＋0×0＋5×0＋0×0＋0×0＋0×0＋2×1＋0×0＋0×2

＝5

||x||＝3×3＋2×2＋0×0＋5×5＋0×0＋0×0＋0×0＋2×2＋0×0＋0×0

＝6.48

||y||＝1×1＋0×0＋0×0＋0×0＋0×0＋0×0＋0×0＋1×1＋0×0＋2×2

＝2.45

cos（x,y)=0.31

如圖2.16所示，餘弦相似度實際上是x和y之間夾角（餘弦）的度量。這樣，如果餘弦相似度為1，則x和y之間的夾角為0°，并且除長度之外，x和y是相同的：如果餘弦相似度為0，則x和y之間的夾角為90°,并且它們不包含任何相同的詞（術語)。

式（2.6）可以寫成式（2.8）的形式：

其中，

。x和y被它們的長度除，将它們規範化到長度為1。這意味着在計算相似度時，餘弦相似度不考慮兩個資料對象的量值。（當量值是重要的時候，歐幾裡得距離可能是一種更好的選擇。）對于長度為1的向量，餘弦度量可以通過簡單地取内積計算。進而，在需要計算大量對象之間的餘弦相似度時，将對象規範化，使之為機關長度可以減少計算時間。

3.廣義Jaccard系數（Tanimoto系數）

廣義Jaccard系數可以用于文檔資料，并在二進制屬性情況下歸約為Jaccard系數。該系數用EJ表示，由下式定義：

4.相關性

相關性經常被用來測量兩組被觀察到的值之間的線性關系。是以，相關性可以測量兩個變量（高度和重量）之間或兩個對象（一對溫度時間序列）之間的關系。相關性可以測量類型和取值尺度差異很大的屬性間的相似度，如果兩個資料對象中的值來自不同的屬性，通常更頻繁地使用相關性來度量屬性之間的相似度。

更準确地，兩個資料對象例如向量x和y之間的皮爾森相關（Pearson’s correlation）系數由下式定義：

這裡使用标準的統計學記号和定義：

例2.18 完全相關　相關度總是在-1到1之間取值。相關度為1（-1)意味x和y具有完全正（負）線性關系，即xk=ayk+b，其中a和b是常數。下面兩個x和y的值集分别給出相關度為-1和+1的情況。為簡單起見，第一組中取x和y的均值為0。

例2.19 非線性關系　如果相關度為0，則兩個資料對象的屬性之間不存線上性關系。然而，仍然可能存在非線性關系。在下面的例子中，資料對象的屬性之間存在非線性關系yk=x2k，但是它們的相關度為0。

x=（-3，-2，-1，0，1,2,3)

y=（　9,　4,　1,0,1,4,9)

例2.20 相關性可視化　通過繪制對應屬性值對可以很容易地判定兩個資料對象x和y之間的相關性。圖2.17給出了一些圖，x和y具有30個屬性，這些屬性的值随機地産生（服從正态分布），使得x和y的相關度從-1到1。圖中每個小圓圈代表30個屬性中的一個，其x坐标是x的一個屬性的值，而其y坐标是y的相同屬性的值。

如果通過減去均值，然後規範化使其長度為1來變換x和y，則它們的相關度可以通過求點積來計算。（注意，這與其他情況下使用的标準化不同，比如2.3.7節讨論的先減去均值，并被标準偏差除。）這種變換突出了相關度量和餘弦度量之間的有趣關系。特别地，x和y之間的相關性與x′和y′之間的餘弦相同。然而，即使x和y與x′和y′具有相同的相關度量，它們之間的餘弦也不相同，即使它們都具有相同的相關度量。通常，當兩個向量的均值為0時，兩個向量之間的相關性僅在特殊情況下等于餘弦度量。

5.連續屬性度量方法間的差異

我們剛剛定義了三種連續屬性的鄰近度度量方法：餘弦、相關性和闵可夫斯基距離。在這一節中，我們将展示這三個鄰近度度量方法之間的差異。具體而言，我們考慮兩種常用的資料變換方法，即常數因子縮放（乘）和常數值平移（加法）。如果對資料對象進行資料變換之後，該鄰近度度量方法的值保持不變，則該鄰近度度量方法被認為對資料變換具有不變性。表2.12比較了餘弦、相關性和闵可夫斯基距離度量對于縮放和平移操作的不變性的行為。可以看出，相關性度量對于縮放和平移都有不變性，而餘弦度量隻對縮放具有不變性。另一方面，闵可夫斯基距離度量對縮放和平移都是敏感的，是以對兩者都不具有不變性。

我們用一個例子來說明不同鄰近度度量之間的差異的意義。

例2.21 比較鄰近度度量　考慮下面兩個具有七個數值屬性的向量x和y。

x=（1,2,4,3,0,0,0)

y=（1,2,3,4,0,0,0)

可以看出，x和y都有4個非零值，并且兩個向量中的值大部分是相同的，除了第三個和第四個分量。兩個向量之間的餘弦、相關性和歐幾裡得距離計算如下：

毫無疑問，x和y具有接近1的餘弦和相關度量，而它們之間的歐幾裡得距離很小，表明它們非常相似。現在我們考慮向量ys，它是y（乘以2的常數因子）的縮放版本，以及向量yt，它是通過将y平移5個機關來構造的，如下所示：

ys=2×y=（2,4,6,8,0,0,0)

yt=y+5=（6,7,8,9,5,5,5)

我們感興趣的是ys和yt是否與原始向量y一樣，都跟x鄰近度相同。表2.13展示了不同方法計算的向量對（x，y）、（x，ys）和（x，yt）的鄰近度。可以看出，即使用ys或yt代替y之後，x和y之間的相關性值保持不變。然而，餘弦值在計算（x，y）和（x，ys）時仍然等于0.9667，但當計算為（x，yt）時，餘弦值顯著降低到0.7940。上訴結果突出展示了與相關性度量相比，餘弦隻對縮放具有不變性，對平移不具有不變性。另一方面，歐幾裡得距離對3對向量計算出不同的值，那是因為它對縮放和平移都很敏感。

我們可以從這個例子中觀察到，當在資料上應用縮放或平移操作時，不同的鄰近度度量表現不同。是以，正确的鄰近度度量方法的選擇取決于資料對象之間的相似性的特點及對給定應用的意義。例如，如果x和y表示文檔項矩陣中不同單詞的頻率，則使用ys替換y時鄰近度保持不變的鄰近度度量方法将是有意義的，因為ys隻是y的縮放版本，在文檔中表示單詞出現的分布。然而，yt與y不同，因為它包含大量在y中不存在的非零頻率的詞。由于餘弦對縮放具有不變性，而對平移不具有不變性，是以對這個應用來說餘弦将是一個理想的選擇。

考慮一個不同的場景，其中x代表某地理位置連續七天的攝氏溫度。y、ys和yt為使用三種不同的測量尺度在另一位置測量的溫度。注意，不同的溫度機關具有不同的偏移量（例如，攝氏和開氏溫标）和不同的縮放因子87（例如，攝氏度和華氏度）。我們希望使用鄰近度度量方法來捕獲溫度值之間的鄰近度，且不受測量尺度的影響。那麼，相關性将是該應用的鄰近度測量方法的理想選擇，因為它對縮放和平移都具有不變性。

另一個例子，考慮x代表在7個地點測量的降水量（cm）的情景。y、ys、yt為三種不同的模型預測的在這些位置的降水值。理想情況下，我們希望選擇一個模型，準确地重建x中的降水量而不産生任何誤差。很明顯，y在x中提供了一個很好的近似值，而ys和yt提供了較差的降水估計，盡管它們找到了不同地點的降水趨勢。是以，我們需要選擇一個鄰近度度量方法，懲罰來自實際觀測與模型估計中的任何差異，并且對縮放和平移操作都敏感。歐幾裡得距離滿足此屬性，是以将是該應用的鄰近度度量的正确選擇。事實上，歐幾裡德距離通常用于計算模型的準确性，這将在後面的第3章中讨論。

2.4.6　互資訊

與相關性一樣，互資訊被用作兩組成對值之間的相似性度量，該值有時被用作相關性的替代物，特别是在值對之間疑為非線性關系時。這一度量方法來自資訊論，它是關于如何正式定義和量化資訊的研究。事實上，互資訊是一組值對另一組提供多少資訊的度量方法，這些值成對地出現，例如高度和重量。如果兩組值是獨立的，即一組值不包含另一組值的任何資訊，則它們的互資訊是0。另一方面，如果兩組值完全依賴，即知道一組值則能知道另一組值，反之亦然，則它們具有最大互資訊。互資訊不具有最大值，但我們将定義它的标準化版本，其範圍在0到1之間。

為了定義互資訊，我們考慮兩組值X和Y，它們成對出現（X，Y）。我們需要測量一組值中的平均資訊，以及它們的值對。這通常用熵來衡量。更具體地，假設X和Y是離散的，也就是說，X可以取m個不同的值，u1，u2，…，um，Y可以取n個不同的值v1，v2，…，vn。然後，它們的個體和聯合熵可以根據每個值和一對值的機率來定義：

如果值或組合值的機率為0，則通常将0log2（0）取值為0。

X和Y的互資訊可以直接定義如下：

注意H（X，Y)是對稱的，即H（X，Y)=H（Y，X)，是以互資訊也是對稱的，即I（X，Y)=I（Y)。

實際上，X和Y是同一資料集中的兩個屬性或兩行中的值。在例2.22中，兩個向量x和y表示這些值，并且利用值或值對出現在x和y中的頻率計算每個值或值對的機率（xi，yi）,其中xi表示x的第i個元素，yi表示y的第i個元素。下面用前面的例子來說明。

例2.22 評估非線性關系的互資訊　回憶例2.19，其中yk＝x2k，但它們的相關性為0。

x=（-3,-2,-1,0,1,2,3)

從圖2.18可知，I（x，y)=H（x)+H（y)-H（x，y)=1.9502。雖然多種方法可以用來規範互資訊，參見本例的文獻注釋，我們将應用一種令互資訊除以log2（min（m，n))的方法，并産生0到1之間的結果。這産生的值為1.9502log2（4)=0.9751。是以，x和y是強相關的。它們不是完全相關的，因為給定y的值，除了y＝0之外，關于x的值有一定的歧義。注意，對于y=-x，歸一化互資訊将是1。

　

2.4.7　核函數

很容易了解相似性和距離在諸如聚類之類的應用中可能是有用的，它試圖将相似對象分組在一起。更不明顯的是，許多其他資料分析任務，包括預測模組化和維歸約，可以用資料對象的逐對“鄰近度”來表示。更具體地，許多數學分析問題可以被數學公式化為輸入，例如一個核矩陣K，它可以被認為是一種鄰近度矩陣。是以，使用初始預處理步驟将輸入資料轉換為核心矩陣，該核心矩陣是資料分析算法的輸入。

更正式地說，如果一個資料集有m個資料對象，那麼K是m×m的矩陣。如果xi和xj是第i個和第j個資料對象，則Kij是通過核函數計算的K的第ij個熵：kij=κ（xi,xj)（2.16)正如我們将在下面的材料中看到的，核矩陣的使用允許算法對各種資料的更廣泛的适用性，還能擴充僅用于檢測線性關系的算法到非線性關系上模組化的能力。

核使算法資料獨立　如果算法使用一個核矩陣，那麼它可以與任何類型的資料一起使用，并為該資料設計核函數。算法2.1證明了這一觀點。雖然隻有一些資料分析算法可以被修改為使用核矩陣作為輸入，但是這種方法是非常強大的，因為它允許這樣的算法與幾乎任何類型的資料一起使用，其中可以為資料定義适當的核函數。是以，一個分類算法可以運用到例如記錄資料、字元串資料或圖形資料等資料上。如果一個算法可以被重新構造成使用核矩陣，那麼它對不同類型的資料的适用性急劇增加。正如将在後面的章節中看到的，許多聚類、分類和異常檢測算法隻使用相似性或距離，是以，可以很容易地修改為與核函數一起使用。

将資料映射到高維資料空間可以允許非線性關系的模組化　基于核的資料分析算法還有另一個同樣重要的方面：它們能夠用隻模拟線性關系的算法來模組化非線性關系。通常，這是通過首先将資料從低維資料空間轉換（映射）到高維空間來實作的。

例2.23 将資料映射到高次元空間　考慮由下面等式給出的兩個變量x和y之間的關系，它定義了兩個次元的橢圓關系（見圖2.19a）：

我們可以通過建立3個新的變量u、v和w來映射二維資料到三個次元，這些變量被定義如下：

是以，我們現在可以将式（2.17）表示為線性方程。這個方程描述了一個平面的三個次元。橢圓上的點将位于該平面上，而橢圓内和外的點将位于平面的相對側。如圖2.19b所示，這個3D圖的視角是沿着分離平面的表面，使得平面以線的形式出現。

核技巧　上面所示的方法顯示了将資料映射到高維空間的價值，該操作對于基于核的方法是必需的。從概念上講，我們首先定義一個函數φ，将資料點x和y映射到高維空間中的資料點φ（x)和φ（y)，使得内積能夠給出所期望的x、y鄰近度度量的方法。通過使用這樣的方法可能會犧牲很多，因為我們大大擴充了資料的大小，增加我們分析的計算複雜性，最終通過計算高維空間中的相似性來解決維數災難的問題。然而，并不是這樣的，因為可以通過定義核函數κ來避免這些問題，該核函數κ可以計算相同的相似性值，但是可以用原始空間中的資料點，即κ（x，y)＝<φ（x)，φ（y)>。這就是所謂的核技巧。核技巧有一個非常堅實的數學基礎，是資料分析領域中一個非常強大的方法。

并不是一對資料對象的每一個函數都滿足核函數所需的性質，但是可以為各種資料類型設計許多有用的核。例如，三個常見的核函數是多項式、高斯（徑向基函數（RBF））和sigmoid核。如果x和y是兩個資料對象（特别是兩個資料向量），那麼這三個核函數可以分别表示如下：

其中，α與c≥0是常數，d是多項式度的整型參數，x-y是向量x-y的長度，σ>0為調整高斯分布的參數。

例2.24 多項式核　注意，在前一節中給出的核函數（将資料映射到更高維空間，然後在高維空間計算資料的内積）計算與我們原始資料相同的相似度值。例如，對于度為2的多項式核，讓其成為将二維資料向量x=（x1，x2)映射到高維空間的函數。特别地，

對于更高維的空間，将鄰近度定義為φ（x)和φ（y)的内積，如<φ（x)，φ（y)>。接着，如前所述，可以表示為：

其中,κ是由式（2.19)定義的。具體而言，如果x=（x1，x2)和y=（y1，y2)，則

更一般地說，核技巧取決于定義κ和φ，進而使式（2.23）成立。這是為各種各樣的核所做的。

這種基于核的方法的讨論隻是為了簡要介紹這個主題，并省略了許多細節。4.9.4節提供了有關基于核方法的更全面的讨論，在用于分類的非線性支援向量機中讨論了這些問題。基于核分析的更翔實的參考資料可以在本章的文獻注釋中找到。

2.4.8　Bregman散度

本節，我們簡略介紹Bregman散度（Bregman divergence)，它是一組具有共同性質的鄰近函數。這樣，可以構造使用Bregman散度的一般資料挖掘算法，如聚類算法，具體的例子是K均值聚類算法（7.2節）。注意，本節需要向量計算方面的知識。

Bregman散度是損失或失真函數。為了了解損失函數，考慮如下情況：設x和y是兩個點，其中y是原來的點，而x是它的某個失真或近似，例如，x可能是由于添加了一些随機噪聲到y上而産生的。損失函數的目的是度量用x近似y導緻的失真或損失。當然，x和y越類似，失真或損失就越小，因而Bregman散度可以用作相異性函數。

有如下正式定義。定義2.6（Bregman散度）　給定一個嚴格凸函數Φ（連同一些通常會滿足的适度限制)，由該函數生成的Bregman散度（損失函數）D（x，y)通過下面的公式給出：

其中，Φ（y)是在y上計算的Φ的梯度，x-y是x與y的向量差，而<Φ（y)，（x-y)>是Φ（y)和（x-y)的内積。對于歐幾裡得空間中的點，内積就是點積。D（x，y)可以寫成D（x，y)=Φ（x)-L（x)，其中L（x)=Φ（y)+<Φ（y)，（x-y)>代表在y上正切于函數Φ的平面方程。使用微積分學的術語，L（x)是函數Φ在y點附近的線性部分，而Bregman散度是一個函數與該函數的線性近似之間的差。選取不同的Φ，可以得到不同的Bregman散度。

例2.25 我們使用平方歐幾裡得距離給出Bregman散度的一個具體例子。為了簡化數學計算，我們僅限于一維。設x和y是實數，而Φ（t)是實數值函數，Φ（t)=t2。在此情況下，梯度歸結為導數，而點積歸結為乘積。例如，式（2.25）變成式（2.26）：

該例的圖形在圖2.20中給出，其中y=1。在x=2和x=3上給出了Bregman散度。

2.4.9　鄰近度計算問題

本節讨論與鄰近度度量有關的一些重要問題：（1）當屬性具有不同的尺度（scale）或相關時如何處理；（2）當對象包含不同類型的屬性（例如，定量屬性和定性屬性）時如何計算對象之間的鄰近度；（3）當屬性具有不同的權重（即并非所有的屬性都對對象的鄰近度具有相等的貢獻）時，如何處理鄰近度計算。

1.距離度量的标準化和相關性

距離度量的一個重要問題是當屬性具有不同的值域時如何處理。（這種情況通常稱作“變量具有不同的尺度。”）在前面的例子中，使用歐幾裡得距離，基于年齡和收入兩個屬性來度量人之間的距離。除非這兩個屬性是标準化的，否則兩個人之間的距離将被收入所左右。

一個相關的問題是，除值域不同外，當某些屬性之間還相關時，如何計算距離。當屬性相關、具有不同的值域（不同的方差），并且資料分布近似于高斯（正态）分布時，歐幾裡得距離的拓展——Mahalanobis距離是有用的。相關變量對标準距離度量有很大影響，因為任何相關變量的變化反映在所有相關變量的變化中。具體地說，兩個對象（向量）x和y之間的Mahalanobis距離定義為：

其中，Σ-1是資料協方差矩陣的逆。注意，協方差矩陣Σ是這樣的矩陣，它的第ij個元素是第i個和第j個屬性的協方差，由式（2.11）定義。

例2.26 在圖2.21中有1000個點，其x屬性和y屬性的相關度為0.6。在橢圓長軸兩端的兩個大點之間的歐幾裡得距離為14.7，但Mahalanobis距離僅為6。這是因為Mahalanobis距離不太關注最大方差方向的差異。實踐中，計算Mahalanobis距離的代價昂貴，但是對于其屬性相關的對象來說是值得的。如果屬性相對來說不相關，隻是具有不同的值域，則隻需要對變量進行标準化就足夠了。

2.組合異種屬性的相似度

前面的相似度定義所基于的方法都假定所有屬性具有相同類型。當屬性具有不同類型時，就需要更一般的方法。直截了當的方法是使用表2.7分别計算出每個屬性之間的相似度，然後使用一種輸出為0和1之間相似度的方法組合這些相似度。一種方法是将總相似度定義為所有屬性相似度的平均值。不幸的是，如果某些屬性是非對稱屬性，這種方法的效果不好。例如，如果所有的屬性都是非對稱的二進制屬性，則相似性度量先歸結為簡單比對系數——一種對于二進制非對稱屬性并不合适的度量。處理該問題的最簡單的方法是：如果兩個對象在非對稱屬性上的值都是0，97則在計算對象相似度時忽略它們。類似的方法也能很好地處理缺失值。

概括地說，算法2.2可以有效地計算具有不同類型屬性的兩個對象x和y之間的相似度。修改該過程可以很輕松地處理相異度。

3.使用權值

在前面的大部分讨論中，所有的屬性在計算鄰近度時都會被同等對待。但是，當某些屬性對鄰近度的定義比其他屬性更重要時，我們并不希望同等對待。為了處理這種情況，可以通過對每個屬性的貢獻權重來修改鄰近度公式。

屬性權重為wk時，式（2.28）變成：

闵可夫斯基距離的定義也可以修改為：

2.4.10　選擇正确的鄰近度度量

一些一般觀察可能會對你有所幫助。首先，鄰近度度量的類型應當與資料類型相适應。98對于許多稠密的、連續的資料，通常使用距離度量，如歐幾裡得距離等。連續屬性之間的鄰近度通常用屬性值的差來表示，并且距離度量提供了一種将這些差組合到總鄰近度度量的良好方法。盡管屬性可能有不同的取值範圍和不同的重要性，但這些問題通常都可以用前面介紹的方法處理，例如規範化和屬性權重。

對于稀疏資料，常常包含非對稱的屬性，通常使用忽略00比對的相似性度量。從概念上講，這反映了如下事實：對于一對複雜對象，相似度依賴于它們共同具有的性質數而不是依賴于它們都缺失的性質數目。餘弦、Jaccard和廣義Jaccard度量對于這類資料是合适的。

資料向量還有一些其他特征需要考慮。之前讨論了歐幾裡得距離、餘弦和相關性對于縮放（乘法）和平移（加法）的不變性。這種考慮的實際意義是，餘弦更适合于稀疏的文檔資料，因為文檔向量中隻需要考慮資料的縮放，而相關性更适用于時間序列，因為時間序列中資料的縮放和平移都很重要。當兩個資料向量的每個特征取值比較接近時，歐幾裡得距離或其他類型的闵可夫斯基距離是最合适的。

在某些情況下，需要使用資料變換或規範化去得到合适的相似性度量。例如，時間序列資料可能具有顯著影響相似性的趨勢或周期模式。此外，正确地計算相似度還需要考慮時間延遲。最後，兩個時間序列可能隻在特定的時間周期上相似，例如，氣溫與天然氣的用量之間存在很強的聯系，但是這種聯系僅出現在取暖季節。

實踐考慮也是重要的。有時，一種或多種鄰近度度量已經在某個特定領域使用，是以，其他人已經回答了應當使用何種鄰近度度量的問題。另外，所使用的軟體包或聚類算法可能完全限制了選擇；如果關心效率，則可能希望選擇具有某些性質的鄰近度度量，這些性質（如三角不等式）可以用來降低鄰近度計算量（見本章習題25)。

然而，如果常見的實踐或實踐限制并未規定某種選擇，則正确地選擇鄰近度度量可能是一項耗時的任務，需要仔細地考慮領域知識和度量使用的目的。可能需要評估許多不同的相似性度量，以确定哪些結果最有意義。

文獻注釋

了解待分析的資料至關重要，并且在基本層面，這是測量理論的主題。比如說，定義屬性類型的初始動機是精确地指出哪些統計操作對何種資料是合法的。我們給出了測量理論的概述，這些源于S.S.Stevens的經典文章［112］。（表2.2和表2.3取自Stevens［113］。）盡管這是最普遍的觀點并且相當容易了解和使用，但是測量理論遠不止這些。權威的讨論可以在測量理論基礎的三卷系列書［88，94，114］中找到。同樣值得關注的是Hand［77］的文章，文中廣泛地讨論了測量理論和統計學，并且附有該領域其他研究者的評論。許多關于Stevens論文的評論和擴充見文獻［66，97，117］。最後，有許多書籍和文章都介紹了科學與工程學特定領域中的測量問題。

資料品質是一個範圍廣泛的主題，涉及使用資料的每個學科。精度、偏置、準确率的讨論和一些重要的圖可以在許多科學、工程學和統計學的導論性教材中找到。資料品質“适合使用”的觀點在Redman［103］中有更詳細的解釋。對資料品質感興趣的人一定也會對MIT的總體資料品質管理計劃［95，118］感興趣。然而，處理特定領域的資料品質問題所需要的知識最好是通過考察該領域的研究者的資料品質實踐得到。

與其他預處理任務相比，聚集是一個不夠成形的主題。然而，聚集是資料庫聯機分析處理（OLAP）［68，76，102］領域使用的主要技術之一。聚集在符号資料分析領域也起到了一些作用（Bock和Diday［64］)。該領域的一個目标是用符号資料對象彙總傳統的記錄資料，而符号資料對象的屬性比傳統屬性更複雜。例如，這些屬性的值可能是值的集合（類别）、區間、具有權重的值的集合（直方圖）。符号資料分析的另一個目标是能夠在由符号資料對象組成的資料上進行聚類、分類和其他類型的資料分析。

抽樣是一個已經在統計學及其相關領域中透徹研究的主題。許多統計學導論性書籍（如Lindgren［90］）中都有關于抽樣的讨論，并且還有通篇讨論該主題的書，如Cochran的經典教科書［67］。Gu和Liu［74］提供了關于資料挖掘抽樣的綜述，而Olken和Rotem［98］提供了關于資料庫抽樣的綜述。還有許多涉及資料挖掘和資料庫抽樣的文獻也值得關注，包括Palmer和Faloutsos［100］、Provost等［101］、Toivonen［115］、Zaki等［119］。

在統計學中，已經用于維歸約的傳統技術是多元定标（MDS）（Borg和Groenen［65］，Kruskal和Uslaner［89］）和主成分分析（PCA）（Jolloffe［80］），主成分分析類似于奇異值分解（SVD）（Demmel［70］）。維歸約詳見附件B。

離散化是一個已經在資料挖掘領域廣泛讨論的主題。有些分類算法隻能使用分類屬性，并且關聯分析需要二進制資料，這樣就有了重要的動機去考察如何最好地對連續屬性進行二進制化或離散化。對于關聯分析，建議讀者閱讀Srikant和Agrawal［111］，而分類領域離散化的一些有用的參考文獻包括Dougherty等［71］、Elomaa和Rousu［72］、Fayyad和Irani［73］以及Hussain等［78］。

特征選擇是另一個在資料挖掘領域被徹底研究的主題，Molina等的綜述［96］以及Liu和Motada的兩本書［91，92］提供了涵蓋該主題的廣泛資料。其他有用的文章包括Blum和Langley［63］、Kohavi和John［87］和Liu等［93］。

很難提供特征變換主題的參考文獻，因為不同學科的實踐差異很大。許多統計學書籍都讨論了變換，但是通常都限于特定的目的，如確定變量的規範性，或者確定變量具有相等的方差。我們提供兩個參考文獻：Osborne［99］和Tukey［116］。

盡管已經讨論了一些最常用的距離和相似性度量，但是還有數以百計的這樣的度量，并且更多的度量正在被提出。與本章的其他許多主題一樣，許多度量都局限于特定的領域，例如，在時間序列領域，見Kalpakis等［81］、Keogh和Pazzani［83］的文章。聚類方面的書提供了最好的一般讨論，特别是如下書籍：Anderberg［62］、Jain和Dubes［79］、Kaufman和Rousseeuw［82］以及Sneath和Sokal［109］。

盡管基于資訊的相似性度量的計算難度大且計算代價高，但是它最近卻變得越來越流行。Cover和Thomas［69］很好地闡述了資訊理論。如果連續變量遵循一個如高斯等常見的分布，則該連續變量的互資訊的計算比較簡單。然而，實際情況往往比較複雜，是以許多新技術被提出。Khan等人的文章［85］在短時間序列上研究比較了被提出的各種方法。參見R和Matlab的相關資訊包。Resher等人最近發表的論文［104，105］讓互資訊備受關注。該論文提出了基于互資訊的方法，該方法具有很優越的性能。在論文發表初期，得到了一些支援［110］，但是也有研究者提出了該方法的局限性［75，86，108］。

兩本較流行的介紹核方法的書籍是文獻［106］和文獻［107］。後者還給出一個與核方法相關的網站［84］。此外，目前許多資料挖掘、機器學習和統計學習教材都有一些關于核方法的介紹。關于核方法在支援向量機中的使用的參考文獻見4.9.4節。

參考文獻

習題

1.在第2章的第一個例子中，統計人員說：“是的，字段2和3也有不少問題。”從所顯示的三行樣本資料，你能解釋她為什麼這樣說嗎？

2.将下列屬性分類成二進制的、離散的或連續的，并将它們分類成定性的（标稱的或序數的）或定量的（區間的或比率的）。某些情況下可能有多種解釋，是以如果你認為存在二義性，簡略給出你的理由。

例子：年齡。回答：離散的、定量的、比率的。

（a) 用AM和PM表示的時間。

（b) 根據曝光表測出的亮度。

（c) 根據人的判斷測出的亮度。

（d) 按度測出的0和360之間的角度。

（e) 奧運會上授予的銅牌、銀牌和金牌。

（f) 海拔高度。

（g) 醫院中的病人數。

（h) 書的ISBN号（查找網上的格式）。

（i) 用如下值表示的透光能力：不透明、半透明、透明。

（j) 軍銜。

（k) 到校園中心的距離。105

（l) 用每立方厘米克表示的物質密度。

（m) 外套寄存号碼。（出席一個活動時，你通常會将外套交給服務生，然後他給你一個号碼，你可以在離開時用它來領取你的外套。）

3.某個地方公司的銷售主管與你聯系，他相信他已經設計出了一種評估顧客滿意度的完美方法。他這樣解釋他的方案：“這太簡單了，我簡直不敢相信，以前竟然沒有人想到，我隻是記錄顧客對每種産品的抱怨次數，我在資料挖掘書中讀到計數具有比率屬性，是以，我的産品滿意度度量必定具有比率屬性。但是，當我根據顧客滿意度度量評估産品并拿給老闆看時，他說我忽略了顯而易見的東西，說我的度量毫無價值。我想，他簡直是瘋了，沒發現我們的暢銷産品滿意度最差，因為對它的抱怨最多。你能幫助我擺平他嗎？”

（a) 誰是對的，銷售主管還是他的老闆？如果你的回答是他的老闆，你需要做些什麼來修正滿意度度量？

（b) 對于原來的産品滿意度度量的屬性類型，你的想法是什麼？

4.幾個月之後，習題3中提到的那個銷售主管又同你聯系。這次，他設計了一個更好的方法，用以評估顧客喜愛一種産品超過喜愛其他類似産品的程度。他解釋說：“在開發一種新産品時，我們通常建立一些變種并評估顧客更喜歡哪一種。我們的标準做法是同時散發所有的産品變種并要求他們根據喜愛程度對産品變種劃分等級，然而，我們的評測題目很不明确，當有兩個以上産品時尤其如此，這讓測試占用了很長的時間。我建議對産品逐對比較，然後使用這些比較來劃分等級，這樣，如果我們有3個産品變種，我們就讓顧客比較變種1和2，然後是2和3，最後是3和1。使用我的方法，評測時間是原來的三分之一，但是進行評測的雇員抱怨說，他們不能從評測結果得到一緻的等級評定。昨天，我的老闆想要知道最新的産品評估。另外我還得告訴你，老的産品評估方法就是他提出的。你能幫助我嗎？”

（a) 銷售主管是否陷入困境？他的方法能夠根據顧客的喜好産生産品變種的有序等級嗎？解釋你的觀點。106

（b) 是否有辦法修正銷售主管的方法？對于基于逐對比較建立序數度量，你做何評價？

（c) 對于原來的産品評估方案，每個産品變種的總等級通過計算所有評測題目上的平均值得到，你是否認為這是一種合理的方法？你會采取哪種方法？

5.辨別号對于預測是有用的，你能想象出一種情況嗎？

6.一位教育心理學家想使用關聯分析來分析測試結果。測試包含100個問題，每個問題有4個可能的答案。

（a) 如何将該資料轉換成适合關聯分析的形式？

（b) 能得到何種屬性類型以及有多少個屬性？

7.下面哪種量更可能具有時間自相關性：日降水量和日氣溫？為什麼？

8.讨論：為什麼文檔詞矩陣是具有非對稱的離散特征或非對稱的連續特征的資料集？

9.許多科學領域依賴于觀測而不是（或不僅是）設計的實驗，比較涉及觀測科學與實驗科學和資料挖掘的資料品質問題。

10.讨論測量精度與術語單精度和雙精度之間的差别。在計算機科學，單精度和雙精度通常分别表示32位和64位浮點數。

11.對于處理存放在文本檔案而不是二進制格式中的資料，給出至少兩個優點。

12.差別噪聲和離群點。確定考慮以下問題：

（a) 噪聲曾令人感興趣或使人期望嗎？離群點呢？

（b) 噪聲對象可能是離群點嗎？

（c) 噪聲對象總是離群點嗎？

（d) 離群點總是噪聲對象嗎？

（e) 噪聲能将典型值變成例外值嗎？反之呢？107

13.考慮發現資料對象的K個最近鄰問題。某個程式員為該任務設計了算法2.3。

（a) 如果資料集中存在重複對象，讨論該算法可能存在的問題。假定對于相同的對象，距離函數隻傳回距離0。

（b) 如何解決該問題？

14.對亞洲象群的成員測量如下屬性：重量、高度、象牙長度、象鼻長度和耳朵面積。基于這些測量，可以使用2.4節的哪種相似性度量來對這些大象進行比較或分組？論證你的答案并說明特殊情況。

15.給定m個對象的集合，這些對象劃分成K組，其中第i組的大小為mi。如果目标是得到容量為n（a) 從每組随機地選擇n×mi/m個元素。

（b) 從資料集中随機地選擇n個元素，而不管對象屬于哪個組。

16.考慮一個文檔詞矩陣，其中tfij是第i個詞（術語）出現在第j個文檔中的頻率，而m是文檔數。考慮由下式定義的變量變換：

其中，dfi是出現第i個詞的文檔數，稱作詞的文檔頻率（document frequency)。該變換稱作逆文檔頻率（inverse document frequency)變換。

（a) 如果詞出現在一個文檔中，該變換的結果是什麼？如果術語出現在每個文檔中呢？

（b) 該變換的目的可能是什麼？

17.假定我們對比率屬性x使用平方根變換，得到一個新屬性x'。作為分析的一部分，你識别出區間（a，b)，在該區間内，x'與另一個屬性y具有線性關系。

（a) 換算成x，（a，b)的對應區間是什麼？

（b) 給出y關聯x的方程。

18.本習題比較和對比某些相似性和距離度量。

（a) 對于二進制資料，L1距離對應于漢明距離，即兩個二進制向量不同的位數。Jaccard相似度是兩個二進制向量之間相似性的度量。計算如下兩個二進制向量之間的漢明距離和Jaccard相似度。

x=0101010001

y=0100011000

（b) Jaccard相似度與漢明距離哪種方法更類似于簡單比對系數，哪種方法更類似于餘弦度量？解釋你的結論。（注意：漢明度量是距離，而其他三種度量是相似性，但是不要被這一點所迷惑。）

（c) 假定你正在根據共同包含的基因的個數比較兩個不同物種的有機體的相似性。你認為哪種度量更适合用來比較構成兩個有機體的遺傳基因，是漢明距離還是Jaccard相似度？解釋你的結論。（假定每種動物用一個二進制向量表示，其中如果一個基因出現在有機體中，則對應的屬性取值1,否則取值0。)

（d) 如果你想比較構成相同物種的兩個有機體的遺傳基因（例如，兩個人），你會使用漢明距離、Jaccard系數，還是一種不同的相似性或距離度量？解釋原因。（注意，兩個人的相同基因超過99.9%。）

19.對于下面的向量x和y，計算指定的相似性或距離度量。

（a) x=（1，1，1，1)，y=（2，2，2，2)，計算餘弦、相關性、歐幾裡得。

（b) x=（0，1，0，1)，y=（1，0，1，0)，計算餘弦、相關性、歐幾裡得、Jaccard。

（c) x=（0，-1，0，1)，y=（1，0，1，0)，計算餘弦、相關性、歐幾裡得。

（d) x=（1，1，0，1，0，1)，y=（1，1，1，0，0，1)，計算餘弦、相關性、Jaccard。

（e) x=（2，-1，0，2，0，-3)，y=（-1，1，-1，0，0，-1)，計算餘弦、相關性。

20.這裡，進一步考察餘弦度量和相關性度量。

（a) 對于餘弦度量，可能的值域是什麼？

（b) 如果兩個對象的餘弦度量為1，它們相等嗎？解釋原因。

（c) 如果餘弦度量與相關性度量有關系的話，有何關系？（提示：在餘弦和相關性相同或不同情況下，考慮諸如均值、标準差等統計量。）

（d) 圖2.22a顯示100000個随機生成的點的餘弦度量與歐幾裡得距離之間的關系，這些點已經規範化，L2的長度為1。當向量的L2長度為1時，關于歐幾裡得距離與餘弦相似性之間的關系，你能得出什麼樣的一般觀測結論？

（e) 圖2.22b顯示100000個随機生成的點的相關性度量與歐幾裡得距離之間的關系，這些點已經标準化，具有均值0和标準差1。當向量已經标準化，具有均值0和标準差1時，關于歐幾裡得距離與相關性之間的關系，你能得出什麼樣的一般觀測結論？

（f) 當每個資料對象的L2長度為1時，推導餘弦相似度與歐幾裡得距離之間的數學關系。

（g) 當每個資料點通過減去均值并除以其标準差标準化時，推導相似度與歐幾裡得距離之間的數學關系。

21.證明下列給出的集合差度量滿足2.4.3節的度量公理:

其中，A和B是集合，A-B是集合差。

22.讨論如何将相關值從區間［-1，1］映射到區間［0，1］。注意，你所使用的變換類型可能取決于你的應用。是以，考慮兩種應用：對時間序列聚類，給定一個時間序列預測另一個的性質。

23.給定一個在區間［0，1］取值的相似性度量，描述兩種将該相似度變換成區間［0，∞］中的相異度的方法。

24.通常，鄰近度定義在一對對象之間。

（a) 闡述兩種定義一組對象之間鄰近度的方法。

（b) 如何定義歐幾裡得空間中兩個點集之間的距離？

（c) 如何定義兩個資料對象集之間的鄰近度？（除鄰近度定義在任意一對對象之間之外，對資料對象不做任何假定。）

25.給定歐幾裡得空間中一個點集S，以及S中每個點到點x的距離。（x是否屬于S并不重要。）

（a) 如果目标是發現點y（y≠x)指定距離ε内的所有點，解釋如何利用三角不等式和已經計算得到的到x的距離，來減少必需的距離計算數量。提示：三角不等式d（x，z)≤d（x，y)+d（y，x)可以寫成d（x，y)≥d（x，z)-d（y，z)。

（b) x和y之間的距離對距離計算的數量有何影響？

（c) 假定你可以從原來的資料點的集合中發現一個較小的子集S′，使得資料集中的每個點至少到S′中一個點的距離不超過指定的ε，并且你還得到了S′中每對點之間的距離矩陣。描述一種技術——使用這些資訊，以最少的距離計算量，從資料集中計算到一個指定點距離不超過β的所有點的集合。

26.證明1-Jaccard相似度是兩個資料對象x和y之間的一種距離度量，該度量滿足2.4.3節的度量公理。具體地，d（x，y)=1-J（x，y)。

27.證明定義為兩個資料向量x和y之間夾角的距離度量滿足2.4.3節的度量公理。具體地，d（x，y)=arccos（cos（x，y))。

28.解釋為什麼計算兩個屬性之間的鄰近度通常比計算兩個對象之間的相似度簡單。