数据仓库与数据挖掘ppt习题

数据仓库与数据挖掘主讲教师：王浩畅E-mail:wanghch_angel@SchoolofComputer&InformationTechnologyofNEPU第2章数据预处理练习1假定用于分析的数据包含属性age.数据元组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)该数据的均值是什么?中位数是什么?(b)该数据的众数是什么？讨论数据的峰(c)数据的中列数是什么？解答(a)均值：中位数：有序集中间值或者中间两个值平均。奇数个，中间值：25(b)：表示数据集中出现频率最高的值两个值出现了相同的最高频率，25和35，都出现了4次，也就是双峰(c)中列数：最大值和最小值的平均（13+70）/2=41.5练习2假定用于分析的数据包含属性age.数据元组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.(d)找出数据的第一个四分位数Q1和第三个四分位数Q3(e)给出数据的五数概括解答(d)第一个四分位数Q1：20第三个四分位数Q3：35中位数：有序集中间值或者中间两个值平均。奇数个，中间值：25(e)五数概括:13,20,25,35,70练习3假定用于分析的数据包含属性age.数据元组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.(f)画出数据的盒图解答2035257013年龄(f)52噪声数据(3)数据平滑的分箱方法price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34练习假定用于分析的数据包含属性age.数据元组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.使用分箱均值光滑对以上数据进行光滑，箱的深度为3.解释你的步骤解答Step1:排序数据.Step2:将有序值划分到大小为3的等频箱中Step3:计算每个箱中数据的算术平均值.Step4:.将每个箱中的每个值用此箱的算术平均值替换

Bin1:44/3,44/3,44/3Bin2:55/3,55/3,55/3Bin3:21,21,21Bin4:24,24,24…规范化最小－最大规范化：对原始数据进行线性变换。假定minA

和

maxA

分别为属性A的最小和最大值。将A的值v映射到区间[new_minA,new_maxA]中的v’最小-最大规范化通过计算例：

假定属性income的最小与最大值分别为12000美元和98000美元。我们想把income映射到区间[0.0,0.1]。根据最小最大规范化，income值73600美元将变换为：数据变换(2)z-score规范化：属性A的值基于A的平均值和标准差规范化。最大最小值未知，或者离群点影响较大的时候适用例：假定属性income的均值和标准差分别为54000美元和16000美元。使用z-score规范化，值73600美元转换为数据变换(3)小数定标规范化：通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。例：假定A的取值由-986～917。A的最大绝对值为986。使用小数定标规范化，用1000（即j=3）除每个值，这样，－986规范化为－0.986，而917被规范化为0.917。数据变换(4)其中，j是使Max(||)<1的最小整数练习用如下两种方法规范化如下数据组200;300;400;600;1000(a)min-max规范化令min=0，max=1(b)z-score规范化解答(a)min-max规范化令min=0，max=1(b)z-score规范化例

下面的数据是AllElectronics

通常销售的商品的单价表（按$取整）。已对数据进行了排序：1,1,5,5,5,5,5,5,8,8,10,10,10,10,12,12,12,12,14,14,14,15,15,15,15,15,15,18,18,18,18,18,18,18,18,20,20,20,20,20,20,20,21,21,21,21,25,25,25,25,25,25,28,28,30,30,30为进一步压缩数据，让每个桶代表price的一个不同值。通过自然划分分段将数值区域划分为相对一致的、易于阅读的、看上去更直观或自然的区间。聚类分析产生概念分层可能会将一个工资区间划分为：[51263.98,60872.34]通常数据分析人员希望看到划分的形式为[50000，60000]自然划分的3-4-5规则常被用来将数值数据划分为相对一致，“更自然”的区间自然划分的3-4-5规则规则的划分步骤：如果一个区间最高有效位上包含3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；(72,3,2)如果一个区间最高有效位上包含2，4，或8个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位上包含1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%3-4-5规则——例子假定AllElectronics

所有分部1999年的利润覆盖了一个很宽的区间，由-$351,976.00到$4,700,896.50。用户希望自动地产生利润的概念分层。为了改进可读性，我们使用记号(l...r]表示区间(l,r]。例如，(-$1,000,000...$0]表示由-$1,000,000（开的）到$0（闭的）的区间。1．根据以上信息，最小和最大值分别为MIN=-$351,976.00和MAX=$4,700,896.50。对于分段的顶层或第一层，要考虑的最低（第5个百分位数）和最高（第95个百分位数）值是：LOW=-$159,876，HIGH=$1,838,761。2．给定LOW和HIGH，最高有效位在百万美元数字位（即，msd=1,000,000）。LOW向下对百万美元数字位取整，得到LOW’=-$1,000,000；HIGH向上对百万美元数字位取整，得到HIGH’=+$2,000,000。3-4-5规则——例子3．由于该区间在最高有效位上跨越了三个值，即，(2,000,000–(1,000,000))/1,000,000=3，根据3-4-5规则，该区间被划分成三个等宽的区间：(-$1,000,000...$0],($0...$1,000,000]和($1,000,000...$2,000,000]。这代表分层结构的最顶层。4.现在，我们考察MIN和MAX，看它们“适合”在第一层分划的什么地方。由于第一个区间(-$1,000,000...$0]覆盖了MIN值（即，LOW′<MIN），我们可以调整该区间的左边界，使区间更小一点。MIN的最高有效位字在十万数字位。MIN向下对十万数字位取整，得到MIN’=-$400,000。因此，第一个区间被重新定义为(-$400,000...$0]。由于最后一个区间($1,000,000...$2,000,000]不包含MAX值，即MAX>HIGH′，我们需要创建一个新的区间来覆盖它。对MAX向上对最高有效位取整，新的区间为($2,000,000…$5,000,000]。因此，分层结构的最顶层包含4个区间：(-$400,000...$0]，($0...$1,000,000]，($1,000,000...$2,000,000]和($2,000,000...$5,000,000]。3-4-5规则——例子5.递归地，每一个区间可以根据3-4-5规则进一步划分，形成分层结构的下一个较低层：•第一个区间(-$400,000...$0]划分成4个子区间：(-$400,000...-$300,000],(-$300,000...-$200,000],(-$200,000...-$100,000]和(-$100,000...$0]。•第二个区间($0...$1,000,000]划分成5个子区间：($0...$200,000],($200,000...$400,000],($400,000...$600,000],($600,000...$800,000]和($800,000...$1,000,000]。•第三个区间($1,000,000...$2,000,000]划分成5个子区间：($1,000,000...$1,200,000],($1,200,000...$1,400,000],($1,400,000...$1,600,000],($1,600,000...$1,800,000]和($1,800,000…$2,000,000]。•最后一个区间($2,000,000...$5,000,000]划分成3个子区间:($2,000,000...$3,000,000],($3,000,000...$4,000,000]和($4,000,000...$5,000,000]。类似地，如果必要的话，3-4-5规则可以在较低的层上继续迭代3-4-5规则——例子(-$400-$5,000)(-$400-0)(-$400--$300)(-$300--$200)(-$200--$100)(-$100-0)(0-$1,000)(0-$200)($200-$400)($400-$600)($600-$800)($800-$1,000)($2,000-$5,000)($2,000-$3,000)($3,000-$4,000)($4,000-$5,000)($1,000-$2,000)($1,000-$1,200)($1,200-$1,400)($1,400-$1,600)($1,600-$1,800)($1,800-$2,000)

msd=1,000 Low=-$1,000 High=$2,000第二步第四步第一步-$351 -$159 profit $1,838 $4,700 MinLow(i.e,5%-tile) High(i.e,95%-0tile)Maxcount(-$1,000-$2,000)(-$1,000-0)(0-$1,000)第三步($1,000-$2,000)第3章数据仓库和数据挖掘的OLAP技术习题假定数据仓库包含三个维：time,doctor和patient；两个度量：count和charge；其中，charge是医生对一位病人的一次来访的收费。(a)列举三种流行的数据仓库建模模式。(b)使用星型模式，画出上面数据仓库的模式图。解答(a)星型模式、雪花模式、或事实星座模式(b)习题假定数据仓库包含三个维：time,doctor和patient；两个度量：count和charge；其中，charge是医生对一位病人的一次来访的收费。(c)由基本方体[day,doctor,patient]开始，为列出2004年每位医生的收费总数，应当执行哪些OLAP操作？解答上卷（Roll-up）操作，时间维的概念分层向上攀升，从day攀升到year.切片（Slice）操作，fortime=2004.上卷（Roll-up）操作：维规约，对patient维进行规约。patientfromindividualpatienttoall.第4章挖掘频繁模式、关联和相关由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则A

D，其支持度=60%置信度Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,FD

A(60%,75%)Apriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素L1和L2可以执行连接操作的条件是Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk

。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持计数：2使用Apiori性质由L2产生C31．连接：C3=L2

L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以删除这个选项；{B,C,E}的2项子集是{B,C},{B,E},{C,E}，它的所有2－项子集都是L2的元素，因此保留这个选项。3．这样，剪枝后得到C3={{B,C,E}}从FP-tree的项头表开始,由频率低的节点开始按照每个频繁项的连接遍历FP-tree列出能够到达此项的所有前缀路径，得到条件模式基条件模式基item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤1:从FP-tree到条件模式基对每个模式基计算基中每个项累积计数用模式基中的频繁项建立条件FP-treem-条件模式库:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤2:建立条件FP-treeEmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}p条件FP-tree条件模式基项通过建立条件模式库得到频繁集对强关联规则的批评（1）例1：(Aggarwal&Yu,PODS98)在5000个学生中3000个打篮球3750个喝麦片粥2000个学生既打篮球又喝麦片粥然而，打篮球=>喝麦片粥[40%,66.7%]是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高打篮球=>不喝麦片粥[20%,33.3%]这个规则远比上面那个要精确，尽管支持度和置信度都要低的多31January202339由关联分析到相关分析打篮球=>喝麦片粥打篮球=>不喝麦片粥对强关联规则的批评（2）例1：上述数据可以得出buys(X,“computergames”)=>buys(X,“videos”)[40%,60%]但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。由此可见A=>B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。由关联分析到相关分析我们需要一种度量事件间的相关性或者是依赖性的指标当项集A的出现独立于项集B的出现时，P(A∪B)=P(A)P(B)，即lift＝1，表明A与B无关，lift>1表明A与B正相关，lift<1表明A与B负相关将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为：P({game,video})/(P({game})×P({video}))

=0.4/(0.75×0.6)=0.89结论：录像带和游戏之间存在负相关第6章分类和预测31January202343信息增益(2)设属性A具有v个不同值{a1,a2,…,av}。可以用属性A将S划分为v个子集{S1,...,Sv}；其中，Sj

包含S中这样一些样本，它们在A上具有值aj。如果A选作测试属性（即，最好的划分属性），则这些子集对应于由包含集合S的结点生长出来的分枝。设Sij

是子集Sj

中类Ci

的样本数。根据A划分子集的熵或期望信息由下式给出：A上该划分的获得的信息增益定义为具有最高信息增益的属性,是给定集合中具有高度区分度的属性.所以可以通过计算集合S中样本的每个属性的信息增益,来得到一个属性的相关性的排序ageincomestudentcredit_ratingbuys_computer<=30highnofairno<=30highnoexcellentno31…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes<=30mediumnofairno<=30lowyesfairyes>40mediumyesfairyes<=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes>40mediumnoexcellentno判定归纳树算法示例通过信息增益的属性选择Class:buys_computer=“yes”Class:buys_computer=“no”I(s1,s2)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly判定归纳树算法示例(1)计算基于熵的度量——信息增益，作为样本划分的根据Gain(age)=0.246Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048然后，对测试属性每个已知的值，创建一个分支，并以此划分样本，得到第一次划分判定归纳树算法示例(2)判定归纳树算法示例(3)age?student?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40由决策树提取分类规则可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示对从根到树叶的每条路径创建一个规则沿着给定路径上的每个属性-值对形成规则前件（"IF"部分）的一个合取项叶节点包含类预测，形成规则后件（"THEN"部分）IF-THEN规则易于理解，尤其树很大时示例：IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“fair”THENbuys_computer=“no”举例说明目标概念PlayTennis的训练样例

DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo统计个数表1类别为cj及在cj条件下Ai取ai的样例数OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong2432433663Yes93022214123No5估计先验概率和条件概率表2先验概率P(cj)和条件概率P(ai|cj)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong0.2220.4440.3330.2220.4440.3330.3330.6670.6670.333Yes0.6430.600.40.40.40.20.80.20.40.6No0.357样例判别现在假设有一个样例x

x={Sunny,Hot,High,Weak}等于yes的概率P(Yes|x)=p(Yes)*p(Sunny|Yes)*p(Hot|Yes)*p(High|Yes)*p(Weak|Yes)* =0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率P(No|x)=p(No)*p(Sunny|No)*p(Hot|No)*p(High|No)*p(Weak|No)* =0.357*0.6*0.4*0.8*0.4=0.027418max(P(Yes|x),P(No|x))=P(No|x),所以我们把x分类为No31January202354朴素贝叶斯分类实例2Class:C1:buys_computer=‘yes’C2:buys_computer=‘no’DatasampleX=(age<=30,Income=medium,Student=yesCredit_rating=Fair)估计先验概率P(cj)和条件概率P(ai|cj)

ageP(<=30|buys_computer=yes)=2/9P(<=30|buys_computer=no)=3/5P(31…40|buys_computer=yes)=4/9P(31…40|buys_computer=no)=0P(>40|buys_computer=yes)=3/9P(>40|buys_computer=no)=2/5incomeP(high|buys_computer=yes)=2/9P(high|buys_computer=no)=2/5P(medium|buys_computer=yes)=4/9P(medium|buys_computer=no)=2/5P(low|buys_computer=yes)=3/9P(low|buys_computer=no)=1/5studentP(yes|buys_computer=yes)=6/9P(yes|buys_computer=no)=1/5P(no|buys_computer=yes)=3/9P(no|buys_computer=no)=4/5credit_rating

P(excellent|buys_computer=yes)=3/9P(excellent|buys_computer=no)=3/5P(fair|buys_computer=yes)=6/9P(fair|buys_computer=no)=2/5P(buys_computer=yes)=9/14P(buys_computer=no)=5/14朴素贝叶斯分类实例2ComputeP(X/Ci)foreachclass

P(age=“<30”|buys_computer=“yes”)=2/9=0.222

P(age=“<30”|buys_computer=“no”)=3/5=0.6

P(income=“medium”|buys_computer=“yes”)=4/9=0.444

P(income=“medium”|buys_computer=“no”)=2/5=0.4

P(student=“yes”|buys_computer=“yes)=6/9=0.667

P(student=“yes”|buys_computer=“no”)=1/5=0.2

P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667

P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4X=(age<=30,income=medium,student=yes,credit_rating=fair)

P(X|Ci):

P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.667=0.044

P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028

P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007Xbelongstoclass“buys_computer=yes” 31January202356打网球实例:估计P(xi|C)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(strong|p)=3/9P(strong|n)=3/5P(Weak|p)=6/9P(Weak|n)=2/5P(p)=9/14P(n)=5/14打网球实例:分类XX=<rain,hot,high,weak>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(weak|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(weak|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286样本X分类为n(don’tplay)第7章聚类分析对象间的相似度和相异度(2)例：用x1=(1,2)和x2=（3,5）表示两个对象。求两点之间的欧几里得距离和曼哈顿距离。欧几里得距离曼哈顿距离二元变量(2)对称的VS.不对称的二元变量对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g.性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：不对称的二元变量中，变量的两个状态的重要性是不同的；e.g.HIV阳性VSHIV阴性给定两个不对称的二元变量，两个都取值1的情况被认为比两个都取值0的情况更有意义。两个都取值0的数目被认为是不重要的，因此被忽略。基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估二元变量的相异度——示例例

二元变量之间的相异度（病人记录表）Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如过Y和P（positive阳性）为1，N为0，则：

分类变量(2)求下面分类变量的相异度矩阵

，p=1,当对象i和j匹配时，d(i,j)=0,当对象不同时，

d(i,j)=1。=序数型变量(2)求下面序数型变量的相异度矩阵Test-2有三个状态，分别是一般，好，优秀，也就是=3第一步：把Test-2的每个值替换为它的秩，四个对象分别赋值为3,1,2,3第二步：将秩映射到【0.0,1.0】区间第三步，采用区间标度变量的相异度计算

方法计算f的相异度，如使用欧几里得距离比例标度变量(2)求下面比例标度变量的相异度矩阵第一步对属性Test-3取对数，分别为2.65，1.34，2.21和3.08第二步利于区间标度变量计算方法，如使用欧几里得距离公式，对到如下相异度矩阵K-Means聚类:例2

(1)假设有四种药品，每种药品有两个属性如下表表示。我们的目标是将这四种药品聚为两个类，即K=2Objectattribute1(X):weightindexattribute2(Y):pHMedicineA11MedicineB21MedicineC43MedicineD54K-Means聚类:例2

(2)每种药品的两个属性表示为坐标上的一个点(X,Y)，如下图所示K-Means聚类:例2(3)1、初始中心点的选择：假设选择medicineA和medicineB作为初始的两个的簇的中心点。表示为c1=(1,1)和c2=(2,1)。2、计算每个对象到中心点的距离：使用欧几里得公式，我们得到距离矩阵K-Means聚类:例2(4)3、对象聚类：将数据对象赋给最近距离的簇集.即medicineA归为group1，medicineB归为group2，medicineC归为group2，medicineD归为group2.4.迭代,重新确定中心点:我们重新计算中心点，Group1只有一个对象medicineA，中心点仍为c1=(1,1)，Group2现有3个对象，中心点位3个对象的坐标的平均值。K-Means聚类:例2(5)5、计算每个对象到新的中心点的距离：和第2步类似，使用欧几里得公式，我们得到距离矩阵如下6、对象聚类：将数据对象赋给最近距离的簇集.和第3步类似。将medicineB移到Group1中，其他不变7、再确定中心点，计算新的分簇的中心点，Group1和Group2各有两个对象，中心点计算如下式所示：

K-Means聚类:例2(6)8、重复第2步，计算每个对象到新的中心点的距离，得到一个新的距离矩阵9、重复第3步,对象重新聚类：将数据对象赋给最近距离的簇集.K-Means聚类:例2(7)最后一次的聚类结果表明聚类结果不再改变，达到稳定，我们得到了最后的聚类结果，如下表所示ObjectFeature1(X):weightindexFeature2(Y):pHGroup(result)MedicineA111MedicineB211MedicineC432MedicineD54273假如空间中的五个点｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设k=2）。样本点间距离如下表所示:

样本点起始中心点为A,B

PAM算法基本思想(续)样本点ABCDEA01223B10243C22015D24103E3353074PAM算法基本思想(续)第一步建立阶段：假如从5个对象中随机抽取的2个中心点为{A，B},则样本被划分为{A、C、D}和{B、E}，如图所示。第二步交换阶段：假定中心点A、B分别被非中心点{C、D、E}替换，根据PAM算法需要计算下列代价TCAC、

TCAD、

TCAE、TCBC、TCBD、

TCBE。我们以TCAC为例说明计算过程：a)当A被C替换以后，A不再是一个中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。b)B是一个中心点，当A被C替换以后，B不受影响，CBAC=0。c)C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算法代价函数的第二种情况CCAC=d(C,C)-d(C,A)=0-2=-2。d)D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1。e)E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是B，根据PAM算法代价函数的第三种情况CEAC=0。因此，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。75PAM算法基本思想(续)

在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，我们选择第一个最小代价的替换（也就是C替换A），根据图（a）所示，样本点被划分为{B、A、E}和{C、D}两个簇。图（b）和图（c）分别表示了D替换A，E替换A的情况和相应的代价

a)C替换A,TCAC=-2(b)D替换A,TCAD=-2(c)E替换A,TCAE=-176PAM算法基本思想(续)

C替换B,TCBC=-2(b)D替换B,TCBD=-2(c)E替换B,TCBE=-2通过上述计算，已经完成了PAM算法的第一次迭代。在下一迭代中，将用其他的非中心点{A、D、E}替换中心点{B、C}，找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。77AGNES算法例子序号 属性1 属性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。第2步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇。第3步：重复第2步的工作，5，6点成为一簇。第4步：重复第2步的工作，7，8点成为一簇。第5步：合并{1，2}，{3，4}成为一个包含四个点的簇。第6步：合并{5，6}，{7，8}，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。AGNES算法例子(续)步骤最近的簇距离最近的两个簇合并后的新簇11{1}，{2}{1，2}，{3}，{4}，{5}，{6}，{7}，{8}21{3}，{4}{1，2}，{3，4}，{5}，{6}，{7}，{8}31{5}，{6}{1，2}，{3，4}，{5，6}，{7}，{8}41{7}，{8}{1，2}，{3，4}，{5，6}，{7，8}51{1，2}，{3，4}{1，2，3，4}，{5，6}，{7，8}61{5，6}，{7，8}{1，2，3，4}，{5，6，7，8}结束DIANA算法例子序号 属性1 属性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。1的平均距离：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96类似地，2的平均距离为2.526；3的平均距离为2.68；4的平均距离为2