Whatisdatamining?

i.數(shù)據(jù)挖掘工

就是從存放在數(shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的大量的數(shù)據(jù)中獲取有效

的、新穎的、潛在有用的、最終可理解的模式的昨平凡過(guò)程。

數(shù)據(jù)挖握(DataMining)?又稱為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(Knowledge

DiscoveryinDatabase,KDD)V就是從大量數(shù)據(jù)中獲取有效的、新穎的、潛在

有用的、最終可理解的模式的非平凡過(guò)程.面單的說(shuō).數(shù)據(jù)挖倔就是:從大量數(shù)

據(jù)中提取或。挖倔”知識(shí)。

2.數(shù)據(jù)倉(cāng)庫(kù)=

英文名稱望DataWarehouse.可簡(jiǎn)寫為D、V或DWH<?

定義：數(shù)據(jù)倉(cāng)庫(kù)是一個(gè)面向主筆的、集成的、相對(duì)穩(wěn)定的、反映歷史變化的

數(shù)據(jù)集用里決策。

數(shù)據(jù)各庫(kù)是決策支持系統(tǒng)(hss)和聯(lián)機(jī)分析應(yīng)用數(shù)據(jù)源的結(jié)構(gòu)化數(shù)據(jù)環(huán)境。

數(shù)據(jù)倉(cāng)庫(kù)研究和解決從數(shù)據(jù)庫(kù)中獲取信息的問(wèn)題-

數(shù)據(jù)倉(cāng)庫(kù)的四大關(guān)延特征，面向主題性、數(shù)據(jù)集成性、數(shù)據(jù)的時(shí)變性和數(shù)據(jù)

的昨易失性。

SupposeyourtaskasasoftwareengineeratBig-Universityistodesignadataminingsystemtoexamine

theiruniversitycoursedatabase,whichcontainsthefollowinginformation:thename,address,andstatus

(e.g.,undergraduateorgraduate)ofeaclistudent,thecoursestaken,andtheircumulativegradepoint

average(GPA).Describethearchitectureyouwouldchoose.Whatisthepurposeofeachcomponentofthis

architecture?

1.3假設(shè)你是BigUniversity的軟件工程師，任務(wù)是設(shè)計(jì)一個(gè)數(shù)據(jù)挖掘系統(tǒng)，分析學(xué)校課程數(shù)據(jù)庫(kù)。

該數(shù)據(jù)庫(kù)包括如下信息：每個(gè)學(xué)生的姓名、地址和狀態(tài)(例如本科生或研究生)、所修課程以及

他們的GPA(平均積分點(diǎn))。描述你要選取的結(jié)構(gòu)。該結(jié)構(gòu)的每個(gè)成分的作用是什么？

答：該應(yīng)用程序的數(shù)據(jù)挖掘的體系結(jié)構(gòu)應(yīng)包括以下主要組成部分：

?數(shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)，萬(wàn)維網(wǎng)或其他信息庫(kù)：這是一個(gè)或一組包含學(xué)生和課程信息數(shù)據(jù)庫(kù)、數(shù)

據(jù)倉(cāng)庫(kù)、電子表格或其他類型的信息庫(kù)；

?數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)服務(wù)器：根據(jù)用戶數(shù)據(jù)挖掘請(qǐng)求，數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)服務(wù)器負(fù)責(zé)提取相關(guān)

數(shù)據(jù)；

?知識(shí)庫(kù)：這是領(lǐng)域的知識(shí)，用于指導(dǎo)搜索或評(píng)估結(jié)果模式的興趣度。

?數(shù)據(jù)挖掘引擎：這是數(shù)據(jù)挖掘系統(tǒng)的基本部分，理想情況下由一組功能模塊組成，用于執(zhí)行

特征化、關(guān)聯(lián)和相關(guān)分析、分類、預(yù)測(cè)、聚類分析、離群點(diǎn)分析和演變分析等任務(wù)。

?模式評(píng)估模塊：該成分使用興趣度度量，并與數(shù)據(jù)挖掘模塊交互，以便將搜索聚焦在有興趣

的模式上。

?用戶界面：該模塊在用戶和數(shù)據(jù)挖掘系統(tǒng)之間通信，允許用戶與系統(tǒng)交互，說(shuō)明挖掘查詢或

任務(wù)，提供信息以幫助搜索聚焦，根據(jù)數(shù)據(jù)挖掘的中間結(jié)果進(jìn)行探索式數(shù)據(jù)挖掘。

Howisadatawarehousedifferentfromadatabase?Howaretheysimilar?

1.4數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)庫(kù)有何不同？有哪些相似之處？p8

答：區(qū)別：數(shù)據(jù)倉(cāng)庫(kù)是面向主題的，集成的，不易更改且隨時(shí)間變化的數(shù)據(jù)集合，用來(lái)支持

管理人員的決策，數(shù)據(jù)庫(kù)由一組內(nèi)部相關(guān)的數(shù)據(jù)和一組管理和存取數(shù)據(jù)的軟件程序組成，是面向

操作型的數(shù)據(jù)庫(kù)，是組成數(shù)據(jù)倉(cāng)庫(kù)的源數(shù)據(jù)。它用表組織數(shù)據(jù)，采用ER數(shù)據(jù)模型。

相似：它們都為數(shù)據(jù)挖掘提供了源數(shù)據(jù)，都是數(shù)據(jù)的組合。

Brieflydescribethefollowingadvanceddatabasesystemsaudapplications:object-relationaldatabases,

spatialdatabases,textdatabases,iiiultiinediadatabases,theWorldWideWeb.

1.5簡(jiǎn)述以下高級(jí)數(shù)據(jù)庫(kù)系統(tǒng)和應(yīng)用：對(duì)象-關(guān)系數(shù)據(jù)庫(kù)、空間數(shù)據(jù)庫(kù)、文本數(shù)據(jù)庫(kù)、多媒體數(shù)據(jù)

庫(kù)、流數(shù)據(jù)和萬(wàn)維網(wǎng)。

答：對(duì)象一關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)是基于面向?qū)ο蟮木幊谭妒降臄?shù)據(jù)是大量對(duì)象類和類層次結(jié)構(gòu)

組織。每個(gè)實(shí)體在數(shù)據(jù)庫(kù)中被視為?個(gè)對(duì)象。該對(duì)象包含一組變量描述的對(duì)象，一組消息的對(duì)象

可以使用的溝通與其他物體或與其余的數(shù)據(jù)庫(kù)系統(tǒng)，以及一套方法，每種方法持有的代碼實(shí)現(xiàn)一

個(gè)消息。

空間數(shù)據(jù)庫(kù)包含空間有關(guān)的數(shù)據(jù)，這可能是代表的形式，柵格或矢量數(shù)據(jù)。柵格數(shù)據(jù)包括n

維位圖或像素地圖，矢量數(shù)據(jù)是由點(diǎn)，線，多邊形或其他種類的圖元處理，一些例子包括地理空

間數(shù)據(jù)庫(kù)(圖)數(shù)據(jù)庫(kù)，超大規(guī)模集成電路芯片設(shè)計(jì)，以及醫(yī)療和衛(wèi)星圖像數(shù)據(jù)庫(kù)。

文本數(shù)據(jù)庫(kù)包含文木文件或其他長(zhǎng)句或段落格式的文字說(shuō)明，如產(chǎn)品規(guī)格、誤差或錯(cuò)誤報(bào)告、

警告信息、總結(jié)報(bào)告、說(shuō)明或其他文件。

多媒體數(shù)據(jù)庫(kù)存儲(chǔ)的圖像，音頻，視頻數(shù)據(jù)，并應(yīng)用于諸如圖像、基于內(nèi)容的檢索、語(yǔ)音郵

件系統(tǒng)、視頻點(diǎn)播系統(tǒng)、互聯(lián)網(wǎng)和以語(yǔ)音為基礎(chǔ)的用戶界面。

流數(shù)據(jù)是一類新的數(shù)據(jù)的產(chǎn)生和分析，其中數(shù)據(jù)動(dòng)態(tài)地從觀測(cè)平臺(tái)(或窗口)流進(jìn)或流出。

特點(diǎn)：海量甚至可能無(wú)限，動(dòng)態(tài)變化，以固定的次序流進(jìn)或流出，只允許一遍或少數(shù)幾遍掃描，

要求快速響應(yīng)時(shí)間。如電力供應(yīng)、網(wǎng)絡(luò)通信、股票交易、電信、Web點(diǎn)擊流、視頻監(jiān)視和氣象或

環(huán)境監(jiān)控?cái)?shù)據(jù)。

萬(wàn)維網(wǎng)上提供豐富的、全世界范圍內(nèi)的聯(lián)機(jī)信息服務(wù)，其中的數(shù)據(jù)對(duì)象鏈接在一起便于交互訪問(wèn)。

與之關(guān)聯(lián)的分布式信息服務(wù)的例子如：美國(guó)在線，雅虎！AltaVista等。

Defineeachofthefollowingdataminingfunctionalities:characterization,discrimination,associationand

correlationanalysis,classification,prediction,clustering,andevolutionanalysis.Giveexamplesofeachdata

miningfmictionality.usingareal-lifedatabasetliatyouarefamiliarwith.

1.6定義下列數(shù)據(jù)挖掘功能：特征化、區(qū)分、關(guān)聯(lián)和相關(guān)分析、預(yù)測(cè)聚類和演變分析。使用你熟

悉的現(xiàn)實(shí)生活的數(shù)據(jù)庫(kù)，給出每種數(shù)據(jù)挖掘功能的例子。

答：特征化是一個(gè)目標(biāo)類數(shù)據(jù)的一般特性或特性的匯總。例如，學(xué)生的特征可被提出，形成所有

大學(xué)的計(jì)算機(jī)科學(xué)專業(yè)一年級(jí)學(xué)生的輪廓，這些特征包括作為一種高的年級(jí)平均成績(jī)(GPA：Grade

pointaversge)的信息，

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

區(qū)分是將目標(biāo)類數(shù)據(jù)對(duì)象的一般特性與一個(gè)或多個(gè)對(duì)比類對(duì)象的一般特性進(jìn)行比較。例如，

具有高GPA的學(xué)生的一般特性可被用來(lái)與具有低GPA的?般特性比較。最終的描述可能是學(xué)生的

一個(gè)?般可比較的輪廓，就像具有高GPA的學(xué)生的75%是四年級(jí)計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生，而具有低

GPA的學(xué)生的65%不是。

關(guān)聯(lián)是指發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，這些規(guī)則表示一起頻繁發(fā)生在給定數(shù)據(jù)集的特征值的條件。例如，-

個(gè)數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則為：major(X,"computingscience")=owns(X,wpersonal

computer")

[support=12%,confidence=98%]其中，X是一個(gè)表示學(xué)生的變量。這個(gè)規(guī)則指出正在學(xué)習(xí)的學(xué)

生，12%

（支持度）主修計(jì)算機(jī)科學(xué)并且擁有一臺(tái)個(gè)人計(jì)算機(jī)。這個(gè)組一個(gè)學(xué)生擁有一臺(tái)個(gè)人電腦的概率

是98%（置信度，或確定度）。

分類與預(yù)測(cè)不同，因?yàn)榍罢叩淖饔檬菢?gòu)造一系列能描述和區(qū)分?jǐn)?shù)據(jù)類型或概念的模型（或功

能），而后者是建立一個(gè)模型去預(yù)測(cè)缺失的或無(wú)效的、并且通常是數(shù)字的數(shù)據(jù)值。它們的相似性

是他們都是預(yù)測(cè)的工具：

分類被用作預(yù)測(cè)目標(biāo)數(shù)據(jù)的類的標(biāo)簽，而預(yù)測(cè)典型的應(yīng)用是預(yù)測(cè)缺失的數(shù)字型數(shù)據(jù)的值。

聚類分析的數(shù)據(jù)對(duì)象不考慮己知的類標(biāo)號(hào)。對(duì)象根據(jù)最大花蕾內(nèi)部的相似性、最小化類之間

的相似性的原則進(jìn)行聚類或分組。形成的每簇可以被看作?個(gè)對(duì)象類。聚類也便于分類法組織

形式，將觀測(cè)組織成類分

層結(jié)構(gòu)，把類似的事件組織在一起。

數(shù)據(jù)演變分析描述和模型化隨時(shí)間變化的對(duì)象的規(guī)律或趨勢(shì)，盡管這可能包括時(shí)間相關(guān)數(shù)據(jù)

的特征化、區(qū)分、關(guān)聯(lián)和相關(guān)分析、分類、或預(yù)測(cè)，這種分析的明確特征包括時(shí)間序列數(shù)據(jù)分析、

序列或周期模式匹配、和基于相似性的數(shù)據(jù)分析

Supposethatthevaluesforagivensetofdataaregroupedintoiutervals.Theintervalsandcorresponding

frequenciesarcasfollows.

2.2假設(shè)給定的數(shù)據(jù)集的值已經(jīng)分組為區(qū)間。區(qū)間和對(duì)應(yīng)的頻率如下。

年齡頻率

「5200

515450

15~20300

20~501500

50~80700

80^11044

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

解答：先判定中位數(shù)區(qū)間：N=200+450+300+l500+700+44=3194；N/2=1597

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

，20-50對(duì)應(yīng)中位數(shù)區(qū)間。

我們有：Zi=20,心3197,(沙卻尸950,.加%“〃力1500,故而加=30,使用公

式(2.3)：

,(心’2](3197/2-950)__?

median=Z.+---------------width=20+,------------x30=32.97

Ifreq—\I1500)

:.median=32.97歲。

Supposethatthedataforanalysisincludestheattributeage.Theagevaluesforthedatatuplesare(in

increasingorder)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.

2.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,

70o

答；

(a)Whatisthemeanofthedata?Whatisthemediant

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

均值

=(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)/

27

=29.96

x=—V.r=809/27=29.96230(公式2.1)。

中位數(shù)應(yīng)是第14個(gè),即xl4=25=Q2。

(b)Whatisthemodeofthedata?Commentonthedata'smodality(i.e.,biniodal,triniodal,etc.).

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

這個(gè)數(shù)集的眾數(shù)有兩個(gè)：25和35,發(fā)生在同樣最高的頻率處,因此是雙峰眾數(shù)。

(c)Whatisthemidrangeofthedata?

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

數(shù)據(jù)的中列數(shù)是最大數(shù)和最小數(shù)的均值。即：midrange=(70+13)/2=41.5?

(d)Canyoufind(roughly)thefirstquartile(QI)andthethirdquartile(Q3)ofthedata?

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

數(shù)據(jù)集的第一個(gè)四分位數(shù)應(yīng)發(fā)生在25%處，即在(N+1)/公(27+1)/4=7處。所以：0=20。

而第三個(gè)四分位數(shù)應(yīng)發(fā)生在75%處，即在3X(N+1)/4=21處。所以：48=35

(e)Givethefive-numbersummaryofthedata.

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

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

大值構(gòu)成。它給出了分布形狀良好的匯總+并且這些數(shù)據(jù)是：13、20、25、35、70。

(f)Showaboxplotofthedata.

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

(g)Howisaquantile-quantileplotdifferentfromaquantileplot?

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

分位數(shù)圖是一種用來(lái)展示數(shù)據(jù)值低于或等于在一個(gè)單變量分布中獨(dú)立的變量的粗略百分比。

這樣，他可以展示所有數(shù)的分位數(shù)信息，而為獨(dú)立變量測(cè)得的值(縱軸)相對(duì)于它們的分位數(shù)(橫

軸)被描繪出來(lái)。但分位數(shù)一分位數(shù)圖用縱軸表示一種單變量分布的分位數(shù),用橫軸表示另一單變

量分布的分位數(shù)。兩個(gè)坐標(biāo)軸顯示它們的測(cè)量值相應(yīng)分布的值域，且點(diǎn)按照兩種分布分位數(shù)值展

示。一條線(y=x)可畫到圖中+以增加圖像的信息。落在該線以上的點(diǎn)表示在y軸上顯示的值的

分布比x軸的相應(yīng)的等同分位數(shù)對(duì)應(yīng)的值的分布高。反之,對(duì)落在該線以下的點(diǎn)則低。

2.7使用習(xí)題2.4給出的age數(shù)據(jù)回答下列問(wèn)題：

(a)使用分箱均值光滑對(duì)以上數(shù)據(jù)進(jìn)行光滑，箱的深度為3。解釋你的步驟。評(píng)述對(duì)于給

定的數(shù)據(jù)，該技術(shù)的效果。

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

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

解答：

(a)使用分箱均值光滑對(duì)以上數(shù)據(jù)進(jìn)行光滑，箱的深度為3。解釋你的步驟。評(píng)述對(duì)于給定

的數(shù)據(jù)，該技術(shù)的效果。

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

步驟1：對(duì)數(shù)據(jù)排序.(因?yàn)閿?shù)據(jù)己被排序，所以此時(shí)不需要該步驟。)

步驟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

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

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

箱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ù)中的離群點(diǎn)？

聚類的方法可用來(lái)將相似的點(diǎn)分成組或“簇”，并檢測(cè)離群點(diǎn)。落到簇的集外的值可以被視

為離群點(diǎn)。作為選擇，一種人機(jī)結(jié)合的檢測(cè)可被采用，而計(jì)算機(jī)用一種事先決定的數(shù)據(jù)分布來(lái)區(qū)

分可能的離群點(diǎn)。這些可能的離群點(diǎn)能被用人工輕松的檢驗(yàn)，而不必檢查整個(gè)數(shù)據(jù)集。

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

其它可用來(lái)數(shù)據(jù)光滑的方法包括別的分箱光滑方法，如中位數(shù)光滑和箱邊界光滑。作為選擇，

等寬箱可被用來(lái)執(zhí)行任何分箱方式，其中每個(gè)箱中的數(shù)據(jù)范圍均是常量。除了分箱方法外，可以

使用回歸技術(shù)擬合成函數(shù)來(lái)光滑數(shù)據(jù)，如通過(guò)線性或多線性回歸。分類技術(shù)也能被用來(lái)對(duì)概念分

層，這是通過(guò)將低級(jí)概念上卷到高級(jí)概念來(lái)光滑數(shù)據(jù)。

Supposeahospitaltestedtheageandbodyfatdatafor18randomlyselectedadultswiththefollowing

result

2.9假設(shè)醫(yī)院檢測(cè)隨機(jī)選擇的18個(gè)成年人年齡和身體脂肪數(shù)據(jù)，得到如下結(jié)果：

age232327273941474950

%fat9.526.57.817.831.425.927.427.231.2

age525454565758586061

%fat34.642.528.833.430.234.132.941.235.7

(a)Calculatethemean,medianandstandarddeviationofageand%fat.

(a)計(jì)算年齡和脂肪百分比的均值、中位數(shù)和標(biāo)準(zhǔn)差.

年齡均值=(23+23+27+27+39+41+47+49+50+52+54+54+56+57+58+58+60+61)/18=836/18=46.44,

中位數(shù)=(50+52)/2=51,

標(biāo)準(zhǔn)差=方差的平方根=開(kāi)根號(hào)(l/n[E(Xi)2-l/n(￡Xi)2])=開(kāi)根號(hào)1/18[2970.44>12.85.

脂肪百分比均值=28.78,中位數(shù)=30.7,標(biāo)準(zhǔn)差=8.99.

(b)Drawtheboxplotsforageand%fat.

(b)繪制年齡和脂肪百分比的盒圖

60

55

50

4540

s如

es35

n3o30

e

<B>25

>20

3515

3010

25

%fat

(c)Drawascatterplotandaq-qplotbasedonthesetwovariables.

(c)根據(jù)這兩個(gè)屬性,繪制散布圖，各q-q圖

q-q圖散布

(d)Normalizethetwovariablesbasedonz-scorenormalization.

(d)根據(jù)z-score規(guī)范化來(lái)規(guī)范化這兩個(gè)屬性(P46)

232327273941474950

z-age-1.83-1.83-1.51-1.51-0.58-0.420.040.200.28

%fat9.526.57.817.831.425.927.127.231.2

z-%fat-2.14-0.25-2.33-1.220.29-0.32-0.15-0.180.27

525454565758586061

z-age0.430.590.590.740.820.900.901.061.13

%fat34.642.528.833.430.234.132.941.235.7

z-%fat0.651.530.00.510.1G0.590.461.38().77

(e)Calculatethecorrelationcoefficient(Person'sproductmomentcoefficient).Arethesetwovariables

positivelyornegativelycorrelated?

(e)計(jì)算相關(guān)系數(shù)(皮爾遜積矩系數(shù)).這兩個(gè)變量是正相關(guān)還是負(fù)相關(guān)？

r4E(a,-A)(b.-B)/NoAo?=(E(a.b.)-NAB)/NoAoB=(E(a,b()-18*46.44*28.78)

/18*12.85*8.99=0.82

相關(guān)系數(shù)是0.82。變量呈正相關(guān)。

2.10.Whatarethevaluerangesofthefollowingnormalizationmethods?

(a)min-maxnormalization

(b)z-scorenormalization

(c)normalizationbydecimalscaling

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

答：

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

值域是［new_min,new_max］。

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

值域是［(oldjnin-mean)/。，(oldjnax-mean)/o］,總的來(lái)說(shuō)，對(duì)于所有可能的數(shù)據(jù)集的值域

是(-8,+8)。

(c)小數(shù)定標(biāo)規(guī)范化。

值域是(一L0,1.0)。

Supposethatadatawarehouseconsistsofthethreedimensionstime,doctor,andpatient,andthetwo

measurescountandcharge,wherechargeisthefeethatadoctorchargesapatientforavisit.

3.3(P97)假定數(shù)據(jù)倉(cāng)庫(kù)包含三維：time,doctor和patient;和兩個(gè)度量：count和charge;

其中，charge是醫(yī)生對(duì)病人一次診治的收費(fèi)。

(a)列舉三種流行的數(shù)據(jù)倉(cāng)庫(kù)建模模式

答：三類模式一般用于建模數(shù)據(jù)倉(cāng)庫(kù)架構(gòu)的星形模型，雪花模型和事實(shí)星座模型。

(b)使用(a)列舉的模式之一，畫出上面的數(shù)據(jù)倉(cāng)庫(kù)的模式圖

timedoctor

diinensioutablefacttablediineusiontable

數(shù)據(jù)倉(cāng)庫(kù)的星形模型

(C)山基本方體［day,doctor,patient］開(kāi)始，為列出2004年每位醫(yī)生的收費(fèi)總數(shù)，應(yīng)當(dāng)執(zhí)行

哪些OLAP操作？沿課程(course)維從courseid“上卷”到department。

?沿時(shí)間(.time｝維從day"上卷"至ljyearo

?取time=2004,對(duì)維/加e作“切W操作

?沿病人patient｝維從個(gè)別病人“上卷”到全部病人。

(d)為得到同樣結(jié)果，寫一個(gè)SQL查詢。假定數(shù)據(jù)存放在關(guān)系數(shù)據(jù)庫(kù)中，其模式為

fee(day,month,year,doctor,hospital,patient,count,charge)。

答：SQL查詢語(yǔ)句如下：

selectdoctor,SUM(charge)

fromfee

whereyear=2004

groupbydoctor

3.5.Supposethatadatawarehouseconsistsofthefourdimeiisioiis.date,spectator,location,andgame,andthe

twomeasures,countandcharge,wherechargeisthefarethataspectatorpayswhenwatchingagameona

givendate.Spectatorsmaybestudents,adults,orseniors,witheachcategoryhavingitsownchargerate.

3.5(P98)假定數(shù)據(jù)倉(cāng)庫(kù)包含4維：date,spectator,location,和game,和兩個(gè)度量：counl和charge;

其中，charge是觀眾在給定的日期觀看節(jié)目的付費(fèi)。觀眾可以是學(xué)生、成年人或老年人，每類觀

眾有不同的收費(fèi)標(biāo)準(zhǔn)。

(a)畫出該數(shù)據(jù)倉(cāng)庫(kù)的星形模式圖。

答：星形模式圖如下：

datesalesspectator

dimeusiontablefacttabledimensiontable

b.由基本方體［date,location,game］開(kāi)始，為列出2004年學(xué)生觀眾在GM_Place的總

付費(fèi)，應(yīng)執(zhí)行的OLAP操作：

?沿時(shí)間(date)塘仄date_id"上卷"到y(tǒng)earQ

?沿時(shí)間(game)維從game_id“上卷”到全部。

?沿時(shí)間(location)墉吠location_id”上卷"至Ulocation_name。

?沿時(shí)間(spectator雄Jkspectatojid“上卷”到status。

?以status="students"、locationname=^GMPlace"andyear三勿。4作轉(zhuǎn)軸操作

3.6.\C(mtribute(lbyTaoCheng\Adatawarehousecanbemodeledbyeitherastarschemaorasnowflake

schema.Brieflydescribethesimilaritiesandthedifferencesofthetwomodels,andthenanalyzetheir

advantagesanddisadvantageswithregardtooneanother.Giveyouropinionofwhichmightbemore

empiricallyusefulandstatethereasonsbehindyouranswer.

3.6數(shù)據(jù)倉(cāng)庫(kù)可以用星形模式或雪花模式建模。簡(jiǎn)略討論這兩種模式的相似點(diǎn)和不同點(diǎn)，然后分

析它們的相對(duì)做優(yōu)、缺點(diǎn)。哪種模式更實(shí)用，給出你觀點(diǎn)并陳述你的理由。

答:星形模式或雪花模式的相似點(diǎn)是它們包含一個(gè)事實(shí)表和一些維表。它們主要的不同在于，

雪花模式的維表可能是規(guī)范化形式，以便減少了冗余，這種表易于維護(hù)并節(jié)省存儲(chǔ)空間。然而，

與巨大的事實(shí)表相比，這種空間的節(jié)省可以忽略。此外，由于執(zhí)行查詢需要更多的連接操作，雪

花形結(jié)構(gòu)可能降低瀏覽的性能，這樣，系統(tǒng)的性能可能相對(duì)的受到影響。星型模式的優(yōu)點(diǎn)是簡(jiǎn)單、

這使得它更有效，但它需要更多的空間。因此，只要空間的要求不是太大時(shí)，星形模式比雪花模

式更好，因?yàn)橥ǔＰ时瓤臻g具有更高的優(yōu)先級(jí)。在工業(yè)上，有時(shí)可能將數(shù)據(jù)從一個(gè)雪花模式非

規(guī)范化為星型模式以加快處理速度，另一種選擇是保持雪花模式的維表，然后相同數(shù)據(jù)的當(dāng)前用

戶折疊為星形。

4.4.SupposethatabasecuboidhasthreedimensionsA.B.C.withthefollowingnumberofcells:\A\=

1.000,000,|B|=10(),and\C\=1000.Supposethateachdimensionisevenlypartitionedinto10por-

tionsforchunking.

4.4假定基本方體有三維A,B,C,其單元數(shù)如下：IAH1000000,|B1=100,|C|=1000.假定每維均等

地分塊成10部分。

(a)假定每維只有一層，畫出完整的立方體的格。

答：完整的立方體的格如下圖

ABC

(b)如果每個(gè)立方體單元存放一個(gè)4字節(jié)的度量，若立方體是稠密的，所計(jì)算的立方體有多大？

答：所計(jì)算的立方體大小如下：

all：1

A:1,000,000;B\100;C:1,000;小計(jì)：1,001,100

AB:1,000,000*100=100,000,000;BC\100*1,000=100,000;AC:

1,000,000*1,000=1,000,000,000;

小計(jì):1,100,100,000

ABC:1,000,000*100*1,000=100,000,000,000

總和：1+1,001,100+1,100,100,000+100,000,000,000=101,101,101,101*4=

404,404,404,404字節(jié)

(C)指出空間需求量最小的立方體中的塊計(jì)算次序，并計(jì)算2-D平面計(jì)算所需要的內(nèi)存空間總

量。

答：順序計(jì)算，需要最少數(shù)量的空間B-C-A.如圖所示：

ALL

ABC

計(jì)算二維平面需要的總主內(nèi)存空間是：

總空間=(100X1,000)+(1,000,000X10)+(100X10,000)=20,100,000單元*4字節(jié)/單元=

80,400,000字節(jié)

4.12.Considerthefollowingmultifeaturecubequery:Groupingbyallsubsetsof{item,t,egion,month},findthe

minimumshelflifein2(X)4foreachgroup,andthefractionofthetotalsalesduetotupleswhosepriceis

lessthan$100.andwhoseshelflifeisbetween1.25and1.5oftheiiiininnnnshelflife.

4.12考慮下面的多特征立方體查詢：按也em,region,小。〃統(tǒng)｝的所有子集分組，對(duì)每組找出200祚的

最小貨架壽命，并對(duì)價(jià)格低于100美元，最小貨架壽命在1.25~1.5之間的元組找出總銷售額部分。

(a)畫出該查詢的多特征立方體圖。P126

R0―>R1(>=1.25*min(shelf)and<=1.5*min(shelf))

(b)用擴(kuò)充的SQL表示查詢

selectitem,region,month,MIN(shelf),SUM(R1)

fromPurchases

whereyear=2004

cubebyitem,region,month:RI

suchthat(R1.Shelf>=1.25*MIN(Shelf)andR1.Shelf<=1.5*MIN(Shelf))andRI.Price<100

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

答：不，這不是一個(gè)分布式的多特征立方體。因?yàn)樵趕uchthat子句中含有<=的條件。

5.1.TheApriorialgorithmusespriorknowledgeofsubsetsupportproperties.

5.l.Apriori算法使用子集支持性質(zhì)的先驗(yàn)知識(shí)。

(a)證明頻繁項(xiàng)集的所有非空的子集也必須是頻繁的。

答：設(shè)s是一個(gè)頻繁項(xiàng)集，加/sup是最小支持度閥值，任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的

集合，|D|是D有事務(wù)量，則有力⑷=|D|；

再設(shè)s'是s的非空子集，則任何包含項(xiàng)集s的事務(wù)將同樣包含項(xiàng)集s',即：

support_count(s))>supportcount(s)=min_supX|D|.

所以，s'也是一個(gè)頻繁項(xiàng)集。

(b)證明項(xiàng)集s的任意非空子集s，的支持至少和s的支持度一樣大。

答：設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的集合，|D|是D的事務(wù)量，由定義得：

上,.suvporLcount(s)

supports)=—―—---

設(shè)s'是s的非空子集，由定義得：support0)=support瑞unt(s')

由(a)可知：supports')>support(s)

由此證明，項(xiàng)集S的任意非空子集S，的支持至少和S的支持度一樣大。

(C)給定頻繁項(xiàng)集I和I的子集s,證明規(guī)則"s’=(/一『)”的置信度不可能大于“S=(2-S)”

答：設(shè)s是/的子集，則前dence(s=(/-s))=::圖;，?).

confidence(s/=^(l—s'))=再;:

設(shè)s'是S的非空子集，則support)

由(b)可知：support_count(sf)>supportcount(s),

此外，confidenceks1)=(/-$'))Wconfidence's)今(J-s))

所以，規(guī)則“s'今°一『)”的置信度不可能大于"s)”。

5.3.Adatabasehasfivetransactions.Letmin^sup=60%andmin^conf=80%.

5.3設(shè)數(shù)據(jù)庫(kù)有5個(gè)事務(wù)。設(shè)minsup=60%,minconf=80%

TIDitems.bought

TWO{M,O,N,K,E,Y)

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

T300{M,A,K,E)

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

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

（a）分別使用Apriori和FP增長(zhǎng)算法找出所有頻繁項(xiàng)集。比較兩種挖掘過(guò)程的效率。

mo1

mk3

me2

my2

ok3oke3

oe3key2

oy2

ke4

ky3

ey2

FP-growth:SeeFigure5.2fortheFP-tree.

itemconditionalpatternbaseconditionaltreefrequentpattern

y{{k,e,m,o:l},{k,e,o:l},{k,m:l}}k:3{k,y：3}

0{{k,e,m:l},{k,e:2)k:3,e:3{k,o:3},{e,o:3},{k,e,o:3}

m{{k,e:2},{krl}}k:3{k,m:3}

e{{k：4}}k:4{k,e:4}

效率比較：Apriori需多次掃描數(shù)據(jù)庫(kù)而FP增長(zhǎng)建立FP樹(shù)只需一次的掃描。在Apriori算法中

產(chǎn)生候選是昂貴的（由于聯(lián)接），而FP增長(zhǎng)不產(chǎn)生任何候選。

（b）列舉所有與下面的元規(guī)則匹配的強(qiáng)關(guān)聯(lián)規(guī)則（給出支持度S和置信度C），其中，X是代表顧

客的變量，item,是表示項(xiàng)的變量（如："A”、"B”等）：

VT€transaction,btiys(X,item\)Abuys(X、itern2)=buys(X,item3)卜c]

答：k,o—>e[0.6,1]

e,o—?k10.6JJ

5.5.Adatabasehasfourtransactions.Letmin^sup=60%andmin^conf=80%.

5.5.數(shù)據(jù)庫(kù)有4個(gè)事務(wù),設(shè)minsup=60%,minconf=80%

CUSLJDTIDitemsJxjught(intheformofbrand-ilcm^category)

01T100{King's-Crab.Sunset-Milk.Dairyland-Cheese,Best-Bread}

02T200{Best-Cheese,Dairyland-Milk,Goldenfarm-Apple.l'asty-Pie,Wonder-Bread}

01T300{Westcoast-Apple,Dairyland-Milk,Wonder-Bread,Tasty.Pic}

03T100{Wonder-Bread,Sunset-Milk.Dairyland-Clicese)

(a)在item_category粒度(例如，itenn可以是"Milk"),對(duì)于下面的規(guī)則模板

YX€transaction^buys(X、Abuys(X,item2)abuys(X,items)[s,c]

對(duì)最大的k,列出頻繁k項(xiàng)集包含最大的k的頻繁k項(xiàng)集的所有強(qiáng)關(guān)聯(lián)規(guī)則(包括它們的支持度S

和置信度c).

(b)在粒度(例如：item1可以是“Sunset-Milk”)對(duì)于下面的規(guī)則模板

YXGcustomer,buys(X,item\)Abuys(X,item2)=>buys(<X.item2)

對(duì)最大的k,列出頻繁k項(xiàng)集(但不輸出任何規(guī)則)。

k=3andthefrequent3-itemsetis{Bread,Milk,Cheese}.Therulesare

BreadACheese今Milk,[75%,100%]

CheesAMilk=>Bread,[75%,100%]

CheeseMilkABread,[75%,100%]

5.10.SupposethatadatarelationdescribingstudeutsatBigUniversityhasbeengeueralizedtothegeneralized

relationRinTable5.1.

5.10假定描述BigUniversity大學(xué)生的數(shù)據(jù)關(guān)系已泛化為表5-13的廣義關(guān)系R.(題目見(jiàn)P179)

(a)畫出status,major,age,nationality的概念分層

學(xué)生可以輕松地勾勒出相應(yīng)的概念層次。

(b)寫一個(gè)程序，對(duì)所有層使用?致的支持度，詳見(jiàn)P179

status(X,''underxfraduaten)Amajor(X,**science^)=>gpa(X,“3.6…4.O”)[20%100%]

status(X,"undergraduate")Amajor(X,"appLsciences=gpa(X,“3,2…3.6”)[43%,100%]

status(X,"undergraduaten)Aage(X.Uyoung^)ngpa(X."3.2…3.6")[55%,71%]

status(X,''undergraduate1")Anationality(X,"North^America=9-gpa(X,u3.2...3.6^)[42%,62%]

major(X,“science")Anationality(X,“North.America")今gpa(X,“36.4?！?[20%,100%]

majorfX,''appLsciencesAnationality(X,"'North^American)>gpa(X,“32…3.6”)[31%,100%]

major(X,"science")Aage(X,''young"')=gpa(X.“3.6…4.0”)[20京,100%]

major(X."appLsciences")Aage(X,"young")"gpa(X,“3.2…3.6")[43%,100%]

age(X,^young^)Anationality(X.“North^Amcriai”)ngpa(X,'*3.2...3.6^)[42%,65%]

status(X,**juniorn)=major(X."engineering")=gpa(X,“32,36”)[21%100%]

statusfX,“junior”)Aage(X,21...25)=>gpa(X,”3.2…3.6”)[21%,83.5%]

status(X,"junior^)Anationality(X,“Canada")=gpa(X,“3.2...3.6”,[28%,77%]

major(X,''engineering^)Aage(X,21...25)=>gpa(X.**3.2...3.6^)[21%.100%]

age(X,16...20)Anationality(X,^Canada*7=ffpa(X.**3.2...3.6^)[30%,80%]

.(c)使用層交叉單項(xiàng)過(guò)濾，詳見(jiàn)P179

s￡a加s(X,“亍”加””)Aage(X,T6...20")號(hào)輛(X,“3?2,?,3.6”)[20%,58%]

statuslx.^senior^)Aage(X,“16...20")=gpa(X,“3.6...4.0")[14%,77%]

S￡Q加S(X,“PW)age(X,“26…30")/\=gpa(X,“3.6…4.0”)[12%,100%]

status(X,junior^)A7iQt，<mQ/My(X,"E〃rope")=^gpQ(X,“3.2...3.6”)[13%,100%]

statuslx,usenior'y)nationality[XikCanaday')=>gpa(X,U3.2...3.G,?)[14%,85%]

major(X,"math")Aage(X^16...20)=gpa(X,“36.40”)[11%,100%]

majorlx,French)Aagc(X,16…20)=gpa(X,“3.2…3.6")[12%,92%]

majoRx,"cs”)△na￡，a2a/i￡"(X,"Ca7zada")=gpa(X,“3.2...3.6”)[18%,100%]

major(X,“engineering”)f\nationality[X.^Canada')=^gpa(X,u3.2...3.6,5)[12%,100%]

major(X,“French")A〃Q/ioRa/4v(X,“Ca7ZQda")=>gpa(X,"3.233.6")[12口.96%]

age(X^21...25)Anationality[XuCanada'')=>gpa(X,u3.2...3.Gn)[12%,100%]

5.14.Thefollowingcontingencytablesummarizessupermarkettransactiondata,wherehotdogsreferstothe

transactionscontaininghotdogs,hotdogsreferstothetransactionsthatdonotcontainhotdogs,hamburgers

referstothetransactionscontaininghamburgers,andhajiiburgcrsreferstothetransactionsthatdonot

containhamburgers.

5.14下面的相依表匯總了超級(jí)市場(chǎng)的事務(wù)數(shù)據(jù)。其中，hotdogs表示包含熱狗的事務(wù)，hotdogs

表示不包含熱狗的事務(wù)，hamburgers表示包含漢堡包的事務(wù)，hamburgers表示不包含漢堡包的事

務(wù)，

hotdogshotdogsErow

hamburgers2,0005002.500

hamburgers1,00()1,5002,500

^col3,0002.000

(a)假定挖掘出了關(guān)聯(lián)規(guī)則?"dogs=hamburgers''o給定最小支持度閥值25%,最小置信度

閥值50%,該關(guān)聯(lián)規(guī)則是強(qiáng)規(guī)則嗎？

答：根據(jù)規(guī)則，support=2000/5000=40%,confidence=2000/3000=66.7%,該關(guān)聯(lián)規(guī)則是

強(qiáng)規(guī)則.

(b)根據(jù)給定的數(shù)據(jù)，買hotdogs獨(dú)立于買humburgers嗎？如果不是，二者之間存在何種相

關(guān)聯(lián)系。

答：corr{hotdog;hamburger}=P({hotdog,hamburger})/(P({hotdog})

P({hamburger})=Q.4/(0.5X0.6)=1.33>1.所以，買hotdogs不是獨(dú)立于買humburgers。

兩者存在正相關(guān)關(guān)系

6.1.Brieflyoutlinethemajorstepsofdecisiontreeclassification.

6.1筒述決策樹(shù)分類的主要步驟。

G.6.Givena5GBdatasetwith50attributes(eachcontaining100distinctvalues)and512MBofmainmemory

inyourlaptop,outlineanefficientmethodthatconstructsdecisiontreesinsuchlargedatasets.Justify

youranswerbyroughcalculationofyourmainmemoryusage.

6.6給定一個(gè)具有50個(gè)屬性(每個(gè)屬性包含100個(gè)不同值)的5GB的數(shù)據(jù)集，而你的臺(tái)式機(jī)有

512M內(nèi)存。簡(jiǎn)述對(duì)這種大型數(shù)據(jù)集構(gòu)造決策樹(shù)的一種有效算法。通過(guò)粗略地計(jì)算機(jī)主存的使用說(shuō)

明你的答案是正確的。

WewillusetheRainForestalgorithmforthisproblem.AssumethereareCclasslabels.Themostmemory

requiredwillbeforAVC-setfortherootofthetree.TocomputetheAVC-setfortherootnode,wescan

thedatabaseonceandconstructtheAVC-listforeachofthe50attributes.ThesizeofeachAVC-listis

100xC.ThetotalsizeoftheAVC-setisthen100xCx50,whichwilleasilyfitinto512MBofmemory

forareasonableC.ThecomputationofotherAVC-setsisdoneinasimilarwaybuttheywillbesmaller

becausetherewillbelessattributesavailable.ToreducethenumberofscanswecancomputetheAVC-set

fornodesatthesamelevelofthetreeinparallel.WithsuchsmallAVC-setspernode,wecanprobablyfit

thelevelinmemory.

這個(gè)問(wèn)題我們將使用雨林算法。假設(shè)有C類標(biāo)簽。最需要的內(nèi)存將是avc-set為根的樹(shù)。計(jì)算

avc-set的根節(jié)點(diǎn)，我們掃描一次數(shù)據(jù)庫(kù)，構(gòu)建