數(shù)據(jù)挖掘概念與技術

數(shù)據(jù)挖掘一一概念概念與技術

DataMining

Conceptsandlechniques

習題答案

第1章引言

1.1什么是數(shù)據(jù)挖掘？在你的回答中，針對以下問題：

1.21.6定義下列數(shù)據(jù)挖掘功能：特征化、區(qū)分、關聯(lián)和相關分析、猜測

聚類和演化分析。使用你熟識的現(xiàn)實生活的數(shù)據(jù)庫，給出每種數(shù)據(jù)

挖掘功能的例子。

解答：

因特征化是一個目標類數(shù)據(jù)的一般特性或特性的匯總。例如，同學的特

征可被提出，形成全部高校的計算機科學專業(yè)一班級同學的輪廓，

這些特征包括作為一種高的班級平均成果(GPA：Gradepointaversge)

的信息，還有所修的課程的最大數(shù)量。

E區(qū)分是將目標類數(shù)據(jù)對象的一般特性與一個或多個對比類對象的一

般特性進行比較。例如，具有高GPA的同學的一般特性可被用來

與具有低GPA的一般特性比較。最終的描述可能是同學的一個一

般可比較的輪廓，就像具有高GPA的同學的75%是四班級計算機科

學專業(yè)的同學，而具有低GPA的同學的65%不是。

S關聯(lián)是指發(fā)覺關聯(lián)規(guī)章，這些規(guī)章表示一起頻繁發(fā)生在給定數(shù)據(jù)集的

特征值的條件。例如，一個數(shù)據(jù)挖掘系統(tǒng)可能發(fā)覺的關聯(lián)規(guī)

則為：

major(X,''computingscience")?owns(X,''personal

computer")[support=12%,confidence=98%]

其中，X是一個表示同學的變量。這個規(guī)章指出正在學習的同學，12%

(支持度)主修計算機科學并且擁有一臺個人計算機。這個組一個同

學擁有一臺個人電腦的概率是98%(置信度，或確定度)。

E分類與猜測不同，由于前者的作用是構造一系列能描述和區(qū)分數(shù)據(jù)類

型或概念的模型(或功能)，而后者是建立一個模型去猜測缺失的

或無效的、并且通常是數(shù)字的數(shù)據(jù)值。它們的相像性是他們都是猜

測的工具：分類被用作猜測目標數(shù)據(jù)的類的標簽，而猜測典型的應用

是猜測缺失的數(shù)字型數(shù)據(jù)的值。

S聚類分析的數(shù)據(jù)對象不考慮已知的類標號。對象依據(jù)最大花蕾內部的相似

性、最小化類之間的相像性的原則進行聚類或分組。形成的每一簇可以被看作

一個對象類。聚類也便于分類法組織形式，將觀測組織成類分層結構，把類似

的大事組織在一起。

0數(shù)據(jù)延邊分析描述和模型化隨時間變化的對象的規(guī)律或趨勢，盡管這可

能包括時間相關數(shù)據(jù)的特征化、區(qū)分、關聯(lián)和相關分析、分類、或猜測，

這種分析的明確特征包括時間序列數(shù)據(jù)分析、序列或周期模式匹配、和

基于相像性的數(shù)據(jù)分析

1.31.9列舉并描述說明數(shù)據(jù)挖掘任務的五種原語。

解答：

用于指定數(shù)據(jù)挖掘任務的五種原語是：

?任務相關數(shù)據(jù)：這種原語指明給定挖掘所處理的數(shù)據(jù)。它包括指明數(shù)據(jù)

庫、數(shù)據(jù)庫表、或數(shù)據(jù)倉庫，其中包括包含關系數(shù)據(jù)、選擇關系數(shù)據(jù)的

條件、用于探究的關系數(shù)據(jù)的屬性或維、關于修復的數(shù)據(jù)排序和分組。

國挖掘的數(shù)據(jù)類型：這種原語指明白所要執(zhí)行的特定數(shù)據(jù)挖掘功能，如特

征化、區(qū)分、關聯(lián)、分類、聚類、或演化分析。同樣，用戶的要求可能

更特別，并可能供應所發(fā)覺的模式必需匹配的模版。這些模版或超模式

（也被稱為超規(guī)章）能被用來指導發(fā)覺過程。

S背景學問：這種原語允許用戶指定已有的關于挖掘領域的學問。這樣的

學問能被用來指導學問發(fā)覺過程，并且評估發(fā)覺的模式。關于數(shù)據(jù)中關

系的概念分層和用戶信念是背景學問的形式。

S模式愛好度度量：這種原語允許用戶指定功能，用于從學問中分割不感

愛好的模式，并且被用來指導挖掘過程，也可評估發(fā)覺的模式。這樣就

允許用戶限制在挖掘過程返回的不感愛好的模式的數(shù)量，由于一種數(shù)據(jù)

挖掘系統(tǒng)可能產生大量的模式。愛好度測量能被指定為簡易性、確定性、

適用性、和新奇性的特征。

S發(fā)覺模式的可視化：這種原語述及發(fā)覺的模式應被顯示出來。為了使數(shù)

據(jù)挖掘能有效地將學問傳給用戶，數(shù)據(jù)挖掘系統(tǒng)應能將發(fā)覺的各種形式

的模式展現(xiàn)出來，正如規(guī)章、表格、餅或條形圖、決策樹、立方體或其

它視覺的表示。

1.4L13描述以下數(shù)據(jù)挖掘系統(tǒng)與數(shù)據(jù)庫或數(shù)據(jù)倉庫集成方法的差別：不

耦合、松散耦合、半緊耦合和緊密耦合。你認為哪種方法最流行，為

什么？

解答：數(shù)據(jù)挖掘系統(tǒng)和數(shù)據(jù)庫或數(shù)據(jù)倉庫系統(tǒng)的集成的層次的

差別如下。

E不耦合：數(shù)據(jù)挖掘系統(tǒng)用像平面文件這樣的原始資料獲得被挖掘的原

始數(shù)據(jù)集，由于沒有數(shù)據(jù)庫系統(tǒng)或數(shù)據(jù)倉庫系統(tǒng)的任何功能被作為

處理過程的一部分執(zhí)行。因此，這種構架是一種糟糕的設計。

E松散耦合：數(shù)據(jù)挖掘系統(tǒng)不與數(shù)據(jù)庫或數(shù)據(jù)倉庫集成，除了使用被挖

掘的初始數(shù)據(jù)集的源數(shù)據(jù)和存儲挖掘結果。這樣，這種構架能得到

數(shù)據(jù)庫和數(shù)據(jù)倉庫供應的敏捷、高效、和特征的優(yōu)點。但是，在大

量的數(shù)據(jù)集中，由松散耦合得到高可測性和良好的性能是特別困難

的，由于很多這種系統(tǒng)是基于內存的。

0半緊密耦合：一些數(shù)據(jù)挖掘原語，如聚合、分類、或統(tǒng)計功能的估計

算，可在數(shù)據(jù)庫或數(shù)據(jù)倉庫系統(tǒng)有效的執(zhí)行，以便數(shù)據(jù)挖掘系統(tǒng)在挖

掘-查詢過程的應用。此外，一些常常用到的中間挖掘結果能被估計

算并存儲到數(shù)據(jù)庫或數(shù)據(jù)倉庫系統(tǒng)中，從而增加了數(shù)據(jù)挖掘系統(tǒng)的

性能。

S緊密耦合：數(shù)據(jù)庫或數(shù)據(jù)倉庫系統(tǒng)被完全整合成數(shù)據(jù)挖掘系統(tǒng)的一

部份，并且因此供應了優(yōu)化的數(shù)據(jù)查詢處理。這樣的話，數(shù)據(jù)挖掘

子系統(tǒng)被視為一個信息系統(tǒng)的功能組件。這是一中高度期望的結

構，由于它有利于數(shù)據(jù)挖掘功能、高系統(tǒng)性能和集成信息處理環(huán)境

的有效實現(xiàn)。

從以上供應的體系結構的描述看，緊密耦合是最優(yōu)的，沒有值得顧慮的技

術和執(zhí)行問題。但緊密耦合系統(tǒng)所需的大量技術基礎結構仍舊在進展變化，

其實現(xiàn)并非易事。因此，目前最流行的體系結構仍是半緊密耦合，由于它是

松散耦合和緊密耦合的折中。

1.51.14描述關于數(shù)據(jù)挖掘方法和用戶交互問題的三個數(shù)據(jù)挖掘挑戰(zhàn)。

第2章數(shù)據(jù)預處理

2.12.2假設給定的數(shù)據(jù)集的值己經分組為區(qū)間。區(qū)間和對應的頻率如下。

年齡頻率

1~5200

5~15450

15-20300

20?501500

50-80700

80-11044

計算數(shù)據(jù)的近似中位數(shù)值。

解答：先判定中位數(shù)區(qū)間：

N=200+450+300+1500+700+44=3194；N/2=1597

,/200+450+300=950<1597<2450=950+1500；

20~50對應中位數(shù)區(qū)間。我們有：￡i=20,

N=3197,(??eq)/=950,freqmedian=\500,width=30,使用公

式(2.3)：

3197/2a95

median=Lt+^=20+lLU30=32.97

freq匚015000

me也”=32.97歲。

2.22.4假定用于分析的數(shù)據(jù)包含屬性age。數(shù)據(jù)元組的age值(以遞增序)

是：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,

33,33,35,35,35,35,36,40,45,46,52,70。

(a)該數(shù)據(jù)的均值是什么？中位數(shù)是什么？

(b)該數(shù)據(jù)的眾數(shù)是什么？爭論數(shù)據(jù)的峰(即雙峰、三峰等)。

(c)數(shù)據(jù)的中列數(shù)是什么？

(d)你能(粗略地)找出數(shù)據(jù)的第一個四分位數(shù)(QD和第三個四分位數(shù)(Q3)嗎？

(e)給出數(shù)據(jù)的五數(shù)概括。

⑴畫出數(shù)據(jù)的盒圖。

(g)分位數(shù)一分位數(shù)圖與分位數(shù)圖的不同之處是什么？

解答：

(a)該數(shù)據(jù)的均值是什么？中位數(shù)是什么？

均值是:=809/27=29.96E30(公式2.1)。中位數(shù)應是第14

個，即笛4=25=。2。

(b)該數(shù)據(jù)的眾數(shù)是什么？爭論數(shù)據(jù)的峰(即雙峰、三峰等)。這個數(shù)集的眾數(shù)有

兩個：25和35,發(fā)生在同樣最高的頻率處，因此是雙峰

眾數(shù)。

(C)數(shù)據(jù)的中列數(shù)是什么？數(shù)據(jù)的中列數(shù)是最大術和最小是的均值。即：

midrange=(70+\3)/2=41.5。

(d)你能(粗略地)找出數(shù)據(jù)的第一個四分位數(shù)(Q)和第三個四分位數(shù)(。3)嗎？

數(shù)據(jù)集的第一個四分位數(shù)應發(fā)生在25%處，即在(N+1)/4=7處。所以：。產20,

而笫三個四分位數(shù)應發(fā)生在75%處，即在3x(N+l)/4=21處。所以：Q=35

(e)給出數(shù)據(jù)的五數(shù)概括。

一個數(shù)據(jù)集的分布的5數(shù)概括由最小值、第一個四分位數(shù)、中位數(shù)、第三個

四分位數(shù)、和最大值構成。它給出了分布外形良好的匯總，并且這些數(shù)據(jù)是：13、

20、25、35、70。

⑴畫出數(shù)據(jù)的盒略。

(g)分位數(shù)一分位數(shù)圖與分位數(shù)圖的不同之處是什么？分位數(shù)圖是一種用

來展現(xiàn)數(shù)據(jù)值低于或等于在一個單變量分布中獨立的變

量的粗略百分比。這樣，他可以展現(xiàn)全部數(shù)的分位數(shù)信息、，而為獨立變量測得的

值(縱軸)相對于它們的分位數(shù)(橫軸)被描繪出來。

但分位數(shù)一分位數(shù)圖用縱軸表示一種單變量分布的分位數(shù)，用橫軸表示另一

單變量分布的分位數(shù)。兩個坐標軸顯示它們的測量值相應分布的值域，且點依據(jù)

兩種分布分位數(shù)值展現(xiàn)。一條線(y=x)可畫到圖中，以增加圖像的信息。落在

該線以上的點表示在y軸上顯示的值的分布比x軸的相應的等同分位數(shù)對應的值

的分布高。反之，對落在該線以下的點則低。

2.32.7使用習題2.4給出的age數(shù)據(jù)回答下列問題：

(a)使用分箱均值光滑對以上數(shù)據(jù)進行光滑，箱的深度為3。解釋你的步驟,

評述對于給定的數(shù)據(jù)，該技術的效果。

(b)如何確定數(shù)據(jù)中的離群點？

(c)對于數(shù)據(jù)光滑，還有哪些其他方法？

解答：

(a)使用分箱均值光滑對以上數(shù)據(jù)進行光滑，箱的深度為3。解釋你的步驟,

評述對于給定的數(shù)據(jù)，該技術的效果。

用箱深度為3的分箱均值光滑對以上數(shù)據(jù)進行光滑需要以下步驟:

E步驟1：對數(shù)據(jù)排序。(由于數(shù)據(jù)已被排序，所以此時不需要該步驟。)

S步驟2：將數(shù)據(jù)劃分到大小為3的等頻箱中。

箱1：13,15,16箱2：16,19,20箱3：20,21,22

箱4：22,25,25箱5：25,25,30箱6：33,33,35

箱7：35,35,35箱8：36,40,45箱9：46,52,70

E步驟3：計算每個等頻箱的算數(shù)均值。

0步驟4：用各箱計算出的算數(shù)均值替換每箱中的每個值。

箱1：44/3,44/3,44/3箱2：55/3,55/3,55/3箱3：21,21,21

箱4：24,24,24箱5：80/3,80/3,80/3箱6：101/3,101/3,101/3

箱7：35,35,35箱8：121/3,121/3,121/3箱9：56,56,56(b)如

何確定數(shù)據(jù)中的離群點？聚類的方法可用來將相像的點分成組或“簇”，并

檢測離群點。落到簇的集

外的值可以被視為離群點。作為選擇，一種人機結合的檢測可被采納，而計算機

用一種事先打算的數(shù)據(jù)分布來區(qū)分可能的離群點。這些可能的離群點能被用人工

輕松的檢驗，而不必檢查整個數(shù)據(jù)集。

(C)對于數(shù)據(jù)光滑，還有哪些其他方法？

其它可用來數(shù)據(jù)光滑的方法包括別的分箱光滑方法，如中位數(shù)光滑和箱邊界光

滑。作為選擇，等寬箱可被用來執(zhí)行任何分箱方式，其中每個箱中的數(shù)據(jù)范圍均

是常量。除了分箱方法外，可以使用回歸技術擬合成函數(shù)來光滑數(shù)據(jù)，如通過線

性或多線性回歸。分類技術也能被用來對概念分層，這是通過將低級概念上卷到

高級概念來光滑數(shù)據(jù)。

2.42.10如下法律規(guī)范化方法的值域是什么？

(a)min-max法律規(guī)范化。

(b)z-score法律規(guī)范化。

(c)小數(shù)定標法律規(guī)范

化。解答：

(a)min-max法律規(guī)范化。值

域是［new_min,new_max］?(b)

z-score法律規(guī)范化。

值域是［(old_min—mean)/0,(old_max—mean)/。］,總的來說，對于全部可能

的數(shù)據(jù)集的值域是(-00,+8)。

(C)小數(shù)定標法律規(guī)范

化。值域是(一

1.0,1.0)o

2.52.12使用習題2.4給出的age數(shù)據(jù)，回答以下問題：

(a)使用min-max法律規(guī)范化將age值35變換到［0.0,1.0|區(qū)間。

(b)使用z-score法律規(guī)范化變換age值35,其中age的標準差為12.94歲。

(c)使用小數(shù)定標法律規(guī)范化變換age值35。

(d)對于給定的數(shù)據(jù)，你情愿使用哪種方法？陳述你的理由。

解答：

(a)使用min-max法律規(guī)范化將age值35變換到［0.0,1.0］區(qū)間。

■:miiiA=13,maxA=70,new_minA=0.0,new_maxA=1.0,而v=35,

,v□min.,.、

v-(new_max.□new_mmA)+minA

maxA□min4

=3513(1.00.0)+0.0=0.3860

70D13

(b)使用z-score法律規(guī)范化變換age值35,其中age的標準差為12.94歲。

-13+15+2?16+19+2-20+21+2-22+4-25

A=---------------------------------------------------------------

27

30+2?33+4?35+36+40+45+46+52+70

H---------------------------------------------------------------

27

=塑=29.963

27

白(4口4)

0：=^-----------=161.2949.o=12.7002

八浦AVA

或s2

□(4口可

1=1

=167.4986,〃=5；=12.9421

N

vOA35□29.9635.037

=0.3966H0.400

°A12.700212.7002

,vD/435口29.963_5.037

或匕==0.3892H0.39

12.9421~12.9421

(c)使用小數(shù)定標法律規(guī)范化變換age值

35。v35

==0.35

由于最大的肯定值為70,所以j=2。v'=1°，I。？

(d)對于給定的數(shù)據(jù)，你情愿使用哪種方法？陳述你的理由。

略。

2.62.14假設12個銷售價格紀錄組已經排序如下：5,10,11,13,15,35,

50,55,72,92,204,215。使用如下每種方法將其劃分成三個箱。

(a)等頻(等深)劃分。

(b)等寬劃分。

(C)聚類。解

答：

(a)等頻(等深)劃分。

binl5,10,11,13

binl15,35,50,55

(b)等寬劃分。

binl72,91,204,215

每個區(qū)間的寬度是：(215-5)/3=70

binl5,10,11,13,15,35,50,55,72

binl91

binl204,215

(c)聚類。

我們可以使用一種簡潔的聚類技術：用2個最大的間隙將數(shù)據(jù)分成3個箱。

binl5,10,11,13,15

binl35,50,55,72,91

binl204,215

2.72.15使用習題2.4給出的age數(shù)據(jù)，

(a)畫出一個等寬為10的等寬直方圖；

(b)為如下每種抽樣技術勾畫例子：SRSWOR,SRSWR,聚類抽樣，分層

抽樣。使用大小為5的樣本和層“青年”，“中年”和“老年”。

解答：(a)畫出一個等寬為10的等寬直方圖；

8

L.

152535455565

(b)為如下每種抽樣技術勾畫例子：SRSWOR,SRSWR,聚類抽樣，分層抽

樣。使用大小為5的樣本和層“青年”，“中年”和“老年”。

元組：

13T1022T1935

T215T?25T2035

T12T21

T3162535

T416T1325T2236

Tl4T23

T5192540

T[5T24

T6203045

T16T25

T7203346

T17

T82133T2652

T7

2235270

T9TI8

SRSWOR和SRSWR：不是同次的隨機抽樣結果可以不同，但前者因無放回

所以不能有相同的元組。

SRSWOR(n=5)SRSWR(n=5)

T416T720

T

T620720

TIO22T2035

TH25T2135

T2652T2546

聚類抽樣：設起始聚類共有6類，可抽其中的m類。

Sample1Sample2Sample3Sample4Sample5Sample6

T)T,6T

13T20TH25332I3552

6T26

T7T12T17T22T27

T2152025333670

T13T1ST23

T316T821253540

T4Ti4T19T24

16T922253545

T.5T20T25

T519TIO22303546

Sample2Sample5

T21

T62035

T22

T72036

T23

T82140

T24

T92245

T25

T102246

分層抽樣：依據(jù)年齡分層抽樣時.，不同的隨機試驗結果不同。

Ti13youngT1022youngTl935middleage

T215youngTn25youngT2035middleage

T|2T21

T316young25young35middleage

TT13T22

416young25young36middleage

T14T23

T519young25young40middleage

T15T4

T620young30middleage245middleage

20young33middleage46middleage

T7T16T25

T17T26

T821young33middleage52middleage

T922youngT1835middleageT2770senior

T416young

T1225young

T|733middleage

46middleage

T25

T2770Senior

2.855555555555555555555555555

3.13.4假定BigUniversity的數(shù)據(jù)倉庫包含如下4個維:student(studenl_name,

area_id,major,status,university),course(course_name,department),

semester(semester,year)和instructor(dept,rank)；2個度量：count和avg_gradeo

在最低概念層，度量avg_grade存放同學的實際課程成果。在較高概念層，

avg_grade存放給定組合的平均成果。

(a)為該數(shù)據(jù)倉庫畫出雪花形模式圖。

(b)由基本方體［student,course,semester,instructor］開始，為歹出

BigUniversity每個同學的CS課程的平均成果，應使用哪些特別的

OLAP操作。

(c)假如每維有5層(包括all),如“student<major<status<university<an"，

該立方體包含多少方體？

解答：

a)為該數(shù)據(jù)倉庫畫出雪花形模式圖。雪花模式如圖所示。

b)由基本方體［student,course,semester,instructor］開始，為列出

BigUniversity每個同學的CS課程的平均成果，應使用哪些特別的

OLAP操作。

這些特別的聯(lián)機分析處理(OLAP)操作有：

i.沿課程(course)維從course_id"上卷"到department0

ii.沿同學(student)維從student_id"上卷"到universityo

iii.取department="CS"和university"aBigUniversity沿課程

(course)維和同學(student)維切片。

iv.沿同學(sludent)維從university下鉆至ljstudent_name。

c)假如每維有5層(包括all),如“student<majorvstatus<university<an",

該立方體包含多少方體？

這個立方體將包含54=625個方體。

courseunivstudent

維表

course_id

course_namc

department

semester

維表

seniester_id

semester

year

area

維表

instructor

維表area_id

Instructocidcity

deptprovince

rankcountry

題3.4圖題3.4中數(shù)據(jù)倉庫的雪花形模式

第四章

4.12022-11-29

4.2有幾種典型的立方體計算方法，

4.3題4.12考慮下面的多特征立方體查詢：按｛item,region,month｝的全

部子集分組，對每組找出2004年的最小貨架壽命，并對價格低于100美

元、貨架壽命在最小貨架壽命的1.25?1.5倍之間的元組找出總銷售額部分。

d)畫出該查詢的多特征立方體圖。

e)用擴充的SQL表示該查詢。

f)這是一個分布式多特征立方體嗎？為什

么？解答：

(a)畫出該查詢的多特征立方體圖。R0-Rl('

1.25*min(shelf)and^l.5*min(shelf))(b)用

擴充的SQL表示該查詢。

selectitem,region,month,Min(shelf),SUM(Rl)

from

Purchas

ewhere

year=20

04

cubebyitem,

region,month:RI

suchthatRI.shelf>1.25*MIN(Shelf)and(Rl.Shelf<1.5*MIN(ShelDand

Rl.Price<100

(c)這是一個分布式多特征立方體嗎？為什么？這不是一個分布多特征立

方體，由于在“suchthat”語句中采納了V條件。

4.42022-11-29

4.52022-11-29

第五章

5.1Apriori算法使用子集支持度性質的先驗學問。

節(jié)介紹了由頻繁項集產生關聯(lián)規(guī)章的方法。提出了一個更有效的方法。

解釋它為什么比節(jié)的方法更有效。(提示:考慮將習題5.1(b)和習題5.1(c)的性

質結合到你的設計中。)

5.3數(shù)據(jù)庫有5個事物。設min_sup=60%,

min_conf=80。T1D購買的商品

T100{M,0,N,K,E,

Y}

T200{D,O,N,K,E,

Y)T300{M,A,K,E)

T400{M,U,C,K,Y)

T500{C,0,0,K,I,E)

g)分別使用Apriori和FP增長算法找出全部的頻繁項集。比較兩種挖

掘過程的效率。

h)列舉全部與下面的的元規(guī)章匹配的強關聯(lián)規(guī)章(給出支持度s和

置信度c),其中，X是代表顧客的變量，item是表示項的變量(如

“A”、“B”等)：

□x匚transaction,buys(X,itemi)Abuys(X,item2)?buys(X,itemi)[s,c]

解答：

(a)分別使用Apriori和FP增長算法找出全部的頻繁項集。比較兩種挖掘

過程的效率。

Apriori算法：由于只有5次購買大事，所以肯定支持度是5xmin_sup=3?

YM3/

丫MO1/

:。3M:MK31

'N28

'ME2oo

:K5MYMYMK

y產y

'E400\o3M\OK3：

383oocX0KEy

-8='K5oo(L=f0E3oo(

oo2r=<KEY

18f“，0E3QO2]

，E4°°:KE

100[0Y00

0082

Y300KY3

1f

8KE4QO

200

008KY3

\00

8f

1/<EY205r

L,=[OKE3]

FP-growth：數(shù)據(jù)庫的第一次掃描與Apriori算法相同，得到Li。再按支持度

計數(shù)的遞減序排序，得到：汁｛(K:5),(E:4),(M:3),(O:3),(Y3)｝。掃描沒個事

務，按以上L的排序，從根節(jié)點開頭，得到FP-樹。

Root

E:4M:1

M:20:2Y:1

0:1Y:1

題5.3圖FP增長算法

項條件模式基條件FP樹產生的頻繁模式

Y{{KE,M,0:l},{K,E,O:1},{K,M:1}}K3{K,Y:3(

{{K,E,M:1},{KE:2}}

0K:3,E:3{K,O:3),{E,O:3},{K,E,O:3)

{{KE:2},(K:l)}

MK3{KM:3}

{{K:4}}

EK:4{KE:4}

效率比較：Apriori算法的計算過程必需對數(shù)據(jù)庫作多次掃描，而FP-增長算法在

構造過程中只需掃描一次數(shù)據(jù)庫，再加上初始時為確定支持度遞減排序的一次掃

描，共計只需兩次掃描。由于在Apriori算法中的自身連接過程產生候選項集，

候選項集產生的計算代價特別高，而FP-增長算法不需產生任何候選項。

(b)列舉全部與下面的的元規(guī)章匹配的強關聯(lián)規(guī)章(給出支持度s和置信度

c),其中，X是代表顧客的變量，item是表示項的變量(如"A”、“B”

等)：

□xDtransaction,buys(X,"K")八buys(X,"O")?buys(X,"E")[s=0.6,c=l]

□xDtransaction,buys(X,“E")/\buys(X,"E”)?buys(X,“K”)[s=0.6,c=l]

或也可表示為

K,0—>E[s(support)=0.6或60%,c(confidence)=1或100%]

E,O—>K[s(support)=0.6或60%,c(confidence)=l或100%]

5.4(實現(xiàn)項目)使用你熟識的程序設計語言(如C++或Java),實現(xiàn)本章介

紹的三種頻繁項集挖掘算法：

第6章分類和猜測6.1簡述決策樹分類的主要步驟。

6.26.11下表由雇員數(shù)據(jù)庫的訓練數(shù)據(jù)組成。數(shù)據(jù)已泛化。例如，age"31…

35”表示年齡在31~35之間。對于給定的行，count表示department,status,age

和salary在該行具有給定值的元組數(shù)。

departmentstatusagesalarycount

salessenior31…3546K-50K30

salesjunior26…3026K-30K40

salesjunior31…3531K-35K40

systemsjunior21-2546K-50K20

systemssenior31-3566K-70K5

systemsjunior26-3046K-50K3

systemssenior41…4566K-70K3

marketingsenior36-4046K—50K10

marketingjunior31…3541K-45K