數(shù)據(jù)倉庫與數(shù)據(jù)挖掘課件

Ch14.

1.概述02十月20231數(shù)據(jù)庫教程（沈--06.8）(1)數(shù)據(jù)管理的層次結(jié)構(gòu)

(2)數(shù)據(jù)倉庫的產(chǎn)生(3)從數(shù)據(jù)倉庫到數(shù)據(jù)挖掘Ch14.1.概述(1)數(shù)據(jù)管理的層次結(jié)構(gòu)下圖不同管理層次的三類信息系統(tǒng)：02十月20232數(shù)據(jù)庫教程（沈--06.8）Ch14.

1.概述02十月20233數(shù)據(jù)庫教程（沈--06.8）事務(wù)處理系統(tǒng)（TPS，Transaction

Processing

System）——對于基層管理人員來說，所要完成的數(shù)據(jù)管理任務(wù)基本上是針對某種業(yè)務(wù)應(yīng)用來做單項(xiàng)性管理。對這個層次的信息系統(tǒng)來說，一般是掌握基層業(yè)務(wù)部門的操作信息、運(yùn)行狀態(tài)、完成日常管理。本書介紹的關(guān)系數(shù)據(jù)庫技術(shù)，建立相應(yīng)的聯(lián)機(jī)事務(wù)處理系統(tǒng)（OLTP，OnlineTransactionProcessing），顯然能很好地完成這項(xiàng)任務(wù)。管理信息系統(tǒng)（MIS，Management

Information

System）——對于中層管理人員來說，所要完成的數(shù)據(jù)管理任務(wù)是起承上啟下的作用，一方面要綜合有關(guān)基層部門的有關(guān)信息，另一方面要向高層領(lǐng)導(dǎo)提供相關(guān)決策信息，并落實(shí)高層領(lǐng)導(dǎo)提出的全局性總目標(biāo)。本書介紹的關(guān)系數(shù)據(jù)庫技術(shù)，基于OLTP建立的信息系統(tǒng)，信息內(nèi)容適合綜合化處理，也可以較好地完成任務(wù)。決策支持系統(tǒng)（DSS，Decision

SupportSystem）——對于高層領(lǐng)導(dǎo)人員來說，主要的任務(wù)是制定企事業(yè)單位的總目標(biāo)并提出落實(shí)總目標(biāo)的方針與預(yù)算。在這一層次，數(shù)據(jù)管理的任務(wù)重要應(yīng)是對數(shù)據(jù)的決策分析。目前，數(shù)據(jù)都是DBMS統(tǒng)一管理，企事業(yè)單位都相應(yīng)建立起了操作型數(shù)據(jù)庫。以下我們看到，在這種操作型數(shù)據(jù)庫基礎(chǔ)上，想要構(gòu)建DSS，有很大困難，是不適合的。在這種背景下，數(shù)據(jù)倉庫（Data

Warehouse）技術(shù)應(yīng)運(yùn)而生。Ch14.

1.概述02十月20234數(shù)據(jù)庫教程（沈--06.8）(2)數(shù)據(jù)倉庫的產(chǎn)生數(shù)據(jù)管理對于高層管理人員，主要是進(jìn)行決策分析。從決策分析的要求看，傳統(tǒng)的操作型數(shù)據(jù)庫，所建立OLTP系統(tǒng)是很不合適的。為什么呢？可從決策分析所需要數(shù)據(jù)有以下幾個方面的特征來看：面向主題：決策分析都是圍繞一些主題而展開的，如銷售企業(yè)，圍繞顧客、供應(yīng)商、產(chǎn)品、銷售組織等主題，關(guān)注決策者關(guān)注的數(shù)據(jù)建模與分析，而不把注意力放在機(jī)構(gòu)的日常操作和事務(wù)處理。對于決策分析的主題來說，所需的數(shù)據(jù)多為總結(jié)性數(shù)據(jù)，而不一定需要操作型數(shù)據(jù)庫大量存放的細(xì)節(jié)數(shù)據(jù)。這也正解釋高層管理人員對現(xiàn)行數(shù)據(jù)管理的一種批評——“數(shù)據(jù)豐富，信息貧乏”。集成的：決策分析所需數(shù)據(jù)將是多種異構(gòu)數(shù)據(jù)源，不但需要本單位的數(shù)據(jù)，也需要有關(guān)的其他單位的數(shù)據(jù)。這些數(shù)據(jù)有些來自各類數(shù)據(jù)庫，有些來自文件，也有些來自

Internet網(wǎng)獲取的HTML文件。所需的數(shù)據(jù)是多種異構(gòu)數(shù)據(jù)源的集成。時變的：決策分析不但需要反映當(dāng)前情況的數(shù)據(jù)（如2～3個月），還需要?dú)v史數(shù)據(jù)（通常是5～10年），以便分析變化趨勢，進(jìn)行決策。由于數(shù)據(jù)須在時間維上展開，數(shù)據(jù)量將是非常巨大的。非易失的：決策分析所需的數(shù)據(jù)不一定需要及時更新，通常只需兩種訪問方式：數(shù)據(jù)的初始化裝入和以讀為主的訪問。在這樣的背景下，數(shù)據(jù)倉庫技術(shù)應(yīng)運(yùn)而生。Ch14.

1.概述02十月20235數(shù)據(jù)庫教程（沈--06.8）20世紀(jì)80年代中期，提出了數(shù)據(jù)倉庫的概念。到底什么是數(shù)據(jù)倉庫？可以有多種方式定義，很難提出一個嚴(yán)格的定義。現(xiàn)在通常采用被稱為數(shù)據(jù)倉庫之父的W.H.Inmon的說法作為定義：“數(shù)據(jù)倉庫是一個面向主題的、集成的、時變的、非易失的數(shù)據(jù)集合，支持管理部門的決策過程”。(3)從數(shù)據(jù)倉庫到數(shù)據(jù)挖掘?qū)τ跇?gòu)建的數(shù)據(jù)倉庫，如何使用？數(shù)據(jù)倉庫系統(tǒng)的用戶界面包括的若干決策工具和接口，其中一個重要的技術(shù)就是數(shù)據(jù)挖掘（Data

Mining，簡稱維DM，也稱為知識發(fā)現(xiàn)KDD，Knowledge

Discovery

in

DB

and

DW）。Ch14.

2.

數(shù)據(jù)倉庫02十月20236數(shù)據(jù)庫教程（沈--06.8）概述數(shù)據(jù)倉庫的建立——數(shù)據(jù)模型、數(shù)據(jù)模式

(3)OLAP技術(shù)Ch14.

2.

數(shù)據(jù)倉庫(1)概述1)數(shù)據(jù)倉庫的定義現(xiàn)對數(shù)據(jù)倉庫定義中的4個特性作進(jìn)一步解釋:主題性：傳統(tǒng)的操作型數(shù)據(jù)庫系統(tǒng)都是圍繞某一企事業(yè)單位的應(yīng)用來組織數(shù)據(jù)的，而數(shù)據(jù)倉庫系統(tǒng)則是用于決策分析，要面向主題來組織數(shù)據(jù)。下圖表示數(shù)據(jù)組織圍繞保險公司面向主題的一個例子。02十月20237數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫集成性：面向應(yīng)用的操作型數(shù)據(jù)庫系統(tǒng)，對不同應(yīng)用有不同的表示方法，而當(dāng)數(shù)據(jù)進(jìn)入數(shù)據(jù)倉庫時，必須消除各種應(yīng)用問題的許多不一致性。如圖示例說明數(shù)據(jù)倉庫的集成問題。02十月20238數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫時變性：操作型數(shù)據(jù)庫一般的數(shù)據(jù)時間期限是60～90天，而數(shù)據(jù)倉庫通常要存放5～10年的數(shù)據(jù)；操作型數(shù)據(jù)庫含有“當(dāng)前值”的數(shù)據(jù)，其準(zhǔn)確性在訪問時是有效的，但此當(dāng)前值數(shù)據(jù)能被更新。而數(shù)據(jù)倉庫中的數(shù)據(jù)僅僅是一系列某一時刻生成的復(fù)雜的快照；操作型數(shù)據(jù)庫的基本結(jié)構(gòu)中可能包含也可能不包含時間元素，如年、月、日等。而數(shù)據(jù)倉庫中的基本數(shù)據(jù)結(jié)構(gòu)總是包含某種時間元素。圖示例說明數(shù)據(jù)隨時間變化的問題。02十月20239數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫非易失性：對于傳統(tǒng)的操作型數(shù)據(jù)庫通常是一次訪問或處理一到若干個記錄，可隨時對數(shù)據(jù)進(jìn)行更新；但數(shù)據(jù)倉庫中的數(shù)據(jù)具有非常不同的特性：其數(shù)據(jù)倉庫不進(jìn)行一般意義下的數(shù)據(jù)更新。圖表示數(shù)據(jù)的非易失性問題。02十月202310數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫2）DBS與DWSDBS是我們前面詳細(xì)講過的一種數(shù)據(jù)管理系統(tǒng)，第一部分就概述了系統(tǒng)組成結(jié)構(gòu)的三大部分：數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng)和用戶界面。聯(lián)機(jī)操作型數(shù)據(jù)庫系統(tǒng)主要任務(wù)是執(zhí)行聯(lián)機(jī)事務(wù)和查詢處理，所以，這種系統(tǒng)也稱為聯(lián)機(jī)事務(wù)處理系統(tǒng)（OLTP，Online

TransactionProcessing）。數(shù)據(jù)倉庫是在數(shù)據(jù)庫基礎(chǔ)上產(chǎn)生的一種數(shù)據(jù)集合，用于數(shù)據(jù)管理中的決策分析。對數(shù)據(jù)倉庫而言，自然也有數(shù)據(jù)庫系統(tǒng)概念，是管理、使用數(shù)據(jù)倉庫的一種數(shù)據(jù)管理系統(tǒng)。它的系統(tǒng)組成體系機(jī)構(gòu)可用圖表示。02十月202311數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫(2)數(shù)據(jù)倉庫的建立——數(shù)據(jù)模型、數(shù)據(jù)模式1）數(shù)據(jù)倉庫模型正像建立數(shù)據(jù)庫的重點(diǎn)是研究數(shù)據(jù)模型、數(shù)據(jù)模式一樣，對于數(shù)據(jù)倉庫來說，有必要深入理解兩個概念——數(shù)據(jù)模型與數(shù)據(jù)模式。數(shù)據(jù)倉庫一般來說是基于多維數(shù)據(jù)模型（Multi-Dimension

Data

Model）。該模型將數(shù)據(jù)看作數(shù)據(jù)立方體（Data

Cube）形式?，F(xiàn)舉例說明數(shù)據(jù)立方體的概念。下圖是銷售數(shù)據(jù)的數(shù)據(jù)立方體示例。02十月202312數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫02十月202313數(shù)據(jù)庫教程（沈--06.8）所有的銷售數(shù)據(jù)組織成立方體形式，以多維形式對數(shù)據(jù)建模和觀察，它由維和事實(shí)定義。維——是關(guān)于一個企事業(yè)想要記錄的數(shù)據(jù)方面，如示例中列出的商店－時

間－商品就是設(shè)計(jì)的3個維，每一個維都有一個維表與之相連，進(jìn)一步描述這個維。例如，商店的維表可以包含屬性：商店名、地址、電話、經(jīng)理等。事實(shí)——多維數(shù)據(jù)模型都是圍繞主題來組織的，該主題就用事實(shí)表表示。

事實(shí)是用數(shù)值度量的。例如，上面例子圍繞銷售主題建立數(shù)據(jù)倉庫的事實(shí)，事實(shí)表包括相關(guān)維表的關(guān)鍵字、銷售量、銷售金額等。立方體比較直觀，便于圖示。但在數(shù)據(jù)倉庫中，數(shù)據(jù)立方體的多維，當(dāng)然不是局限于3維，可以是n維的。Ch14.

2.

數(shù)據(jù)倉庫2）數(shù)據(jù)模式采用數(shù)據(jù)模型來描述某一具體企事業(yè)單位的數(shù)據(jù)倉庫數(shù)據(jù)，就引入了另一個概念——數(shù)據(jù)模式。多維數(shù)據(jù)模型，具體的維表與事實(shí)表如何組織描述，可以有多種不同形式。常見的形式有：星型、雪花型以及事實(shí)星座型。現(xiàn)仍以銷售數(shù)據(jù)倉庫為例。圖14-8，14-9，14-10分別示例說明三種數(shù)據(jù)模式。圖14-8

銷售數(shù)據(jù)星型模式：02十月202314數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫圖14-9

銷售數(shù)據(jù)雪花模式：02十月202315數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫圖14-10

銷售與貨運(yùn)事實(shí)星座模式：02十月202316數(shù)據(jù)庫教程（沈--06.8）Ch14.

2.

數(shù)據(jù)倉庫02十月202317數(shù)據(jù)庫教程（沈--06.8）在上述數(shù)據(jù)建模中，對數(shù)據(jù)立方體再介紹以下概念。度量（Measure）的分類與計(jì)算——數(shù)據(jù)立方體的度量是一個數(shù)值函數(shù)，指的是對數(shù)據(jù)立方體的每一個點(diǎn)所求的值。數(shù)據(jù)立方體空間的多維點(diǎn)，可由維－值對來定義，例如某一空間點(diǎn)上，時間＝“1季度”，商品＝“PC機(jī)”，商店＝“No.1”，通過對給定點(diǎn)的各維－值對來聚集數(shù)據(jù)，即計(jì)算該點(diǎn)的度量值。度量可以根據(jù)所用的聚集函數(shù)而分成三類：①分配型：假設(shè)數(shù)據(jù)劃分為n個集合，函數(shù)在每一部分上計(jì)算得到一個聚集值。如果將函數(shù)用于n個聚集值得到的結(jié)果，與將函數(shù)用于所有數(shù)據(jù)得到的數(shù)據(jù)一樣，則該函數(shù)就是一種分配型的計(jì)算。例如：計(jì)算Count（）可以這樣計(jì)算，先將數(shù)據(jù)立方體分割為若干個子立方體的集合，對每個子立方體計(jì)算Count（），然后求和。這樣，Count（）就是分配型的聚集函數(shù)。同理，Sum（），Min（），Max（）也是分配型聚集函數(shù)。②代數(shù)型：如果能夠由一個具有M個參數(shù)的代數(shù)函數(shù)計(jì)算（其中M是一個有界整數(shù)），而每個參數(shù)都可由一個分配型聚集函數(shù)求得，則稱這種計(jì)算是代數(shù)型的。例如，Avg（）可由Sum（）/Count（）計(jì)算，其中Sum（）與Count（）都是分配型聚集函數(shù)。類似地，min_N（），max_N（）等也都是代數(shù)型聚集函數(shù)。③整體型：整體型聚集函數(shù)既不滿足分配型，也不滿足代數(shù)型，例如取中位數(shù)（一組數(shù)的位數(shù)數(shù)是指數(shù)據(jù)按大小排序后，取居中的一個數(shù)，若有偶數(shù)個數(shù)，則取居中兩數(shù)的平均值）就是一個整體型聚集函數(shù)。概念分層——數(shù)據(jù)模式中有一個概念分層的問題，概念分層是一個映射序列，對于數(shù)據(jù)模式來說，隱含有概念分層的問題，例如，商品維表中的小類

大類，商店維表中的市名

省名，如期維表中的日

月

季度

年。數(shù)據(jù)模式中的概念分層，為數(shù)據(jù)管理的分析綜合提供了方便。Ch14.

2.

數(shù)據(jù)倉庫02十月202318數(shù)據(jù)庫教程（沈--06.8）3)構(gòu)建數(shù)據(jù)倉庫的步驟與數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)庫設(shè)計(jì)過程相類似，數(shù)據(jù)倉庫的構(gòu)建要按一定的步驟進(jìn)行，構(gòu)建數(shù)據(jù)倉庫一般有兩個主要步驟：①數(shù)據(jù)準(zhǔn)備階段；②數(shù)據(jù)倉庫模式設(shè)計(jì)階段。①數(shù)據(jù)準(zhǔn)備階段:主要是ETL（抽取、轉(zhuǎn)換、裝載），數(shù)據(jù)抽取是指從異構(gòu)多數(shù)據(jù)源中圍繞主題選取相關(guān)的數(shù)據(jù)，并要對這些數(shù)據(jù)進(jìn)行清理，消除噪聲和不一致數(shù)據(jù)，并完成集成過程中的轉(zhuǎn)換，使數(shù)據(jù)具有集成性，表示方式一致，并轉(zhuǎn)換為適合聚集操作的有關(guān)形式。經(jīng)過數(shù)據(jù)轉(zhuǎn)換階段的工作，才能將數(shù)據(jù)源裝載到數(shù)據(jù)倉庫中。②數(shù)據(jù)倉庫模式設(shè)計(jì)階段:面對實(shí)際應(yīng)用問題，如何面向主題進(jìn)行數(shù)據(jù)倉庫設(shè)計(jì)

(采用多維數(shù)據(jù)模型設(shè)計(jì)星型、雪花等數(shù)據(jù)模式）是一個用戶、數(shù)據(jù)倉庫技術(shù)人員共同合作要完成的一個重要工作，有較大的難度。Ch14.

2.

數(shù)據(jù)倉庫02十月202319數(shù)據(jù)庫教程（沈--06.8）設(shè)計(jì)方法通常有三種：自頂向下（Top-Down），自底向上（Bottom-Up），混合方法。自頂向下方法——由總體規(guī)劃與設(shè)計(jì)開始，當(dāng)對必須解決的業(yè)務(wù)應(yīng)用問題比較清楚，已掌握成熟的技術(shù)，可采用這種方法。首先，建立企業(yè)級的數(shù)據(jù)倉

庫：對已所要抽取的操作型數(shù)據(jù)庫細(xì)工和其它數(shù)據(jù)，使用集中模式，一次

數(shù)據(jù)重構(gòu)，將冗余與不一致盡量減少，構(gòu)建全局性的企業(yè)數(shù)據(jù)倉庫；然后，圍繞部門主題，建立數(shù)據(jù)集市（Data

Mart）。自底向上方法——從實(shí)驗(yàn)與原型開始，先建部門數(shù)據(jù)集市，然后擴(kuò)大到企業(yè)數(shù)據(jù)倉庫。首先，局限在一定的主題范圍，本部門自治設(shè)計(jì)，建立部門局部的數(shù)據(jù)集市；然后，在若干個數(shù)據(jù)集市建成后，去除冗余與不一致性，將創(chuàng)建企業(yè)數(shù)據(jù)倉庫作為首期目標(biāo)?；旌戏椒ā梢哉J(rèn)為是上面兩種方法的混合，既能利用自頂向下方法有計(jì)劃的戰(zhàn)略性特點(diǎn)，由能保持自底向上方法快速實(shí)現(xiàn)與較快應(yīng)用的優(yōu)點(diǎn)。Ch14.

2.

數(shù)據(jù)倉庫02十月202320數(shù)據(jù)庫教程（沈--06.8）(3)OLAP技術(shù)概述多維分析技術(shù)OLAP操作語言概述OLAP的由來——傳統(tǒng)的關(guān)系數(shù)據(jù)庫應(yīng)用系統(tǒng)，是一種面向操作型數(shù)據(jù)的環(huán)境，處理對象是確定的業(yè)務(wù)數(shù)據(jù)，目的是解決特定業(yè)務(wù)處理問題。例如，典型計(jì)費(fèi)系統(tǒng)、航班售票系統(tǒng)等。這種系統(tǒng)的數(shù)據(jù)時效性強(qiáng)，需及時更新數(shù)據(jù)，而大量的歷史數(shù)據(jù)不得不保存到脫機(jī)的存儲介質(zhì)中去。那么，如何利用這些海量數(shù)據(jù)，完成面向決策分析的任務(wù)，傳統(tǒng)的OLTP就難以勝任。這樣，

OLAP就應(yīng)運(yùn)而生，正如數(shù)據(jù)倉庫之父W.H.Inmon所講的，“現(xiàn)在該是把哪些歷史數(shù)據(jù)搬出來的時候了?！甭?lián)機(jī)分析處理（OLAP）的概念，最早是由關(guān)系數(shù)據(jù)庫系統(tǒng)奠基人E.F.Codd在1993年提出的。當(dāng)時，Codd認(rèn)為OLTP已不能滿足終端用戶對數(shù)據(jù)庫查詢分析的需求，SQL的簡單查詢不能滿足用戶的分析需求。終端用戶的決策分析，需要對大量數(shù)據(jù)經(jīng)過計(jì)算而得到?jīng)Q策，Codd提出了多維數(shù)據(jù)模型的多維分析的概念，即出現(xiàn)了OLAP技術(shù)的概念。Ch14.

2.

數(shù)據(jù)倉庫02十月202321數(shù)據(jù)庫教程（沈--06.8）OLAP的定義——OLAP是一種基于數(shù)據(jù)集合（數(shù)據(jù)倉庫或數(shù)據(jù)庫）的面向分析處理的技術(shù)。采用OLAP技術(shù)，用戶能靈活操縱某企事業(yè)單位的數(shù)據(jù)，以多維數(shù)據(jù)模型的形式，從多方面、多角度來觀察數(shù)據(jù)的狀態(tài)，從而為決策分析提供有力支持。OLAP、OLTP的比較——OLTP基于關(guān)系操作型數(shù)據(jù)庫，OLAP基于數(shù)據(jù)倉庫，重點(diǎn)在于數(shù)據(jù)分析與決策，是對共享多維數(shù)據(jù)的決策分析。OLTP與OLAP的比較，可用表14-1以展示。Ch14.

2.

數(shù)據(jù)倉庫02十月202322數(shù)據(jù)庫教程（沈--06.8）表14-1

OLTP與OLAP的比較OLTPOLAP用戶操作人員，底層管理人員決策和高層管理人員功能日常操作處理分析決策設(shè)計(jì)原則面向應(yīng)用面向主題數(shù)據(jù)當(dāng)前的，細(xì)節(jié)的，二維的，分立的歷史的，聚集的，多維的，集成的存取讀/寫數(shù)十條記錄讀上百萬條記錄工作單位短的簡單事務(wù)長的復(fù)雜事務(wù)用戶數(shù)成千上萬個上百個數(shù)據(jù)規(guī)模100MB～GB100GB～TBCh14.

2.

數(shù)據(jù)倉庫02十月202323數(shù)據(jù)庫教程（沈--06.8）OLAP系統(tǒng)的特征——①快速性：OLAP系統(tǒng)采用專門的存儲形式，經(jīng)過大量的預(yù)計(jì)算，雖然操作涉及復(fù)雜的事務(wù)，但分析過程仍具有快速性特點(diǎn)；②可分析性：系統(tǒng)處理的問題與有關(guān)的邏輯和統(tǒng)計(jì)分析，不是一般的簡單計(jì)算；③共享性：潛在地共享有關(guān)數(shù)據(jù)；④多維性：這是OLAP的關(guān)鍵特性，可從不同難度進(jìn)行計(jì)算；⑤信息性：這是OLAP的目的所在，完成數(shù)據(jù)的信息解釋。Ch14.

2.

數(shù)據(jù)倉庫02十月202324數(shù)據(jù)庫教程（沈--06.8）2）多維分析技術(shù)OLAP多維分析技術(shù)建立在多維數(shù)據(jù)模型的基礎(chǔ)上，涉及的重要概念列舉如下：維——是人們觀察數(shù)據(jù)的特定角度，是考慮問題時的一類屬性，屬性集合構(gòu)成一個維（如：時間維、地理維等）。維的層次——人們觀察數(shù)據(jù)的某個特定角度（即某個維）還可以表示細(xì)節(jié)程度不同的各個描述方面（如：時間維——分別是日期、月份、季度、年）。維的成員——維的一個取值，是數(shù)據(jù)項(xiàng)在某維中位置的描述（如：“某年某月某日”是在時間維上某一位置的描述）。度量——用戶瀏覽多維數(shù)據(jù)集時查看的數(shù)值，是用來評測分析的一種指標(biāo)值。如：社會保險系統(tǒng)中的基金收繳金額、養(yǎng)老金撥付金額，就是一種度量值。立方體——多維數(shù)據(jù)集合，是分析的一個主題，由多個維和若干度量值構(gòu)建并匯總而成的多維數(shù)據(jù)結(jié)構(gòu)集合，是OLAP的分析對象。Ch14.

2.

數(shù)據(jù)倉庫02十月202325數(shù)據(jù)庫教程（沈--06.8）OLAP系統(tǒng)基本操作：切片和切塊（Slice，Dice）——在多維數(shù)據(jù)立方體中，按二維進(jìn)行切片，按三維進(jìn)行切塊，可得到所需的某部分?jǐn)?shù)據(jù)。如圖14-11就表示社會保險數(shù)據(jù)在地理、時間、單位分類進(jìn)行切塊和切片的數(shù)據(jù)。圖14-11

社會保險數(shù)據(jù)立方體的切片、切塊示例：Ch14.

2.

數(shù)據(jù)倉庫02十月202326數(shù)據(jù)庫教程（沈--06.8）鉆?。―rill）——鉆取包含向下鉆取（Drill-down）和向上鉆?。―rill-up）/上卷（Roll-up）操作，在操作中鉆取的深度與維所劃分的層次是相對的。圖14-12表示社會保險數(shù)據(jù)立方體按單位維向下/向上鉆取的數(shù)據(jù)示例。Ch14.

2.

數(shù)據(jù)倉庫02十月202327數(shù)據(jù)庫教程（沈--06.8）旋轉(zhuǎn)（Rotate）/轉(zhuǎn)軸（Pivot）——通過旋轉(zhuǎn)（也稱為轉(zhuǎn)軸），可以得到不同視角的數(shù)據(jù)。圖14-13表示社會保險數(shù)據(jù)立方體的旋轉(zhuǎn)操作示例。Ch14.

2.

數(shù)據(jù)倉庫02十月202328數(shù)據(jù)庫教程（沈--06.8）3)OLAP操作語言傳統(tǒng)關(guān)系數(shù)據(jù)庫系統(tǒng)的操作語言是SQL，那么對多維數(shù)據(jù)立方體的OLAP操作語言是什么呢？這方面的標(biāo)準(zhǔn)化還有待進(jìn)一步工作，這里以微軟提供的

MDX語言為例進(jìn)行介紹。MDX語言概述:MDX（Multidimensional

Expression）是一種支持多維數(shù)據(jù)立方體定義和操作的語言，由微軟公司提供。MDX在語法的很多方面與SQL相似，但不能算是SQL語言的擴(kuò)展。MDX提供數(shù)據(jù)結(jié)構(gòu)定義的DQL語法，用于創(chuàng)建（和刪除）多維數(shù)據(jù)集、維度、度量值以及它們的坐標(biāo)對象的MDX命令。MDX提供多維立方體操作的查詢語句，包含了與SQL類似的Select、From、Where子句，MDX還提供了函數(shù)等，增強(qiáng)了操作能力。基本的MDX查詢是：Select[<軸維度1>[,<軸維度2>…]]From[<多維數(shù)據(jù)集>][Where[<切片1>[,<切片2>…]]]SQL語言是從表返回一個仍是表的二維數(shù)據(jù)集，而MDX是從多維數(shù)據(jù)集返回多維數(shù)據(jù)子集。Ch14.

2.

數(shù)據(jù)倉庫02十月202329數(shù)據(jù)庫教程（沈--06.8）現(xiàn)以社會保險系統(tǒng)中的應(yīng)用為例加以說明。Select{[地理].[西安].[市本級],[地理].[西安].[雁塔區(qū)]}ONCOLUMNS，{[時間].[2001年],[時間].[2002年]}ON

ROWSFrom基金收繳Where([單位].[事業(yè)],[收繳類型].[正常繳納])即可得到如下結(jié)果。Ch14.02十月202330數(shù)據(jù)庫教程（沈--06.8）3.數(shù)據(jù)挖掘概述數(shù)據(jù)挖掘的過程數(shù)據(jù)挖掘的基本方法

(4)復(fù)雜數(shù)據(jù)類型的挖掘Ch14.3.

(1)概述02十月202331數(shù)據(jù)庫教程（沈--06.8）(1)概述:1)數(shù)據(jù)挖掘技術(shù)的產(chǎn)生;2)數(shù)據(jù)挖掘的定義.1)數(shù)據(jù)挖掘技術(shù)的產(chǎn)生:從數(shù)據(jù)庫技術(shù)的發(fā)展過程看，20世紀(jì)80年代以來，數(shù)據(jù)庫系統(tǒng)在各行各業(yè)廣泛應(yīng)用，全球的信息量每隔20個月就要增加一倍。一個中等規(guī)模的企業(yè)每天要產(chǎn)生100MB以上的業(yè)務(wù)數(shù)據(jù)，據(jù)統(tǒng)計(jì)，1993年全球的計(jì)算機(jī)數(shù)據(jù)存儲容量約為2000TB，到2000年增加到300萬TB。但是，據(jù)估計(jì)，目前一個大型企事業(yè)單位的數(shù)據(jù)，大約只有7％得到較好地應(yīng)用，對于數(shù)據(jù)管理來說，陷入了一個尷尬境地――“數(shù)據(jù)豐富，信息（知識）貧乏”。數(shù)據(jù)管理用于決策分析的技術(shù)應(yīng)運(yùn)而生：一方面數(shù)據(jù)倉庫技術(shù)的提出與發(fā)展，另一方面數(shù)據(jù)挖掘技術(shù)的產(chǎn)生。先看一個例子：啤酒與尿布的故事――美國加州某超市連鎖店通過對存儲的銷售數(shù)據(jù)采用數(shù)據(jù)挖掘技術(shù)分析發(fā)現(xiàn)：下班前后或周末購買嬰兒尿布的顧客較多為男性，往往同時購買啤酒，兩類互不相干的商品有一定的關(guān)聯(lián)。于是，連鎖店經(jīng)理當(dāng)機(jī)立斷，重新布置貨架，將男士們需要的日常生活用品就近布置，取得了有關(guān)商品銷量大增的驕人業(yè)績。80年代以來，人們逐漸關(guān)注這方面的研究，其它數(shù)據(jù)挖掘的例子也就層出不窮.正像數(shù)據(jù)庫技術(shù)的發(fā)展一樣，開始時是一個一個行業(yè)的建立使用，逐步鋪開。數(shù)據(jù)挖掘技術(shù)，目前雖沒有數(shù)據(jù)庫技術(shù)這樣家喻戶曉，但經(jīng)過多年的發(fā)展，應(yīng)用領(lǐng)域也已是一個熱門領(lǐng)域，應(yīng)用面已相當(dāng)廣泛。Ch14.3.

(1)概述02十月202332數(shù)據(jù)庫教程（沈--06.8）2)數(shù)據(jù)挖掘的定義較為廣泛接受的數(shù)據(jù)挖掘定義是：提取隱含于數(shù)據(jù)集合（數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它數(shù)據(jù)集合）中未知的、有用的、不一般的（即不象

OLAP中那樣計(jì)算總和、平均值子類的普通信息）信息或知識。數(shù)據(jù)挖掘，也有另外一種說法：數(shù)據(jù)庫中的知識發(fā)現(xiàn)KDD（Knowledge

Discovery

in

Database）或知識提?。↘nowledgeExtraction），數(shù)據(jù)/模式分析（Data/PatternAnalysis），也有人認(rèn)為數(shù)據(jù)挖掘DM是KDD的一個步驟，特別在討論實(shí)現(xiàn)過程時，往往認(rèn)為KDD是較廣泛的過程，而DM是其中的一個步驟。從數(shù)據(jù)庫技術(shù)看，在邏輯上從大量數(shù)據(jù)中提取規(guī)則，數(shù)據(jù)挖掘采用的是歸納推理的方法。而根據(jù)大量數(shù)據(jù)，采用歸納方法，推斷出一般化的規(guī)則、規(guī)律，也就是形成信息或知識。從更廣泛的角度來看，數(shù)據(jù)挖掘是一門跨學(xué)科的技術(shù)，綜合采用了統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫技術(shù)、機(jī)器學(xué)習(xí)、模式識別、人工智能、可視化技術(shù)，很難嚴(yán)格區(qū)分?jǐn)?shù)據(jù)挖掘與這些學(xué)科之間的界限。Ch14.3.

(2)數(shù)據(jù)挖掘的過程(2)數(shù)據(jù)挖掘的過程:1)知識發(fā)現(xiàn)KDD的全過程2)數(shù)據(jù)挖掘（Data

Mining，DM）過程1)知識發(fā)現(xiàn)KDD的全過程02十月202333數(shù)據(jù)庫教程（沈--06.8）Ch14.3.

(2)數(shù)據(jù)挖掘的過程2)數(shù)據(jù)挖掘（Data

Mining，DM）過程數(shù)據(jù)挖掘作為整個知識發(fā)現(xiàn)（KDD）的一個重要步驟，起著關(guān)鍵作用。有時，當(dāng)單獨(dú)將數(shù)據(jù)挖掘過程抽出來闡述時，也經(jīng)常把KDD過程與DM過程不加區(qū)分，正像提到KDD概念、DM概念時也不加區(qū)分。數(shù)據(jù)挖掘過程，可用下圖來表示。某種意義上看，也是知識發(fā)現(xiàn)的全過程，其中的模式（Pattern）發(fā)現(xiàn)――數(shù)據(jù)挖掘的關(guān)鍵步驟，相當(dāng)于上面KDD過程中的數(shù)據(jù)挖掘。02十月202334數(shù)據(jù)庫教程（沈--06.8）Ch14.3.

(2)數(shù)據(jù)挖掘的過程02十月202335數(shù)據(jù)庫教程（沈--06.8）①數(shù)據(jù)選擇：數(shù)據(jù)挖掘正像采礦一樣，先要通過地質(zhì)普查找到礦藏所在源，這里就是提出挖掘的目標(biāo)，也就是選擇好限定的主題，來選擇相關(guān)的數(shù)據(jù)。例如，目標(biāo)是優(yōu)化銷售策略，那么，根據(jù)這樣的目標(biāo)，圍繞此主題選取與銷售相關(guān)的數(shù)據(jù)記錄作為數(shù)據(jù)挖掘的對象。②數(shù)據(jù)預(yù)處理：對于選擇好的數(shù)據(jù)，必須經(jīng)過預(yù)處理提高數(shù)據(jù)質(zhì)量，才能使得數(shù)據(jù)挖掘更加有效。因?yàn)椴唤?jīng)預(yù)處理的數(shù)據(jù)，往往垃圾數(shù)據(jù)比較多，數(shù)據(jù)的決策分析是一種典型的“垃圾進(jìn)垃圾出”的過程，數(shù)據(jù)預(yù)處理對數(shù)據(jù)挖掘的結(jié)果有重要的影響。數(shù)據(jù)預(yù)處理技術(shù)主要包括：數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換和數(shù)據(jù)歸約。③模式（Pattern）發(fā)現(xiàn)：這是數(shù)據(jù)挖掘的關(guān)鍵一步。蘊(yùn)涵在數(shù)據(jù)中的規(guī)律、規(guī)則或特征，也就是通常所說的知識，表現(xiàn)在數(shù)據(jù)的某種模式上，發(fā)現(xiàn)數(shù)據(jù)模式關(guān)鍵是人機(jī)交互地選擇算法，這一步是數(shù)據(jù)挖掘中的核心內(nèi)容，下面我們將單列一節(jié)介紹數(shù)據(jù)挖掘的基本內(nèi)容與方法。④解釋評估：通過模式發(fā)現(xiàn)算法可以得到較多的模式。對于給定的用戶，是否對所有模式都感興趣，答案是否定的。所以，數(shù)據(jù)挖掘過程的最后一步，是討論從挖掘出的模式中得到有趣模式的問題，即對用戶有用的模式，也就是對挖掘出的模式進(jìn)行解釋評估。Ch14.3.

(2)數(shù)據(jù)挖掘的過程02十月202336數(shù)據(jù)庫教程（沈--06.8）有關(guān)解釋評估，需要討論以下一些問題：①模式興趣度的度量：一是客觀度量，例如對于形如X→Y的關(guān)聯(lián)規(guī)則，客觀度量通常采用支持度和置信度來定義，支持度Support(X→Y)=P(X∪Y)，其中P(X∪Y)是項(xiàng)集X和Y并的概率。置信度Confidence(X→Y)=P(Y|X)，其中P(Y|X)是包含X的事務(wù)也包含Y的概率。對于度量再引入閾值，由用戶來控制，用戶可以認(rèn)為置信度閾值不超過50%的模式是無趣的。對此，下面還要詳細(xì)討論的。另一種是主觀度量，實(shí)際上是用戶的一種主觀預(yù)感，認(rèn)為合理的或認(rèn)為出乎意料的，給出模式是否有趣的結(jié)論。②數(shù)據(jù)挖掘的完全性：數(shù)據(jù)挖掘能否挖掘出所有有趣的模式，這是較難做到的。只能說，對于某些數(shù)據(jù)挖掘任務(wù)，根據(jù)用戶提出的限制和興趣度量，在一定條件下保證算法的完全性。③數(shù)據(jù)挖掘能夠僅僅產(chǎn)生有趣的模式嗎？往往數(shù)據(jù)挖掘可能會生成一些不是有趣的模式，我們希望僅僅產(chǎn)生有趣模式，這是一個數(shù)據(jù)挖掘優(yōu)化問題。如何識別真正有趣的模式，過濾掉一些不感興趣的模式，采用興趣度度量來知道數(shù)據(jù)挖掘過程，是數(shù)據(jù)挖掘中最后一步重要的工作。Ch14.3.

(3)數(shù)據(jù)挖掘的基本方法02十月202337數(shù)據(jù)庫教程（沈--06.8）(3)數(shù)據(jù)挖掘的基本方法數(shù)據(jù)挖掘算法，針對不同的挖掘任務(wù)，有很多不同的方法，本節(jié)只闡述下面4種基本方法：1．分類、2．聚類、3．關(guān)聯(lián)分析、4．時間序列。1）分類①概述分類是對數(shù)據(jù)的一個重要抽象，從機(jī)器學(xué)習(xí)的觀點(diǎn)看，分類是一種監(jiān)督學(xué)習(xí)，即根據(jù)應(yīng)用的需要確定分類的類別，通過對訓(xùn)練數(shù)據(jù)的分類學(xué)習(xí)歸納出分

類規(guī)則，利用測試數(shù)據(jù)對模型的準(zhǔn)確率進(jìn)行測試，再對數(shù)據(jù)進(jìn)行分類操作。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法分類過程分兩步完成，如圖所示。02十月202338數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法②分類算法以決策樹算法為例，說明分類算法的思路。例如，要對顧客是否購買電腦進(jìn)行測試，圖就是決策樹的示例。02十月202339數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202340數(shù)據(jù)庫教程（沈--06.8）算法14-1：Generate_Decision_Tree（由給定的訓(xùn)練數(shù)據(jù)生成決策樹）輸入：訓(xùn)練樣本Samples，由離散值屬性表示，候選屬性的集合是Attribute_List輸出：決策樹算法描述：⒈）創(chuàng)建節(jié)點(diǎn)N；⒉）if

Samples

都在同一類C

then返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記；⒊）if

Attribute_List

為空then返回N作為葉節(jié)點(diǎn)，標(biāo)記為Samples中類別個數(shù)最多的類別；//多數(shù)表決⒋）從Attribute_List中選擇一個信息增益最大的屬性test_attribute；//屬性選擇方法的信息增益概念，需要解釋并將此節(jié)點(diǎn)N標(biāo)記為test_attribute；⒌）for

each

test_attribute

中的已知取值ai由節(jié)點(diǎn)N長出一個條件為test_attribute=ai的分支；//劃分Samples

設(shè)Si是Samples中test_attribute=ai的樣本的集合；//其中的一個劃分⒍）if

Si為空then加上一個葉節(jié)點(diǎn)，標(biāo)記為Samples中類別最多的類；⒎）else

加上一個由Generate_Decision_Tree(Si,Attribute_List,test_attribute）返回的節(jié)點(diǎn)；Ch14.3.(3)數(shù)據(jù)挖掘的基本方法信息增益方法：這是上面決策樹算法中屬性選擇的基本方法。信息增益的定義。設(shè)S識包含s個數(shù)據(jù)樣本的集合，假定類標(biāo)號屬性具有m個不同值，即定義m個不同的類別Ci(i=1,2,…,m)，設(shè)si是類Ci中的樣本數(shù)，對一個給定的樣本分類可給出所需的期望信息：其中pi是任一樣本屬于類別Ci的概率，可按si/s估計(jì)，對數(shù)函數(shù)以2為底，是因?yàn)樾畔⒁远M(jìn)制位編碼。設(shè)屬性A具有v個不同值{a1,a2,…av}，利用屬性A可將數(shù)據(jù)集合S劃分為v個子集{S1,S2,…Sv}，其中Sj包含了S集合中屬性A取aj值的樣本。若屬性A被選為測試屬性，設(shè)sij為子集sj中屬于Ci類的樣本數(shù)，那么，利用屬性A劃分當(dāng)前樣本集所需的期望信息是：其中當(dāng)作第j個子集的權(quán)值，而是對于給定子集Sj的期望信息。E(A)計(jì)算結(jié)果越小，表示其子集劃分結(jié)果越好。在A上分支將獲得的編碼信息是：

Gain(A)=I(S1,…,Sm)-E(A)定義為利用屬性A對當(dāng)前分支節(jié)點(diǎn)進(jìn)行劃分的信息增益。02十月202341數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202342數(shù)據(jù)庫教程（沈--06.8）現(xiàn)以購買電腦相關(guān)的訓(xùn)練數(shù)據(jù)樣本為例，說明信息增益方法的思路。RID年齡收入是否學(xué)生信用評估是否購買電腦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好NoCh14.3.(3)數(shù)據(jù)挖掘的基本方法對于表給出的訓(xùn)練數(shù)據(jù)集合，分類的標(biāo)記為2類，類C1對應(yīng)于買電南yes，類C2對應(yīng)于no，類yes有9個樣本，類no有5個樣本，計(jì)算得到：現(xiàn)計(jì)算有關(guān)屬性的信息增益，從屬性年齡開始，對年齡<=30

s11=2

s12=3

I(s11,s21)=0.971對年齡31..40

s12=4

s22=0

I(s11,s21)=0對年齡>40

s13=3

s23=2

I(s11,s21)=0.971樣本按年齡劃分，期望信息為：02十月202343數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202344數(shù)據(jù)庫教程（沈--06.8）故這種劃分的信息增益是：Gain(年齡)＝I(s1,s2)-E(age)=0.246。類似地，可以計(jì)算Gain（收入）=0.029，Gain（是否學(xué)生）=0.151，Gain（信用評估）=-0.048，由于年齡在屬性中具有最高的信息增益，被選作為測試屬性，對此可創(chuàng)建分支的節(jié)點(diǎn)。也就是一開始給出的決策樹示例將Age作為分支節(jié)點(diǎn)的原因。我們以決策樹方法簡述了算法的實(shí)現(xiàn)過程。分類算法除了決策樹方法外，常用的方法還有很多，例如：基于統(tǒng)計(jì)學(xué)的貝葉斯分類方法、神經(jīng)網(wǎng)絡(luò)分類方法、k-最近鄰方法、遺傳算法、粗糙集方法、模糊集方法等等。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202345數(shù)據(jù)庫教程（沈--06.8）2)聚類①概述分類是指定類別將數(shù)據(jù)集合劃分的一種技術(shù)，從其學(xué)習(xí)角度來看，是有指導(dǎo)的學(xué)習(xí)。而聚類也是要對數(shù)據(jù)集合進(jìn)行分析加以劃分，但要劃分的類別是未知的，是一種無指導(dǎo)的學(xué)習(xí)。聚類是指將數(shù)據(jù)集合劃分為由類似數(shù)據(jù)組成的多個類（也可稱為簇，cluster）的過程，同一類（或簇）中的數(shù)據(jù)彼此相似，與其它類中的數(shù)據(jù)相異。聚類的典型應(yīng)用領(lǐng)域有：市場營銷（幫助市場營銷人員發(fā)現(xiàn)基本顧客的不同群組，利用這一分析制定更有針對性的營銷計(jì)劃），生物研究（用于動物植物聚類，對基因聚類，獲得對種群固有結(jié)構(gòu)的認(rèn)識），城市規(guī)劃（根據(jù)房屋的類型、價值、地理位置對城市房屋分組），Web文檔分類（Web文檔數(shù)據(jù)是海量的，獲得有關(guān)文檔的特性，聚類后加以逐類分析）等等。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法聚類技術(shù)的相關(guān)概念：點(diǎn)與距離。點(diǎn)——將數(shù)據(jù)視為多維空間中點(diǎn)的集合，數(shù)據(jù)聚類問題演化為多維空間中點(diǎn)的

聚類問題。至于如何將數(shù)據(jù)視作多維空間中的點(diǎn)，有不同的表示方法：（1）將數(shù)據(jù)表示為向量，數(shù)據(jù)集合是一個向量集合，{Xi}（i=1,2,…,N）是N個點(diǎn)的數(shù)據(jù)向量集合，引入中心點(diǎn)（2）數(shù)據(jù)集合看作是矩陣形式，表示為關(guān)系數(shù)據(jù)庫表的形式，其中一行就是數(shù)據(jù)集合中的一個點(diǎn)。距離——有了點(diǎn)的概念，自然可引入基于點(diǎn)的距離概念，距離可表示為兩點(diǎn)之間的歐幾里德距離：或曼哈頓距離：數(shù)據(jù)點(diǎn)之間的相似與相異，用距離的大小加以度量，進(jìn)行聚類分析。02十月202346數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202347數(shù)據(jù)庫教程（沈--06.8）②聚類算法劃分法——典型的劃分法是K-平均算法。給定某一包含n個數(shù)據(jù)元素的數(shù)據(jù)庫，生成的類（或簇）的數(shù)目為K，將n個數(shù)據(jù)劃分為K類（K≤n），以使同一

類中的數(shù)據(jù)相似，而不同類中的數(shù)據(jù)相異。下面是K-平均算法的描述。算法14-2：K-平均//劃分的K-平均算法基于簇中數(shù)據(jù)的平均值輸入：簇的數(shù)據(jù)K，數(shù)據(jù)庫包含n個元組D={x1,…,xn}輸出：K個簇，是平方誤差準(zhǔn)則最小算法：for

k=1,…,K

do//令r(k)是從D={x1,…,xn}中隨機(jī)選取的一個點(diǎn)while在聚類Ck中有變化發(fā)生do形成聚類：for

k=1,…,K

doCk={x∈D|d(rk,x)≤d(rj,x)對所有j=1,…,K,j≠k};end;計(jì)算新的聚類中心：for

k=1,…,K

dork=Ck內(nèi)點(diǎn)的平均值向量；end；end；Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202348數(shù)據(jù)庫教程（沈--06.8）k-平均算法，開始為每個聚類選擇一個初始的中心點(diǎn)，然后以初始中心值為核心形成聚類，再用迭代法反復(fù)修改初始的聚類，直到無明顯改進(jìn)為止。k-平均算法的復(fù)雜度是O(knI)，k是聚類數(shù)，n為數(shù)據(jù)集合大小，I是迭代次數(shù)，通常k<<n，I<<n，算法以局部最優(yōu)結(jié)束。層次法——將所有數(shù)據(jù)組織成一顆聚類的樹，分別可以自底向上或自頂向下進(jìn)行層次分解，自底向上分解的層次法通常稱為凝聚的，自頂向下分解的層次法通常稱為分裂的。一般以凝聚的層次聚類用得較多。其算法可簡單描述如下：for

i=1,…,n

令C={x(i)};while

存在一個以上的聚類do令Ci和Cj為使系統(tǒng)中任意兩個聚類間的距離D=(Ck,Cn)最小化得兩個聚類；Ci=Ci∪Cj;end;Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202349數(shù)據(jù)庫教程（沈--06.8）除了以上兩種主要的聚類方法以外，還有其它較多的聚類方法：基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等等，還有一些聚類算法集成了多種聚類方法的思想，綜合性采用多種聚類技術(shù)可取得更好的聚類效果。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202350數(shù)據(jù)庫教程（沈--06.8）3）關(guān)聯(lián)分析①概述關(guān)聯(lián)分析是數(shù)據(jù)挖掘中較早引起興趣得一種數(shù)據(jù)分析方法，關(guān)聯(lián)分析是發(fā)現(xiàn)數(shù)據(jù)集合中數(shù)據(jù)之間的聯(lián)系。數(shù)據(jù)之間的聯(lián)系，可能表現(xiàn)為兩種形式：一種是同一交易（有時也可說是同一事務(wù)）內(nèi)數(shù)據(jù)之間的聯(lián)系，如在顧客的一筆交易中，購買兩種不同商品之間的聯(lián)系；另一種是不同交易內(nèi)數(shù)據(jù)之間的聯(lián)系，如一個顧客在一次交易中買了甲商品，探討另一次交易中購買乙商品的可能性，也是研究數(shù)據(jù)之間的聯(lián)系。在數(shù)據(jù)挖掘領(lǐng)域，前者就是此處所述的關(guān)聯(lián)分析，后者是下節(jié)要講述的時間序列。關(guān)聯(lián)分析中的若干基本概念：Ch14.3.(3)數(shù)據(jù)挖掘的基本方法支持度可信度02十月202351數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法關(guān)聯(lián)規(guī)則舉例交易 數(shù)據(jù)項(xiàng)t1

A,B,C,Dt2

A,B,Dt3

A,D,Et4

B,Ct5

A,B,C,D關(guān)聯(lián)規(guī)則支持度可信度60%75%50%75%60%75%60%100%02十月202352數(shù)據(jù)庫教程（沈--06.8）Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202353數(shù)據(jù)庫教程（沈--06.8）②關(guān)聯(lián)分析典型算法關(guān)聯(lián)分析典型算法，比較有名的是Apriori算法（1993年R.Agrawal等人提出）。該算法實(shí)現(xiàn)分兩步：1）找出所有頻繁數(shù)據(jù)項(xiàng)集（frequent

itemsets）：即找出所有支持度超過指定閾值的數(shù)據(jù)項(xiàng)集；2）利用頻繁數(shù)據(jù)項(xiàng)集，生成候選的關(guān)聯(lián)規(guī)則，并驗(yàn)證其可信度，如果可信度超過指定的閾值，則該關(guān)聯(lián)規(guī)則即為所要找關(guān)聯(lián)規(guī)則。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202354數(shù)據(jù)庫教程（沈--06.8）算法14-3：Apriori算法，利用層次迭代找出頻繁項(xiàng)集輸入：交易（事務(wù)）數(shù)據(jù)庫D，最小支持度閾值min_sup輸出：D中的頻繁項(xiàng)集L流程：L1=find_frequent_1_itemset(D);//發(fā)現(xiàn)1-項(xiàng)集

for(k=2;Lk-1≠Φ;k++){Ck=apriori_gen(Lk-1,min_sup);//根據(jù)頻繁k-1項(xiàng)集產(chǎn)生候選k項(xiàng)集

for

each

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

for

each

c∈Ct,C.count++;}Lk={c∈Ck|C.count≥min_sup}}return

L=UkLk;Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202355數(shù)據(jù)庫教程（沈--06.8）Procedure

apriori_gen(Lk-1:k-1-項(xiàng)集；min_sup:最小支持度閾值)for

eachl1∈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；//將兩個項(xiàng)集連接到一起if

has_infrequent_subset

(c,Lk-1)thendelete

c；//除去不可能產(chǎn)生頻繁項(xiàng)集的候選else

Ck=Ck∪{C};}return

Ck;Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202356數(shù)據(jù)庫教程（沈--06.8）Procedure

has_infrequent_subset(C,Lk-1)for

each

(k-1)-subset

s

of

Cifs!∈Lk-1return

TRUE;else

return

FALSE;Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202357數(shù)據(jù)庫教程（沈--06.8）4)時間序列①概述時間序列數(shù)據(jù)挖掘，是指表示不同交易之間的數(shù)據(jù)關(guān)聯(lián)，例如，某一顧客多次購買商品，每次交易的數(shù)據(jù)項(xiàng)集構(gòu)成時間序列，在時間序列中發(fā)現(xiàn)的模式，就是一種數(shù)據(jù)之間的關(guān)聯(lián)。下圖就是不同交易的數(shù)據(jù)之間關(guān)聯(lián)的示例。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202358數(shù)據(jù)庫教程（沈--06.8）顧客號交易時間數(shù)據(jù)項(xiàng)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-21CCh14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202359數(shù)據(jù)庫教程（沈--06.8）顧客號數(shù)據(jù)項(xiàng)集序列1<{A,B},

{D},

{E,G,H}>2<{C}>3<{D},

{E,G}>4<{D,F,G}>5<{D},

{C}>Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202360數(shù)據(jù)庫教程（沈--06.8）對這種時間序列的數(shù)據(jù)，為找到數(shù)據(jù)之間關(guān)聯(lián)，引入如下概念。設(shè)有兩個不同顧客的數(shù)據(jù)項(xiàng)序列為<a1,a2,…,an>和<b1,b2,…,bm>，如有整數(shù)i1<i2<…<in，使a1≤bi1，使

a1≤bi2，…，使a1≤bin，則稱<a1,a2,…,an>包含于<b1,b2,…,bm>之中，表示<a1,a2,…,an>≤<b1,b2,…,bm>。這種包含關(guān)系，即表示這兩個顧客都支持序列<a1,a2,…,an>，即這兩個表示不同時間的交易數(shù)據(jù)之間存在關(guān)聯(lián)性。例如，圖中，<{C}>≤<{D,C}>表示顧客2和5都支持<{C}>，而<{D},{E,G}>≤<{A,B},{D},{E,G,H}>表示顧客1、3和5都支持<{D},{E,G}>，支持度s%=40%，凡是支持度超過指定閾值的序列稱為頻繁序列，對于時間序列挖掘而言，其基本問題就是要找出頻繁序列。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202361數(shù)據(jù)庫教程（沈--06.8）②時間序列挖掘基本方法現(xiàn)介紹AprioriAll算法，它是尋找頻繁序列的基本方法，圖14-23是該算法的描述。Procedure

AprioriAll()beginL1＝{frequent

1-sequences};//1-sequences是只包含一個數(shù)據(jù)項(xiàng)集的序列for

(k:=2;Lk-1=Φ;

k++)

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

forall

custom-sequences

in

the

dataset

doforall

cancidates

c∈Ck

contained

in

custom-c.count++;{sequence

do}Lk:={

c∈Ck

|c.count

≥

minsupport}}Answer:=Maximal

sequences

in

∪kLk;endCh14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202362數(shù)據(jù)庫教程（沈--06.8）AprioriG()

: insert

into

Ckselectp.fitemset1,…,p.fitemsetk-1,

q.fitemsetk-1fromLk-1p,Lk-1qwherep.fitemset1=q.fitemset1,…p.fitemsetk-2=q.fitemsetk-2,p.fitemsetk-1<>q.fitemsetq-1;其中fitemset是頻繁數(shù)據(jù)項(xiàng)集。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202363數(shù)據(jù)庫教程（沈--06.8）從此算法的實(shí)現(xiàn)過程看，與前面關(guān)聯(lián)分析算法Apriori較為相像，實(shí)際上將帶時間的交易數(shù)據(jù)轉(zhuǎn)換為顧客的數(shù)據(jù)項(xiàng)集序列，就為

尋找頻繁數(shù)據(jù)項(xiàng)集作了準(zhǔn)備。算法實(shí)施前，先將交易數(shù)據(jù)排序（以顧客標(biāo)識為主鍵，

交易時間為次鍵進(jìn)行升序排序），然后篩

選出頻繁數(shù)據(jù)項(xiàng)集，在此基礎(chǔ)上經(jīng)過變換

發(fā)現(xiàn)頻繁序列。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202364數(shù)據(jù)庫教程（沈--06.8）③時間序列挖掘的其它內(nèi)容時間序列是指包含隨時間變化而發(fā)生的數(shù)值或事件序列，對這類數(shù)據(jù)的挖掘，上面所述內(nèi)容屬于挖掘序列模式，即從與時間相關(guān)的數(shù)據(jù)中，挖掘出相關(guān)的頻繁發(fā)生模式，例如所舉例子，從購買某類商品的顧客可能會在近期內(nèi)購買另一類商品，就是一種序列模式。除此以外，時序數(shù)據(jù)挖掘還有趨勢分析，相似搜索等重要內(nèi)容。趨勢分析——時序數(shù)據(jù)中包含一個變量Y，可以認(rèn)為是時間的函數(shù)Y=F(t)，時序分析即研究其中的趨勢變化、循環(huán)變化、季節(jié)性變化或無規(guī)律變化。采用數(shù)學(xué)上的平滑方法、曲線擬合方法、最小二

乘法等可以完成有關(guān)的數(shù)據(jù)分析，制定預(yù)測方案。Ch14.3.(3)數(shù)據(jù)挖掘的基本方法02十月202365數(shù)據(jù)庫教程（沈--06.8）相似搜索——給定了一個時間序列數(shù)據(jù)，相似搜索是發(fā)現(xiàn)所有與它相似的時序數(shù)據(jù)，是一種序列匹配問題。相似搜索有如下主要的方法：（1）數(shù)據(jù)轉(zhuǎn)換，從時域到頻域。通常采用傅立葉變換、小波變換就可以完成這種轉(zhuǎn)換。采用歐幾里德的概念進(jìn)行相似性測量，完成數(shù)據(jù)匹配。（2）索引方法。采用R-樹、R*樹，改進(jìn)數(shù)據(jù)存儲結(jié)構(gòu)，提高相似搜索的速度。（3）時間序列查詢語言，完成復(fù)雜查詢，支持范圍查詢、最鄰近查詢等，搜索與給定時序數(shù)據(jù)相似的時序數(shù)據(jù)。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202366數(shù)據(jù)庫教程（沈--06.8）（4）復(fù)雜數(shù)據(jù)類型的挖掘前面所介紹的數(shù)據(jù)挖掘，主要針對結(jié)構(gòu)化數(shù)據(jù)進(jìn)行討論的。而復(fù)雜數(shù)據(jù)類型，諸如文本數(shù)據(jù)、多媒體數(shù)據(jù)、Web數(shù)據(jù)都表現(xiàn)為半結(jié)構(gòu)化或非結(jié)構(gòu)化形式，此處對復(fù)雜數(shù)據(jù)類型的挖掘，舉文本、多媒體和Web這三類較流行的數(shù)據(jù)進(jìn)行簡要介紹。1）文本數(shù)據(jù)挖掘以文本形式存放的數(shù)據(jù)，包含一些半結(jié)構(gòu)化字段，如標(biāo)題、作者、出版社、出版時間、長度等，但也包含無結(jié)構(gòu)的

文本內(nèi)容。對這類半結(jié)構(gòu)化的文本數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)分

析方法是采用情報檢索（Information

Retrieval），大部分是利用索引來完成檢索。但是，在文本數(shù)據(jù)迅猛增

加時，傳統(tǒng)情報檢索已無法滿足實(shí)際需求。例如，不知

道文本中究竟包含哪些內(nèi)容時，要想準(zhǔn)確查詢較為困難，想對文本進(jìn)行比較，評估文本的重要性、相關(guān)性等等，

文本數(shù)據(jù)挖掘應(yīng)運(yùn)而生。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202367數(shù)據(jù)庫教程（沈--06.8）文本挖掘的主要內(nèi)容有：（1）基于關(guān)鍵字關(guān)聯(lián)分析。首先收集經(jīng)常一起出現(xiàn)的關(guān)鍵字或詞匯，然后對其進(jìn)行關(guān)聯(lián)分析。關(guān)聯(lián)分析的方法與前面所述的事務(wù)數(shù)據(jù)關(guān)聯(lián)分析相似，但在此以前，要完成詞根處理、去除非用詞等預(yù)處理，將數(shù)據(jù)表示為包含{文檔標(biāo)識符，關(guān)鍵字集合}在內(nèi)的形式，轉(zhuǎn)換為事務(wù)數(shù)據(jù)關(guān)聯(lián)分析問題。（2）文本分類分析。自動地對大量文本進(jìn)行分類，是一種重要的文本挖掘。一般做法是：先把一組預(yù)先分類過的文本當(dāng)作訓(xùn)練集，然后對訓(xùn)練集進(jìn)行分析得出分類模式。對這種分類模式需經(jīng)一定的測試，不斷細(xì)化。粗看起來，與前面事務(wù)數(shù)據(jù)的分類很相似，但因兩類數(shù)據(jù)的不同，不能采用事務(wù)數(shù)據(jù)分類時的決策樹分析，而是采用基于關(guān)聯(lián)的分類，細(xì)節(jié)不贅述。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202368數(shù)據(jù)庫教程（沈--06.8）2）多媒體數(shù)據(jù)挖掘現(xiàn)實(shí)生活中存在大量多媒體數(shù)據(jù)，例如，圖像數(shù)據(jù)、音頻數(shù)據(jù)、視頻數(shù)據(jù)等等，對這類數(shù)據(jù)的管理，從一般性的數(shù)據(jù)庫管理到數(shù)據(jù)挖掘進(jìn)行數(shù)據(jù)分析，是當(dāng)前數(shù)據(jù)庫技術(shù)的一個熱門領(lǐng)域。此處，以圖像數(shù)據(jù)挖掘?yàn)橹鹘榻B一些多媒體數(shù)據(jù)挖掘的主要方法：多媒體數(shù)據(jù)的相似搜索，多媒體數(shù)據(jù)的多維分析，多媒體數(shù)據(jù)的分類與預(yù)測分析以及多媒體數(shù)據(jù)的關(guān)聯(lián)挖掘。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202369數(shù)據(jù)庫教程（沈--06.8）多媒體數(shù)據(jù)的相似搜索——主要有兩種方法：（1）基于描述的搜索方法，在多媒體數(shù)據(jù)上建立標(biāo)引（如：關(guān)鍵字、標(biāo)題等）再進(jìn)行檢索。這種方法若手工完成是很費(fèi)勁的，若自動完成，往往檢索結(jié)果質(zhì)量較差。（2）基于內(nèi)容的搜索方法，是近年來的主要方法，針對圖像內(nèi)容中的顏

色構(gòu)成、紋理、形狀等進(jìn)行特征描述再檢索。例如，基

于顏色直方圖的特征表示，多特征（顏色直方圖、形狀、位置和結(jié)構(gòu)）構(gòu)成的特征標(biāo)識，基于小波變換的特征標(biāo)

識，建立了特征標(biāo)識以后，就可以利用圖像特征向量匹

配來進(jìn)行相似搜索。多媒體數(shù)據(jù)的多維分析——采用按傳統(tǒng)的從關(guān)系數(shù)據(jù)構(gòu)造

數(shù)據(jù)立方體相似的方法，設(shè)計(jì)和構(gòu)造多媒體數(shù)據(jù)立方體。多媒體數(shù)據(jù)立方體可包含針對多媒體的維和度量，如顏

色、紋理和形狀。在此基礎(chǔ)上，進(jìn)行基于視覺內(nèi)容的多

維分析，并完成多種知識的挖掘，包括匯總、比較、分

類、關(guān)聯(lián)和聚類。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202370數(shù)據(jù)庫教程（沈--06.8）多媒體數(shù)據(jù)的分類和預(yù)測分析——分類和預(yù)測分析已經(jīng)用于多媒體數(shù)據(jù)挖掘，尤其在科學(xué)研究中，如天文學(xué)、地震學(xué)和地理科學(xué)的研究。目前圖像數(shù)據(jù)挖掘應(yīng)用中決策樹分類是最基本的數(shù)據(jù)挖掘方法。數(shù)

據(jù)預(yù)處理在圖像數(shù)據(jù)挖掘中是相當(dāng)重要的，它包括數(shù)據(jù)清理、數(shù)據(jù)

聚焦和特征提取，同時由于數(shù)據(jù)量很大，需要使用并行、分布處理

等技術(shù)來加強(qiáng)處理能力。多媒體數(shù)據(jù)中的關(guān)聯(lián)分析——多媒體數(shù)據(jù)中的關(guān)聯(lián)可能會涉及三類：（1）圖像內(nèi)容和非圖像內(nèi)容特征間的關(guān)聯(lián)，如規(guī)劃“如果照片的上

半部分的50%是藍(lán)色，那它很可能是天空”屬于此類，它把圖像內(nèi)容和關(guān)鍵字“天空”關(guān)聯(lián)在一起。（2）與空間關(guān)系無關(guān)的圖像內(nèi)容的關(guān)聯(lián)，如規(guī)劃“若一個圖像包含兩個藍(lán)方框，那么就可能包含一個紅色圓”，所描述的關(guān)聯(lián)構(gòu)思關(guān)于圖像內(nèi)容的，但與空間關(guān)系無關(guān)。（3）有空間關(guān)系的圖像內(nèi)容間的關(guān)聯(lián)，如“若兩個黃方框之間有一個紅色三角形，那么下面就可能有一個大的橢圓物體”，這里所描述的與圖像關(guān)聯(lián)的對象具有空間關(guān)系。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202371數(shù)據(jù)庫教程（沈--06.8）3）Web挖掘隨著Internet技術(shù)的發(fā)展，尤其是Web的全球普及，使得Web上的信息無比豐富。但是，這些信息主要是一些大量的異構(gòu)數(shù)據(jù)源，文檔結(jié)構(gòu)性差，其

數(shù)據(jù)多為半結(jié)構(gòu)化或非結(jié)構(gòu)化。對這些數(shù)據(jù)如何

管理、分析，一種有效的方法是互聯(lián)網(wǎng)搜索引擎，利用此引擎可以有效發(fā)現(xiàn)和很好利用互聯(lián)網(wǎng)的信

息資源。但是，這種方法存在如下不足：首先是

一個主題可能包含成千上萬的文檔，從而導(dǎo)致搜

索引擎的查詢結(jié)果結(jié)構(gòu)常常也是非常巨大，而其

中只有較少以部分與用戶相關(guān)；其次是許多與主

題相關(guān)的文檔或許沒有包含相應(yīng)的關(guān)鍵字。例如

“data

mining”關(guān)鍵字，可能會發(fā)現(xiàn)與“miningindustry”有關(guān)的網(wǎng)頁。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202372數(shù)據(jù)庫教程（沈--06.8）搜索引擎顯然不能作為利用Web信息資源的唯一方法，同時我們還可看出，要對Web數(shù)據(jù)進(jìn)行有效的知識發(fā)現(xiàn)存在以下問題：1）互聯(lián)網(wǎng)數(shù)據(jù)太大以至無法有效構(gòu)造數(shù)據(jù)倉庫并進(jìn)行數(shù)據(jù)挖掘。2）網(wǎng)頁的復(fù)雜性遠(yuǎn)遠(yuǎn)要大于任何傳統(tǒng)的文本文檔。3）互聯(lián)網(wǎng)的資源具有很大的動態(tài)性。

4）互聯(lián)網(wǎng)的用戶群體具有多樣性。5）互聯(lián)網(wǎng)上的信息只有一小部分是真正有用的或相關(guān)的，通常來說互聯(lián)網(wǎng)上99％的信息對99％的用戶是無用的。正因?yàn)檫@樣，Web數(shù)據(jù)挖掘應(yīng)運(yùn)而生。Web挖掘就是要發(fā)現(xiàn)網(wǎng)頁的讀取模式、互聯(lián)網(wǎng)結(jié)構(gòu)和互聯(lián)網(wǎng)內(nèi)容描述所存在的規(guī)律和動態(tài)特點(diǎn)，從網(wǎng)頁的海洋中（據(jù)統(tǒng)計(jì)，2000年初，網(wǎng)頁數(shù)已達(dá)8億頁，并估計(jì)每4個月要翻一番。）發(fā)現(xiàn)高質(zhì)量的信息，有效地進(jìn)行知識發(fā)現(xiàn)。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202373數(shù)據(jù)庫教程（沈--06.8）Web挖掘是將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)和Web結(jié)合起來，進(jìn)行Web知識的提取，從Web文檔和Web活動中抽取感興趣的潛在的有用模式和隱藏的信息。一般地，Web挖掘可以分為三類：Web內(nèi)容挖掘，Web結(jié)構(gòu)挖掘和Web使用挖掘。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202374數(shù)據(jù)庫教程（沈--06.8）（1）Web內(nèi)容挖掘Web內(nèi)容挖掘是對Web上大量文檔集合的內(nèi)容進(jìn)行總結(jié)、分類、聚類、關(guān)聯(lián)分析以及利用Web文檔進(jìn)行趨勢預(yù)測等，其中最重要的是，文本的特征表示、分類和聚類。文本的特征表示——Web文檔是半結(jié)構(gòu)化或非結(jié)構(gòu)化的，這樣的特殊性使得現(xiàn)存的數(shù)據(jù)挖掘技術(shù)無法直接加以應(yīng)用。我們需要對Web文本進(jìn)行預(yù)處理，抽取代表其特征的元數(shù)據(jù)。這些特征可以用結(jié)構(gòu)化形式保存，作為文檔的中間表示形式。W3C近來制定的XML、RDF等規(guī)范提供了對Web文檔進(jìn)行描述的語言和框架。矢量空間模型（VSM）是近年來應(yīng)用較多且效果較好的方法之一。在該模型中，文檔空間被看作是由一組正交詞條矢量所形成的矢量空間，每個文檔d表示為其中的一個范式特征矢量

V(d)=(k1,w1(d);…;ki,wi(d);…;kn,wn(d))，其中ki為詞條項(xiàng)，wi(d)為ki在d中的權(quán)值，可以將d中出現(xiàn)的所有單詞作為ki，也可以要求

ki是d中出現(xiàn)的所有短語，從而提高內(nèi)容特征表示的準(zhǔn)確性。wi(d)一般被定義為ki在d中出現(xiàn)頻率tfi(d)的函數(shù)，即wi(d)=ψ(tfi(d))，常用的ψ函數(shù)有：布爾函數(shù)、平方根函數(shù)、對數(shù)函數(shù)和TF1DF函數(shù)。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202375數(shù)據(jù)庫教程（沈--06.8）Web文本分類——文本分類是一種典型的有知道的機(jī)器學(xué)習(xí)問題，一般分為訓(xùn)練和分類兩個階段。具體過程為：訓(xùn)練階段——

1）定義類別集合Z={z1,…,zi,…,zm}，這些類別可以是層次式的，頁可以是并列式的；給出訓(xùn)練文檔集合F={f1,…,fj,…fn}，每個訓(xùn)練文檔fj被標(biāo)上所屬的類別標(biāo)識zi；統(tǒng)計(jì)文本集合F中所有文檔的特征矢量V(fj)，確定代表Z中每個類別的特征矢量V(zi)。分類階段——對測試文檔集合TD={d1,…,dk,…,dr}中的每個待分類文檔dk，計(jì)算其特征向量V(dk)與每個V(zi)之間的相似度Sim(dk,zi)；選取相似度最大的一個類別作為dk的類別。在計(jì)算Sim(dk,zi)時，有多種方法可供選擇。最簡單的方式是僅考慮兩個特征矢量中所包含的詞條的重疊程度，即Sim(dk,zi)=(∩n(dk,zi))/(∪n(dk,zi))，其中，∩n(dk,zi)是V(dk)和V(zi)具有的相同詞條數(shù)目，∪n(dk,zi)是V(dk)和V(zi)具有的所有詞條數(shù)目；最常用的方法是考慮兩個特征矢量之間的夾角余弦，即Sim(dk,zi)=(V(dk).V(zi))/(|V(dk)|*|V(zi)|)。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202376數(shù)據(jù)庫教程（沈--06.8）Web文本聚類——Web文本聚類是一種典型的無指導(dǎo)的機(jī)器學(xué)習(xí)問題。目前的文本聚類方法大致可以分為層次凝聚法和平面劃分法兩種類型。對于給定的文檔集合D={d1,…,di,…,dn}，層次凝聚法的具體過程如下。將D中的每個文檔di看作是一個具有單個成員的簇

zi={di}，這些簇構(gòu)成了D的一個聚類Z={z1,…,zi,…zn}；計(jì)算Z中每對簇(zi,zj)之間的相似度Sim(zi,zj)；

3）選取具有最大相似度的簇對，并將它們合并為一個新的簇，zk=zi∪zj，從而構(gòu)成了D的一個新的聚類，Z={z1,…,zn-1}；4）重復(fù)上述步驟，直到Z中剩下一個簇為止。該過程構(gòu)造出一顆生成樹，其中包含了簇的層次信息，以及所有簇內(nèi)和簇間的相似度。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202377數(shù)據(jù)庫教程（沈--06.8）平面劃分法與層次凝聚法的區(qū)別在于，它將文檔集合水平地分割為若干個簇，而不是生成層次化的嵌套簇。對于給定的文檔集合D={d1,…,di,…,dn}，平面劃分法的具體過程如下：確定要生成的簇的數(shù)目k；按照某種原則生成k個聚類中心作為聚類的核

Y={y1,…,yi,…,yk}；對D中的每個文檔di，依次計(jì)算它與每個核yi的相似度

Sim=(di,yj)；選取具有最大相似度的核，將其歸入以yj為聚類中心的簇zj，從而得到D的一個聚類Z＝{z1,…,zk}；重復(fù)步驟2，3，4若干次，以得到較為穩(wěn)定的聚類結(jié)果。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202378數(shù)據(jù)庫教程（沈--06.8）（2）Web結(jié)構(gòu)挖掘整個Web空間里，有許多有用知識包含在

Web頁面超鏈結(jié)構(gòu)與Web頁面內(nèi)部結(jié)構(gòu)之中。Web結(jié)構(gòu)挖掘主要是通過對Web站點(diǎn)的結(jié)果進(jìn)行分析和歸納，發(fā)現(xiàn)頁面的結(jié)果和Web間的結(jié)果，在此基礎(chǔ)上找出權(quán)威頁面，利用發(fā)現(xiàn)的這種知識可以改進(jìn)搜索引擎。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202379數(shù)據(jù)庫教程（沈--06.8）下面介紹兩種Web結(jié)構(gòu)挖掘的方法。1）rank方法rank方法的基本思想是：一個頁面被多次引用，則這個頁面很可能是重要的；一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面很可能是重要的。一個頁面的重要性被均分并被傳遞到它所引用的頁面。頁面重要性度量的定義：u是一個Web頁面，F(xiàn)u是u引用的頁面集合，Bu是引用u的頁面集合，Nu=|Fu|，則u的重要性為R(u)=∑v∈Bu(R(v)/Nu)。對于一個查詢q，搜索引擎首先利用相似度函數(shù)找到k個頁面，然后利用公式ranking-score(q,d)=w1*Sim(q,d)+w2*R(d)計(jì)算每個頁面的重要性，然后進(jìn)行排名。這里，w1,w2∈[0,1]，w1+w2=1，Sim(q,d)是相似度函數(shù)，Sim(q,d),R(d)∈[0,1]。Ch14.3

（4）復(fù)雜數(shù)據(jù)類型的挖掘02十月202380數(shù)據(jù)庫教程（沈--06.8）2）Hub/Authority方法Hub/Authority方法的基本思想是：Hub是指一個或多個Web頁面，它提供了指向權(quán)威頁面的連接集合。Hub