ch數據倉庫與數據挖掘實用

會計學1ch數據倉庫與數據挖掘實用17一月20232Ch14.1.概述(1)數據管理的層次結構下圖不同管理層次的三類信息系統(tǒng)：第1頁/共88頁17一月20233Ch14.1.概述事務處理系統(tǒng)（TPS，TransactionProcessingSystem）——對于基層管理人員來說，所要完成的數據管理任務基本上是針對某種業(yè)務應用來做單項性管理。對這個層次的信息系統(tǒng)來說，一般是掌握基層業(yè)務部門的操作信息、運行狀態(tài)、完成日常管理。本書介紹的關系數據庫技術，建立相應的聯機事務處理系統(tǒng)（OLTP，OnlineTransactionProcessing），顯然能很好地完成這項任務。管理信息系統(tǒng)（MIS，ManagementInformationSystem）——對于中層管理人員來說，所要完成的數據管理任務是起承上啟下的作用，一方面要綜合有關基層部門的有關信息，另一方面要向高層領導提供相關決策信息，并落實高層領導提出的全局性總目標。本書介紹的關系數據庫技術，基于OLTP建立的信息系統(tǒng)，信息內容適合綜合化處理，也可以較好地完成任務。決策支持系統(tǒng)（DSS，DecisionSupportSystem）——對于高層領導人員來說，主要的任務是制定企事業(yè)單位的總目標并提出落實總目標的方針與預算。在這一層次，數據管理的任務重要應是對數據的決策分析。目前，數據都是DBMS統(tǒng)一管理，企事業(yè)單位都相應建立起了操作型數據庫。以下我們看到，在這種操作型數據庫基礎上，想要構建DSS，有很大困難，是不適合的。在這種背景下，數據倉庫（DataWarehouse）技術應運而生。第2頁/共88頁17一月20234Ch14.1.概述(2)數據倉庫的產生數據管理對于高層管理人員，主要是進行決策分析。從決策分析的要求看，傳統(tǒng)的操作型數據庫，所建立OLTP系統(tǒng)是很不合適的。為什么呢？可從決策分析所需要數據有以下幾個方面的特征來看：面向主題：決策分析都是圍繞一些主題而展開的，如銷售企業(yè)，圍繞顧客、供應商、產品、銷售組織等主題，關注決策者關注的數據建模與分析，而不把注意力放在機構的日常操作和事務處理。對于決策分析的主題來說，所需的數據多為總結性數據，而不一定需要操作型數據庫大量存放的細節(jié)數據。這也正解釋高層管理人員對現行數據管理的一種批評——“數據豐富，信息貧乏”。集成的：決策分析所需數據將是多種異構數據源，不但需要本單位的數據，也需要有關的其他單位的數據。這些數據有些來自各類數據庫，有些來自文件，也有些來自Internet網獲取的HTML文件。所需的數據是多種異構數據源的集成。時變的：決策分析不但需要反映當前情況的數據（如2～3個月），還需要歷史數據（通常是5～10年），以便分析變化趨勢，進行決策。由于數據須在時間維上展開，數據量將是非常巨大的。非易失的：決策分析所需的數據不一定需要及時更新，通常只需兩種訪問方式：數據的初始化裝入和以讀為主的訪問。在這樣的背景下，數據倉庫技術應運而生。第3頁/共88頁17一月20235Ch14.1.概述20世紀80年代中期，提出了數據倉庫的概念。到底什么是數據倉庫？可以有多種方式定義，很難提出一個嚴格的定義?，F在通常采用被稱為數據倉庫之父的W.H.Inmon的說法作為定義：“數據倉庫是一個面向主題的、集成的、時變的、非易失的數據集合，支持管理部門的決策過程”。(3)從數據倉庫到數據挖掘對于構建的數據倉庫，如何使用？數據倉庫系統(tǒng)的用戶界面包括的若干決策工具和接口，其中一個重要的技術就是數據挖掘（DataMining，簡稱維DM，也稱為知識發(fā)現KDD，KnowledgeDiscoveryinDBandDW）。第4頁/共88頁17一月20236Ch14.2.數據倉庫(1)概述(2)數據倉庫的建立——數據模型、數據模式(3)OLAP技術第5頁/共88頁17一月20237Ch14.2.數據倉庫(1)概述1)數據倉庫的定義現對數據倉庫定義中的4個特性作進一步解釋:主題性：傳統(tǒng)的操作型數據庫系統(tǒng)都是圍繞某一企事業(yè)單位的應用來組織數據的，而數據倉庫系統(tǒng)則是用于決策分析，要面向主題來組織數據。下圖表示數據組織圍繞保險公司面向主題的一個例子。

第6頁/共88頁17一月20238Ch14.2.數據倉庫集成性：面向應用的操作型數據庫系統(tǒng)，對不同應用有不同的表示方法，而當數據進入數據倉庫時，必須消除各種應用問題的許多不一致性。如圖示例說明數據倉庫的集成問題。第7頁/共88頁17一月20239Ch14.2.數據倉庫時變性：操作型數據庫一般的數據時間期限是60～90天，而數據倉庫通常要存放5～10年的數據；操作型數據庫含有“當前值”的數據，其準確性在訪問時是有效的，但此當前值數據能被更新。而數據倉庫中的數據僅僅是一系列某一時刻生成的復雜的快照；操作型數據庫的基本結構中可能包含也可能不包含時間元素，如年、月、日等。而數據倉庫中的基本數據結構總是包含某種時間元素。圖示例說明數據隨時間變化的問題。第8頁/共88頁17一月202310Ch14.2.數據倉庫非易失性：對于傳統(tǒng)的操作型數據庫通常是一次訪問或處理一到若干個記錄，可隨時對數據進行更新；但數據倉庫中的數據具有非常不同的特性：其數據倉庫不進行一般意義下的數據更新。圖表示數據的非易失性問題。第9頁/共88頁17一月202311Ch14.2.數據倉庫2）DBS與DWSDBS是我們前面詳細講過的一種數據管理系統(tǒng)，第一部分就概述了系統(tǒng)組成結構的三大部分：數據庫、數據管理系統(tǒng)和用戶界面。聯機操作型數據庫系統(tǒng)主要任務是執(zhí)行聯機事務和查詢處理，所以，這種系統(tǒng)也稱為聯機事務處理系統(tǒng)（OLTP，OnlineTransactionProcessing）。數據倉庫是在數據庫基礎上產生的一種數據集合，用于數據管理中的決策分析。對數據倉庫而言，自然也有數據庫系統(tǒng)概念，是管理、使用數據倉庫的一種數據管理系統(tǒng)。它的系統(tǒng)組成體系機構可用圖表示。第10頁/共88頁17一月202312Ch14.2.數據倉庫(2)數據倉庫的建立——數據模型、數據模式1）數據倉庫模型正像建立數據庫的重點是研究數據模型、數據模式一樣，對于數據倉庫來說，有必要深入理解兩個概念——數據模型與數據模式。數據倉庫一般來說是基于多維數據模型（Multi-DimensionDataModel）。該模型將數據看作數據立方體（DataCube）形式?，F舉例說明數據立方體的概念。下圖是銷售數據的數據立方體示例。

第11頁/共88頁17一月202313Ch14.2.數據倉庫所有的銷售數據組織成立方體形式，以多維形式對數據建模和觀察，它由維和事實定義。

維——是關于一個企事業(yè)想要記錄的數據方面，如示例中列出的商店－時間－商品就是設計的3個維，每一個維都有一個維表與之相連，進一步描述這個維。例如，商店的維表可以包含屬性：商店名、地址、電話、經理等。

事實——多維數據模型都是圍繞主題來組織的，該主題就用事實表表示。事實是用數值度量的。例如，上面例子圍繞銷售主題建立數據倉庫的事實，事實表包括相關維表的關鍵字、銷售量、銷售金額等。 立方體比較直觀，便于圖示。但在數據倉庫中，數據立方體的多維，當然不是局限于3維，可以是n維的。第12頁/共88頁17一月202314Ch14.2.數據倉庫2）數據模式采用數據模型來描述某一具體企事業(yè)單位的數據倉庫數據，就引入了另一個概念——數據模式。多維數據模型，具體的維表與事實表如何組織描述，可以有多種不同形式。常見的形式有：星型、雪花型以及事實星座型?，F仍以銷售數據倉庫為例。圖14-8，14-9，14-10分別示例說明三種數據模式。圖14-8銷售數據星型模式：第13頁/共88頁17一月202315Ch14.2.數據倉庫圖14-9銷售數據雪花模式：第14頁/共88頁17一月202316Ch14.2.數據倉庫圖14-10銷售與貨運事實星座模式：第15頁/共88頁17一月202317Ch14.2.數據倉庫在上述數據建模中，對數據立方體再介紹以下概念。度量（Measure）的分類與計算——數據立方體的度量是一個數值函數，指的是對數據立方體的每一個點所求的值。數據立方體空間的多維點，可由維－值對來定義，例如某一空間點上，時間＝“1季度”，商品＝“PC機”，商店＝“No.1”，通過對給定點的各維－值對來聚集數據，即計算該點的度量值。度量可以根據所用的聚集函數而分成三類：①分配型：假設數據劃分為n個集合，函數在每一部分上計算得到一個聚集值。如果將函數用于n個聚集值得到的結果，與將函數用于所有數據得到的數據一樣，則該函數就是一種分配型的計算。例如：計算Count（）可以這樣計算，先將數據立方體分割為若干個子立方體的集合，對每個子立方體計算Count（），然后求和。這樣，Count（）就是分配型的聚集函數。同理，Sum（），Min（），Max（）也是分配型聚集函數。②代數型：如果能夠由一個具有M個參數的代數函數計算（其中M是一個有界整數），而每個參數都可由一個分配型聚集函數求得，則稱這種計算是代數型的。例如，Avg（）可由Sum（）/Count（）計算，其中Sum（）與Count（）都是分配型聚集函數。類似地，min_N（），max_N（）等也都是代數型聚集函數。③整體型：整體型聚集函數既不滿足分配型，也不滿足代數型，例如取中位數（一組數的位數數是指數據按大小排序后，取居中的一個數，若有偶數個數，則取居中兩數的平均值）就是一個整體型聚集函數。概念分層——數據模式中有一個概念分層的問題，概念分層是一個映射序列，對于數據模式來說，隱含有概念分層的問題，例如，商品維表中的小類大類，商店維表中的市名省名，如期維表中的日月季度年。數據模式中的概念分層，為數據管理的分析綜合提供了方便。第16頁/共88頁17一月202318Ch14.2.數據倉庫3)構建數據倉庫的步驟與數據庫系統(tǒng)中數據庫設計過程相類似，數據倉庫的構建要按一定的步驟進行，構建數據倉庫一般有兩個主要步驟：①數據準備階段；②數據倉庫模式設計階段。①數據準備階段:主要是ETL（抽取、轉換、裝載），數據抽取是指從異構多數據源中圍繞主題選取相關的數據，并要對這些數據進行清理，消除噪聲和不一致數據，并完成集成過程中的轉換，使數據具有集成性，表示方式一致，并轉換為適合聚集操作的有關形式。經過數據轉換階段的工作，才能將數據源裝載到數據倉庫中。②數據倉庫模式設計階段:面對實際應用問題，如何面向主題進行數據倉庫設計(采用多維數據模型設計星型、雪花等數據模式）是一個用戶、數據倉庫技術人員共同合作要完成的一個重要工作，有較大的難度。第17頁/共88頁17一月202319Ch14.2.數據倉庫設計方法通常有三種：自頂向下（Top-Down），自底向上（Bottom-Up），混合方法。自頂向下方法——由總體規(guī)劃與設計開始，當對必須解決的業(yè)務應用問題比較清楚，已掌握成熟的技術，可采用這種方法。首先，建立企業(yè)級的數據倉庫：對已所要抽取的操作型數據庫細工和其它數據，使用集中模式，一次數據重構，將冗余與不一致盡量減少，構建全局性的企業(yè)數據倉庫；然后，圍繞部門主題，建立數據集市（DataMart）。自底向上方法——從實驗與原型開始，先建部門數據集市，然后擴大到企業(yè)數據倉庫。首先，局限在一定的主題范圍，本部門自治設計，建立部門局部的數據集市；然后，在若干個數據集市建成后，去除冗余與不一致性，將創(chuàng)建企業(yè)數據倉庫作為首期目標。混合方法——可以認為是上面兩種方法的混合，既能利用自頂向下方法有計劃的戰(zhàn)略性特點，由能保持自底向上方法快速實現與較快應用的優(yōu)點。第18頁/共88頁17一月202320Ch14.2.數據倉庫(3)OLAP技術1）概述2）多維分析技術3）OLAP操作語言1）概述OLAP的由來——傳統(tǒng)的關系數據庫應用系統(tǒng)，是一種面向操作型數據的環(huán)境，處理對象是確定的業(yè)務數據，目的是解決特定業(yè)務處理問題。例如，典型計費系統(tǒng)、航班售票系統(tǒng)等。這種系統(tǒng)的數據時效性強，需及時更新數據，而大量的歷史數據不得不保存到脫機的存儲介質中去。那么，如何利用這些海量數據，完成面向決策分析的任務，傳統(tǒng)的OLTP就難以勝任。這樣，OLAP就應運而生，正如數據倉庫之父W.H.Inmon所講的，“現在該是把哪些歷史數據搬出來的時候了?！甭摍C分析處理（OLAP）的概念，最早是由關系數據庫系統(tǒng)奠基人E.F.Codd在1993年提出的。當時，Codd認為OLTP已不能滿足終端用戶對數據庫查詢分析的需求，SQL的簡單查詢不能滿足用戶的分析需求。終端用戶的決策分析，需要對大量數據經過計算而得到決策，Codd提出了多維數據模型的多維分析的概念，即出現了OLAP技術的概念。第19頁/共88頁17一月202321Ch14.2.數據倉庫OLAP的定義——OLAP是一種基于數據集合（數據倉庫或數據庫）的面向分析處理的技術。采用OLAP技術，用戶能靈活操縱某企事業(yè)單位的數據，以多維數據模型的形式，從多方面、多角度來觀察數據的狀態(tài)，從而為決策分析提供有力支持。OLAP、OLTP的比較——OLTP基于關系操作型數據庫，OLAP基于數據倉庫，重點在于數據分析與決策，是對共享多維數據的決策分析。

OLTP與OLAP的比較，可用表14-1以展示。

第20頁/共88頁17一月202322Ch14.2.數據倉庫表14-1OLTP與OLAP的比較OLTPOLAP用戶操作人員，底層管理人員決策和高層管理人員功能日常操作處理分析決策設計原則面向應用面向主題數據當前的，細節(jié)的，二維的，分立的歷史的，聚集的，多維的，集成的存取讀/寫數十條記錄讀上百萬條記錄工作單位短的簡單事務長的復雜事務用戶數成千上萬個上百個數據規(guī)模100MB～GB100GB～TB第21頁/共88頁17一月202323Ch14.2.數據倉庫OLAP系統(tǒng)的特征——①快速性：OLAP系統(tǒng)采用專門的存儲形式，經過大量的預計算，雖然操作涉及復雜的事務，但分析過程仍具有快速性特點；②可分析性：系統(tǒng)處理的問題與有關的邏輯和統(tǒng)計分析，不是一般的簡單計算；③共享性：潛在地共享有關數據；④多維性：這是OLAP的關鍵特性，可從不同難度進行計算；⑤信息性：這是OLAP的目的所在，完成數據的信息解釋。第22頁/共88頁17一月202324Ch14.2.數據倉庫2）多維分析技術OLAP多維分析技術建立在多維數據模型的基礎上，涉及的重要概念列舉如下：維——是人們觀察數據的特定角度，是考慮問題時的一類屬性，屬性集合構成一個維（如：時間維、地理維等）。維的層次——人們觀察數據的某個特定角度（即某個維）還可以表示細節(jié)程度不同的各個描述方面（如：時間維——分別是日期、月份、季度、年）。維的成員——維的一個取值，是數據項在某維中位置的描述（如：“某年某月某日”是在時間維上某一位置的描述）。度量——用戶瀏覽多維數據集時查看的數值，是用來評測分析的一種指標值。如：社會保險系統(tǒng)中的基金收繳金額、養(yǎng)老金撥付金額，就是一種度量值。立方體——多維數據集合，是分析的一個主題，由多個維和若干度量值構建并匯總而成的多維數據結構集合，是OLAP的分析對象。第23頁/共88頁17一月202325Ch14.2.數據倉庫OLAP系統(tǒng)基本操作：切片和切塊（Slice，Dice）——在多維數據立方體中，按二維進行切片，按三維進行切塊，可得到所需的某部分數據。如圖14-11就表示社會保險數據在地理、時間、單位分類進行切塊和切片的數據。圖14-11

社會保險數據立方體的切片、切塊示例：第24頁/共88頁17一月202326Ch14.2.數據倉庫鉆取（Drill）——鉆取包含向下鉆?。―rill-down）和向上鉆取（Drill-up）/上卷（Roll-up）操作，在操作中鉆取的深度與維所劃分的層次是相對的。圖14-12表示社會保險數據立方體按單位維向下/向上鉆取的數據示例。第25頁/共88頁17一月202327Ch14.2.數據倉庫旋轉（Rotate）/轉軸（Pivot）——通過旋轉（也稱為轉軸），可以得到不同視角的數據。圖14-13表示社會保險數據立方體的旋轉操作示例。第26頁/共88頁17一月202328Ch14.2.數據倉庫3)OLAP操作語言傳統(tǒng)關系數據庫系統(tǒng)的操作語言是SQL，那么對多維數據立方體的OLAP操作語言是什么呢？這方面的標準化還有待進一步工作，這里以微軟提供的MDX語言為例進行介紹。MDX語言概述:MDX（MultidimensionalExpression）是一種支持多維數據立方體定義和操作的語言，由微軟公司提供。MDX在語法的很多方面與SQL相似，但不能算是SQL語言的擴展。MDX提供數據結構定義的DQL語法，用于創(chuàng)建（和刪除）多維數據集、維度、度量值以及它們的坐標對象的MDX命令。MDX提供多維立方體操作的查詢語句，包含了與SQL類似的Select、From、Where子句，MDX還提供了函數等，增強了操作能力?；镜腗DX查詢是：

Select[<軸維度1>[,<軸維度2>…]]From[<多維數據集>][Where[<切片1>[,<切片2>…]]]SQL語言是從表返回一個仍是表的二維數據集，而MDX是從多維數據集返回多維數據子集。第27頁/共88頁17一月202329Ch14.2.數據倉庫現以社會保險系統(tǒng)中的應用為例加以說明。

Select{[地理].[西安].[市本級],[地理].[西安].[雁塔區(qū)]}ONCOLUMNS，

{[時間].[2001年],[時間].[2002年]}ONROWSFrom基金收繳

Where([單位].[事業(yè)],[收繳類型].[正常繳納])即可得到如下結果。第28頁/共88頁17一月202330Ch14.3.數據挖掘(1)概述(2)數據挖掘的過程(3)數據挖掘的基本方法(4)復雜數據類型的挖掘第29頁/共88頁17一月202331Ch14.3.(1)概述(1)概述:1)數據挖掘技術的產生;2)數據挖掘的定義.1)數據挖掘技術的產生:從數據庫技術的發(fā)展過程看，20世紀80年代以來，數據庫系統(tǒng)在各行各業(yè)廣泛應用，全球的信息量每隔20個月就要增加一倍。一個中等規(guī)模的企業(yè)每天要產生100MB以上的業(yè)務數據，據統(tǒng)計，1993年全球的計算機數據存儲容量約為2000TB，到2000年增加到300萬TB。但是，據估計，目前一個大型企事業(yè)單位的數據，大約只有7％得到較好地應用，對于數據管理來說，陷入了一個尷尬境地――“數據豐富，信息（知識）貧乏”。數據管理用于決策分析的技術應運而生：一方面數據倉庫技術的提出與發(fā)展，另一方面數據挖掘技術的產生。先看一個例子：啤酒與尿布的故事――美國加州某超市連鎖店通過對存儲的銷售數據采用數據挖掘技術分析發(fā)現：下班前后或周末購買嬰兒尿布的顧客較多為男性，往往同時購買啤酒，兩類互不相干的商品有一定的關聯。于是，連鎖店經理當機立斷，重新布置貨架，將男士們需要的日常生活用品就近布置，取得了有關商品銷量大增的驕人業(yè)績。

80年代以來，人們逐漸關注這方面的研究，其它數據挖掘的例子也就層出不窮.正像數據庫技術的發(fā)展一樣，開始時是一個一個行業(yè)的建立使用，逐步鋪開。數據挖掘技術，目前雖沒有數據庫技術這樣家喻戶曉，但經過多年的發(fā)展，應用領域也已是一個熱門領域，應用面已相當廣泛。第30頁/共88頁17一月202332Ch14.3.(1)概述2)數據挖掘的定義較為廣泛接受的數據挖掘定義是：提取隱含于數據集合（數據庫、數據倉庫或其它數據集合）中未知的、有用的、不一般的（即不象OLAP中那樣計算總和、平均值子類的普通信息）信息或知識。數據挖掘，也有另外一種說法：數據庫中的知識發(fā)現KDD（KnowledgeDiscoveryinDatabase）或知識提取（KnowledgeExtraction），數據/模式分析（Data/PatternAnalysis），也有人認為數據挖掘DM是KDD的一個步驟，特別在討論實現過程時，往往認為KDD是較廣泛的過程，而DM是其中的一個步驟。從數據庫技術看，在邏輯上從大量數據中提取規(guī)則，數據挖掘采用的是歸納推理的方法。而根據大量數據，采用歸納方法，推斷出一般化的規(guī)則、規(guī)律，也就是形成信息或知識。從更廣泛的角度來看，數據挖掘是一門跨學科的技術，綜合采用了統(tǒng)計學、數據庫技術、機器學習、模式識別、人工智能、可視化技術，很難嚴格區(qū)分數據挖掘與這些學科之間的界限。第31頁/共88頁17一月202333Ch14.3.(2)數據挖掘的過程(2)數據挖掘的過程:1)知識發(fā)現KDD的全過程

2)數據挖掘（DataMining，DM）過程1)知識發(fā)現KDD的全過程第32頁/共88頁17一月202334Ch14.3.(2)數據挖掘的過程2)數據挖掘（DataMining，DM）過程數據挖掘作為整個知識發(fā)現（KDD）的一個重要步驟，起著關鍵作用。有時，當單獨將數據挖掘過程抽出來闡述時，也經常把KDD過程與DM過程不加區(qū)分，正像提到KDD概念、DM概念時也不加區(qū)分。數據挖掘過程，可用下圖來表示。某種意義上看，也是知識發(fā)現的全過程，其中的模式（Pattern）發(fā)現――數據挖掘的關鍵步驟，相當于上面KDD過程中的數據挖掘。第33頁/共88頁17一月202335Ch14.3.(2)數據挖掘的過程①數據選擇：數據挖掘正像采礦一樣，先要通過地質普查找到礦藏所在源，這里就是提出挖掘的目標，也就是選擇好限定的主題，來選擇相關的數據。例如，目標是優(yōu)化銷售策略，那么，根據這樣的目標，圍繞此主題選取與銷售相關的數據記錄作為數據挖掘的對象。②數據預處理：對于選擇好的數據，必須經過預處理提高數據質量，才能使得數據挖掘更加有效。因為不經預處理的數據，往往垃圾數據比較多，數據的決策分析是一種典型的“垃圾進垃圾出”的過程，數據預處理對數據挖掘的結果有重要的影響。數據預處理技術主要包括：數據清理、數據集成、數據變換和數據歸約。③模式（Pattern）發(fā)現：這是數據挖掘的關鍵一步。蘊涵在數據中的規(guī)律、規(guī)則或特征，也就是通常所說的知識，表現在數據的某種模式上，發(fā)現數據模式關鍵是人機交互地選擇算法，這一步是數據挖掘中的核心內容，下面我們將單列一節(jié)介紹數據挖掘的基本內容與方法。④解釋評估：通過模式發(fā)現算法可以得到較多的模式。對于給定的用戶，是否對所有模式都感興趣，答案是否定的。所以，數據挖掘過程的最后一步，是討論從挖掘出的模式中得到有趣模式的問題，即對用戶有用的模式，也就是對挖掘出的模式進行解釋評估。第34頁/共88頁17一月202336Ch14.3.(2)數據挖掘的過程有關解釋評估，需要討論以下一些問題：①模式興趣度的度量：一是客觀度量，例如對于形如X→Y的關聯規(guī)則，客觀度量通常采用支持度和置信度來定義，支持度Support(X→Y)=P(X∪Y)，其中P(X∪Y)是項集X和Y并的概率。置信度Confidence(X→Y)=P(Y|X)，其中P(Y|X)是包含X的事務也包含Y的概率。對于度量再引入閾值，由用戶來控制，用戶可以認為置信度閾值不超過50%的模式是無趣的。對此，下面還要詳細討論的。另一種是主觀度量，實際上是用戶的一種主觀預感，認為合理的或認為出乎意料的，給出模式是否有趣的結論。②數據挖掘的完全性：數據挖掘能否挖掘出所有有趣的模式，這是較難做到的。只能說，對于某些數據挖掘任務，根據用戶提出的限制和興趣度量，在一定條件下保證算法的完全性。③數據挖掘能夠僅僅產生有趣的模式嗎？往往數據挖掘可能會生成一些不是有趣的模式，我們希望僅僅產生有趣模式，這是一個數據挖掘優(yōu)化問題。如何識別真正有趣的模式，過濾掉一些不感興趣的模式，采用興趣度度量來知道數據挖掘過程，是數據挖掘中最后一步重要的工作。第35頁/共88頁17一月202337Ch14.3.(3)數據挖掘的基本方法

(3)數據挖掘的基本方法數據挖掘算法，針對不同的挖掘任務，有很多不同的方法，本節(jié)只闡述下面4種基本方法：1．分類、2．聚類、3．關聯分析、4．時間序列。1）分類①概述分類是對數據的一個重要抽象，從機器學習的觀點看，分類是一種監(jiān)督學習，即根據應用的需要確定分類的類別，通過對訓練數據的分類學習歸納出分類規(guī)則，利用測試數據對模型的準確率進行測試，再對數據進行分類操作。第36頁/共88頁17一月202338Ch14.3.(3)數據挖掘的基本方法分類過程分兩步完成，如圖所示。第37頁/共88頁17一月202339Ch14.3.(3)數據挖掘的基本方法②分類算法以決策樹算法為例，說明分類算法的思路。例如，要對顧客是否購買電腦進行測試，圖就是決策樹的示例。第38頁/共88頁17一月202340Ch14.3.(3)數據挖掘的基本方法算法14-1：Generate_Decision_Tree（由給定的訓練數據生成決策樹）輸入：訓練樣本Samples，由離散值屬性表示，候選屬性的集合是Attribute_List輸出：決策樹算法描述：⒈）創(chuàng)建節(jié)點N；⒉）ifSamples都在同一類Cthen

返回N作為葉節(jié)點，以類C標記；⒊）ifAttribute_List為空then

返回N作為葉節(jié)點，標記為Samples中類別個數最多的類別；//多數表決⒋）從Attribute_List中選擇一個信息增益最大的屬性test_attribute；//屬性選擇方法的信息增益概念，需要解釋并將此節(jié)點N標記為test_attribute；⒌）foreachtest_attribute中的已知取值ai

由節(jié)點N長出一個條件為test_attribute=ai的分支；//劃分Samples設Si是Samples中test_attribute=ai的樣本的集合；//其中的一個劃分⒍）ifSi為空then

加上一個葉節(jié)點，標記為Samples中類別最多的類；⒎）else加上一個由Generate_Decision_Tree(Si,Attribute_List,test_attribute）返回的節(jié)點；第39頁/共88頁17一月202341Ch14.3.(3)數據挖掘的基本方法信息增益方法：這是上面決策樹算法中屬性選擇的基本方法。信息增益的定義。設S識包含s個數據樣本的集合，假定類標號屬性具有m個不同值，即定義m個不同的類別Ci(i=1,2,…,m)，設si是類Ci中的樣本數，對一個給定的樣本分類可給出所需的期望信息： 其中pi是任一樣本屬于類別Ci的概率，可按si/s估計，對數函數以2為底，是因為信息以二進制位編碼。設屬性A具有v個不同值{a1,a2,…av}，利用屬性A可將數據集合S劃分為v個子集{S1,S2,…Sv}，其中Sj包含了S集合中屬性A取aj值的樣本。若屬性A被選為測試屬性，設sij為子集sj中屬于Ci類的樣本數，那么，利用屬性A劃分當前樣本集所需的期望信息是：其中當作第j個子集的權值，而是對于給定子集Sj的期望信息。E(A)計算結果越小，表示其子集劃分結果越好。在A上分支將獲得的編碼信息是：Gain(A)=I(S1,…,Sm)-E(A)定義為利用屬性A對當前分支節(jié)點進行劃分的信息增益。第40頁/共88頁17一月202342Ch14.3.(3)數據挖掘的基本方法現以購買電腦相關的訓練數據樣本為例，說明信息增益方法的思路。

RID年齡收入是否學生信用評估是否購買電腦

1<=30高No中No2<=30高No好No331..40高No中Yes4>40中No中Yes5>40低Yes中Yes6>40低Yes好No731..40低Yes好Yes8<=30中No中No9<=30低Yes中Yes10>40中Yes中Yes11<=30中Yes好Yes1231..40中No好Yes1331..40高Yes中Yes14>40中No好No第41頁/共88頁17一月202343Ch14.3.(3)數據挖掘的基本方法對于表給出的訓練數據集合，分類的標記為2類，類C1對應于買電南yes，類C2對應于no，類yes有9個樣本，類no有5個樣本，計算得到：現計算有關屬性的信息增益，從屬性年齡開始，對年齡<=30s11=2s12=3I(s11,s21)=0.971對年齡31..40s12=4s22=0I(s11,s21)=0對年齡>40s13=3s23=2I(s11,s21)=0.971樣本按年齡劃分，期望信息為：第42頁/共88頁17一月202344Ch14.3.(3)數據挖掘的基本方法故這種劃分的信息增益是：Gain(年齡)＝I(s1,s2)-E(age)=0.246。類似地，可以計算Gain（收入）=0.029，Gain（是否學生）=0.151，Gain（信用評估）=-0.048，由于年齡在屬性中具有最高的信息增益，被選作為測試屬性，對此可創(chuàng)建分支的節(jié)點。也就是一開始給出的決策樹示例將Age作為分支節(jié)點的原因。我們以決策樹方法簡述了算法的實現過程。分類算法除了決策樹方法外，常用的方法還有很多，例如：基于統(tǒng)計學的貝葉斯分類方法、神經網絡分類方法、k-最近鄰方法、遺傳算法、粗糙集方法、模糊集方法等等。第43頁/共88頁17一月202345Ch14.3.(3)數據挖掘的基本方法2)聚類①概述分類是指定類別將數據集合劃分的一種技術，從其學習角度來看，是有指導的學習。而聚類也是要對數據集合進行分析加以劃分，但要劃分的類別是未知的，是一種無指導的學習。聚類是指將數據集合劃分為由類似數據組成的多個類（也可稱為簇，cluster）的過程，同一類（或簇）中的數據彼此相似，與其它類中的數據相異。聚類的典型應用領域有：市場營銷（幫助市場營銷人員發(fā)現基本顧客的不同群組，利用這一分析制定更有針對性的營銷計劃），生物研究（用于動物植物聚類，對基因聚類，獲得對種群固有結構的認識），城市規(guī)劃（根據房屋的類型、價值、地理位置對城市房屋分組），Web文檔分類（Web文檔數據是海量的，獲得有關文檔的特性，聚類后加以逐類分析）等等。第44頁/共88頁17一月202346Ch14.3.(3)數據挖掘的基本方法聚類技術的相關概念：點與距離。點——將數據視為多維空間中點的集合，數據聚類問題演化為多維空間中點的聚類問題。至于如何將數據視作多維空間中的點，有不同的表示方法：（1）將數據表示為向量，數據集合是一個向量集合，{Xi}（i=1,2,…,N）是N個點的數據向量集合，引入中心點（2）數據集合看作是矩陣形式，表示為關系數據庫表的形式，其中一行就是數據集合中的一個點。距離——有了點的概念，自然可引入基于點的距離概念，距離可表示為兩點之間的歐幾里德距離：或曼哈頓距離：數據點之間的相似與相異，用距離的大小加以度量，進行聚類分析。第45頁/共88頁17一月202347Ch14.3.(3)數據挖掘的基本方法②聚類算法劃分法——典型的劃分法是K-平均算法。給定某一包含n個數據元素的數據庫，生成的類（或簇）的數目為K，將n個數據劃分為K類（K≤n），以使同一類中的數據相似，而不同類中的數據相異。下面是K-平均算法的描述。算法14-2：K-平均//劃分的K-平均算法基于簇中數據的平均值輸入：簇的數據K，數據庫包含n個元組D={x1,…,xn}輸出：K個簇，是平方誤差準則最小算法：

fork=1,…,Kdo//令r(k)是從D={x1,…,xn}中隨機選取的一個點

while在聚類Ck中有變化發(fā)生do

形成聚類：fork=1,…,Kdo Ck={x∈D|d(rk,x)≤d(rj,x)對所有j=1,…,K,j≠k}; end;

計算新的聚類中心：fork=1,…,Kdo rk=Ck內點的平均值向量；

end；

end；第46頁/共88頁17一月202348Ch14.3.(3)數據挖掘的基本方法k-平均算法，開始為每個聚類選擇一個初始的中心點，然后以初始中心值為核心形成聚類，再用迭代法反復修改初始的聚類，直到無明顯改進為止。k-平均算法的復雜度是O(knI)，k是聚類數，n為數據集合大小，I是迭代次數，通常k<<n，I<<n，算法以局部最優(yōu)結束。層次法——將所有數據組織成一顆聚類的樹，分別可以自底向上或自頂向下進行層次分解，自底向上分解的層次法通常稱為凝聚的，自頂向下分解的層次法通常稱為分裂的。一般以凝聚的層次聚類用得較多。其算法可簡單描述如下：fori=1,…,n令C={x(i)};while存在一個以上的聚類do

令Ci和Cj為使系統(tǒng)中任意兩個聚類間的距離D=(Ck,Cn)最小化得兩個聚類；

Ci=Ci∪Cj;end;第47頁/共88頁17一月202349Ch14.3.(3)數據挖掘的基本方法除了以上兩種主要的聚類方法以外，還有其它較多的聚類方法：基于密度的方法、基于網格的方法、基于模型的方法等等，還有一些聚類算法集成了多種聚類方法的思想，綜合性采用多種聚類技術可取得更好的聚類效果。第48頁/共88頁17一月202350Ch14.3.(3)數據挖掘的基本方法3）關聯分析①概述關聯分析是數據挖掘中較早引起興趣得一種數據分析方法，關聯分析是發(fā)現數據集合中數據之間的聯系。數據之間的聯系，可能表現為兩種形式：一種是同一交易（有時也可說是同一事務）內數據之間的聯系，如在顧客的一筆交易中，購買兩種不同商品之間的聯系；另一種是不同交易內數據之間的聯系，如一個顧客在一次交易中買了甲商品，探討另一次交易中購買乙商品的可能性，也是研究數據之間的聯系。在數據挖掘領域，前者就是此處所述的關聯分析，后者是下節(jié)要講述的時間序列。關聯分析中的若干基本概念：第49頁/共88頁17一月202351Ch14.3.(3)數據挖掘的基本方法支持度可信度

第50頁/共88頁17一月202352Ch14.3.(3)數據挖掘的基本方法關聯規(guī)則舉例

交易

數據項t1A,B,C,Dt2A,B,Dt3A,D,Et4B,Ct5A,B,C,D關聯規(guī)則支持度可信度60%75%50%75%60%75%60%100%第51頁/共88頁17一月202353Ch14.3.(3)數據挖掘的基本方法②關聯分析典型算法關聯分析典型算法，比較有名的是Apriori算法（1993年R.Agrawal等人提出）。該算法實現分兩步：1）找出所有頻繁數據項集（frequentitemsets）：即找出所有支持度超過指定閾值的數據項集；2）利用頻繁數據項集，生成候選的關聯規(guī)則，并驗證其可信度，如果可信度超過指定的閾值，則該關聯規(guī)則即為所要找關聯規(guī)則。第52頁/共88頁17一月202354Ch14.3.(3)數據挖掘的基本方法算法14-3：Apriori算法，利用層次迭代找出頻繁項集輸入：交易（事務）數據庫D，最小支持度閾值min_sup輸出：D中的頻繁項集L流程：L1=find_frequent_1_itemset(D);//發(fā)現1-項集for(k=2;Lk-1≠Φ;k++){Ck=apriori_gen(Lk-1,min_sup);//根據頻繁k-1項集產生候選k項集

foreacht∈D{//掃描數據庫DCt=subset(Ck,t);//獲得t所包含的候選項集

foreachc∈Ct,C.count++;}Lk={c∈Ck|C.count≥min_sup}}returnL=UkLk;第53頁/共88頁17一月202355Ch14.3.(3)數據挖掘的基本方法Procedureapriori_gen(Lk-1:k-1-項集；min_sup:最小支持度閾值)foreachl1∈Lk-1foreachl2∈Lk-1if(l1[1]=l2[1])∧(l1[2]=l2[2])∧…∧(l1[k-2]=l2[k-2])∧l1[k-1]=l2[k-1]then{C=l1?l2；//將兩個項集連接到一起

ifhas_infrequent_subset(c,Lk-1)thendeletec；//除去不可能產生頻繁項集的候選

elseCk=Ck∪{C};}returnCk;第54頁/共88頁17一月202356Ch14.3.(3)數據挖掘的基本方法Procedurehas_infrequent_subset(C,Lk-1)foreach(k-1)-subsetsofC ifs!∈Lk-1 returnTRUE; elsereturnFALSE;第55頁/共88頁17一月202357Ch14.3.(3)數據挖掘的基本方法4)時間序列①概述時間序列數據挖掘，是指表示不同交易之間的數據關聯，例如，某一顧客多次購買商品，每次交易的數據項集構成時間序列，在時間序列中發(fā)現的模式，就是一種數據之間的關聯。下圖就是不同交易的數據之間關聯的示例。第56頁/共88頁17一月202358Ch14.3.(3)數據挖掘的基本方法顧客號交易時間數據項106/11/99-9A,B206/11/99-10C106/11/99-11D306/11/99-13D106/12/99-9E,G,H406/12/99-10D,F,G506/12/99-17D306/12/99-18E,G506/13/99-21C第57頁/共88頁17一月202359Ch14.3.(3)數據挖掘的基本方法顧客號數據項集序列1<{A,B},{D},{E,G,H}>2<{C}>3<{D},{E,G}>4<{D,F,G}>5<{D},{C}>第58頁/共88頁17一月202360Ch14.3.(3)數據挖掘的基本方法對這種時間序列的數據，為找到數據之間關聯，引入如下概念。設有兩個不同顧客的數據項序列為<a1,a2,…,an>和<b1,b2,…,bm>，如有整數i1<i2<…<in，使a1≤bi1，使a1≤bi2，…，使a1≤bin，則稱<a1,a2,…,an>包含于<b1,b2,…,bm>之中，表示<a1,a2,…,an>≤<b1,b2,…,bm>。這種包含關系，即表示這兩個顧客都支持序列<a1,a2,…,an>，即這兩個表示不同時間的交易數據之間存在關聯性。例如，圖中，<{C}>≤<{D,C}>表示顧客2和5都支持<{C}>，而<{D},{E,G}>≤<{A,B},{D},{E,G,H}>表示顧客1、3和5都支持<{D},{E,G}>，支持度s%=40%，凡是支持度超過指定閾值的序列稱為頻繁序列，對于時間序列挖掘而言，其基本問題就是要找出頻繁序列。第59頁/共88頁17一月202361Ch14.3.(3)數據挖掘的基本方法②時間序列挖掘基本方法現介紹AprioriAll算法，它是尋找頻繁序列的基本方法，圖14-23是該算法的描述。ProcedureAprioriAll()begin L1＝{frequent1-sequences};//1-sequences是只包含一個數據項集的序列

for(k:=2;Lk-1=Φ;k++)do { Ck::=AprioriG(Lk-1);//生成k-sequence候選序列集

forallcustom-sequencesinthedatasetdo { forallcancidatesc∈Ckcontainedincustom-sequencedo c.count++; } Lk:={c∈Ck|c.count≥minsupport} } Answer:=Maximalsequencesin∪kLk; end第60頁/共88頁17一月202362Ch14.3.(3)數據挖掘的基本方法AprioriG(): insertintoCk selectp.fitemset1,…,p.fitemsetk-1,q.fitemsetk-1 fromLk-1p,Lk-1q wherep.fitemset1=q.fitemset1,… p.fitemsetk-2=q.fitemsetk-2, p.fitemsetk-1<>q.fitemsetq-1;

其中fitemset是頻繁數據項集。第61頁/共88頁17一月202363Ch14.3.(3)數據挖掘的基本方法從此算法的實現過程看，與前面關聯分析算法Apriori較為相像，實際上將帶時間的交易數據轉換為顧客的數據項集序列，就為尋找頻繁數據項集作了準備。算法實施前，先將交易數據排序（以顧客標識為主鍵，交易時間為次鍵進行升序排序），然后篩選出頻繁數據項集，在此基礎上經過變換發(fā)現頻繁序列。第62頁/共88頁17一月202364Ch14.3.(3)數據挖掘的基本方法③時間序列挖掘的其它內容 時間序列是指包含隨時間變化而發(fā)生的數值或事件序列，對這類數據的挖掘，上面所述內容屬于挖掘序列模式，即從與時間相關的數據中，挖掘出相關的頻繁發(fā)生模式，例如所舉例子，從購買某類商品的顧客可能會在近期內購買另一類商品，就是一種序列模式。除此以外，時序數據挖掘還有趨勢分析，相似搜索等重要內容。趨勢分析——時序數據中包含一個變量Y，可以認為是時間的函數Y=F(t)，時序分析即研究其中的趨勢變化、循環(huán)變化、季節(jié)性變化或無規(guī)律變化。采用數學上的平滑方法、曲線擬合方法、最小二乘法等可以完成有關的數據分析，制定預測方案。第63頁/共88頁17一月202365Ch14.3.(3)數據挖掘的基本方法相似搜索——給定了一個時間序列數據，相似搜索是發(fā)現所有與它相似的時序數據，是一種序列匹配問題。相似搜索有如下主要的方法：（1）數據轉換，從時域到頻域。通常采用傅立葉變換、小波變換就可以完成這種轉換。采用歐幾里德的概念進行相似性測量，完成數據匹配。（2）索引方法。采用R-樹、R*樹，改進數據存儲結構，提高相似搜索的速度。（3）時間序列查詢語言，完成復雜查詢，支持范圍查詢、最鄰近查詢等，搜索與給定時序數據相似的時序數據。第64頁/共88頁17一月202366Ch14.3（4）復雜數據類型的挖掘（4）復雜數據類型的挖掘前面所介紹的數據挖掘，主要針對結構化數據進行討論的。而復雜數據類型，諸如文本數據、多媒體數據、Web數據都表現為半結構化或非結構化形式，此處對復雜數據類型的挖掘，舉文本、多媒體和Web這三類較流行的數據進行簡要介紹。1）文本數據挖掘以文本形式存放的數據，包含一些半結構化字段，如標題、作者、出版社、出版時間、長度等，但也包含無結構的文本內容。對這類半結構化的文本數據，傳統(tǒng)的數據分析方法是采用情報檢索（InformationRetrieval），大部分是利用索引來完成檢索。但是，在文本數據迅猛增加時，傳統(tǒng)情報檢索已無法滿足實際需求。例如，不知道文本中究竟包含哪些內容時，要想準確查詢較為困難，想對文本進行比較，評估文本的重要性、相關性等等，文本數據挖掘應運而生。第65頁/共88頁17一月202367Ch14.3（4）復雜數據類型的挖掘文本挖掘的主要內容有：（1）基于關鍵字關聯分析。首先收集經常一起出現的關鍵字或詞匯，然后對其進行關聯分析。關聯分析的方法與前面所述的事務數據關聯分析相似，但在此以前，要完成詞根處理、去除非用詞等預處理，將數據表示為包含{文檔標識符，關鍵字集合}在內的形式，轉換為事務數據關聯分析問題。（2）文本分類分析。自動地對大量文本進行分類，是一種重要的文本挖掘。一般做法是：先把一組預先分類過的文本當作訓練集，然后對訓練集進行分析得出分類模式。對這種分類模式需經一定的測試，不斷細化。粗看起來，與前面事務數據的分類很相似，但因兩類數據的不同，不能采用事務數據分類時的決策樹分析，而是采用基于關聯的分類，細節(jié)不贅述。第66頁/共88頁17一月202368Ch14.3（4）復雜數據類型的挖掘2）多媒體數據挖掘現實生活中存在大量多媒體數據，例如，圖像數據、音頻數據、視頻數據等等，對這類數據的管理，從一般性的數據庫管理到數據挖掘進行數據分析，是當前數據庫技術的一個熱門領域。 此處，以圖像數據挖掘為主介紹一些多媒體數據挖掘的主要方法：多媒體數據的相似搜索，多媒體數據的多維分析，多媒體數據的分類與預測分析以及多媒體數據的關聯挖掘。第67頁/共88頁17一月202369Ch14.3（4）復雜數據類型的挖掘多媒體數據的相似搜索——主要有兩種方法：（1）基于描述的搜索方法，在多媒體數據上建立標引（如：關鍵字、標題等）再進行檢索。這種方法若手工完成是很費勁的，若自動完成，往往檢索結果質量較差。（2）基于內容的搜索方法，是近年來的主要方法，針對圖像內容中的顏色構成、紋理、形狀等進行特征描述再檢索。例如，基于顏色直方圖的特征表示，多特征（顏色直方圖、形狀、位置和結構）構成的特征標識，基于小波變換的特征標識，建立了特征標識以后，就可以利用圖像特征向量匹配來進行相似搜索。多媒體數據的多維分析——采用按傳統(tǒng)的從關系數據構造數據立方體相似的方法，設計和構造多媒體數據立方體。多媒體數據立方體可包含針對多媒體的維和度量，如顏色、紋理和形狀。在此基礎上，進行基于視覺內容的多維分析，并完成多種知識的挖掘，包括匯總、比較、分類、關聯和聚類。第68頁/共88頁17一月202370Ch14.3（4）復雜數據類型的挖掘多媒體數據的分類和預測分析——分類和預測分析已經用于多媒體數據挖掘，尤其在科學研究中，如天文學、地震學和地理科學的研究。目前圖像數據挖掘應用中決策樹分類是最基本的數據挖掘方法。數據預處理在圖像數據挖掘中是相當重要的，它包括數據清理、數據聚焦和特征提取，同時由于數據量很大，需要使用并行、分布處理等技術來加強處理能力。多媒體數據中的關聯分析——多媒體數據中的關聯可能會涉及三類：（1）圖像內容和非圖像內容特征間的關聯，如規(guī)劃“如果照片的上半部分的50%是藍色，那它很可能是天空”屬于此類，它把圖像內容和關鍵字“天空”關聯在一起。（2）與空間關系無關的圖像內容的關聯，如規(guī)劃“若一個圖像包含兩個藍方框，那么就可能包含一個紅色圓”，所描述的關聯構思關于圖像內容的，但與空間關系無關。（3）有空間關系的圖像內容間的關聯，如“若兩個黃方框之間有一個紅色三角形，那么下面就可能有一個大的橢圓物體”，這里所描述的與圖像關聯的對象具有空間關系。第69頁/共88頁17一月202371Ch14.3（4）復雜數據類型的挖掘3）Web挖掘隨著Internet技術的發(fā)展，尤其是Web的全球普及，使得Web上的信息無比豐富。但是，這些信息主要是一些大量的異構數據源，文檔結構性差，其數據多為半結構化或非結構化。對這些數據如何管理、分析，一種有效的方法是互聯網搜索引擎，利用此引擎可以有效發(fā)現和很好利用互聯網的信息資源。但是，這種方法存在如下不足：首先是一個主題可能包含成千上萬的文檔，從而導致搜索引擎的查詢結果結構常常也是非常巨大，而其中只有較少以部分與用戶相關；其次是許多與主題相關的文檔或許沒有包含相應的關鍵字。例如“datamining”關鍵字，可能會發(fā)現與“miningindustry”有關的網頁。第70頁/共88頁17一月202372Ch14.3（4）復雜數據類型的挖掘搜索引擎顯然不能作為利用Web信息資源的唯一方法，同時我們還可看出，要對Web數據進行有效的知識發(fā)現存在以下問題：1）互聯網數據太大以至無法有效構造數據倉庫并進行數據挖掘。2）網頁的復雜性遠遠要大于任何傳統(tǒng)的文本文檔。3）互聯網的資源具有很大的動態(tài)性。4）互聯網的用戶群體具有多樣性。5）互聯網上的信息只有一小部分是真正有用的或相關的，通常來說互聯網上99％的信息對99％的用戶是無用的。正因為這樣，Web數據挖掘應運而生。Web挖掘就是要發(fā)現網頁的讀取模式、互聯網結構和互聯網內容描述所存在的規(guī)律和動態(tài)特點，從網頁的海洋中（據統(tǒng)計，2000年初，網頁數已達8億頁，并估計每4個月要翻一番。）發(fā)現高質量的信息，有效地進行知識發(fā)現。第71頁/共88頁17一月202373Ch14.3（4）復雜數據類型的挖掘Web挖掘是將傳統(tǒng)的數據挖掘技術和Web結合起來，進行Web知識的提取，從Web文檔和Web活動中抽取感興趣的潛在的有用模式和隱藏的信息。一般地，Web挖掘可以分為三類：Web內容挖掘，Web結構挖掘和Web使用挖掘。第72頁/共88頁17一月202374Ch14.3（4）復雜數據類型的挖掘（1）Web內容挖掘Web內容挖掘是對Web上大量文檔集合的內容進行總結、分類、聚類、關聯分析以及利用Web文檔進行趨勢預測等，其中最重要的是，文本的特征表示、分類和聚類。文本的特征表示——Web文檔是半結構化或非結構化的，這樣的特殊性使得現存的數據挖掘技術無法直接加以應用。我們需要對Web文本進行預處理，抽取代表其特征的元數據。這些特征可以用結構化形式保存，作為文檔的中間表示形式。W3C近來制定的XML、RDF等規(guī)范提供了對Web文檔進行描述的語言和框架。矢量空間模型（VSM）是近年來應用較多且效果較好的方法之一。在該模型中，文檔空間被看作是由一組正交詞條矢量所形成的矢量空間，每個文檔d表示為其中的一個范式特征矢量V(d)=(k1,w1(d);…;ki,wi(d);…;kn,wn(d))，其中ki為詞條項，wi(d)為ki在d中的權值，可以將d中出現的所有單詞作為ki，也可以要求ki是d中出現的所有短語，從而提高內容特征表示的準確性。wi(d)一般被定義為ki在d中出現頻率tfi(d)的函數，即wi(d)=ψ(tfi(d))，常用的ψ函數有：布爾函數、平方根函數、對數函數和TF1DF函數。第73頁/共88頁17一月202375Ch14.3（4）復雜數據類型的挖掘Web文本分類——文本分類是一種典型的有知道的機器學習問題，一般分為訓練和分類兩個階段。具體過程為：訓練階段——1）定義類別集合Z={z1,…,zi,…,zm}，這些類別可以是層次式的，頁可以是并列式的；2）給出訓練文檔集合F={f1,…,fj,…fn}，每個訓練文檔fj被標上所屬的類別標識zi；3）統(tǒng)計文本集合F中所有文檔的特征矢量V(fj)，確定代表Z中每個類別的特征矢量V(zi)。分類階段——1）對測試文檔集合TD={d1,…,dk,…,dr}中的每個待分類文檔dk，計算其特征向量V(dk)與每個V(zi)之間的相似度Sim(dk,zi)；2）選取相似度最大的一個類別作為dk的類別。在計算Sim(dk,zi)時，有多種方法可供選擇。最簡單的方式是僅考慮兩個特征矢量中所包含的詞條的重疊程度，即Sim(dk,zi)=(∩n(dk,zi))/(∪n(dk,zi))，其中，∩n(dk,zi)是V(dk)和V(zi)具有的相同詞條數目，∪n(dk,zi)是V(dk)和V(zi)具有的所有詞條數目；最常用的方法是考慮兩個特征矢量之間的夾角余弦，即Sim(dk,zi)=(V(dk).V(zi))/(|V(dk)|*|V(zi)|)。第74頁/共88頁17一月202376Ch14.3（4）復雜數據類型的挖掘Web文本聚類——Web文本聚類是一種典型的無指導的機器學習問題。目前的文本聚類方法大致可以分為層次凝聚法和平面劃分法兩種類型。對于給定的文檔集合D={d1,…,di,…,dn}，層次凝聚法的具體過程如下。1）將D中的每個文檔di看作是一個具有單個成員的簇zi={di}，這些簇構成了D的一個聚類Z={z1,…,zi,…zn}；2）計算Z中每對簇(zi,zj)之間的相似度Sim(zi,zj)；3）選取具有最大相似度的簇對，并將它們合并為一個新的簇，zk=zi∪zj，從而構成了D的一個新的聚類，Z={z1,…,zn-1}；4）重復上述步驟，直到Z中剩下一個簇為止。該過程構造出一顆生成樹，其中包含了簇的層次信息，以及所有簇內和簇間的相似度。第75頁/共88頁17一月202377Ch14.3（4）復雜數據類型的挖掘平面劃分法與層次凝聚法的區(qū)別在于，它將文檔集合水平地分割為若干個簇，而不是生成層次化的嵌套簇。對于給定的文檔集合D={d1,…,di,…,dn}，平面劃分法的具體過程如下：1）確定要生成的簇的數目k；2）按照某種原則生成k個聚類中心作為聚類的核Y={y1,…,yi,…,yk}；3）對D中的每個文檔di，依次計算它與每個核yi的相似度Sim=(di,yj)；4）選取具有最大相似度的核，將其歸入以yj為聚類中心的簇zj，從而得到D的一個聚類Z＝{z1,…,zk}；5）重復步驟2，3，4若干次，以得到較為穩(wěn)定的聚類結果。

第76頁/共88頁17一月202378Ch14.3（4）復雜數據類型的挖掘（2）Web結構挖掘整個Web空間里，有許多有用知識包含在Web頁面超鏈結構與Web頁面內部結構之中。Web結構挖掘主要是通過對Web站點的結果進行分析和歸納，發(fā)現頁面的結果和Web間的結果，在此基礎上找出權威頁面，利用發(fā)現的這種知識可以改進搜索引擎。第77頁/共88頁17一月202379Ch14.3（4）復雜數據類型的挖掘下面介紹兩種Web結構挖掘的方法。1）rank方法rank方法的基本思想是：一個頁面被多次引用，則這個頁面很可能是重要的；一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面很可能是重要的。一個頁面的重要性被均分并被傳遞到它所引用的頁面。頁面重要性度量的定義：u是一個Web頁面，Fu是u引用的頁面集合，Bu是引用u的頁面集合，Nu=|Fu|，則u的重要性為R(u)=∑v∈Bu(R(v)/Nu)。對于一個查詢q，搜索引擎首先利用相似度函數找到k個頁面，然后利用公式ranking-score(q,d)=w1*Sim(q,d)+w2*R(d)計算每個頁面的重要性，然后進行排名。這里，w1,w2∈[0,1]，w1+w2=1，Sim(q,d)是相似度函數，Sim(q,d),R(d)∈[0,1]。第78頁/共88頁17一月202380Ch14.3（4）復雜數據類型的挖掘2）Hub/Authority方法Hub/Authority方法的基本思想是：Hub是指一個或多個Web頁面，它提供了指向權威頁面的連接集合。Hub頁面起到了隱含說明某話題權威頁面的作用。通常，好的Hub是指許多好的權威頁面，好的權威（Authority）是指由許多好的Hub所指向的頁面。這種Hub與Authority之間的