数据挖掘导论习题答案(中文版)-USB迷|专注于互联网分享

2024年8月6日发(作者：塞吉月)

(e) 比较数目的候选人和频繁itemsets inparts生成(c)和(d)。

答:

第二种方法可以产生较少的数量的候选人和频繁itemsets。

2. (一)考虑在数据集显示在表7.4。假设我们可以采用以下的离散化战略的连续属性的

数据集。

D 1: 分区的每个连续的属性分为3个大小相等的纸槽。

D 2: 分区的每个连续的属性为3个纸槽;在每个容器包含相等数量的交易。

对于每个策略,请回答以下问题:

我。构造binarized版本的数据集。二、推导出所有的频繁itemsets支

持≥30%。

表7.4。数据集的练习2。

TID

答:

表7.5显示了数据的Keyword for DISCRETIZED Method（将EQUAL_AREAS使用D

1,Keyword for DISCRETIZED Method（将EQUAL_AREAS时间间隔:

• X 1:温度介于80和87

• X 2:温度介于88和95之间

• X 3:温度介于96和103

• Y 1:压力在1025和1051,

• Y 2:压力之间的1052和1078,

• Y 3:压力之间的1079和1105。

温度

103

100

101

压力

1105

1040

1090

1084

1038

1080

1025

1030

1100

报警1

报警2

报警3

第7章关联分析:先进的概念。

表7.5。 Keyword for DISCRETIZED Method（将EQUAL_AREAS数据使用D 1。

TID

X X X Y Y Y

报警1 报警2 报警3

1 2 3 1 2 3

0 1 0 0 0 1 0 0 1

1 0 0 1 0 0 1 1 0

0 0 1 0 0 1 1 1 1

0 0 1 0 0 1 1 0 0

1 0 0 1 0 0 0 1 1

0 0 1 0 0 1 1 1 0

1 0 0 1 0 0 1 0 1

1 0 0 1 0 0 1 0 0

0 0 1 0 0 1 1 1 1

表7.6。 Keyword for DISCRETIZED Method（将EQUAL_AREAS数据使用D 2。

X X X Y Y Y

报警1 报警2 报警3

1 2 3 1 2 3

0 1 0 0 0 1 0 0 1

1 0 0 0 1 0 1 1 0

0 0 1 0 0 1 1 1 1

0 1 0 0 1 0 1 0 0

1 0 0 1 0 0 0 1 1

0 0 1 0 1 0 1 1 0

1 0 0 1 0 0 1 0 1

0 1 0 1 0 0 1 0 0

0 0 1 0 0 1 1 1 1

表7.6显示了数据的Keyword for DISCRETIZED Method（将EQUAL_AREAS使用D

1,Keyword for DISCRETIZED Method（将EQUAL_AREAS时间间隔:

• X 1:温度介于80和85

• X 2:温度介于86和97

• X 3:温度介于100和103

• Y 1:压力在1025和1038,

• Y 2:压力之间的1039和1084,

• Y 3:压力之间的1085和1105。

对于D 1有7经常1 itemset 12、频繁的2 itemset和5经常3 itemset。

TID

对于D 2有9经常1 itemset 7经常2 itemset 1经常3 itemset。

(二)连续属性也可以Keyword for DISCRETIZED Method（将EQUAL_AREAS使用群集的方法。

i. 图一图中的温度与压力的数据pointsshown于表7.4。

答:

图中的温度和压力的是如下图所示。

图7.1。温度与压力。

ii. 有多少自然的群你观察的图吗? Assigna标签(C

、

等

)

在每个群集的图形。

答: 有两个天然的群集数据。

iii. 哪种类型的群集算法你认为可以用toidentify群集吗? 说明你的理由。答: K表示的算法。

iv. 更换温度和压力的属性在表7.4 withasymmetric binary属性 C

、

等的构造矩阵的交易使用的是新的属性与属性的报

警

报警

和报警

。

答:

表7.7。示例中的数字的数据集。

TID

报警1

报警2

报警3

v. 推导出所有的频繁itemsets支持≥30%从binarized数据。

答:

有5种常用的1 itemset 7经常2 itemset 1经常3 itemset。

3。考虑到数据集显示在表7.8。第一属性是连续的,而其余的两个属性是不对称的。一条被

认为是强有力的如果其支持的超过15%,对它的信任超过了60%。提供的数据表7.8支持

以下两个强大的规则:

(i) {(1≤ A ≤2,B =1}→{C =1}

(ii) {5≤ A ≤8,B =1}→{C =1}

表7.8。数据集的练习3。

A B C

1 1 1

2 1 1

3 1 0

4 1 0

5 1 1

6 0 1

7 0 0

8 1 1

9 0 0

10 0 0

11 0 0

12 0 1

(a) 计算的支持和信任,这两个规则。

答:

S({(1≤ A ≤2,B =1}→{C =1})=1/6 c({(1≤ A ≤2,B =1}→{C =1})=

1 s({5≤ A ≤8,B =1}→{C =1})=1/6 c({5≤ A ≤8,B =1}→{C =1})=

(b) 找到《议事规则》使用的是传统的 Apriori 算法,我们需要在discretize连续属性

的

。假

设我们应用的宽度相等的贮藏方法discretize数据 bin-

宽度

、

4。对于每个

纸

槽

-width,国家是否有上述两个规则都是发现的 Apriori 算法。 (注的规则可能不相同

的形式,因为它可能包含更宽或更窄的间隔时间

一

。)对于每条规则对应于上面的两个规则,计算它的支持和信任。

答:

当

纸槽

宽度

=2:

表7.9。综合数据集。

在哪里

A1=1≤ A ≤2; A2=3≤ A ≤4。

3=5

≤ A ≤6; A4=7

≤

A ≤8。

5=9

≤ A ≤10; A6=11≤ A ≤12;

对于第一条,有一相应的规则:

{A1=1,B =1}→{C =1}

S(A1=1,B =1}→{CC =1=1}})=1)=1/6 c(A1=1,B =1}→{

由于支持和信心是大于阈值的规则可以被发现。

第二个规则,有两个相应的规则:

{{AA4=13=1,B,B =1=1}}→→{{CC =1=1}}

对于这两种规则的支持是1和信心的是1。由于支持的是低于阈值(15%),这些规则不能被生

成。

当

纸槽

宽度

=3:

表7.10。综合数据集。

在哪里

A1=1≤ A ≤3; A2=4≤ A ≤6;

A3=7≤ A ≤9; A4=10≤ A ≤12;

对于第一条,有一相应的规则:

{A1=1,B =1}→{C =1}

Sc(AA1=11=1,B,B =1=1}}→→{{

=1}}

)=2

)=1

由于支持和信心是大于阈值的规则可以被发现。发现的规则是在常规形式比原来的规则。

第二个规则,有两个相应的规则:

{{AA3=12=1,B,B =1=1}}→→{{CC =1=1}}

对于这两种规则的支持是1和信心的是1。由于支持的是低于阈值(15%),这些规则不能被生

成。

当

纸槽

宽度

=4:

表7.11。综合数据集。

在哪里

A1=1≤

A3=9

A ≤4≤; A2=5≤

≤

;

A ≤8。

对于第一条,有一correspomding规则:

{A1=1,B =1}→{C =1}

Sc(AA1=11=1,B,B =1=1}}→→{{

=1}}

)=1

因为信心是低于阈值(60%),然后是规则无法生成的。

第二个规则,是一种对应的规则:

{A2=1,B =1}→{C =1}

S(A2=1,B =1}→{CC =1=1}})=1)=1/6 c(A2=1,B =1}→{

由于支助和阈值大于阈值,该规则可以被发现。

(c)意见的效力,使用的是相同的宽度的方法的分类上面的数据集。有

纸槽

-宽度,允许您

找到这两个规则令人满意吗? 如果没有,有什么替代的方法你可以采取以确保您将会

找到两个规则?

答:

无的离散化方法可以有效地找到这两个规则。一种方法,以确保你可以找到这两个规

则是开始与槽的宽度等于2和考虑所有可能的mergings邻近的时间间隔。例如,离散

的时间间隔:

1 <= A<=2,3 <= A<=4,5 <= A<=6,·,11 <= A<=12

1 <= A<=4,5 <= A<=8,9 <= A<=12

4. 考虑到数据集显示在表7.12。

表7.12。数据集的练习4。

年龄数字的小时在线每周(二)

(一)

0-5 5-10 10-20 20-30 30-40

10-15 2 3 5 3 2

15-25 2 5 10 10 3

25-35 10 15 5 3 2

35-50 4 6 5 3 2

(一)为每个组合的规则下面给出指定的规则,具有最高的信任。

我。 15

答:

两个15

二。 15

答:

规则15

(83.3%)。三、15

答:

规则10

(73.8%)。

(二)假设我们有兴趣,找到的平均工作时间用在网上每周的互联网用户的年龄在15岁至35

岁。写下相应的统计数字为基础的关联规则的特点的部分用户。要计算平均花费几

个小时在线,大约每个时间间隔的中点值(例如,使用的是 B =7.5,表示间隔5

答:

有65人的平均年龄是15至35岁。

平均花费几个小时在线

2.5 × 12/65 Gmt-9.5 × 20/65 ×第15天15/65（dib/5+25 × 13/65+35 × 5/65=13.92

。

因此统计数据为基础的协会的规则是:

15≤ A< 35-→ B : φ =13.82

。

(c)是否有定量的关联规则在第(二)部分在统计上是显著的比较其意味着对的平均小时数

用在网上的其他用户不属于该组的年龄。

对于其他用户的平均花费几个小时的在线为:

2.5 × 6/35+7.5 × 9/35+15 × 10/35+25 × 6/65+35 × 4/65=14.93

。

标准偏差的两个群体是9.786(15≤年龄 < 35岁)和10.203(年龄 < 15岁或≥35岁)。

这一区别不是很大,95%的置信水平。

5. 在数据集的属性下面给出的描述,您如何将它转换为Binary的交易数据中设置相应的关联

分析。具体而言,说明每个属性的原始数据集。

(a) 有多少binary属性它将对应的端口和LUN；设置、

(b) How的值的原始属性将映射到值ofthe binary属性和

较少的二元属性。

以下是列表中的属性的数据集及其可能的值。假定所有的属性都是收集在每个学生的基

础:

• 年份 :1年级、2年级、普通、高级、研究生:硕士研究生:博士研究生、专业答:

(a) 每个属性的值可以表示使用的是不对称的二元属性。因此,共有7 binary属性。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

• Zip Code :邮政编码主页地址的美国学生、zip代码为本地地址的非美国学生回答:

(a) 每个属性的值代表的是一种不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的数邮编。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

家)。

• 学院 :农业、建筑、继续教育、教育、人文、工程、自然科学、商务、法律、医学、

牙医、药学、护理、兽医回答:

(a) 每个属性的值代表的是一种不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的学院。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

疗学校工程和自然科学的可能组合到同一学校。

• 校园 :1如果学生生活在校园内,否则为0的回答:

(a) 此属性可以被映射至一二元属性。

(b) 有无分层结构。

• 以下每个属性的值为1的如果人说出的语言和值为0,否则。

– 阿拉伯文

– 孟加拉文

– 中文普通话

– 英文

– 葡萄牙语

– 俄罗斯

– 西班牙语回答:

(a) 每个属性的值可以是不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的方言。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

6. 考虑到数据集显示在表7.13。假设我们有兴趣inextracting以下协会的规则:

{α

≤年龄≤ α

、

钢琴=Yes}-→{欣赏古典音乐=Yes}

表7.13。数据集的练习6。

年

龄

钢琴

是的

无

是的

无

欣赏古典音乐。

是的

无

是的

无

是的

无

是的

无

无是的

处理连续的特性,我们将同等频率的方法与第3、第4和第6的时间间隔。绝对的属性是

由推出的很多新的非对称二元属性的明确的值。假设该支持的阈值是10%的置信度阈值

是70%。

(a) 假设我们的discretize年龄属性为3个相等的频率间隔。查找一对值为 α

和 α

,满足

最小支持和信任的最小要求。

答:

(α

=19,α

=29): s =16.7%,c =100%。

(b) 重复第(一)部分由discretizing满属性成4个相等的frequencyintervals。比较所提取

的规则对其进行您已获得在第(一)部分。

答:

没有任何规则符合支持和信任的阈值。

的规则对其进行您已获得在第(一)部分。

答:

(α

=9,α

=11): s =16.7%,c =100%。

(d) 从结果中的一部分(一)、(二)、(三)、讨论如何选择ofdiscretization间隔会影响规则

提取的协会规则挖掘算法。

如果离散化间隔太宽,有些规则可能没有足够的信心,将检测到的算法。如果离散化的

间隔太窄的规则在第(一)部分将会丢失。

7. 考虑到交易中所示表7.14的项目分类givenin图7.25。

表7.14。例如,市场篮子的交易。

交易ID

购买的项目

芯片、Cookie、经常苏打粉、火腿

芯片、火腿、去骨鸡、饮食苏打

火腿、培根肉、整鸡、定期的苏打水

芯片、火腿、去骨鸡、饮食苏打

芯片、熏肉、无骨鸡

芯片、火腿、熏肉、整鸡、定期的苏打水

芯片、饼干、无骨鸡、饮食苏打

(a) 什么是主要的挑战,采矿协会的规则itemtaxonomy吗?

答:

困难的决定正确的支持和信任的阈值。项目住在较高层级的分类法有较高的支持比

居住在较低层级的分类。许多规则也可能是冗余的。

(b) 考虑的做法,每个交易 t 所更换的扩展交易 t 包含的所有项目中 t 以及他们重新

将更换byspective的祖先。例如,交易

使用此Cookie}

{芯片、饼干、零食的t ={

、

晶片、

食品

、

}

。

答:

的办法来获取所有的频繁itemsets(大小4支70%。 ≥

有8经常1 itemsets 25频繁2、itemsets 34频繁的3 itemsets 20频繁的4 itemsets。

常用的4 itemsets是:

{食品、快餐食品、肉类、苏打粉}{食品、{食品、快餐食品、肉、芯片}

快餐食品、肉、猪肉}

{食品、快餐食品、苏打粉、芯片}

{食品、快餐食品、芯片、鸡}

{食品、肉类、苏打粉、猪肉}{食品、

肉类、苏打粉、火腿}

{粮食、肉、芯片、鸡}{食品、肉、猪

肉、火腿}

{食品、快餐食品、肉类、鸡}

{食品、快餐食品、芯片、猪肉}{食品、

肉类、苏打粉、芯片}

{食品、肉类、苏打粉、鸡}{食品、肉、

芯片、猪肉}

{粮食、肉、猪肉、鸡}{食品、苏打粉、

猪肉、火腿}

{的快餐食品、肉类、苏打粉、芯片}

{的快餐食品、肉、芯片、猪肉}

{的快餐食品、肉、芯片、鸡} {肉、苏打粉、猪肉、火腿}

高一级的层次结构中产生的。接下来,我们使用频繁itemsets发现在更高一级的层次

结构来生成候选itemsets涉及项目在较低的层次。例如,我们生成的候选itemset{芯

片”的饮食

苏打推导出所有的频繁itemsets(大小4)}只如果{的

快餐食品

、

小苏打的

}是经常发生的。

使用这种方法要≥70%。

答:

有8经常1 itemsets 6经常2 itemsets,1经常3 itemset。常用的2 itemsets和3

itemsets是:

{的快餐食品、肉}

{肉碱}

{芯片、鸡}

{的快餐食品、肉类、苏打粉}

{的快餐食品、苏打粉}

{芯片、猪肉}

{猪肉、鸡肉}

(d) 比较频繁itemsets中找到的零件(b)和(c)。 Commenton的效率和完整性算法。

答:

这种方法在第(二)部分是更为完整的,但效率较低的方法中的第(三)部分。这种方法

在第(三)部分的效率更高,但可能会丢失某些频繁itemsets。

8. 下面的问题研究如何支持和信任的关联规则可能视情况而有所不同,存在概念的层次结

构。

(a) 考虑项目 x 在给定的概念的层次结构。让我们来表示 k 儿童的 x 在概

念的层次结构。显示, s(x)≤

),其中 s(·)是支持的项目。什么情况下会出现不平等成为平等的吗?

答:

如果没有交易包含多个儿童的 x,然后

(b) 让 p 和 q 表示对项目,而ˆp ˆq 其相应的家长在概念的层次结构。如果 s({p

、

q}) >minsup(i

)

,其中,s({p

、

qˆ})、(二)以下itemsets肯定是经常的吗? S({p

、

qˆ})、

(三)、 s({p

、

q ˆˆ})。

答:

所有三个itemsets肯定是经常发生的。

问

}。假设的建立信任的规则超过 minconf

。

以下哪一项的规则可以

保证的

信心高于 minconf? (i){p}-→{qˆ}(二){pˆ}-→{

}

和

(

三

)

{

pˆ

}-→{

qˆ

}

。

答:

只{p}-→{qˆ}是保证信心高于 minconf。

9. (一)列表中所有的4个“蛙跳”载于下面的数据序列:

< {1,3}{2}{2,3}{4} >,

假设没有时间的限制。

答:

< {1,3}{2}{2} >

< {1,3}{2}{4} >

< {1,3}{3}{4} >

< {1,3}{2}{3} >

< {1

、

3}2

、

3} >

< {1}{2}{2,3} >

< {1}{2}{2}{4} >< {1}{2,3}{4} >

< {1}{2}{3}{4} >< {3}{2}{2,3} >

< {3}{2}{2}{4} >

< {3}{2}{3}{4} >

< {3}{2,3}{4} >

< {2}{2,3}{4} >

(b) 列表中所有的3个元素的“蛙跳”中所载的数据顺序forpart(一)假设没有时间限制。

答:

< {1,3}{2}{2,3} >

< {1,3}{2}{4} >

< {1,3}{2}{2} >

< {1,3}{3}{4} >

< {1,3}{2,3}{4} >

< {1,3}{2}{3} >

< {1}{2}{2,3} >

< {1}{3}{4} >

< {1}{2}{3} >

< {3}{2}{2,3} >

< {3}{3}{4} >

< {3}{2}{3} >

< {1}{2}{4} >< {1}{2}{2} >

< {1}{2,3}{4} >

< {3}{2}{4} >

< {3}{2}{2} >

< {3}{2,3}{4} >

的。

答:

这将包括所有的“蛙跳”中第(一)部分以及以下:

< {1

、

< {1”

、

“2”

、

“3}{2} >

4} >

< {1”

、

“2”

、

“3}{4} >

< {1”

、

“2”

、

< {1,3}{3,4} >

“3}{3} >

< {1}{2}{3,4} >< {3}{2}{3,4} >

< {1,3}{2,4} >

< {1,2}{2,4} >

< {1}{2}{2,4} >

< {1,2}{2}{4} >

< {3}{2}{2,4} >

< {2,3}{2,3} >

< {1,2}{2,3} >

< {2,3}{3,4} >

< {1,2}{3,4} >

< {2

、

< {1

、

3}{3}{4} >< {1}{2}{2,4} >< {3}{2

、

2}{3}{4} >

< {2,3}{2,4} >

、

4} >

< {2,3}{2}{4} >

{3}{2}{3,4} >

< {1}{2

、

4} >

< {1}{2}{3,4} >

< {3}{2}{2,4} >

< {2}{2

、

4} >

(d) 列表中所有的3个元素的“蛙跳”中所载的数据顺序forpart(一)假设时间限制的态度

是灵活的。

答:

这将包括所有的“蛙跳”的一部分(b)以及以下:

< {1”

、

“2”

、

“3}{2}{4} >

< {1”

、

“2”

、

< {1”

、

“2”

、

“3}{2,3}{4} >

“3}{3}{4} >< {1,2}{2}{4} >

< {1

、

2}{3}{4} >

< {2,3}{2}{4} >

< {2,3}{2,3}{4} >

< {1}{2}{3,4} >

< {3}{2}{2,4} >

< {3}{2}{2

、

4} >

< {1,3}{2}{3,4} >

< {1,2}{2,3}{4} >

< {2

、

3}{3}{4} >

< {1}{2}{2,4} >

< {1}{2}{2

、

4} >< {3}{2}{3,4} >

< {1,3}{2}{2,4} >

< {1,3}{2}{2

、

4} >

10. 查找所有的频繁的“蛙跳”的支持≥50%给定序列数据库中所示表7.15。假设没有时间限

制的序列。

答:

< {A} >、 < {B} >、 < {C} >、 < {D} >、 < {E} >

< {A}{C} >、 < {A}{D} >、 < {A}{E} >、 < {B}{C} >

< {B}{D} >、 < {B}{E} >、 < {C}{D} >、 < {C}{E} >、 < {D,E} >

11. (一)为每个序列 w =

...ei...ei

得

...

弹性

> 下面给出确定他们是否是“蛙跳”的顺序

< {1”

、

“2”

、

“3}2

、

4}2

、

5}35}6} >

表7.15。例如,事件序列生成的各种传感器。

传感

器

S 1

S 2

S 3

S 4

S 5

时间戳

事件

A、B

D、E

A、B

C、D

D、E

B、C

A、D

受到以下时间限制:

Mingap=0

(间隔时间最后的事件在 ei 和第一次活动在 ei

得

是 > 0)

Maxgap=3

(间隔第一事件在 ei 和最后的事件

在 ei

得

值≤3)

Maxspan=5

(间隔第一次活动在 e

和最后的事件

在

弹性

值≤5)

(时间之间的第一次和最后一次发生的事件 ei 是

Ws =1 ≤1)

• 答:w =< {1}是2}3} >

• 答:w =< {1

、

2号

、

4}5

、

6} >

• 答:w =< {2

、

4是。}24}6} >

• 答:w =< {1}是。2

、

4}6} >

• 答:w =< {1”

、

“2号}3

、

4}5

、

6} >

(b)确定每个“蛙跳” w 在以往的问题是连续的“蛙跳”的以下序列

中

。

• S =< {1”

、

“2”

、

“3

、

6}1”

、

“2”

、

“3

、

6}1”

、

“2”

、

“3

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 是的。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1

、

4}1”

、

“2”

、

“3

、

6}3

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 是的。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1

、

2}1

、

4}3

、

6}5

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 否。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1”

、

“2”

、

“3}2

、

5}4

、

6} > - w =< {1}{2}{3} >

答: 否。 - w =< {1

、

4}5

、

6} > 答: 不。 - w =< {2

、

4}24}6} >

答: 否。 - w =< {1}{2,4}{6} > 答: 是的。

- w答:=< {1

、

2是。}3

、

4}5

、

6} >

12. 对于每个下面的顺序,确定他们是否是“蛙跳”,下面的数据序列:

受到以下时间限制:

Mingap=0

(间隔时间最后的事件在 ei 和第一次活动在 ei

得

是 > 0)

Maxgap=2

(间隔第一事件在 ei 和最后的事件

在 ei

得

值≤2)

Maxspan=6

(间隔第一次活动在 e

和最后的事件

在

弹性

值≤6)

Ws =1

答: 是的。

答: 否。

13. 请考虑以下频繁的3序列:

(时间之间的第一次和最后一次发生的事件 ei 是

≤1)

<<< {{{112

、、

}{23

、

}{33}{'4'3>}>、>、<和<{1{12

、

}{2<34{}}2}{>>3}{<<4{{'12}

、

{3}.2

、

33}} >>、 << {{12

、

23}{}44}} >>、、

(a) 列表中的所有候选的4序列产生的候选人generationstep的普惠制的算法。

答:

< {1”

、

“2”

、

“3}{3} >、 < {1”

、

“2”

、

“3}{4} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

(b) 列表中的所有候选的4序列的修剪的过程候选人pruningstep的普惠制的算法(假定

没有时间限制)。

答:

如果没有时间限制,所有的“蛙跳”的候选人必须是经常发生的。因此,在修剪后的候选

人是:

< {1”

、

“2”

、

“3}{3} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

定 maxgap =1)。

答:

有时间的限制,只有连续的“蛙跳”的候选人必须是经常发生的。因此,在修剪后的候选

人是:

< {1”

、

“2”

、

“3}{3} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

14. 考虑数据图中所示顺序在表7.16对于给定的对象。 Countthe次数的顺序

据以下计算方法:

假定 ws =0、 mingap =0、 =maxgap 3 maxspan =5)。

根

表7.16。例如,事件序列数据的练习14。

时间戳

事件

P、Q

R、S

Q、R

Q、S

9 P

Q、r、

(a) COBJ(一次发生的每个对象的)。

答: 1个。

(b) 童工(CWIN)(发生一个滑动窗口)。

答: 2个。

(d) 腾出位于警政大楼O(不同的发生可能性的事件时间戳的重叠)。

答: 3。

(e) 腾出位于警政大楼(不同的发生任何事件时间戳的重叠)。

答: 2个。

15. 描述类型的必要修改以适应频繁subgraphmining算法来处理:

(a) 指示图

(b) 未标记的图形

(d) 已断开连接的图表

对于每种类型的图,由于上述描述的步骤,算法将会受到影响(候选代,候选人的修剪和支持

的计数),和任何的优化,可以帮助提高其效率的算法。

答:

(a) 邻接矩阵可能不是对称的,这影响到候选人的一代使用vertex不断增长的方法。

(b) 一种无标签的图是相当于带有标签的图中所有的顶点具有相同的标签。

见:M.J. 扎基,有效地挖掘频繁的树木在森林中,在Proc。第八届ACM SIGKDD Int’l Conf。

在知识发现和数据挖掘

2002年6月)。

16. 提请所有的候选子图表从加入对图形中所列款额图7.2。承担的边缘不断增长的方法用

于展开“子图表。

答: 请参见图7.3。

17. 所有的候选子图表获得加入对graphsshown的图7.4。承担的边缘不断增长的方法用于

展开“子图表。

答: 请参见图7.5。

18. (一)如果支持的定义是诱发的子图的关系,表明了建立信任的规则 g

-→ g

可以大于1如

果 g

和 g

都不允许有重叠的顶点集。

答:

我们说明这一带的例子。考虑5个图形、 G

、

2,···,

如图

7.6

。

图

所示的右手

(b)

图7.2。图为演习16日。

(一)

(b)

图7.3。解决方案的练习16。

图为子图的 G

、

和

。

因此

s(g

1)=4

/5=80%。同样,我们可以显示, s(g

2)=60%

因为

是子图

的 G

、

和

s(g

3)=40%

因为

是子图的 G

和 G

。

考虑协会的规则、 g

-→ g

。

使用标准定义的信心

因为之间的比例支持

∪ g

≡::: g

第

图7.4。图为演习17日。

图7.5。解决方案的练习17。

支持 g

我们就获得了一项建立信任的值大于

因为

s(g

>s(g

。

(b) 什么是时间复杂性需要确定canonical labelof统计图包含|V |顶点吗?

答:

E 子图g 1

A 1 D

1子图支持=80%

引起的子图的支持=80%

子图g 2

子图支持=60%

引起的子图的支持=20%

A1 E

A 1 D

子图g 3

图数据集

子图支持=40%

1 D

引起的子图的支持=40%

图7.6。计算的支持,子图的图形。

A na指ıve方法要求|V |! 计算来检查所有可能的排列的canonical标签。

并的两个常见的子图表共享相同的内核。确定最大数目的候选人获得的子图表由于

automorphism的核心大小 k。

答: k。

(d) 两个常见的子图表的大小 k 可以共享多个内核。确定了最大数量的内核可以共享的

两个常见的子图表。

答: k -1。

19. (一)考虑图形的挖掘算法使用了边材的不断增长的方法来连接两个不定向和未加权子图

表显示在图19 a。

i. 所有的不同的内核时获得合并两个分图。

答: 请参见图7.7。

图7.7。解决练习19。

ii. 有多少人是生成的使用以下内核吗?

答: 没有任何一位候选人的 k 得的子图可以生成的内核。

20. 原来的关联规则挖掘框架认为只存在状态属性一起放在同一笔交易。在有些情况

下,itemsets,很少也可能是丰富的。例如itemset电视、DVD、VCR¬表明,许多客户购买

的电视机和DVD都不买相机。

在这一问题,系统会要求您将该协会的规则框架,以消极itemsets(即itemsets同时包含这两

种的存在和不存在的项目)。我们将使用否定符号()提到缺乏的项目。

(a) A na指ıve方式产生的消极itemsets是延长每个transactionto包括缺少的项目如表

7.17。

i. 假设交易数据库中包含1000个不同的项目中的总数是积极itemsets,可配备新

一代表7.17。示例中的数字的数据集。

TID

电

视

¬电

视

DVD ¬DVD

录像

机

本录

像机

...

1 0 0 1 0 1 ...

可由这些项目? (注:一种积极的itemset中不包含任何否定的项目)。

答: 21000-1。

ii. 什么是最大数量的频繁itemsets可以begenerated从这些交易的吗? (假定a频

繁的itemset中可能包含积极的、消极的,或两种类型的项目) 答: 22000-1。

iii. 解释为什么这种na指ıve方法延长每个transactionwith消极的项目是不切合

实际的负面itemsets。答: 候选人itemsets太大,很多人亦冗余的和无用的(例

如itemset中包含这两个项目中的 x 和 x)。

(b) 考虑在数据库中所示表7.14。什么是支持andconfidence值以下的负面关联规则涉

及经常和饮食苏打粉吗?

i. ¬经常-→饮食。

答: s =42.9%、 c =100%。二、定期-→¬的饮食。

答: s =42.9%、 c =100%。三、褫夺的饮食-→常

规。

答: s =42.9%、 c =100%。

第四。饮食-→¬经常。

答: s =42.9%、 c =100%。

21. 假设我们想要提取的积极和消极itemsets从数据集包含 d 项目。

(a) 考虑的一种方式,在我们推出了一种新的变量到representeach消极的项目。采用这

一方法。项目的数量的增长从 d 到2d。总大小是多少的itemset lattice、假设的

itemset可能含有积极和消极两项相同的变量?

答: 22

。

(b) 假设itemset必须包含积极的或消极的项目不同的变量。例如itemset{a,A,B,C}是无

效的,因为它既包含积极的和消极的项目变量 a。总大小是多少的itemset格子状的

吗? 答:

22. 对于每种类型的模式下面的定义,确定是否支持的措施是单调的、反单调的、或非单调的

(即,既不是也不是单调的反单调的)关于增加itemset大小。

(a) Itemsets含有积极和消极的项目,例如{A,B,C,d}。是的支持措施单调的、反单调的、

或非单调的应用时,这种模式吗?

答: 反单调的。

(b) 布尔逻辑模式如{(a∨b∨c)、d、e},其中可能包含两个disjunctions和连词的项目。是

的支持措施单调的、反单调的、或非单调的应用时,这种模式吗?

答: 非单调。

23. 许多协会的分析算法依赖 Apriori-想办法查找常见的模式。整体结构的算法如下。

算法7.1 Apriori-喜欢的算法。

1: k =1。

3: 重复

K = k +1。

Ck =genCandidate(Fk

-1

)。

{查找常用的1模式。}

{候选代}

{候选修剪}

6: Ck =pruneCandidate函数Ck、 Fk

-1

)。

7: Ck =count函数Ck、 D)。

{支持计数}

{解压频繁模式}

9: 直至 Fk =∅

10:答案= ”。

假设我们有兴趣,找到布尔逻辑的规则,如

{a ∨ b}-→{c,d}

其中可能包含两个disjunctions和连词的项目。相应的itemset可以写成{(a ∨ b),c

、

d}。

(a) 没有原则的Apriori仍然保持这种itemsets吗?

(b) 应该如何在新一代候选步骤进行修改以查找suchpatterns吗?

(d) 应如何支持盘点的步骤加以修改,以便找到这种模式吗?

答:

请参阅R Srikant、Q Vu R Agrawal先生:采矿协会的规则和项目的限制。在处理器的第三

个Int’l Conf的知识发现和数据挖掘,1997年。

群集的分析:

基本概念和算法。

1. 考虑数据集包含220个数据向量中的每个向量有32个组件和每个组件都是4字节的值。假

设矢量量子化是用于压缩和216原型的引导程序都会用到。有多少字节的存储空间并设置

的数据采取之前和之后的压缩和什么是压缩比?

压缩之前,数据集需要4 × 32 × 220=134

、

217

、

728字节。在压缩后的数据集需要4 × 32

× 216=8

、

388

、

608字节的原型“引导程序”和2 × 220=2

、

097

、

152字节为引导程序,因

为确定原型矢量相关的每个引导程序的数据只需要两个字节。因此,在压缩后的字节数

10,485,760来表示数据。压缩比率为12.8。

2. 找到所有的群集的设置,如图所示点在图8.1中。

该解决方案还表示在图8.1中。

图8.1。点练习2。

3. 许多partitional群集算法,自动确定thenumber的群集要求,这是我们的优势。列表中的在两

种情况下没有这种情况。

(a) 当有的分层结构中的数据。大多数算法thatautomatically确定群集partitional,因此忽

略了可能的子群集。

(b) 当群集的配置实用程序。如果某一特定减少数据大小是所需的,则有必要指定群集的群

集(中心)的生产。

4. 给定 K 同样大小的群集的概率随机选择的初始质心将来自任何给定群集是1K,但是概率,每

个群集有一种最初的中心是要低得多。 (应该很清楚的是,有一种最初的中心在每个群集都

是一种良好的开始情况对于K的手段。)如果有 K

的

群集和每个群集都有 n

个

点,那么概

率、 p、选择样本的大小 K 最初的中心从每个群集都是按等式8.1的。 (这是假设采样与更

换。)从这一公式,我们可以计算,例如,可能有一初步的中心从四个通道的每个群集是

4/44=0.0938。

多种方式选择一种中心从每个群集

P = =

KnK!

(8.1)

(a) 阴谋的可能性,获得一点从每个群集的大小sampleof K 值的 K 介于2和100之间。

解决方案如图4所示。请注意,概率基本上是0的时间 K =10。

(b) K 群集、 K =10

、

100 和1000,找到的概率样本的大小2K 至少包含一点从每个群集。

您可以使用数学方法或统计模拟,以确定答案。

我们使用的仿真计算得到的答案。分别的概率是0.21, < 10 6、 < 10-6。

从分析的角度出发,对

不要来自某一特定群集

概率的点并不来自某一特定群集,1、因此,概率,2K 点的

是(1-

。因此,概率至少一200点来自某一特定群

集是1-(1-

。如果我们假定的独立(这是太过乐观,但大约如此。值越大, K),然后是

上界的可能性,所有群集都表示在最终的样本是由(1-1-

)

。给定的值这种绑定是

0.27,2007年5.7e和8.2e 64、分别。

图8.2。概率至少一点从每个群集。练习4。

5. 识别群集在图8.3使用中心、毗连和densitybased的定义。还指示群集的每个案例并给出

简短说明你的理由。注意到黑暗的数目或圆点表示密度。如果它有助于、承担中心的意

味着K的手段,连成一片的手段单一链路和密度为基础的手段。DBSCAN

(一) (b) (c) (d)

图8.3。群集的练习5。

(a) 中心提供的 2个群集。矩形的区域将会分成两半的。注意噪音是否包括在两个群集。

毗连的 1群集,因为该两个圆形的区域将被加入的噪音。

密度为基础的 2个群集,每个圆形区域。噪声将会被淘汰。

(b) 中心提供的 1个群集包含两个环。毗连的 2群集的每一环。密度的 2群集的每一环。

毗邻的 1个群集。这三个三角区域将连接在一起,因为他们触摸。

密度为基础的 3个群集,每个三角区域。虽然这三个三角型触摸、密度的地区他们触摸

低于整个内地的三角。

(d) 中心提供的 2个群集。两个组的线路将分为两个部分。毗邻的 5个群集。每个设置

的行言论掺杂将成为群集。

密度为基础的 2个群集。两个组的行定义了两个区域

高密度的分隔区域的低密度。

6. 对于以下列出的两个维度分,(1)提供了一种绘制草图,以了解他们将拆分为群集的K指的给

定数量的群集和(2)表明大致位置产生的中心。假设我们使用的是方形的错误目标函数。

如果您认为有多种可能的解决方案,然后请表明是否每个解决方案是一项全球性的或当地的

最低限度。请注意,该标签的每个图图8.4中与相应的这个问题的一部分,如图8.4(a)与第(一)

部分。

当地最小的全球最小

本地最小

(一) (b)

图8.4。图中的练习6。

(a) K =2。假设该点是均匀地分布在圆内,有多少可能的方法是在那里(理论)的分区的分

成两个群集的吗? 什么位置的两个中心? (再一次,你不需要提供准确的质心位置,仅仅

是一种定性的描述。

在理论上,有无限多的方式来分割圆分成两个群集-只需采取任何行大道的圆圈。这条

线可以让任意角度0◦≤ θ ≤180◦与x轴。该中心将躺在角平分线垂直的线,分割了圈内

的两个群集和将对称的位置。所有这些解决方案都将具有相同的、全球最小的、错误

的。

(b) K =3。之间的距离的边缘界是稍微大于半径的圆。

如果您开始的,最初的中点,是真正的点,你一定会获得这种解决方案,因为限制的界的多

个半径之外。当然,角平分线可以有任意的角度,上述,它可以是其他的圆圈,将被拆分。

所有这些解决方案都具有相同的全球最小的错误。

三个复选框可以显示的三个群集,这将导致在现实的情况下,最初的中点是实际的数据

点。

(d) K =2。

在这两个案例的矩形显示群集。在第一种情况下,这两个群集仅有本地最小而在第二种

情况下的群集是一种在全球范围内最小的的解决方案。

(e) K =3。提示:使用“对称的状况和记住,我们是在寻找一种粗略的草图,将会产生何种结

果。

该解决方案显示在顶部的图,最上面的两个群集装在两个框中,而第三个群集是封闭的

区域定义的三角和矩形。 (两个较小的组中的图应该是对称的。我认为,第二种方案的

建议,学生也有可能,虽然它是一种本地最小,可能很少会在实践中看到的这个配置的点。

注意的是,虽然两个饼形切割出更大的圆圈所示为上一点,这是不一定的情况下,它取决

于精确的位置和大小的圆。有差距的两个饼图形状的削减,是由第三(较大的)的群集。

(想象一下的小圆圈的另一侧)或之间的边界上的两个饼形切口可能实际上是一条线段。

7. 假设的数据集。

• 有

米

积分和 K 群集、

• 一半的点和群集是在“更多”密集区域、•一半的点和群集是在“低密度”区域,

和•这两个区域都分开的。

为给定的数据集,会发生以下情况,以便最大程度地减少squared error当找到 K

的

群集:

(a) 中心应当平等地分布在更多的密集和lessdense地区。

(b) 更多的中心应分配给较密集的地区。

注意:不要分心的特殊情况或带来以外的其他因素的密度。但是,如果你觉得真正的答案是

不同的从任何给定的上述证明,您的响应。

正确的答案是(c)。低密度的区域需要更多的中心如果squared error是最小的。

8. 考虑意味着群集的对象从二元交易的数据集。什么是最小值和最大值的组件的意味着什么?

什么是口译的群集组件意味着什么? 该组件最准确地描绘对象的群集?

(a) 该组件的平均的范围在0和1之间。

(b) 对于任何特定的组件,它的值是小部分的对象在群集的,有1个。如果我们不对称的

Binary数据,如市场棉箱的数据,则可被视为政府的可能性,例如,客户在本集团代表的群

集购买特定的项目。

数据的,因为,对于大多数群集、绝大多数的组件将具有值为零。为常规的二元数据,

例如,结果真实的虚假的检测,重要部件是过高或过低的整个数据集。

9. 举个例子,某个数据集由3个自然组,(几乎都是)K的手段将有可能找到正确的群集,但河沿K

意味着不会。

考虑一种数据集,由三个圆形的群集,这是相同的数量和分布的点,其中心位于一行和位于中

心的中间群集是同样遥远的其他两个。二等分K意味着将永远分离的中间群集在第一次迭

代中,因此,永远不能产生正确的设置的群集。 (后处理可用于解决这种情况。)

10. 将角度的余弦值的措施是适当的相似性测量使用withK的意味着群集的时间序列数据? 为

什么可以或不可以吗? 如果没有,有什么类似的措施,将是更合适的吗?

时间系列的数据密集型的高维数据,因此,余弦的措施将是不适当的,因为角度的余弦值的措

施是适当的,稀疏的数据。如果规模的时间序列是很重要的,那么欧几里德距离将是适当的。

如果只有形状的时间系列都是很重要的,然后关联将是适当的。请注意,如果比较的时间系

列需要考虑到这一系列的时间可能会导致或滞后另一或仅是与另一种在特定的时间段,然

后更先进的方法来建模的时间序列相似性必须被使用。

11. 总的SSE指令集的总和SSE指令集的每个单独的属性。什么itmean如果SSE的变量之一

是低的所有群集的吗? 低只为一群集? 高所有群集的吗? 高只为一群集? 你如何使用每个

变量的SSE指令集的信息以提高您的群集?

(a) 如果SSE指令的属性之一是低的所有群集,则将变量isessentially恒定的和很少使用的

分离的数据划分到不同的组中。

(b) 如果SSE指令集的一种属性是相对较低的一群,则此属性有助于定义群集。

(d) 如果SSE指令的属性是相对较高的一群,则相距赔率与所提供的信息的属性与较低的

SSE指令集,定义群集。它可能仅仅是在这种情况下,群集定义了该属性的不同定义的

其他属性,但在任何情况下,这意味着此属性并不有助于定义群集。

(e) 这一想法是要消除属性差的区别powerbetween群集,即较低或较高的SSE指令的所有

群集,因为它们是无用的群集。请注意,属性高的SSE指令的所有群集都特别麻烦,如果

他们有相对较高的SSE指令集的其他属性(也许是因为它们的分摊比额表以来,引进了

大量的噪音计算总的SSE指令集。

12. 领导者的算法(Hartigan[4])表示每个群集使用的点,称为“

领袖

”和分配每个点到群集的相应

为最接近的领导人,除非这一距离超过用户指定的阈值。在这种情况下,点成为领导人的新

的群集。

注,本文介绍的算法是不完全的领导人的算法中所述Hartigan将点到的第一位领导人在该

阈值的距离。答案适用于算法中所述的问题。

(a) 有什么优点和缺点的领导人算法ascompared K意味着什么?

领导者的算法只需要一次扫描的数据,因此是计算更有效率,因为每个对象都与最终的

一组中心最多一次。虽然领先的算法是订单相关的、固定的订购的对象,它始终产生

相同的群集。但是,与K的手段,这是不可能的数目设置群集产生的领导人算法、除了

间接的。另外,K表示算法几乎总是生产出质量更好的群集上测得的SSE指令集。

(b) 建议如何领先算法可能会得到改善。

使用样本以确定分配之间的距离的点。所获得的知识从这一进程中可以用于更多的

智能化地设置阈值的值。

领导者的算法可以修改群集的几个阈值在单一通道。

13. Voronoi图的 K 点的平面是一种分区的所有各点的飞机到 K

的

区域,每点(平面)被分配到最

接近的点在 K

的

指定点。 (见图8.5)之间的关系是怎样的Voronoi图和K意味着群集吗? 什

么做的Voronoi图中告诉我们可能的形状的K意味着群集吗?

(a) 如果我们有 K 的意味着群集,然后将平面分为 K

的

Voronoi区域的表示点最接近每个

中心。

(b) 之间的边界上出现群集中分段构建“线性”。有可能这tosee绘制一条线连接两个中心

然后绘制垂直的线之间的一半位置处的中心位置。这种垂直的线拆分平面分成两个

区域,每个包含点中最接近中心的区域中包含的。

图8.5。 Voronoi图的练习13。

14. 你是给定的数据集与100的记录并要求群集数据。您可以使用K意味着群集的数据,但对于

所有值的 K,1≤ K ≤100 K指算法仅返回一非空的群集。您然后应用增量版本的K,但却获得

完全相同的结果。这是如何可能的? 如何将单个链路或DBSCAN处理此类数据的吗?

(a) 该数据由完全重复的一种对象。

(b) 单一的链接(和许多其他的种种机遇分层计划会产生分层群集,但这点会出现在哪个群

集将取决于订购的点和精确的算法。但是,如果被dendrogram绘制显示接近每个对

象将被合并,然后它会很明显的是,数据是重复的。 DBSCAN能找到所有的点是核心点

连接在一起并产生一种单一的群集。

15. 传统的种种机遇分层群集的例程合并两个clustersat的每个步骤。它似乎有可能这种方法

准确地捕获(嵌套)群集结构的数据集的点吗? 如果没有,说明您可以如何进行后期处理的数

据以获取更准确的查看的群集结构。

(a) 这种方法并不准确地捕获的嵌套群集的数据结构。例如,考虑一组三个组,每个都有两

个、三个和四个小类,分别为。理想的分层结构的群集将有三个分支从根一至三个主

要群集的然后两个、三个和四个分支机构从每个群集。传统的种种机遇的方法不能

产生这样的一种结构。

(b) 最简单的类型的后处理将试图将其抚平的分层结构的群集的群集在树中。

16. 使用的相似性矩阵表8.1执行单一和完整linkhierarchical群集。显示您的结果绘制

dendrogram。 Dendrogram的应明确显示的顺序点被合并。

该解决方案显示在图8.6(a)和8.6(b)。

17. 分层的群集有时用于生成 K 群集、 K> 1的群集上的 Kth 级别dendrogram。 (根目录是在级

别1)的群集产生的这种方式,我们就可以评估的行为层次上的群集不同类型的数据和群集,

也比较的分层方法K的手段。

以下是一组的一维积分:{6

、

48。

(a) 对于下面的每个设置的最初的中点,创建两个clustersby分配每个点到最近的中心位置,

然后计算表8.1。相似矩阵的练习16。

P 1 P 2 P 3 P 4 P 5

1.00 0.10 0.41 0.55 0.35

0.10 1.00 0.64 0.47 0.98

0.41 0.64 1.00 0.44 0.85

0.55 0.47 0.44 1.00 0.76

0.35 0.98 0.85 0.76 1.00

2 5 3 4 1

2 5 3 1 4

(一)单一的链接。 (b)完整的链路。

图8.6。 Dendrograms练习16。

总的平方误差每组的两个群集。显示群集的总squared error的每组的中心。

我。 {18

、

45}

第一组是6、12、18、24、30。

Error=360。

第二个群集是42、48。

Error=18。

总错误=378二、{15

、

40}第一集为6、12、18、24。

Error=180。

第二个群集是30、42、48。

Error=168。

总错误=348。

(b) 做两套,中心位置代表稳定的解决方案;即,如果K meansalgorithm是运行在该组的点

使用给定的中心位置作为起始的重心将会有任何变化,在“群集”生成的吗?

是的,这两个中心都是稳定的解决方案。

在两个群集是{6、12、18、24、30日}和{42、48}。

(d) 这种技术,K的手段或单链接,似乎产生了“mostnatural"群集的这种情况吗? (对于K的

手段,采取群集的最低squared error)。

最小可产生最自然的群集。

(e) 什么定义的群集没有这种自然的群集correspondto吗? (好分隔的、中心的、连续的、

或密度)。

最小的以太网地址的连续生产的群集。但是,密度也可以接受的答案。即使是中心的

是可以接受的,因为一组中心提供所需的群集。

(f) 什么众所周知的特点K指算法说明theprevious行为吗?

K的意思是不太好,找到群集的大小不同,至少当他们没有得到很好地分隔。造成这种

情况的原因是,目标是最大程度地减少squared error导致它“休息”的更大的群集。因

此,在这一问题的低错误群集解决方案是“非自然的”。

18. 假设我们要查找 K

的

群集使用的病房的方法、河沿K的手段,和普通的K的手段。而这些

解决方案代表了当地或全球最低? 解释一下。

虽然病房的方法取一对群集进行合并的基础上最大程度地减少SSE、没有完善的步骤经常K

的手段。同样,二等分K意味着没有整体的细化步骤。因此,除非这种改进步骤是添加的,

既没有病房的方法也不偏袒K意味着产生一种当地的最低限度。普通K意味着生成的本

地最小,但就像其他两个算法,它不保证产生的全球最低。

19. 分层的群集算法要求 O(m

log(m))的时间,因此,都是不切实际的,直接使用于较大的数据集。

一种可能的技术,从而减少所需的时间进行采样的数据集。例如,如果 K 群集所需的和√m 点

的采样从 m 点,然后分层聚类算法将产生一种分层结构的群集中的大约 O(m)的时间。 K 群

集可以从这种分层的群集的群集上的 Kth 级别dendrogram。剩下的点可以被分配到群集

在线性的时间,通过使用不同的策略。要给出具体的例子,的质心 K 可将群集计算的,然后每

个 m -√m 剩余点可以分配给该群集与最近的中心。

对于下列每种类型的数据或群集、简略地讨论一下如果(1)采样将导致问题的这种做法

和(2)有什么问题的。假定采样技术随机选择点的总集, M 点的,任何没有提到数据的特征或群集

的优化。换句话说,仅集中于所造成的问题。特别是提到的特点。最后,假设 K 是很少于

米

。

(a) 数据有很大的不同大小的群集。

这可能是个问题,特别是如果在数量的点在群集是小的。例如,如果我们有一千多点,有两个

群集、一大小900和1的大小为100和 5%的样本,然后我们将平均最终以45个积分从第

一集和第5点的第二个群集。 5点是很容易错过或群集不正确50。另外,第二个群集有

时会派代表出席会议的不到5点,就在自然的随机样本。

(b) 高维数据。

这可能是个问题,因为数据在高维空间中通常是稀疏矩阵和多点可能需要定义结构的群集

在高维度空间。

根据定义,异常值不是很频繁,他们大多数不会被采样。因此,如果找到了正确的群集依赖于

有异常值,该群集产生的采样将有可能被误导。否则,它是有益的。

(d) 数据与极不正当的区域。

这可能是个问题,因为该结构的边界可能会丢失当采样除非有大量的点进行采样。

(e) 数据与球状的群集。

这通常不是问题,因为不是很多点需要采样保持结构的球状群集作为不规则的一种。

(f) 数据广泛不同的密度。

在这种情况下的数据往往会将来自更密集的地区。请注意,采样是降低密度的所有群集上

的采样系数,例如,如果我们有10%的样本,然后有密集的群集数量减少10倍。对于群集,

不是非常密集的首先,这可能意味着,他们现在都视为噪声或异常值。

(g) 数据有很小比例的噪声点。

采样都不会导致问题。其实,因为我们要排除噪声干扰和自的噪音很小,这可能是有益

的。

(h) Non-Euclidean数据。

这没有特别大的影响。

(i) 辗转相除的数据。

这没有特别大的影响。

(j) 数据与许多和混合属性的类型。

许多属性的讨论在高维度性。混合在─

祝福没有特别大的影响。

20. 考虑以下的四面如图所示8.7。再次、黑暗的ornumber点表示密度。行仅用于区分地区

并不代表点。

(a) (b) (c) (d)

图8.7。图为演习20日。

(a) 对于每个图,您可以使用单一的链接查找模式representedby鼻子、眼睛和嘴巴吗? 解

释一下。

仅用于(b)和(d)。 (二)、点鼻子、眼睛和嘴巴都是很接近的点的这些区域之间。 (d)

只有空间之间的区域。

(b) 对于每个图,你能使用K的手段来找到的模式的representedby鼻子、眼睛和嘴巴吗?

解释一下。

仅用于(b)和(d)。 (b)、K意味着将找到的鼻子、眼睛、嘴、但低密度点也将包括在

内。 (d)将Kmeans查找的鼻子、眼睛、嘴里干脆只要群集数设置为4。

群集技术可以只查找模式的点,而不是空格。

21. 计算熵和纯度的混淆矩阵表8.2中。

表8.2。混淆矩阵的练习21。

群集

娱乐

财务

外国的

地铁国家

体育

总

熵。

纯度

站

676

693

0.20

0.98

333

827

253

1562

1.84

0.53

326

465

105

949

1.70

0.49

354

555

341

943

273

738

3204

1.44

0.61

总

22. 你有两个设置为100点,属于单位的广场。一组点的安排,以便点均匀布置。其他的点集生

成均匀的分布在单位正方形的。

(a)

有什么区别这两个点集的吗?

是的。随机点将有区域较小的或更高的密度,而均匀分布的点当然,密度均匀在整个单

元的广场。

(b)

如果是这样的话,点集通常具有较小的SSE指令集的K=10群集吗?

随机的点会有较低的SSE指令集。

(c)

将有什么行为的DBSCAN在划一的数据集? Therandom数据集?

DBSCAN将合并所有的点划一的数据设置到某个群集或把它们所有的噪音、视阈值。

可能会存在一定的界限问题点的边缘地区。然而,DBSCAN常常可以找到群集中的随

机数据,因为它也有某些变异的密度。

23. 使用数据在行使24、计算的silhouette系数eachpoint中的每个群集,该群集的整体。

群集包含1{P 1,P 2},第2组包含{P 3,P 4}。差异性的矩阵,我们获得的相似度矩阵如下:

表8.3。表的距离练习23

P 1

0.10

P 2

P 3

P 4

”。

0.10

0.65

0.55

0.70

0.60

0.30

0.65

0.70

0.55

0.60

0.30

让显示的平均距离的点到其他点的群集。让 b 指示最小的平均间距的点到点的另一群

集。

P点1:SC=1-a/b=1——0.1/函数(0.65+0.55)/2)=5=0.833

P点2:SC=1-a/b=1——0.1/((0.7+0.6)/2)=0.846

P点2:SC=1-a/b=1——0.3/函数(0.65+0.7)/2)=0.556

P点2:SC=1-a/b=1——0.3/函数(0.55+0.6)/2)=0.478

第1组平均SC=(+0.846 0.833)/2=0.84

第2组平均SC=(+0.478 0.556)/2=0.52

总体平均SC=(0.840+0.517)/2=0.68

24. 给定的一组群集的标注和相似度矩阵显示在表8.4 and8.5分别计算两者之间的相似度矩

阵和理想的相似度矩阵,即矩阵的 ijth 条目是1如果两个对象属于同一群集,否则为0。

表8.4。表中的群集的标注练习24。表8.5。相似矩阵的练习24。

P 3 P 4

P 1 1

P 1 1 0.8 0.65 0.55

P 2 1

P 2 0.8 1 0.7 0.6

P 3 2

P 3 0.65 0.7 1 0.9

P 4 2

P 4 0.55 0.6 0.9 1

我们需要计算两者之间的向量 x =< 1

、

1 > 和向量 y =< 0.8

、

0.65

、

0.55

、

0.7

、

0.6

、

0.3 >,这是两者之间的非对角元素的距离矩阵和理想的相似度矩阵。

点群集的标签点

P 1

我们获取:

标准偏差的矢量 x : σx =0.[5164]没有值的标准偏差的矢

量 y : σy =0.1703协方差的 x 和 y轴:含(x,y)=-0.200因此,corr(x,y)=涵

盖(x,y)/σxσy =-0.227

25. 计算分层F的测量的8个对象{p 1、p 2、p 3、p 4、p 5、p 6、p 7、p 8}和分层的群集图

图8.8。类包含点p 1、p 2、p 3,而p 4、p 5、p 6、p 7、p 8属于B类地址。

图8.8。分层的群集的练习25。

让 R(i,j)=

后者

/ni 表示调用的类

我

的群集 j。让 P(i,j)=

后者

/nj 指示精度为 I

类

的群集 j。

F(i,j)=2R(i,j)×P(i,j)/(R(i,j)+P(i,j))是F的测量类

我

和群集 j。

用于群集1={p1

、

p8}:

Class=A:

R(A,1)=3/3=1,P(A,1)=3/8=0.375 F(A,1)=2

0375/(1+0375)=0.55

Class=B:

R(B,1)=5/5=1,P(A,1)=5/8=0.625,F(A,1)=0.77

用于群集2={p 1、p 2、p 4、p 5}Class=A:

R(A,2)=2/3P(A,2)=2/4,F(A,2)=0.57 Class=B:

R(B,2)=2/5,P(B,2)=2/4,F(B,2)=0.44的群集3={p 3,p 6,p 7,p

8}Class=A:

R(A,3)=1/3P(A,3)=1/4,F(A,3)=0.29 Class=B:

R(B,3)=3/5,P(B,3)=3/4,F(B,3)=0.67

× 1 ×

用于群集4={p 1,p 2}Class=A:

R(A,4)=2/3P(A,4)=2/2,F(A,4)=0.8级=B:

R(B,4)=0/5,P(B,4)=0/2,F(B,4)=0

用于群集5={p 4,p 5}

Class=A:

R(A,5)=0,P(A,5)=0,F(A,5)=0 Class=B:

R(B,5)=2/5,P(B,5)=2/2,F(B,5)=0.57

用于群集6={p 3,p 6}

Class=A:

R(A,6)=1/3P(A,6)=1/2,F(A,6)=0.4级=B:

R(B,6)=1/5,P(B,6)=1/2,F(B,6)=0.29

用于群集7={p 7,p 8}

Class=A:

R(A,7)=0,P(A,7)=1,F(A,7)=0 Class=B:

R(B,7)=2/5,P(B,7)=2/2,F(B,7)=0.57

A类: F(A)=max{F(A,j)}=max{0.55

、

0.57

、

0.29

、

0.8

、

0.4

、

0}=0.8

B类: F(B)=max{F(B,j)}=max{0.77

、

0.44

、

0.67

、

0.57

、

0.29

、

0.57}=

0.77

整个群集:

26. 计算cophenetic相关系数的分层clusteringsin练习16。 (您将需要转换的异同为差异。)

这可以很容易地计算出使用的软件包,例如MATLAB。答案是单链、0.8116和完整的链接、

0.7480。

27. 证明方程8.14。

=SSE指令集

十字词

28. 证明方程8.15。

=办学团体。

再次,跨

29. 证明)=0。

期取消。

这是用于证明TSS=SSE+SSB上页557。

30. 群集的文档可归纳查找前(字)中的文档集,例如通过采取最频繁的 k ,其中 k 是常数,说10、或

考虑到的所有条款,更经常发生于指定的阈值。假设K指的是用于查找群集的两个文档和

文字的文档的数据集。

(a) 如何可能一组术语定义群集的顶层,在documentcluster不同word找到的群集的群集

术语与K的意味着什么?

第一,顶字群集可能、很可能会在某种程度上相互重叠。第二,它是可能的,很多条款将

不会出现在任何的群集形成的顶部。相比之下,K意味着群集的条款将涵盖所有的条

款和不重叠。

(b) 如何能够长期的群集可用于定义群集的文档吗?

一种明显的方法是将文档的术语"群集";即,这些文档的最频繁的包含这些条款中的群

集。

31. 我们可以表示一组数据的集合对象的节点和collectionof属性节点,是联系在一起的每个对

象的每个属性的权重的链接的对象的值的属性。对稀疏数据,如果该值为0,链接被省略了。

两大部份群集将尝试分区此图为不相交的群集,每个群集都包含一组对象的节点和属性节点。

我们的目标是以最大的权重之间的联系对象和属性节点的群集,同时最大限度地减少重量之

间的链接对象和属性的链接在不同的群集。这种类型的群集还称为合作的群集 ,因为该对

象和属性都是集中在同一时间。

(a) 如何为两大部份群集(clustering)不同群集thesets对象和特性的单独购买?

经常群集,仅有一组的限制,有关对象或属性,是适用的。在合作的群集的两个限制的应

用同时进行。因此,分区的对象和特性的相互独立的另一种通常不会产生相同的结果。

(b) 是否有任何情况下,这些方法产生相同的群集?

是的。例如,如果设置的属性是只与该对象在某个特定的群集,即有0个重量的物体在

所有其他群集和相反的一组对象的群集有0个重量为所有其他的属性,然后在找到的

群集的群集将会匹配那些找到的群集的对象和特性的单独销售的。要使用的文档为

例,这将对应的文档的一组数据,包括文档组,仅包含特定词和组词仅出现在某些文档中。

合作自动群集提供了一种描述群集对象的属性,可以将更多的有用的不是描述群集作

为分区的对象。然而,属性的属性区分不同的群集的对象,可能会相互重叠的机会大大

增加,在这种情况下,合作的群集将不能很好地工作。

32. 在图8.9中的匹配的相似度矩阵,按tocluster标签、有的点的集合。差别的阴影和标记的

形状区分群集和每个点集包含100个点和三个群集。在设置的点标记为2,有三个很紧,同

样大小的群集。

答案:1-D、2-C、3-A、4-B

1 2

图8.9。点和相似度矩阵用于练习32。

群集的分析:

更多的问题和算法。

1. 对稀疏数据、讨论为什么只考虑是否存在非零valuesmight给出更准确的查看

的对象除了要考虑实际的幅度值。如果将这种做法是不可取的?

考虑文档数据。直观的、两个文档类似的如果它们包含许多相同的单词。虽

然我们也可以包含的频率与这些词出现的相似性计算的,这有时会给出不可

靠的评估的相似性。特别是,如果某个字词在文档中出现,而往往比其他的字,

然后这个词可以支配的相似性时比较不同程度的考虑。在这种情况下,文档

才会高度相似的其他文件,也包含相同的字词有很高的频率。虽然这可能是

适当的,许多甚至大多数情况下,这可能会导致错误的结论如果字词可以出现

在不同的背景下,这只能是尊敬的,其他的单词。例如,在Word中,“游戏”频繁

出现在讨论运动和视频游戏。

2. 描述更改的时间复杂度为K的手段的数目ofclusters可以找到增加。

作为组的数目,增加的复杂性,K表示方法 O(m

。

3. 考虑一组文档。假设所有的文档都已被标准化的单位长度是1。什么是“形状”

的群集包含的所有文档,其余弦相似性的质心是大于指定的某些常量吗? 换言

之,cos函数d

、

c)≥ δ、其中0 <δ ≤1。

一次文档引导程序已标准化,它们躺在我的 n维hypershpere。约束的所有文档

都具有最低限度的余弦相似性的中心是一种约束,该文件引导程序内的圆锥形,其

交集的领域是一种圆形表面上的领域。

4. 讨论的优点和缺点的治疗群集作为一种优化的问题。除其他因素外,考虑效率、

非确定性和是否有优化的方法捕获所有类型的clusterings感兴趣的。

两个关键优势治疗群集作为一种优化的问题,(1)它提供了一种明确的定义,什么

是群集的过程中所做的工作,和(2)它允许使用的功能强大的优化技术开发的各

种字段。不幸的是,大多数这些优化技术有着很高的时间复杂度。此外,它可以

显示,许多优化问题是NP难,因此,有必要对使用的启发式优化的办法,只能保证本

地的最优解决方案。往往这种技术的工作最好在使用随机初始化,因此,找到的解

决方案可能会有所不同从一台运行,另一台。另一项问题的优化方法是目标函数

使用倾向于大群集而牺牲较小的。

5. 什么是时间和空间复杂度的模糊c意味着什么? 亚太经合组织高官会的吗? 如

何dothese复杂的比较K意味着什么?

其时间复杂度为K的手段 O(I * K * m * n),在那里

我

是迭代的次数达到收敛所

需, K 是簇的数目, m 是的点的数目, n 为数字的属性。所需要的时间的模糊c的

方法基本上是相同的,K的意思,尽管不断的要高得多。时间复杂性的亚太经合组

织高官会也基本上是相同的,Kmeans因为它由多个通过指派的对象质心和重心

都会更新。但是,由于周围的重心也会进行更新和遍数可以很大,亚太经合组织高

官会将通常会低于K的手段。

6. 传统的手段有一定的限制,如敏感异常值和难以处理群集不同的大小和密度、或

与非球状的形状。评论能力,模糊c的手段来处理这些情况。

模糊的c意味着所有的限制,传统的手段,但它本身并不能使硬盘指派的对象添加

到群集。

7. 对模糊的c方法的算法描述在这本书的总和成员资格的任何点的所有群集上的

为1。相反的,我们只可以要求会员学位点在群集在0到1之间。什么是这种

做法的好处和坏处?

主要的优势,这种方法时一点是离群值并不真正属于非常坚决地对任何群集,因

为在这种情况下,点可以有较低的成员在所有群集。但是,这种办法往往是难以

正确地初始化和可执行差当群集并不都是不明显的。在这种情况下,群集的几

个中心可能会合并在一起,或群集的中心可能有很大差异。一次迭代到另一、而

不是更改仅略有增长,但作为普通的K的手段或模糊的c的方法。

8. 解释的差异可能性和概率。

概率是,根据一种共同的统计定义的频率。事件发生时的实验往往至无穷大。概

率是定义的是概率密度函数的函数的属性值的对象。通常,一种概率密度函数

取决于某些参数。考虑到概率密度函数是函数的参数产生的可能性的功能。

9. 等式9.12给出的可能性的一组点的高斯分布的函数的意思是

基于

0.13

微米工

艺

的标准偏差 σ。显示在数学上的最大的可能性估计的 0.13 μ 和 σ 的样本平均

值和样本的标准偏差。

首先,我们解决的问题

基于

0.13

微米工艺的

。

此设置为等于0和解决问题的,我们得到的。

同样,我们可以解决的 σ。

此设置为等于0和解决问题的,我们得到的。

10. 我们采取一样的成人并测量其高度。如果我们记录每个genderof人,我们可以

计算出的平均身高的差异的高度,分别为男子和妇女。假设,但是,这种信息是不

被记录的。才有可能仍在获取这一信息? 解释一下。

高度的男子和妇女都将有单独的高斯分布有不同的手段和可能的不同差异。

通过使用混合模型的方法,我们可以获得的估计数的平均值和方差的两个高度

的分布。由于有了足够大的样本大小的估计参数应当接近于那些可以计算的

如果我们知道了性别的每一个人。

11. 比较会员配重和概率的数字9.1和9.4,是分别从应用模糊和EM的群集到一组相

同的数据点。什么区别您检测、您如何解释这些差异?

在模糊群集方法仅分配给很高的权重的几点中心的群集。这些点较近的两个

或三个群集具有相对较低的权重。这几点都是在最边缘的群集、远离其它群

集也具有较低的权重比的中心要点,但不是低点附近的两个或三个群集。

在64群组的方式指派高权重的两个点在中心的群集和这些较远的边缘。的点

附近的两个或三个群集具有较低的权重,但不是很多,有的模糊不清的群集的步

骤。

两者主要的方法是,点在远边的群集获得更远的中心的群集上的重量与它是属

于群集将会变为更平等的群集的群集的模糊不清的办法,但对EM的方法的点往

往属于更强烈的群集,它是最接近的。

12. 图9.1显示了群集的一种二维的点数据集与twoclusters:最左边的群集的点标以

星号,有些分散,而最右边的群集的点的特点是圆、是紧凑的。右边的紧凑型群

集、有单点(标有箭头)属于分散群集,其中心是更远的紧凑的群集。请解释为什

么这种可能与64群集,但不能K意味着群集。

在64群集,我们计算的概率点属于群集。反过来,这种概率取决于这两个距离

的群集的中心和分布(方差)的群集。因此,某一点,更接近中心的一群比另一仍

然可以有更高的概率就更遥远的群集如果该群集具有较高的传播近的群集。 K

表示只考虑到距离最近的群集时指定的群集。这是相当于EM的方法在所有群

集都被假设为具有相同的差异。

图9.1。数据集的练习12。 64群集的二维点集与两个群集的不同的密度。

13. 显示群集的手动换档变速箱技术的节9.4.2生成sameclusters作为单一的链接。

为了避免并发症和特殊的情况下,假设所有的两两相同之处都是明显的。

在单一的链接,我们开始与群集的单个点然后依次加入两个群集上,有一对点

的最亲密的在一起。从概念上讲,我们可以查看合并的群集,如把一边的两个

最近的点的两个群集。请注意,如果两个群集上的当前连接,然后由此产生的

群集也将被连接。然而,由于群集形成的不相交的点的集合,并边仅放在不同

的群集、无周期可形成。从这些意见和指出,我们开始使用的群集(图),大小

为1的连接vacuously,我们可以推断出的感应,在任何阶段,都在单一的链接群

集的过程中,每个群集的连接的点集没有任何循环。因此,当最后的两个群集

均合并成为单一的群集包含的所有各点,我们也有相连接的图形的所有的点,

是一种生成树的图形。此外,由于每个点的图是连接到其最接近的点的?生成

树?必须是最小生成树。所有这仍然是建立在等价的手动换档变速箱和单一

的链接。请注意,手动换档变速箱基本上是相反的过程,在这个过程中,单链接

内置最小生成树;即打破的边缘开始时间最长的和继续,直到最小的。因此,

它会生成相同的群集作为单个链接,但请按相反的顺序进行。

14. 一种sparsify感应矩阵如下:对于每个对象的行矩阵)、设置所有项为0的除外

对象相应 k-最近的邻居。但是,近距离sparsified矩阵通常不是对称的。

(a) 如果对象 a 是 k-近邻的对象 b、为什么是 b 不一定会在 k-近邻的 ?

审议一项密集的 k得对象和其它对象的一种离群,这是从更远的对象比他

们从每个其他。没有对象的密集的设置将有离群值的 k-最近的邻居列表

中、但异常会有 k 的对象从密集集在其 k-近邻的列表。

(b) 建议至少有两种方法可用来使sparsified接近开关矩阵的对称。

一种方法是将 ijth 条目为0如果 jith 条目为0,反之亦然。另一种方法是

设置 ijth 条目为1如果 jith 条目为1,反之亦然。

15. 举个例子,一组组的合并根据closenessof群集将导致更多的自然组群集于合并

基础上的力量连接()的相互联系的群组。

例子之一是给定的变色龙纸,就可以找到在/ karypis/

出版物/文件/PDF/变色龙。该示例包含两个窄的矩形,点的两侧。顶部矩形被

拆分成两个组,有一组规模小得多的比其它的。即使两个矩形的顶部是接近的,

他们是没有强烈的连接由于它们之间的关系都是在很小的区域。在其他方面,

最大的矩形的顶部和矩形的底部的强烈关连。每个单独的连接不牢固,因为这

两个矩形的不近,但有更多的人,因为该地区的连接是很大的。因此,一种基于连

通性将合并的最大矩形的顶部与底部的矩形。

16. 表9.1列出了两个最近的邻国的4点。

计算SNN5793A相似的每一对点使用定义的相似性SNN5793A定义在算法9.10。

以下是相似SNN5793A矩阵。

17. 对于定义的相似性SNN5793A提供算法9.10的计算距离SNN5793A不考虑位

置的共享的表9.1。两个最近的邻国的4点。

点第一邻居第二个邻居

1 4 3

2 3 4

3 4 2

4 3 1

表9.2。两个最近的邻国的4点。

点

1 2 3 4

2 0 0 1

2 0 2 1 0

3 0 1 2 0

4 1 0 0 2

邻居的两个最近的邻居列表中。换句话说,它可能需要更高的相似性2点共享

相同的最近的邻国在相同或大致相同的顺序。

(a) 介绍您可以如何修改定义SNN5793A类似givehigher相似点,其共享的邻

居是在大致相同的顺序。

这可以通过分配的权重的几点基于他们的位置在最近的邻居列表中。例

如,我们可以在重量的点在最近的邻居列表中的 n - i +1。对于每个点,然

后我们采取的总和或产品的排在两个列表中。这些值然后相加来计算之

间的相似性的两个对象。这种方法是由贾维斯和帕特里克[5]。

(b) 讨论的优点和缺点,这种改动。

这种方法是更复杂的。但是,它是有利的,如果是这种情况,两个对象的更

多类似的如果共享的邻居都是大致相同的牌。此外,它还可能有助于补偿

任意选择 k。

18. 名称至少在一种情况下,您不希望使用群集基于SNN5793A相似或密度。

当您想要根据群集的绝对密度或距离。

19. 网格的群集技术不同于其它的群集技术inthat他们分区空间而不是点集的。

(a) 这将如何影响到这种技术的描述theresulting群集和群集类型,就可以找

到吗?

在基于网格的群集,该群集是叙述的集合相邻的单元格。在某些情况下,

例如在集团、更紧凑的描述是生成的。在任何情况下,描述群集是给定的

某一区域的空间,而不是设置的对象。 (不过,这种说明可以方便地生成。)

是必要的,因为它的工作的矩形区域,该形状的非矩形的群集只能是近似的。

但是,组相邻的单元格可以有孔。

(b) 哪种类型的群集可以找到基于网格的群集实时映像中无法找到的其他类

型的群集的办法吗? (提示:请参阅练习20第8章,第564页)。

通常,基于网格的群集技术仅注意到茂密的地区。但是,这种技术也可以用

来识别稀疏或空的区域,从而找到形态,没有点。但是请注意,这是不适当的

稀疏数据空间。

20. 在集团的阈值用于查找群集的密度保持不变,即使是维数的增加。这是一种潜

在的问题,因为密度低的维度性增加;即找到群集在更高的维度的阈值必须设置

在一定程度上很可能会导致合并的低维群集。评论您是否觉得这是真正的问题,

如果是的话,您可能如何修改集团为解决这一问题。

这是真正的问题所在。类似的问题存在于协会的分析。特别是支持协会模式,

大量的项目往往很低。找到这种模式使用的算法有Apriori是困难的,因为较低

的支助所需的阈值的结果是大量的关联模式有几个项目,就没有什么太大的兴

趣。换言之,关联模式的许多项目(模式在高维空间)的有趣的支持级别(密度),

不做的有趣图案的大小关联模式(尺寸)是低的。一种方法是减少支持的阈值

(密度的阈值)的项目(维数的增加。

21. 给定的一组点的欧几里德空间,正在群集使用的K指算法欧几里德距离、三角不

平等可以用在分配中的步骤以避免计算所有距离的每个点到每个群集的质心。

提供了常规的讨论如何实现这一工作。

Charles Elkan提出以下定理在主旨发言研讨会上的群集数据High-Dimensional

SIAM 2004。

Lemma 1:让 x 点,让 b 和 c 是中心。如果 d(b

、

c)≥2d(x,b) d(x,c)≥ d(x,B)。

证明:

我们知道 d(b

、

c)≤ d(b,x)+ d(x,c)。

所以 d(b

、

c)- d(x,b)≤ d(x,c)。

现在 d(b

、

c)- d(x,b)≥2d(x,b) d(x,b)= d(x,B)。所

以 d(x,b)≤ d(x,c)。

这一定理可以消除大量的不必要的距离计算。

22日。而不是使用该公式源于治疗见等式9.19的我们可以运行Monte Carlo模拟

直接估计的概率样本的大小 s 将至少包含一定比例的积分与群集的连接。使用

蒙特卡罗模拟计算的概率样本的大小 s 有50%的内容的群集大小100总点数量

为1000个,其中的值可以是100、200或500。

这个问题应该说是“包含

至少

50%”。

结果,我们的模拟包括10万审判0、0和0.54,样本大小为100、200和500元。

异常检测

1个。比较和对比不同的技术的异常检测,在第10.1节。特别是,试图确定在这

种情况下定义的异常使用的不同的技术可能等同于或在何种情况下可能会使

传感,但不会。一定要考虑到不同类型的数据。

第一,注意到,近距离和密度的异常流量检测技术是相关的。具体而言,高浓度

的邻居一点意味着,很多点都靠近它,反之亦然。在实践中,密度通常定义的距

离,但它也可以使用定义的基于网格的方法。

“基于模型的方法几乎可用于任何底层的技术,适合模型的数据。但是请注意,

特定的模型、统计或其他方式,必须假设的。因此,基于模型的方法是受到限

制的数据可以被应用。例如,如果该模型假设的高斯分布,则它不能应用到数

据的非高斯分布。

在其他方面,近距离和密度的办法不使任何特定的假设的数据,虽然定义的一

种不正常的现象也不同而有不同的感应——或密度为基础的技术。近距离的

方法可用于几乎任何类型的数据,但近距离的度量必须选择适当的。例如,欧

几里德距离通常用于密集型的、低维度的数据,而余弦相似性测量用于稀疏的、

高维数据。因为密度通常定义的接近、密度为基础的方法也可用于几乎任何

类型的数据。不过意思的密度较不明显的是,在非欧几里德空间的数据。

近距离和密度的异常检测方法通常可以产生类似的结果,虽然有相当大的差

异的技术,不考虑浓度差异在整个数据集或使用不同的感应的措施相同的数

据集。基于模型的方法往往会有很大的不同,从proximityand密度为基础的

办法。

2. 请考虑以下定义的异常:异常是一种objectthat非常有影响力的建立的数据模型。

(a) 比较一下此定义,标准模型为基础的definitionof反常的情况。

标准的基于模型的定义标注对象不适合模型非常以及不正常的现象。虽然

这些对象通常都是非常有影响的模型,它也可以是一项非常有影响力的对

象可以配合的很好。

(b) 是什么规模的数据集(小型、中型或大型的)是这definitionappropriate吗?

这一定义通常更适合较小的数据集,至少如果我们谈论的是一名非常有影

响力的对象。不过,相对较小的组有高度影响力的对象可以有重大影响的

一种模式,但仍然配合得好,即使是中等或较大的数据集。

3. 在一种异常检测、对象表示为点ina多维空间的点分为连续的炮弹,每个壳是一

层周围的一组点的,如外接多边形。对象是一种不正常的现象如果在外壳。

(a) 而定义的一种不正常的现象在部分10.1.2是这一定义最密切有关的吗?

这一定义的是关系最密切的距离的方法。 (二)名称的两个问题的这一定义

的一种不正常的现象。

i. 对于“外接多边形”的办法,远距离的con的搅扰多边形的中心点可以有

很大差异。如果该分发点的不是对称的。

ii. 这种方法并没有设定有意义的编号的ICAL中的反常现象的分数。

4. 关联分析可以用来查找异常情况如下所示。找到强大的协会模式,这涉及到某些

最小数量的对象。异常是那些对象不属于任何这种形态。为使这一更为具体的,

我们注意到,hyperclique关联模式的讨论在第6.8节“特别适合于采用这种办法。

具体地说,由于用户选择的h的信任级别、最大hyperclique模式的对象都找到。

所有的对象,并不出现在最大模式hyperclique至少三个大小可分为离群值。

(a) 此种技术属于任何类别的讨论,thischapter吗? 如果是这样,这一?

在hyperclique,所有成对的对象有保障的余弦相似性的信任或更高。因此,

这种方法也可以被看作是一种近距离的方法。但是,而不是一种状态的距

离的对象就某一特定的对象,有的要求在成对的组合中所有的对象。

(b) 名称一种潜在的力量和一种潜在的弱点,采取这一做法。

实力,这种方法是(1)的对象不属于任何大小3 hyperclique不强烈连接到其

他对象,并可能反常的现象,(2)它是计算的效率。潜在的弱点是(1)该方法不

指定数值异常的分数,但简单的分类对象为正常或异常,(2)它是不可能直接

控制对象的数目分为异常情况,因为只有参数是h的信任和支持的阈值和(3)

的数据需要Keyword for DISCRETIZED Method（将EQUAL_AREAS。

5. 讨论技术,结合多种异常检测技术提高了识别的异常对象。考虑这两个监督,不受

监督的情况下。

在监督的情况下,我们可以利用合奏分类技术。在这些不同的是,这一分类的对象

是由相结合的分类法的分类器的数量,例如,通过投票。在不受监督的方式、投票

的方法也可以使用。请注意这是假设,我们有二元赋值的对象是一种不正常的现

象。如果我们有异常的分数,那么分数可以合并在某些方式,例如平均或最小、产

生的总分数。

6. 描述可能的时间复杂度为异常检测approachesbased的以下方法:基于模型的使

用群集、proximitybased和密度。没有知识的具体方法是必需的。而是把重点

放在基本的计算需求的每个方法,例如所需的时间来计算密度的每个对象。

如果K意味着群集的复杂性是由查找群集。这需要一定的时间成比例的对象的

个数,即 O(m)。距离和密度的方法,通常需要计算所有的成对穿过天空,因此,复杂

。在某些情况下

例如

在低维数据、特殊技术

如

树或

k-d

树可用于计算最近的邻国的对象更有效

即

性往往是 O(m

O(m日志

m),这可以减少总体复杂性当该技术仅基于最近的邻居。另外,基于网格的方法

来计算密度可降低复杂性,密度为基础的异常检测到 O(m),但这种方法不准确,只

有有效的较低层面。

7. “Grubbs’检测,所描述的算法10.1,这是一种更statisticallysophisticated程序检测

异常值,定义 1030。这是迭代和也考虑到的是,在z分数不正常分布。这种算法

计算的z得分,每个值的样本平均值和标准偏差的当前设置的值。该值与最大程

度的z分数是被丢弃的如果其z分数大于 gc的临界值的测试的离群值的显著性

水平 α。重复这一过程直到没有对象的消除。请注意,样本平均值、标准偏差

和 GC 的更新在每次迭代。

算法10.1 Grubbs'的办法,消除异常。

输入的值和 α

的

值的个数, α 是参数, tc 是一种价值选择,使 α = prob(x ≥ tc)的 t 分布

的 m -2个自由度。

重复

计算样本平均值(x)和标准偏差(sx)。

计算值 gc 以

便 prob(|Z|≥ gc)= α。

(在 tc 和

计算z分数的每个值,即 z =(x - x)/sx。

让 g =max|Z|,即找到z分数的最大的规模和 g。

如果 g>gc 然后

消除对应的值 g。

M ← m -1

10:

End If

11:

直到没有对象的消除。

(a) 什么是限制的值

使用显著性水平为0.05。

用于Grubbs’测试的方法m无穷大吗?

请注意,这可能是更好的措词。该数值的表达方法、tc。但严格来说这

不是一种限制为 tc 取决于 m。

”

。

此外,该值的 tc 将继续增加, m,尽管速度缓慢。 M =1020, tc =93的意义价值

为0.05。

(b) 描述在词语的含义上的结果。

分发的 g 是变成 t 分布为 m

的

增加。

8. 许多统计测试异常值,环境whicha几百的意见有很大的数据集。我们研究的局

限性,这种解决办法。

(a) 对一组000值,怎么可能是我们的异常值25KG复合纸袋的测试说价值是一

种离群值如果大于三个标准偏差的平均值? (假定正态分布)。

这个问题应该问有多少离异我们会因为对象这一问题的目的是表明,即使

是很小的概率的一种离群的产量很大数目的异常值的大型数据集。概率是

不受影响的对象的数目。

的概率是0.00135的单侧偏移为3的标准偏差或0.0027英寸的双面的偏差。

因此,该数量的异常对象将是1350或2700。

(b) 没有办法,国家有异常值是对象的异常lowprobability需要加以调整,当处理

大型数据集的吗? 如果是这样的话,如何?

有上千个异常值(根据指定的定义)的对象。我们可以选择接受这些对象作

为异常值或愿意增加阈值以使较少的离群值的结果。

9. 概率密度的点 x 的多变量正态分布的平均微米和协方差矩阵 Σ 是由方程

μ)

”

。

(10.1)

(2π)

|Σ|

1/2

使用的是样本平均值 x 和协方差矩阵为估计的平均微米和协方差矩阵 Σ”分别

显示日志(prob(x))是同等的马哈拉诺比斯之间距离的数据点 x 和样本平均

值 x 加恒定的,并不取决于 x。

”

。

如果我们用的是样本平均值和协方差的估计的 0.13 μ 和Σ分别然后

不断的和经常性的因素并不影响该命令在这一数量中,只有它们的严重程度。

因此,如果我们想要的距离的数量,我们可以只保留变量的一部分,这是马哈拉诺

比斯的距离。

10. 比较下面两个措施在何种程度上对象的belongsto群集:(1)距离,可以从对象的

中心,其最近的群集和(2)的silhouette系数一节中所述的8.5 2。

第一项措施是比较有限的,因为它无视这一事实,该对象也可关闭到另一群集。

Silhouette系数既考虑到距离的对象以其群集及其距离的其它群集。因此,它可

以提供更多的信息如何强烈的对象所属的群集分配的。

11. 考虑(相对距离)K意味着计划的异常值检测中所述第10.5和随附的图、图10.10。

(a) 这点在底部的紧凑型群集图图10.10有较高的异常点的得分比那些点在

顶部的紧凑的群集。为什么?

这意味着点拉有点向上从中心的紧凑型群集的点D。

(b) 假设我们选择组的数目,要多很多,例如,10。将建议的技术仍然是有效的,

找到最极致的离群值在顶部的图吗? 为什么可以或不可以吗?

第这一点就会成为群集本身。

可能会导致错误的结论。

如果绝对的距离是非常重要的。例如,考虑心率监测的患者。如果心率

高于或低于指定范围的值,然后将该有的物理含义。这是不正确的不识别

任何病人超出该范围的异常,即使可能有一组的患者较为相似,都有不正常

的心率。

12. 如果概率是正常的对象是被归类为一种不正常的现象是0.01不懂概率的异常

对象是被归类为不正常的是0.99,那么什么是虚假报警率和检测率99%的对象

都是正常的吗? (使用定义如下。)

数量的异常检测

检测率 =

总数量的异常数量的虚假的异常

虚假报警率。 =

数量的对象分为异常情况

检测率只需99%。

虚假报警率=0.99m× 0.01/(0.99m× 0.01访问速度

。

米

× 0.99=0.50=50%。

13. 当一项全面的培训将是可用的、受控的异常检测技术通常可以超越了不受监督

的异常时的技术绩效评估是使用的措施,例如检测和虚假报警率。然而,在某些

情况下,例如,在欺诈检测、新类型的异常现象始终是发展的。性能可的评价根

据检测和虚假报警率,因为它通常是可以确定的,经调查后,是否有对象(交易)是

正常的。讨论的相对优点的监督与非监督异常检测,在这样的条件下。

当新的异常现象进行检测,不受监督的异常检测计划必须被使用。但是,监控异

常检测的技术仍很重要用于检测已知类型的异常。因此,这两种监督与非监督

异常检测方法应该被使用。有很好的例子,这种情况是网络入侵检测。配置文

件或签字可以创造良好的已知类型的入侵,但无法检测到新的类型的入侵。

14. 考虑一组文档已从一种多largerset各种不同的文档,使所选的文档都是不同的。

如果我们考虑文档,没有高度相关(连接、类似)在一起是不正常的,那么所有的文

档,我们选择了可能会被归类为不正常的现象。它是可能的数据设置为仅包括

有异常的对象或是此种滥用的名词吗?

的内涵是不正常的现象是很罕见的,许多的定义的一种不正常的现象纳入这一

概念在某种程度上。但是,在有些情况下,一种不正常的现象通常不经常出现,

如出现网络故障,但有十分具体的定义。这使它能够区分一种不正常的现象,是

绝对意义上的和的情况出现在大部分对象都是不正常的。此外,在提供的数学

或算法定义的一种不正常的现象,它可能发生,这些定义产生的情况下,很多或所

有对象的数据集可以被归类为不正常的现象。另一种观点可能会说,如果它是

无法界定的有意义的正常情况,然后再所有的对象都是不正常的。 (“独特”一词

是通常用在这方面。)总之,这可以被视为是一种哲学或语义的问题。良好的论

点(虽然可能不是无争议的一部分)可以说,这是有可能的集合中的对象大多是

或所有的异常情况。

15. 考虑的点集,大多数点所在区域的低密度、布塔的几点都是在各区域的密度高。

如果我们定义一种异常现象的点在某一区域的低密度、然后最点会被归类为不

正常的现象。这是一种适当的使用密度为基础的定义异常或不应该的定义进行

修改以某种方式吗?

如果浓度有绝对的意义,例如分配的域名,然后它可能是完全合理的考虑大部分

的点是不正常的。 (请参阅答案以前的练习。)然而,在许多情况下,适当的做法

是使用一种异常检测技术的相对密度。

16. 考虑的一组点的均匀地分布在时间间隔[0、1]。是统计概念的离群值的不常用

的观察值有意义的数据?

不是真的。传统的统计概念的过度依赖的概念与对象相对较低的概率都是可

疑的。均匀分布,没有这种区分。

17. 分析人士适用的异常检测算法的数据集和findsa的异常情况。奇怪的是,分析

师会对异常检测算法的不正常的现象。

(a) 讨论行为的异常检测方法本章所述。 (如果可能,请尝试此为真正的数据

集和算法。)

(b) 你认为的行为异常检测algorithmshould被应用到一组异常的对象吗?

在某些情况下,例如在统计学上的异常检测技术,它将是无效的应用该技术的第

二次,因为假设不再保留。这也可能是真的其他的基于模型的方法。行为的近

距离和密度为基础的方法将取决于具体的技术。有趣的是,该方法采用的是绝

对阈值的距离或密度很可能会进行分类,设置异常情况的异常情况,至少如果原

始参数。相对的办法很可能会把大部分的反常现象是正常的,有些是不正常的

现象。

某个对象是否为异常取决于整个组的对象,因此,它可能是不合理的期望,一种异

常检测技术将标识一组异常等在没有原始数据集。

参考书目

[1] W。 W·科恩。快速有效的规则简介。在 Proc

。第

届国际。

Conf

。在机器学习

”

页面115-123,市Tahoe、CA、1995年7月。

[2] 美国成本和美国Salzberg。一种加权的最接近的邻居的算法学习与象征性的功能。

机

器学习

中10:57 78、1993年。

[3] J。富指rnkranz和G Widmer。增量减少错误的修剪。在 Proc

。

11 Intl

。

Conf

。在

机器学习

中的页面70-77新不伦瑞克新泽西州1994年7月。

[4] J。 Hartigan。

群集算法

。 Wiley,纽约,1975年。

[5] R。 A贾维斯和E A·帕特里克。群集使用的相似性测量基于共同的最接近的邻居。 IEEE

计算机

、C 22(11):1025-1034、1973。

2024年8月6日发(作者：塞吉月)

(e) 比较数目的候选人和频繁itemsets inparts生成(c)和(d)。

答:

第二种方法可以产生较少的数量的候选人和频繁itemsets。

2. (一)考虑在数据集显示在表7.4。假设我们可以采用以下的离散化战略的连续属性的

数据集。

D 1: 分区的每个连续的属性分为3个大小相等的纸槽。

D 2: 分区的每个连续的属性为3个纸槽;在每个容器包含相等数量的交易。

对于每个策略,请回答以下问题:

我。构造binarized版本的数据集。二、推导出所有的频繁itemsets支

持≥30%。

表7.4。数据集的练习2。

TID

答:

表7.5显示了数据的Keyword for DISCRETIZED Method（将EQUAL_AREAS使用D

1,Keyword for DISCRETIZED Method（将EQUAL_AREAS时间间隔:

• X 1:温度介于80和87

• X 2:温度介于88和95之间

• X 3:温度介于96和103

• Y 1:压力在1025和1051,

• Y 2:压力之间的1052和1078,

• Y 3:压力之间的1079和1105。

温度

103

100

101

压力

1105

1040

1090

1084

1038

1080

1025

1030

1100

报警1

报警2

报警3

第7章关联分析:先进的概念。

表7.5。 Keyword for DISCRETIZED Method（将EQUAL_AREAS数据使用D 1。

TID

X X X Y Y Y

报警1 报警2 报警3

1 2 3 1 2 3

0 1 0 0 0 1 0 0 1

1 0 0 1 0 0 1 1 0

0 0 1 0 0 1 1 1 1

0 0 1 0 0 1 1 0 0

1 0 0 1 0 0 0 1 1

0 0 1 0 0 1 1 1 0

1 0 0 1 0 0 1 0 1

1 0 0 1 0 0 1 0 0

0 0 1 0 0 1 1 1 1

表7.6。 Keyword for DISCRETIZED Method（将EQUAL_AREAS数据使用D 2。

X X X Y Y Y

报警1 报警2 报警3

1 2 3 1 2 3

0 1 0 0 0 1 0 0 1

1 0 0 0 1 0 1 1 0

0 0 1 0 0 1 1 1 1

0 1 0 0 1 0 1 0 0

1 0 0 1 0 0 0 1 1

0 0 1 0 1 0 1 1 0

1 0 0 1 0 0 1 0 1

0 1 0 1 0 0 1 0 0

0 0 1 0 0 1 1 1 1

表7.6显示了数据的Keyword for DISCRETIZED Method（将EQUAL_AREAS使用D

1,Keyword for DISCRETIZED Method（将EQUAL_AREAS时间间隔:

• X 1:温度介于80和85

• X 2:温度介于86和97

• X 3:温度介于100和103

• Y 1:压力在1025和1038,

• Y 2:压力之间的1039和1084,

• Y 3:压力之间的1085和1105。

对于D 1有7经常1 itemset 12、频繁的2 itemset和5经常3 itemset。

TID

对于D 2有9经常1 itemset 7经常2 itemset 1经常3 itemset。

(二)连续属性也可以Keyword for DISCRETIZED Method（将EQUAL_AREAS使用群集的方法。

i. 图一图中的温度与压力的数据pointsshown于表7.4。

答:

图中的温度和压力的是如下图所示。

图7.1。温度与压力。

ii. 有多少自然的群你观察的图吗? Assigna标签(C

、

等

)

在每个群集的图形。

答: 有两个天然的群集数据。

iii. 哪种类型的群集算法你认为可以用toidentify群集吗? 说明你的理由。答: K表示的算法。

iv. 更换温度和压力的属性在表7.4 withasymmetric binary属性 C

、

等的构造矩阵的交易使用的是新的属性与属性的报

警

报警

和报警

。

答:

表7.7。示例中的数字的数据集。

TID

报警1

报警2

报警3

v. 推导出所有的频繁itemsets支持≥30%从binarized数据。

答:

有5种常用的1 itemset 7经常2 itemset 1经常3 itemset。

3。考虑到数据集显示在表7.8。第一属性是连续的,而其余的两个属性是不对称的。一条被

认为是强有力的如果其支持的超过15%,对它的信任超过了60%。提供的数据表7.8支持

以下两个强大的规则:

(i) {(1≤ A ≤2,B =1}→{C =1}

(ii) {5≤ A ≤8,B =1}→{C =1}

表7.8。数据集的练习3。

A B C

1 1 1

2 1 1

3 1 0

4 1 0

5 1 1

6 0 1

7 0 0

8 1 1

9 0 0

10 0 0

11 0 0

12 0 1

(a) 计算的支持和信任,这两个规则。

答:

S({(1≤ A ≤2,B =1}→{C =1})=1/6 c({(1≤ A ≤2,B =1}→{C =1})=

1 s({5≤ A ≤8,B =1}→{C =1})=1/6 c({5≤ A ≤8,B =1}→{C =1})=

(b) 找到《议事规则》使用的是传统的 Apriori 算法,我们需要在discretize连续属性

的

。假

设我们应用的宽度相等的贮藏方法discretize数据 bin-

宽度

、

4。对于每个

纸

槽

-width,国家是否有上述两个规则都是发现的 Apriori 算法。 (注的规则可能不相同

的形式,因为它可能包含更宽或更窄的间隔时间

一

。)对于每条规则对应于上面的两个规则,计算它的支持和信任。

答:

当

纸槽

宽度

=2:

表7.9。综合数据集。

在哪里

A1=1≤ A ≤2; A2=3≤ A ≤4。

3=5

≤ A ≤6; A4=7

≤

A ≤8。

5=9

≤ A ≤10; A6=11≤ A ≤12;

对于第一条,有一相应的规则:

{A1=1,B =1}→{C =1}

S(A1=1,B =1}→{CC =1=1}})=1)=1/6 c(A1=1,B =1}→{

由于支持和信心是大于阈值的规则可以被发现。

第二个规则,有两个相应的规则:

{{AA4=13=1,B,B =1=1}}→→{{CC =1=1}}

对于这两种规则的支持是1和信心的是1。由于支持的是低于阈值(15%),这些规则不能被生

成。

当

纸槽

宽度

=3:

表7.10。综合数据集。

在哪里

A1=1≤ A ≤3; A2=4≤ A ≤6;

A3=7≤ A ≤9; A4=10≤ A ≤12;

对于第一条,有一相应的规则:

{A1=1,B =1}→{C =1}

Sc(AA1=11=1,B,B =1=1}}→→{{

=1}}

)=2

)=1

由于支持和信心是大于阈值的规则可以被发现。发现的规则是在常规形式比原来的规则。

第二个规则,有两个相应的规则:

{{AA3=12=1,B,B =1=1}}→→{{CC =1=1}}

对于这两种规则的支持是1和信心的是1。由于支持的是低于阈值(15%),这些规则不能被生

成。

当

纸槽

宽度

=4:

表7.11。综合数据集。

在哪里

A1=1≤

A3=9

A ≤4≤; A2=5≤

≤

;

A ≤8。

对于第一条,有一correspomding规则:

{A1=1,B =1}→{C =1}

Sc(AA1=11=1,B,B =1=1}}→→{{

=1}}

)=1

因为信心是低于阈值(60%),然后是规则无法生成的。

第二个规则,是一种对应的规则:

{A2=1,B =1}→{C =1}

S(A2=1,B =1}→{CC =1=1}})=1)=1/6 c(A2=1,B =1}→{

由于支助和阈值大于阈值,该规则可以被发现。

(c)意见的效力,使用的是相同的宽度的方法的分类上面的数据集。有

纸槽

-宽度,允许您

找到这两个规则令人满意吗? 如果没有,有什么替代的方法你可以采取以确保您将会

找到两个规则?

答:

无的离散化方法可以有效地找到这两个规则。一种方法,以确保你可以找到这两个规

则是开始与槽的宽度等于2和考虑所有可能的mergings邻近的时间间隔。例如,离散

的时间间隔:

1 <= A<=2,3 <= A<=4,5 <= A<=6,·,11 <= A<=12

1 <= A<=4,5 <= A<=8,9 <= A<=12

4. 考虑到数据集显示在表7.12。

表7.12。数据集的练习4。

年龄数字的小时在线每周(二)

(一)

0-5 5-10 10-20 20-30 30-40

10-15 2 3 5 3 2

15-25 2 5 10 10 3

25-35 10 15 5 3 2

35-50 4 6 5 3 2

(一)为每个组合的规则下面给出指定的规则,具有最高的信任。

我。 15

答:

两个15

二。 15

答:

规则15

(83.3%)。三、15

答:

规则10

(73.8%)。

(二)假设我们有兴趣,找到的平均工作时间用在网上每周的互联网用户的年龄在15岁至35

岁。写下相应的统计数字为基础的关联规则的特点的部分用户。要计算平均花费几

个小时在线,大约每个时间间隔的中点值(例如,使用的是 B =7.5,表示间隔5

答:

有65人的平均年龄是15至35岁。

平均花费几个小时在线

2.5 × 12/65 Gmt-9.5 × 20/65 ×第15天15/65（dib/5+25 × 13/65+35 × 5/65=13.92

。

因此统计数据为基础的协会的规则是:

15≤ A< 35-→ B : φ =13.82

。

(c)是否有定量的关联规则在第(二)部分在统计上是显著的比较其意味着对的平均小时数

用在网上的其他用户不属于该组的年龄。

对于其他用户的平均花费几个小时的在线为:

2.5 × 6/35+7.5 × 9/35+15 × 10/35+25 × 6/65+35 × 4/65=14.93

。

标准偏差的两个群体是9.786(15≤年龄 < 35岁)和10.203(年龄 < 15岁或≥35岁)。

这一区别不是很大,95%的置信水平。

5. 在数据集的属性下面给出的描述,您如何将它转换为Binary的交易数据中设置相应的关联

分析。具体而言,说明每个属性的原始数据集。

(a) 有多少binary属性它将对应的端口和LUN；设置、

(b) How的值的原始属性将映射到值ofthe binary属性和

较少的二元属性。

以下是列表中的属性的数据集及其可能的值。假定所有的属性都是收集在每个学生的基

础:

• 年份 :1年级、2年级、普通、高级、研究生:硕士研究生:博士研究生、专业答:

(a) 每个属性的值可以表示使用的是不对称的二元属性。因此,共有7 binary属性。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

• Zip Code :邮政编码主页地址的美国学生、zip代码为本地地址的非美国学生回答:

(a) 每个属性的值代表的是一种不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的数邮编。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

家)。

• 学院 :农业、建筑、继续教育、教育、人文、工程、自然科学、商务、法律、医学、

牙医、药学、护理、兽医回答:

(a) 每个属性的值代表的是一种不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的学院。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

疗学校工程和自然科学的可能组合到同一学校。

• 校园 :1如果学生生活在校园内,否则为0的回答:

(a) 此属性可以被映射至一二元属性。

(b) 有无分层结构。

• 以下每个属性的值为1的如果人说出的语言和值为0,否则。

– 阿拉伯文

– 孟加拉文

– 中文普通话

– 英文

– 葡萄牙语

– 俄罗斯

– 西班牙语回答:

(a) 每个属性的值可以是不对称的二元属性。因此,我们已为很多不对称的二元属性

的若干个不同的方言。

(b) 有一对一的映射关系的原始属性valuesand对称性的二元属性。

6. 考虑到数据集显示在表7.13。假设我们有兴趣inextracting以下协会的规则:

{α

≤年龄≤ α

、

钢琴=Yes}-→{欣赏古典音乐=Yes}

表7.13。数据集的练习6。

年

龄

钢琴

是的

无

是的

无

欣赏古典音乐。

是的

无

是的

无

是的

无

是的

无

无是的

处理连续的特性,我们将同等频率的方法与第3、第4和第6的时间间隔。绝对的属性是

由推出的很多新的非对称二元属性的明确的值。假设该支持的阈值是10%的置信度阈值

是70%。

(a) 假设我们的discretize年龄属性为3个相等的频率间隔。查找一对值为 α

和 α

,满足

最小支持和信任的最小要求。

答:

(α

=19,α

=29): s =16.7%,c =100%。

(b) 重复第(一)部分由discretizing满属性成4个相等的frequencyintervals。比较所提取

的规则对其进行您已获得在第(一)部分。

答:

没有任何规则符合支持和信任的阈值。

的规则对其进行您已获得在第(一)部分。

答:

(α

=9,α

=11): s =16.7%,c =100%。

(d) 从结果中的一部分(一)、(二)、(三)、讨论如何选择ofdiscretization间隔会影响规则

提取的协会规则挖掘算法。

如果离散化间隔太宽,有些规则可能没有足够的信心,将检测到的算法。如果离散化的

间隔太窄的规则在第(一)部分将会丢失。

7. 考虑到交易中所示表7.14的项目分类givenin图7.25。

表7.14。例如,市场篮子的交易。

交易ID

购买的项目

芯片、Cookie、经常苏打粉、火腿

芯片、火腿、去骨鸡、饮食苏打

火腿、培根肉、整鸡、定期的苏打水

芯片、火腿、去骨鸡、饮食苏打

芯片、熏肉、无骨鸡

芯片、火腿、熏肉、整鸡、定期的苏打水

芯片、饼干、无骨鸡、饮食苏打

(a) 什么是主要的挑战,采矿协会的规则itemtaxonomy吗?

答:

困难的决定正确的支持和信任的阈值。项目住在较高层级的分类法有较高的支持比

居住在较低层级的分类。许多规则也可能是冗余的。

(b) 考虑的做法,每个交易 t 所更换的扩展交易 t 包含的所有项目中 t 以及他们重新

将更换byspective的祖先。例如,交易

使用此Cookie}

{芯片、饼干、零食的t ={

、

晶片、

食品

、

}

。

答:

的办法来获取所有的频繁itemsets(大小4支70%。 ≥

有8经常1 itemsets 25频繁2、itemsets 34频繁的3 itemsets 20频繁的4 itemsets。

常用的4 itemsets是:

{食品、快餐食品、肉类、苏打粉}{食品、{食品、快餐食品、肉、芯片}

快餐食品、肉、猪肉}

{食品、快餐食品、苏打粉、芯片}

{食品、快餐食品、芯片、鸡}

{食品、肉类、苏打粉、猪肉}{食品、

肉类、苏打粉、火腿}

{粮食、肉、芯片、鸡}{食品、肉、猪

肉、火腿}

{食品、快餐食品、肉类、鸡}

{食品、快餐食品、芯片、猪肉}{食品、

肉类、苏打粉、芯片}

{食品、肉类、苏打粉、鸡}{食品、肉、

芯片、猪肉}

{粮食、肉、猪肉、鸡}{食品、苏打粉、

猪肉、火腿}

{的快餐食品、肉类、苏打粉、芯片}

{的快餐食品、肉、芯片、猪肉}

{的快餐食品、肉、芯片、鸡} {肉、苏打粉、猪肉、火腿}

高一级的层次结构中产生的。接下来,我们使用频繁itemsets发现在更高一级的层次

结构来生成候选itemsets涉及项目在较低的层次。例如,我们生成的候选itemset{芯

片”的饮食

苏打推导出所有的频繁itemsets(大小4)}只如果{的

快餐食品

、

小苏打的

}是经常发生的。

使用这种方法要≥70%。

答:

有8经常1 itemsets 6经常2 itemsets,1经常3 itemset。常用的2 itemsets和3

itemsets是:

{的快餐食品、肉}

{肉碱}

{芯片、鸡}

{的快餐食品、肉类、苏打粉}

{的快餐食品、苏打粉}

{芯片、猪肉}

{猪肉、鸡肉}

(d) 比较频繁itemsets中找到的零件(b)和(c)。 Commenton的效率和完整性算法。

答:

这种方法在第(二)部分是更为完整的,但效率较低的方法中的第(三)部分。这种方法

在第(三)部分的效率更高,但可能会丢失某些频繁itemsets。

8. 下面的问题研究如何支持和信任的关联规则可能视情况而有所不同,存在概念的层次结

构。

(a) 考虑项目 x 在给定的概念的层次结构。让我们来表示 k 儿童的 x 在概

念的层次结构。显示, s(x)≤

),其中 s(·)是支持的项目。什么情况下会出现不平等成为平等的吗?

答:

如果没有交易包含多个儿童的 x,然后

(b) 让 p 和 q 表示对项目,而ˆp ˆq 其相应的家长在概念的层次结构。如果 s({p

、

q}) >minsup(i

)

,其中,s({p

、

qˆ})、(二)以下itemsets肯定是经常的吗? S({p

、

qˆ})、

(三)、 s({p

、

q ˆˆ})。

答:

所有三个itemsets肯定是经常发生的。

问

}。假设的建立信任的规则超过 minconf

。

以下哪一项的规则可以

保证的

信心高于 minconf? (i){p}-→{qˆ}(二){pˆ}-→{

}

和

(

三

)

{

pˆ

}-→{

qˆ

}

。

答:

只{p}-→{qˆ}是保证信心高于 minconf。

9. (一)列表中所有的4个“蛙跳”载于下面的数据序列:

< {1,3}{2}{2,3}{4} >,

假设没有时间的限制。

答:

< {1,3}{2}{2} >

< {1,3}{2}{4} >

< {1,3}{3}{4} >

< {1,3}{2}{3} >

< {1

、

3}2

、

3} >

< {1}{2}{2,3} >

< {1}{2}{2}{4} >< {1}{2,3}{4} >

< {1}{2}{3}{4} >< {3}{2}{2,3} >

< {3}{2}{2}{4} >

< {3}{2}{3}{4} >

< {3}{2,3}{4} >

< {2}{2,3}{4} >

(b) 列表中所有的3个元素的“蛙跳”中所载的数据顺序forpart(一)假设没有时间限制。

答:

< {1,3}{2}{2,3} >

< {1,3}{2}{4} >

< {1,3}{2}{2} >

< {1,3}{3}{4} >

< {1,3}{2,3}{4} >

< {1,3}{2}{3} >

< {1}{2}{2,3} >

< {1}{3}{4} >

< {1}{2}{3} >

< {3}{2}{2,3} >

< {3}{3}{4} >

< {3}{2}{3} >

< {1}{2}{4} >< {1}{2}{2} >

< {1}{2,3}{4} >

< {3}{2}{4} >

< {3}{2}{2} >

< {3}{2,3}{4} >

的。

答:

这将包括所有的“蛙跳”中第(一)部分以及以下:

< {1

、

< {1”

、

“2”

、

“3}{2} >

4} >

< {1”

、

“2”

、

“3}{4} >

< {1”

、

“2”

、

< {1,3}{3,4} >

“3}{3} >

< {1}{2}{3,4} >< {3}{2}{3,4} >

< {1,3}{2,4} >

< {1,2}{2,4} >

< {1}{2}{2,4} >

< {1,2}{2}{4} >

< {3}{2}{2,4} >

< {2,3}{2,3} >

< {1,2}{2,3} >

< {2,3}{3,4} >

< {1,2}{3,4} >

< {2

、

< {1

、

3}{3}{4} >< {1}{2}{2,4} >< {3}{2

、

2}{3}{4} >

< {2,3}{2,4} >

、

4} >

< {2,3}{2}{4} >

{3}{2}{3,4} >

< {1}{2

、

4} >

< {1}{2}{3,4} >

< {3}{2}{2,4} >

< {2}{2

、

4} >

(d) 列表中所有的3个元素的“蛙跳”中所载的数据顺序forpart(一)假设时间限制的态度

是灵活的。

答:

这将包括所有的“蛙跳”的一部分(b)以及以下:

< {1”

、

“2”

、

“3}{2}{4} >

< {1”

、

“2”

、

< {1”

、

“2”

、

“3}{2,3}{4} >

“3}{3}{4} >< {1,2}{2}{4} >

< {1

、

2}{3}{4} >

< {2,3}{2}{4} >

< {2,3}{2,3}{4} >

< {1}{2}{3,4} >

< {3}{2}{2,4} >

< {3}{2}{2

、

4} >

< {1,3}{2}{3,4} >

< {1,2}{2,3}{4} >

< {2

、

3}{3}{4} >

< {1}{2}{2,4} >

< {1}{2}{2

、

4} >< {3}{2}{3,4} >

< {1,3}{2}{2,4} >

< {1,3}{2}{2

、

4} >

10. 查找所有的频繁的“蛙跳”的支持≥50%给定序列数据库中所示表7.15。假设没有时间限

制的序列。

答:

< {A} >、 < {B} >、 < {C} >、 < {D} >、 < {E} >

< {A}{C} >、 < {A}{D} >、 < {A}{E} >、 < {B}{C} >

< {B}{D} >、 < {B}{E} >、 < {C}{D} >、 < {C}{E} >、 < {D,E} >

11. (一)为每个序列 w =

...ei...ei

得

...

弹性

> 下面给出确定他们是否是“蛙跳”的顺序

< {1”

、

“2”

、

“3}2

、

4}2

、

5}35}6} >

表7.15。例如,事件序列生成的各种传感器。

传感

器

S 1

S 2

S 3

S 4

S 5

时间戳

事件

A、B

D、E

A、B

C、D

D、E

B、C

A、D

受到以下时间限制:

Mingap=0

(间隔时间最后的事件在 ei 和第一次活动在 ei

得

是 > 0)

Maxgap=3

(间隔第一事件在 ei 和最后的事件

在 ei

得

值≤3)

Maxspan=5

(间隔第一次活动在 e

和最后的事件

在

弹性

值≤5)

(时间之间的第一次和最后一次发生的事件 ei 是

Ws =1 ≤1)

• 答:w =< {1}是2}3} >

• 答:w =< {1

、

2号

、

4}5

、

6} >

• 答:w =< {2

、

4是。}24}6} >

• 答:w =< {1}是。2

、

4}6} >

• 答:w =< {1”

、

“2号}3

、

4}5

、

6} >

(b)确定每个“蛙跳” w 在以往的问题是连续的“蛙跳”的以下序列

中

。

• S =< {1”

、

“2”

、

“3

、

6}1”

、

“2”

、

“3

、

6}1”

、

“2”

、

“3

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 是的。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1

、

4}1”

、

“2”

、

“3

、

6}3

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 是的。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1

、

2}1

、

4}3

、

6}5

、

6} > - w =< {1}{2}{3} >

答: 是的。 - w =< {1

、

4}5

、

6} > 答: 是的。 - w =< {2

、

4}24}6} >

答: 否。 - w =< {1}{2,4}{6} >

答: 是的。 - w =< {1

、

2}3

、

4}5

、

6} > 答: 是的。

• S =< {1”

、

“2”

、

“3}2

、

5}4

、

6} > - w =< {1}{2}{3} >

答: 否。 - w =< {1

、

4}5

、

6} > 答: 不。 - w =< {2

、

4}24}6} >

答: 否。 - w =< {1}{2,4}{6} > 答: 是的。

- w答:=< {1

、

2是。}3

、

4}5

、

6} >

12. 对于每个下面的顺序,确定他们是否是“蛙跳”,下面的数据序列:

受到以下时间限制:

Mingap=0

(间隔时间最后的事件在 ei 和第一次活动在 ei

得

是 > 0)

Maxgap=2

(间隔第一事件在 ei 和最后的事件

在 ei

得

值≤2)

Maxspan=6

(间隔第一次活动在 e

和最后的事件

在

弹性

值≤6)

Ws =1

答: 是的。

答: 否。

13. 请考虑以下频繁的3序列:

(时间之间的第一次和最后一次发生的事件 ei 是

≤1)

<<< {{{112

、、

}{23

、

}{33}{'4'3>}>、>、<和<{1{12

、

}{2<34{}}2}{>>3}{<<4{{'12}

、

{3}.2

、

33}} >>、 << {{12

、

23}{}44}} >>、、

(a) 列表中的所有候选的4序列产生的候选人generationstep的普惠制的算法。

答:

< {1”

、

“2”

、

“3}{3} >、 < {1”

、

“2”

、

“3}{4} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

(b) 列表中的所有候选的4序列的修剪的过程候选人pruningstep的普惠制的算法(假定

没有时间限制)。

答:

如果没有时间限制,所有的“蛙跳”的候选人必须是经常发生的。因此,在修剪后的候选

人是:

< {1”

、

“2”

、

“3}{3} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

定 maxgap =1)。

答:

有时间的限制,只有连续的“蛙跳”的候选人必须是经常发生的。因此,在修剪后的候选

人是:

< {1”

、

“2”

、

“3}{3} >、 < {1

、

2}{3}{3} >、 < {1

、

2}{3}{4} >、 < {1}{2,3}{3} >、 < {1}{2,3}{4} >。

14. 考虑数据图中所示顺序在表7.16对于给定的对象。 Countthe次数的顺序

据以下计算方法:

假定 ws =0、 mingap =0、 =maxgap 3 maxspan =5)。

根

表7.16。例如,事件序列数据的练习14。

时间戳

事件

P、Q

R、S

Q、R

Q、S

9 P

Q、r、

(a) COBJ(一次发生的每个对象的)。

答: 1个。

(b) 童工(CWIN)(发生一个滑动窗口)。

答: 2个。

(d) 腾出位于警政大楼O(不同的发生可能性的事件时间戳的重叠)。

答: 3。

(e) 腾出位于警政大楼(不同的发生任何事件时间戳的重叠)。

答: 2个。

15. 描述类型的必要修改以适应频繁subgraphmining算法来处理:

(a) 指示图

(b) 未标记的图形

(d) 已断开连接的图表

对于每种类型的图,由于上述描述的步骤,算法将会受到影响(候选代,候选人的修剪和支持

的计数),和任何的优化,可以帮助提高其效率的算法。

答:

(a) 邻接矩阵可能不是对称的,这影响到候选人的一代使用vertex不断增长的方法。

(b) 一种无标签的图是相当于带有标签的图中所有的顶点具有相同的标签。

见:M.J. 扎基,有效地挖掘频繁的树木在森林中,在Proc。第八届ACM SIGKDD Int’l Conf。

在知识发现和数据挖掘

2002年6月)。

16. 提请所有的候选子图表从加入对图形中所列款额图7.2。承担的边缘不断增长的方法用

于展开“子图表。

答: 请参见图7.3。

17. 所有的候选子图表获得加入对graphsshown的图7.4。承担的边缘不断增长的方法用于

展开“子图表。

答: 请参见图7.5。

18. (一)如果支持的定义是诱发的子图的关系,表明了建立信任的规则 g

-→ g

可以大于1如

果 g

和 g

都不允许有重叠的顶点集。

答:

我们说明这一带的例子。考虑5个图形、 G

、

2,···,

如图

7.6

。

图

所示的右手

(b)

图7.2。图为演习16日。

(一)

(b)

图7.3。解决方案的练习16。

图为子图的 G

、

和

。

因此

s(g

1)=4

/5=80%。同样,我们可以显示, s(g

2)=60%

因为

是子图

的 G

、

和

s(g

3)=40%

因为

是子图的 G

和 G

。

考虑协会的规则、 g

-→ g

。

使用标准定义的信心

因为之间的比例支持

∪ g

≡::: g

第

图7.4。图为演习17日。

图7.5。解决方案的练习17。

支持 g

我们就获得了一项建立信任的值大于

因为

s(g

>s(g

。

(b) 什么是时间复杂性需要确定canonical labelof统计图包含|V |顶点吗?

答:

E 子图g 1

A 1 D

1子图支持=80%

引起的子图的支持=80%

子图g 2

子图支持=60%

引起的子图的支持=20%

A1 E

A 1 D

子图g 3

图数据集

子图支持=40%

1 D

引起的子图的支持=40%

图7.6。计算的支持,子图的图形。

A na指ıve方法要求|V |! 计算来检查所有可能的排列的canonical标签。

并的两个常见的子图表共享相同的内核。确定最大数目的候选人获得的子图表由于

automorphism的核心大小 k。

答: k。

(d) 两个常见的子图表的大小 k 可以共享多个内核。确定了最大数量的内核可以共享的

两个常见的子图表。

答: k -1。

19. (一)考虑图形的挖掘算法使用了边材的不断增长的方法来连接两个不定向和未加权子图

表显示在图19 a。

i. 所有的不同的内核时获得合并两个分图。

答: 请参见图7.7。

图7.7。解决练习19。

ii. 有多少人是生成的使用以下内核吗?

答: 没有任何一位候选人的 k 得的子图可以生成的内核。

20. 原来的关联规则挖掘框架认为只存在状态属性一起放在同一笔交易。在有些情况

下,itemsets,很少也可能是丰富的。例如itemset电视、DVD、VCR¬表明,许多客户购买

的电视机和DVD都不买相机。

在这一问题,系统会要求您将该协会的规则框架,以消极itemsets(即itemsets同时包含这两

种的存在和不存在的项目)。我们将使用否定符号()提到缺乏的项目。

(a) A na指ıve方式产生的消极itemsets是延长每个transactionto包括缺少的项目如表

7.17。

i. 假设交易数据库中包含1000个不同的项目中的总数是积极itemsets,可配备新

一代表7.17。示例中的数字的数据集。

TID

电

视

¬电

视

DVD ¬DVD

录像

机

本录

像机

...

1 0 0 1 0 1 ...

可由这些项目? (注:一种积极的itemset中不包含任何否定的项目)。

答: 21000-1。

ii. 什么是最大数量的频繁itemsets可以begenerated从这些交易的吗? (假定a频

繁的itemset中可能包含积极的、消极的,或两种类型的项目) 答: 22000-1。

iii. 解释为什么这种na指ıve方法延长每个transactionwith消极的项目是不切合

实际的负面itemsets。答: 候选人itemsets太大,很多人亦冗余的和无用的(例

如itemset中包含这两个项目中的 x 和 x)。

(b) 考虑在数据库中所示表7.14。什么是支持andconfidence值以下的负面关联规则涉

及经常和饮食苏打粉吗?

i. ¬经常-→饮食。

答: s =42.9%、 c =100%。二、定期-→¬的饮食。

答: s =42.9%、 c =100%。三、褫夺的饮食-→常

规。

答: s =42.9%、 c =100%。

第四。饮食-→¬经常。

答: s =42.9%、 c =100%。

21. 假设我们想要提取的积极和消极itemsets从数据集包含 d 项目。

(a) 考虑的一种方式,在我们推出了一种新的变量到representeach消极的项目。采用这

一方法。项目的数量的增长从 d 到2d。总大小是多少的itemset lattice、假设的

itemset可能含有积极和消极两项相同的变量?

答: 22

。

(b) 假设itemset必须包含积极的或消极的项目不同的变量。例如itemset{a,A,B,C}是无

效的,因为它既包含积极的和消极的项目变量 a。总大小是多少的itemset格子状的

吗? 答:

22. 对于每种类型的模式下面的定义,确定是否支持的措施是单调的、反单调的、或非单调的

(即,既不是也不是单调的反单调的)关于增加itemset大小。

(a) Itemsets含有积极和消极的项目,例如{A,B,C,d}。是的支持措施单调的、反单调的、

或非单调的应用时,这种模式吗?

答: 反单调的。

(b) 布尔逻辑模式如{(a∨b∨c)、d、e},其中可能包含两个disjunctions和连词的项目。是

的支持措施单调的、反单调的、或非单调的应用时,这种模式吗?

答: 非单调。

23. 许多协会的分析算法依赖 Apriori-想办法查找常见的模式。整体结构的算法如下。

算法7.1 Apriori-喜欢的算法。

1: k =1。

3: 重复

K = k +1。

Ck =genCandidate(Fk

-1

)。

{查找常用的1模式。}

{候选代}

{候选修剪}

6: Ck =pruneCandidate函数Ck、 Fk

-1

)。

7: Ck =count函数Ck、 D)。

{支持计数}

{解压频繁模式}

9: 直至 Fk =∅

10:答案= ”。

假设我们有兴趣,找到布尔逻辑的规则,如

{a ∨ b}-→{c,d}

其中可能包含两个disjunctions和连词的项目。相应的itemset可以写成{(a ∨ b),c

、

d}。

(a) 没有原则的Apriori仍然保持这种itemsets吗?

(b) 应该如何在新一代候选步骤进行修改以查找suchpatterns吗?

(d) 应如何支持盘点的步骤加以修改,以便找到这种模式吗?

答:

请参阅R Srikant、Q Vu R Agrawal先生:采矿协会的规则和项目的限制。在处理器的第三

个Int’l Conf的知识发现和数据挖掘,1997年。

群集的分析:

基本概念和算法。

1. 考虑数据集包含220个数据向量中的每个向量有32个组件和每个组件都是4字节的值。假

设矢量量子化是用于压缩和216原型的引导程序都会用到。有多少字节的存储空间并设置

的数据采取之前和之后的压缩和什么是压缩比?

压缩之前,数据集需要4 × 32 × 220=134

、

217

、

728字节。在压缩后的数据集需要4 × 32

× 216=8

、

388

、

608字节的原型“引导程序”和2 × 220=2

、

097

、

152字节为引导程序,因

为确定原型矢量相关的每个引导程序的数据只需要两个字节。因此,在压缩后的字节数

10,485,760来表示数据。压缩比率为12.8。

2. 找到所有的群集的设置,如图所示点在图8.1中。

该解决方案还表示在图8.1中。

图8.1。点练习2。

3. 许多partitional群集算法,自动确定thenumber的群集要求,这是我们的优势。列表中的在两

种情况下没有这种情况。

(a) 当有的分层结构中的数据。大多数算法thatautomatically确定群集partitional,因此忽

略了可能的子群集。

(b) 当群集的配置实用程序。如果某一特定减少数据大小是所需的,则有必要指定群集的群

集(中心)的生产。

4. 给定 K 同样大小的群集的概率随机选择的初始质心将来自任何给定群集是1K,但是概率,每

个群集有一种最初的中心是要低得多。 (应该很清楚的是,有一种最初的中心在每个群集都

是一种良好的开始情况对于K的手段。)如果有 K

的

群集和每个群集都有 n

个

点,那么概

率、 p、选择样本的大小 K 最初的中心从每个群集都是按等式8.1的。 (这是假设采样与更

换。)从这一公式,我们可以计算,例如,可能有一初步的中心从四个通道的每个群集是

4/44=0.0938。

多种方式选择一种中心从每个群集

P = =

KnK!

(8.1)

(a) 阴谋的可能性,获得一点从每个群集的大小sampleof K 值的 K 介于2和100之间。

解决方案如图4所示。请注意,概率基本上是0的时间 K =10。

(b) K 群集、 K =10

、

100 和1000,找到的概率样本的大小2K 至少包含一点从每个群集。

您可以使用数学方法或统计模拟,以确定答案。

我们使用的仿真计算得到的答案。分别的概率是0.21, < 10 6、 < 10-6。

从分析的角度出发,对

不要来自某一特定群集

概率的点并不来自某一特定群集,1、因此,概率,2K 点的

是(1-

。因此,概率至少一200点来自某一特定群

集是1-(1-

。如果我们假定的独立(这是太过乐观,但大约如此。值越大, K),然后是

上界的可能性,所有群集都表示在最终的样本是由(1-1-

)

。给定的值这种绑定是

0.27,2007年5.7e和8.2e 64、分别。

图8.2。概率至少一点从每个群集。练习4。

5. 识别群集在图8.3使用中心、毗连和densitybased的定义。还指示群集的每个案例并给出

简短说明你的理由。注意到黑暗的数目或圆点表示密度。如果它有助于、承担中心的意

味着K的手段,连成一片的手段单一链路和密度为基础的手段。DBSCAN

(一) (b) (c) (d)

图8.3。群集的练习5。

(a) 中心提供的 2个群集。矩形的区域将会分成两半的。注意噪音是否包括在两个群集。

毗连的 1群集,因为该两个圆形的区域将被加入的噪音。

密度为基础的 2个群集,每个圆形区域。噪声将会被淘汰。

(b) 中心提供的 1个群集包含两个环。毗连的 2群集的每一环。密度的 2群集的每一环。

毗邻的 1个群集。这三个三角区域将连接在一起,因为他们触摸。

密度为基础的 3个群集,每个三角区域。虽然这三个三角型触摸、密度的地区他们触摸

低于整个内地的三角。

(d) 中心提供的 2个群集。两个组的线路将分为两个部分。毗邻的 5个群集。每个设置

的行言论掺杂将成为群集。

密度为基础的 2个群集。两个组的行定义了两个区域

高密度的分隔区域的低密度。

6. 对于以下列出的两个维度分,(1)提供了一种绘制草图,以了解他们将拆分为群集的K指的给

定数量的群集和(2)表明大致位置产生的中心。假设我们使用的是方形的错误目标函数。

如果您认为有多种可能的解决方案,然后请表明是否每个解决方案是一项全球性的或当地的

最低限度。请注意,该标签的每个图图8.4中与相应的这个问题的一部分,如图8.4(a)与第(一)

部分。

当地最小的全球最小

本地最小

(一) (b)

图8.4。图中的练习6。

(a) K =2。假设该点是均匀地分布在圆内,有多少可能的方法是在那里(理论)的分区的分

成两个群集的吗? 什么位置的两个中心? (再一次,你不需要提供准确的质心位置,仅仅

是一种定性的描述。

在理论上,有无限多的方式来分割圆分成两个群集-只需采取任何行大道的圆圈。这条

线可以让任意角度0◦≤ θ ≤180◦与x轴。该中心将躺在角平分线垂直的线,分割了圈内

的两个群集和将对称的位置。所有这些解决方案都将具有相同的、全球最小的、错误

的。

(b) K =3。之间的距离的边缘界是稍微大于半径的圆。

如果您开始的,最初的中点,是真正的点,你一定会获得这种解决方案,因为限制的界的多

个半径之外。当然,角平分线可以有任意的角度,上述,它可以是其他的圆圈,将被拆分。

所有这些解决方案都具有相同的全球最小的错误。

三个复选框可以显示的三个群集,这将导致在现实的情况下,最初的中点是实际的数据

点。

(d) K =2。

在这两个案例的矩形显示群集。在第一种情况下,这两个群集仅有本地最小而在第二种

情况下的群集是一种在全球范围内最小的的解决方案。

(e) K =3。提示:使用“对称的状况和记住,我们是在寻找一种粗略的草图,将会产生何种结

果。

该解决方案显示在顶部的图,最上面的两个群集装在两个框中,而第三个群集是封闭的

区域定义的三角和矩形。 (两个较小的组中的图应该是对称的。我认为,第二种方案的

建议,学生也有可能,虽然它是一种本地最小,可能很少会在实践中看到的这个配置的点。

注意的是,虽然两个饼形切割出更大的圆圈所示为上一点,这是不一定的情况下,它取决

于精确的位置和大小的圆。有差距的两个饼图形状的削减,是由第三(较大的)的群集。

(想象一下的小圆圈的另一侧)或之间的边界上的两个饼形切口可能实际上是一条线段。

7. 假设的数据集。

• 有

米

积分和 K 群集、

• 一半的点和群集是在“更多”密集区域、•一半的点和群集是在“低密度”区域,

和•这两个区域都分开的。

为给定的数据集,会发生以下情况,以便最大程度地减少squared error当找到 K

的

群集:

(a) 中心应当平等地分布在更多的密集和lessdense地区。

(b) 更多的中心应分配给较密集的地区。

注意:不要分心的特殊情况或带来以外的其他因素的密度。但是,如果你觉得真正的答案是

不同的从任何给定的上述证明,您的响应。

正确的答案是(c)。低密度的区域需要更多的中心如果squared error是最小的。

8. 考虑意味着群集的对象从二元交易的数据集。什么是最小值和最大值的组件的意味着什么?

什么是口译的群集组件意味着什么? 该组件最准确地描绘对象的群集?

(a) 该组件的平均的范围在0和1之间。

(b) 对于任何特定的组件,它的值是小部分的对象在群集的,有1个。如果我们不对称的

Binary数据,如市场棉箱的数据,则可被视为政府的可能性,例如,客户在本集团代表的群

集购买特定的项目。

数据的,因为,对于大多数群集、绝大多数的组件将具有值为零。为常规的二元数据,

例如,结果真实的虚假的检测,重要部件是过高或过低的整个数据集。

9. 举个例子,某个数据集由3个自然组,(几乎都是)K的手段将有可能找到正确的群集,但河沿K

意味着不会。

考虑一种数据集,由三个圆形的群集,这是相同的数量和分布的点,其中心位于一行和位于中

心的中间群集是同样遥远的其他两个。二等分K意味着将永远分离的中间群集在第一次迭

代中,因此,永远不能产生正确的设置的群集。 (后处理可用于解决这种情况。)

10. 将角度的余弦值的措施是适当的相似性测量使用withK的意味着群集的时间序列数据? 为

什么可以或不可以吗? 如果没有,有什么类似的措施,将是更合适的吗?

时间系列的数据密集型的高维数据,因此,余弦的措施将是不适当的,因为角度的余弦值的措

施是适当的,稀疏的数据。如果规模的时间序列是很重要的,那么欧几里德距离将是适当的。

如果只有形状的时间系列都是很重要的,然后关联将是适当的。请注意,如果比较的时间系

列需要考虑到这一系列的时间可能会导致或滞后另一或仅是与另一种在特定的时间段,然

后更先进的方法来建模的时间序列相似性必须被使用。

11. 总的SSE指令集的总和SSE指令集的每个单独的属性。什么itmean如果SSE的变量之一

是低的所有群集的吗? 低只为一群集? 高所有群集的吗? 高只为一群集? 你如何使用每个

变量的SSE指令集的信息以提高您的群集?

(a) 如果SSE指令的属性之一是低的所有群集,则将变量isessentially恒定的和很少使用的

分离的数据划分到不同的组中。

(b) 如果SSE指令集的一种属性是相对较低的一群,则此属性有助于定义群集。

(d) 如果SSE指令的属性是相对较高的一群,则相距赔率与所提供的信息的属性与较低的

SSE指令集,定义群集。它可能仅仅是在这种情况下,群集定义了该属性的不同定义的

其他属性,但在任何情况下,这意味着此属性并不有助于定义群集。

(e) 这一想法是要消除属性差的区别powerbetween群集,即较低或较高的SSE指令的所有

群集,因为它们是无用的群集。请注意,属性高的SSE指令的所有群集都特别麻烦,如果

他们有相对较高的SSE指令集的其他属性(也许是因为它们的分摊比额表以来,引进了

大量的噪音计算总的SSE指令集。

12. 领导者的算法(Hartigan[4])表示每个群集使用的点,称为“

领袖

”和分配每个点到群集的相应

为最接近的领导人,除非这一距离超过用户指定的阈值。在这种情况下,点成为领导人的新

的群集。

注,本文介绍的算法是不完全的领导人的算法中所述Hartigan将点到的第一位领导人在该

阈值的距离。答案适用于算法中所述的问题。

(a) 有什么优点和缺点的领导人算法ascompared K意味着什么?

领导者的算法只需要一次扫描的数据,因此是计算更有效率,因为每个对象都与最终的

一组中心最多一次。虽然领先的算法是订单相关的、固定的订购的对象,它始终产生

相同的群集。但是,与K的手段,这是不可能的数目设置群集产生的领导人算法、除了

间接的。另外,K表示算法几乎总是生产出质量更好的群集上测得的SSE指令集。

(b) 建议如何领先算法可能会得到改善。

使用样本以确定分配之间的距离的点。所获得的知识从这一进程中可以用于更多的

智能化地设置阈值的值。

领导者的算法可以修改群集的几个阈值在单一通道。

13. Voronoi图的 K 点的平面是一种分区的所有各点的飞机到 K

的

区域,每点(平面)被分配到最

接近的点在 K

的

指定点。 (见图8.5)之间的关系是怎样的Voronoi图和K意味着群集吗? 什

么做的Voronoi图中告诉我们可能的形状的K意味着群集吗?

(a) 如果我们有 K 的意味着群集,然后将平面分为 K

的

Voronoi区域的表示点最接近每个

中心。

(b) 之间的边界上出现群集中分段构建“线性”。有可能这tosee绘制一条线连接两个中心

然后绘制垂直的线之间的一半位置处的中心位置。这种垂直的线拆分平面分成两个

区域,每个包含点中最接近中心的区域中包含的。

图8.5。 Voronoi图的练习13。

14. 你是给定的数据集与100的记录并要求群集数据。您可以使用K意味着群集的数据,但对于

所有值的 K,1≤ K ≤100 K指算法仅返回一非空的群集。您然后应用增量版本的K,但却获得

完全相同的结果。这是如何可能的? 如何将单个链路或DBSCAN处理此类数据的吗?

(a) 该数据由完全重复的一种对象。

(b) 单一的链接(和许多其他的种种机遇分层计划会产生分层群集,但这点会出现在哪个群

集将取决于订购的点和精确的算法。但是,如果被dendrogram绘制显示接近每个对

象将被合并,然后它会很明显的是,数据是重复的。 DBSCAN能找到所有的点是核心点

连接在一起并产生一种单一的群集。

15. 传统的种种机遇分层群集的例程合并两个clustersat的每个步骤。它似乎有可能这种方法

准确地捕获(嵌套)群集结构的数据集的点吗? 如果没有,说明您可以如何进行后期处理的数

据以获取更准确的查看的群集结构。

(a) 这种方法并不准确地捕获的嵌套群集的数据结构。例如,考虑一组三个组,每个都有两

个、三个和四个小类,分别为。理想的分层结构的群集将有三个分支从根一至三个主

要群集的然后两个、三个和四个分支机构从每个群集。传统的种种机遇的方法不能

产生这样的一种结构。

(b) 最简单的类型的后处理将试图将其抚平的分层结构的群集的群集在树中。

16. 使用的相似性矩阵表8.1执行单一和完整linkhierarchical群集。显示您的结果绘制

dendrogram。 Dendrogram的应明确显示的顺序点被合并。

该解决方案显示在图8.6(a)和8.6(b)。

17. 分层的群集有时用于生成 K 群集、 K> 1的群集上的 Kth 级别dendrogram。 (根目录是在级

别1)的群集产生的这种方式,我们就可以评估的行为层次上的群集不同类型的数据和群集,

也比较的分层方法K的手段。

以下是一组的一维积分:{6

、

48。

(a) 对于下面的每个设置的最初的中点,创建两个clustersby分配每个点到最近的中心位置,

然后计算表8.1。相似矩阵的练习16。

P 1 P 2 P 3 P 4 P 5

1.00 0.10 0.41 0.55 0.35

0.10 1.00 0.64 0.47 0.98

0.41 0.64 1.00 0.44 0.85

0.55 0.47 0.44 1.00 0.76

0.35 0.98 0.85 0.76 1.00

2 5 3 4 1

2 5 3 1 4

(一)单一的链接。 (b)完整的链路。

图8.6。 Dendrograms练习16。

总的平方误差每组的两个群集。显示群集的总squared error的每组的中心。

我。 {18

、

45}

第一组是6、12、18、24、30。

Error=360。

第二个群集是42、48。

Error=18。

总错误=378二、{15

、

40}第一集为6、12、18、24。

Error=180。

第二个群集是30、42、48。

Error=168。

总错误=348。

(b) 做两套,中心位置代表稳定的解决方案;即,如果K meansalgorithm是运行在该组的点

使用给定的中心位置作为起始的重心将会有任何变化,在“群集”生成的吗?

是的,这两个中心都是稳定的解决方案。

在两个群集是{6、12、18、24、30日}和{42、48}。

(d) 这种技术,K的手段或单链接,似乎产生了“mostnatural"群集的这种情况吗? (对于K的

手段,采取群集的最低squared error)。

最小可产生最自然的群集。

(e) 什么定义的群集没有这种自然的群集correspondto吗? (好分隔的、中心的、连续的、

或密度)。

最小的以太网地址的连续生产的群集。但是,密度也可以接受的答案。即使是中心的

是可以接受的,因为一组中心提供所需的群集。

(f) 什么众所周知的特点K指算法说明theprevious行为吗?

K的意思是不太好,找到群集的大小不同,至少当他们没有得到很好地分隔。造成这种

情况的原因是,目标是最大程度地减少squared error导致它“休息”的更大的群集。因

此,在这一问题的低错误群集解决方案是“非自然的”。

18. 假设我们要查找 K

的

群集使用的病房的方法、河沿K的手段,和普通的K的手段。而这些

解决方案代表了当地或全球最低? 解释一下。

虽然病房的方法取一对群集进行合并的基础上最大程度地减少SSE、没有完善的步骤经常K

的手段。同样,二等分K意味着没有整体的细化步骤。因此,除非这种改进步骤是添加的,

既没有病房的方法也不偏袒K意味着产生一种当地的最低限度。普通K意味着生成的本

地最小,但就像其他两个算法,它不保证产生的全球最低。

19. 分层的群集算法要求 O(m

log(m))的时间,因此,都是不切实际的,直接使用于较大的数据集。

一种可能的技术,从而减少所需的时间进行采样的数据集。例如,如果 K 群集所需的和√m 点

的采样从 m 点,然后分层聚类算法将产生一种分层结构的群集中的大约 O(m)的时间。 K 群

集可以从这种分层的群集的群集上的 Kth 级别dendrogram。剩下的点可以被分配到群集

在线性的时间,通过使用不同的策略。要给出具体的例子,的质心 K 可将群集计算的,然后每

个 m -√m 剩余点可以分配给该群集与最近的中心。

对于下列每种类型的数据或群集、简略地讨论一下如果(1)采样将导致问题的这种做法

和(2)有什么问题的。假定采样技术随机选择点的总集, M 点的,任何没有提到数据的特征或群集

的优化。换句话说,仅集中于所造成的问题。特别是提到的特点。最后,假设 K 是很少于

米

。

(a) 数据有很大的不同大小的群集。

这可能是个问题,特别是如果在数量的点在群集是小的。例如,如果我们有一千多点,有两个

群集、一大小900和1的大小为100和 5%的样本,然后我们将平均最终以45个积分从第

一集和第5点的第二个群集。 5点是很容易错过或群集不正确50。另外,第二个群集有

时会派代表出席会议的不到5点,就在自然的随机样本。

(b) 高维数据。

这可能是个问题,因为数据在高维空间中通常是稀疏矩阵和多点可能需要定义结构的群集

在高维度空间。

根据定义,异常值不是很频繁,他们大多数不会被采样。因此,如果找到了正确的群集依赖于

有异常值,该群集产生的采样将有可能被误导。否则,它是有益的。

(d) 数据与极不正当的区域。

这可能是个问题,因为该结构的边界可能会丢失当采样除非有大量的点进行采样。

(e) 数据与球状的群集。

这通常不是问题,因为不是很多点需要采样保持结构的球状群集作为不规则的一种。

(f) 数据广泛不同的密度。

在这种情况下的数据往往会将来自更密集的地区。请注意,采样是降低密度的所有群集上

的采样系数,例如,如果我们有10%的样本,然后有密集的群集数量减少10倍。对于群集,

不是非常密集的首先,这可能意味着,他们现在都视为噪声或异常值。

(g) 数据有很小比例的噪声点。

采样都不会导致问题。其实,因为我们要排除噪声干扰和自的噪音很小,这可能是有益

的。

(h) Non-Euclidean数据。

这没有特别大的影响。

(i) 辗转相除的数据。

这没有特别大的影响。

(j) 数据与许多和混合属性的类型。

许多属性的讨论在高维度性。混合在─

祝福没有特别大的影响。

20. 考虑以下的四面如图所示8.7。再次、黑暗的ornumber点表示密度。行仅用于区分地区

并不代表点。

(a) (b) (c) (d)

图8.7。图为演习20日。

(a) 对于每个图,您可以使用单一的链接查找模式representedby鼻子、眼睛和嘴巴吗? 解

释一下。

仅用于(b)和(d)。 (二)、点鼻子、眼睛和嘴巴都是很接近的点的这些区域之间。 (d)

只有空间之间的区域。

(b) 对于每个图,你能使用K的手段来找到的模式的representedby鼻子、眼睛和嘴巴吗?

解释一下。

仅用于(b)和(d)。 (b)、K意味着将找到的鼻子、眼睛、嘴、但低密度点也将包括在

内。 (d)将Kmeans查找的鼻子、眼睛、嘴里干脆只要群集数设置为4。

群集技术可以只查找模式的点,而不是空格。

21. 计算熵和纯度的混淆矩阵表8.2中。

表8.2。混淆矩阵的练习21。

群集

娱乐

财务

外国的

地铁国家

体育

总

熵。

纯度

站

676

693

0.20

0.98

333

827

253

1562

1.84

0.53

326

465

105

949

1.70

0.49

354

555

341

943

273

738

3204

1.44

0.61

总

22. 你有两个设置为100点,属于单位的广场。一组点的安排,以便点均匀布置。其他的点集生

成均匀的分布在单位正方形的。

(a)

有什么区别这两个点集的吗?

是的。随机点将有区域较小的或更高的密度,而均匀分布的点当然,密度均匀在整个单

元的广场。

(b)

如果是这样的话,点集通常具有较小的SSE指令集的K=10群集吗?

随机的点会有较低的SSE指令集。

(c)

将有什么行为的DBSCAN在划一的数据集? Therandom数据集?

DBSCAN将合并所有的点划一的数据设置到某个群集或把它们所有的噪音、视阈值。

可能会存在一定的界限问题点的边缘地区。然而,DBSCAN常常可以找到群集中的随

机数据,因为它也有某些变异的密度。

23. 使用数据在行使24、计算的silhouette系数eachpoint中的每个群集,该群集的整体。

群集包含1{P 1,P 2},第2组包含{P 3,P 4}。差异性的矩阵,我们获得的相似度矩阵如下:

表8.3。表的距离练习23

P 1

0.10

P 2

P 3

P 4

”。

0.10

0.65

0.55

0.70

0.60

0.30

0.65

0.70

0.55

0.60

0.30

让显示的平均距离的点到其他点的群集。让 b 指示最小的平均间距的点到点的另一群

集。

P点1:SC=1-a/b=1——0.1/函数(0.65+0.55)/2)=5=0.833

P点2:SC=1-a/b=1——0.1/((0.7+0.6)/2)=0.846

P点2:SC=1-a/b=1——0.3/函数(0.65+0.7)/2)=0.556

P点2:SC=1-a/b=1——0.3/函数(0.55+0.6)/2)=0.478

第1组平均SC=(+0.846 0.833)/2=0.84

第2组平均SC=(+0.478 0.556)/2=0.52

总体平均SC=(0.840+0.517)/2=0.68

24. 给定的一组群集的标注和相似度矩阵显示在表8.4 and8.5分别计算两者之间的相似度矩

阵和理想的相似度矩阵,即矩阵的 ijth 条目是1如果两个对象属于同一群集,否则为0。

表8.4。表中的群集的标注练习24。表8.5。相似矩阵的练习24。

P 3 P 4

P 1 1

P 1 1 0.8 0.65 0.55

P 2 1

P 2 0.8 1 0.7 0.6

P 3 2

P 3 0.65 0.7 1 0.9

P 4 2

P 4 0.55 0.6 0.9 1

我们需要计算两者之间的向量 x =< 1

、

1 > 和向量 y =< 0.8

、

0.65

、

0.55

、

0.7

、

0.6

、

0.3 >,这是两者之间的非对角元素的距离矩阵和理想的相似度矩阵。

点群集的标签点

P 1

我们获取:

标准偏差的矢量 x : σx =0.[5164]没有值的标准偏差的矢

量 y : σy =0.1703协方差的 x 和 y轴:含(x,y)=-0.200因此,corr(x,y)=涵

盖(x,y)/σxσy =-0.227

25. 计算分层F的测量的8个对象{p 1、p 2、p 3、p 4、p 5、p 6、p 7、p 8}和分层的群集图

图8.8。类包含点p 1、p 2、p 3,而p 4、p 5、p 6、p 7、p 8属于B类地址。

图8.8。分层的群集的练习25。

让 R(i,j)=

后者

/ni 表示调用的类

我

的群集 j。让 P(i,j)=

后者

/nj 指示精度为 I

类

的群集 j。

F(i,j)=2R(i,j)×P(i,j)/(R(i,j)+P(i,j))是F的测量类

我

和群集 j。

用于群集1={p1

、

p8}:

Class=A:

R(A,1)=3/3=1,P(A,1)=3/8=0.375 F(A,1)=2

0375/(1+0375)=0.55

Class=B:

R(B,1)=5/5=1,P(A,1)=5/8=0.625,F(A,1)=0.77

用于群集2={p 1、p 2、p 4、p 5}Class=A:

R(A,2)=2/3P(A,2)=2/4,F(A,2)=0.57 Class=B:

R(B,2)=2/5,P(B,2)=2/4,F(B,2)=0.44的群集3={p 3,p 6,p 7,p

8}Class=A:

R(A,3)=1/3P(A,3)=1/4,F(A,3)=0.29 Class=B:

R(B,3)=3/5,P(B,3)=3/4,F(B,3)=0.67

× 1 ×

用于群集4={p 1,p 2}Class=A:

R(A,4)=2/3P(A,4)=2/2,F(A,4)=0.8级=B:

R(B,4)=0/5,P(B,4)=0/2,F(B,4)=0

用于群集5={p 4,p 5}

Class=A:

R(A,5)=0,P(A,5)=0,F(A,5)=0 Class=B:

R(B,5)=2/5,P(B,5)=2/2,F(B,5)=0.57

用于群集6={p 3,p 6}

Class=A:

R(A,6)=1/3P(A,6)=1/2,F(A,6)=0.4级=B:

R(B,6)=1/5,P(B,6)=1/2,F(B,6)=0.29

用于群集7={p 7,p 8}

Class=A:

R(A,7)=0,P(A,7)=1,F(A,7)=0 Class=B:

R(B,7)=2/5,P(B,7)=2/2,F(B,7)=0.57

A类: F(A)=max{F(A,j)}=max{0.55

、

0.57

、

0.29

、

0.8

、

0.4

、

0}=0.8

B类: F(B)=max{F(B,j)}=max{0.77

、

0.44

、

0.67

、

0.57

、

0.29

、

0.57}=

0.77

整个群集:

26. 计算cophenetic相关系数的分层clusteringsin练习16。 (您将需要转换的异同为差异。)

这可以很容易地计算出使用的软件包,例如MATLAB。答案是单链、0.8116和完整的链接、

0.7480。

27. 证明方程8.14。

=SSE指令集

十字词

28. 证明方程8.15。

=办学团体。

再次,跨

29. 证明)=0。

期取消。

这是用于证明TSS=SSE+SSB上页557。

30. 群集的文档可归纳查找前(字)中的文档集,例如通过采取最频繁的 k ,其中 k 是常数,说10、或

考虑到的所有条款,更经常发生于指定的阈值。假设K指的是用于查找群集的两个文档和

文字的文档的数据集。

(a) 如何可能一组术语定义群集的顶层,在documentcluster不同word找到的群集的群集

术语与K的意味着什么?

第一,顶字群集可能、很可能会在某种程度上相互重叠。第二,它是可能的,很多条款将

不会出现在任何的群集形成的顶部。相比之下,K意味着群集的条款将涵盖所有的条

款和不重叠。

(b) 如何能够长期的群集可用于定义群集的文档吗?

一种明显的方法是将文档的术语"群集";即,这些文档的最频繁的包含这些条款中的群

集。

31. 我们可以表示一组数据的集合对象的节点和collectionof属性节点,是联系在一起的每个对

象的每个属性的权重的链接的对象的值的属性。对稀疏数据,如果该值为0,链接被省略了。

两大部份群集将尝试分区此图为不相交的群集,每个群集都包含一组对象的节点和属性节点。

我们的目标是以最大的权重之间的联系对象和属性节点的群集,同时最大限度地减少重量之

间的链接对象和属性的链接在不同的群集。这种类型的群集还称为合作的群集 ,因为该对

象和属性都是集中在同一时间。

(a) 如何为两大部份群集(clustering)不同群集thesets对象和特性的单独购买?

经常群集,仅有一组的限制,有关对象或属性,是适用的。在合作的群集的两个限制的应

用同时进行。因此,分区的对象和特性的相互独立的另一种通常不会产生相同的结果。

(b) 是否有任何情况下,这些方法产生相同的群集?

是的。例如,如果设置的属性是只与该对象在某个特定的群集,即有0个重量的物体在

所有其他群集和相反的一组对象的群集有0个重量为所有其他的属性,然后在找到的

群集的群集将会匹配那些找到的群集的对象和特性的单独销售的。要使用的文档为

例,这将对应的文档的一组数据,包括文档组,仅包含特定词和组词仅出现在某些文档中。

合作自动群集提供了一种描述群集对象的属性,可以将更多的有用的不是描述群集作

为分区的对象。然而,属性的属性区分不同的群集的对象,可能会相互重叠的机会大大

增加,在这种情况下,合作的群集将不能很好地工作。

32. 在图8.9中的匹配的相似度矩阵,按tocluster标签、有的点的集合。差别的阴影和标记的

形状区分群集和每个点集包含100个点和三个群集。在设置的点标记为2,有三个很紧,同

样大小的群集。

答案:1-D、2-C、3-A、4-B

1 2

图8.9。点和相似度矩阵用于练习32。

群集的分析:

更多的问题和算法。

1. 对稀疏数据、讨论为什么只考虑是否存在非零valuesmight给出更准确的查看

的对象除了要考虑实际的幅度值。如果将这种做法是不可取的?

考虑文档数据。直观的、两个文档类似的如果它们包含许多相同的单词。虽

然我们也可以包含的频率与这些词出现的相似性计算的,这有时会给出不可

靠的评估的相似性。特别是,如果某个字词在文档中出现,而往往比其他的字,

然后这个词可以支配的相似性时比较不同程度的考虑。在这种情况下,文档

才会高度相似的其他文件,也包含相同的字词有很高的频率。虽然这可能是

适当的,许多甚至大多数情况下,这可能会导致错误的结论如果字词可以出现

在不同的背景下,这只能是尊敬的,其他的单词。例如,在Word中,“游戏”频繁

出现在讨论运动和视频游戏。

2. 描述更改的时间复杂度为K的手段的数目ofclusters可以找到增加。

作为组的数目,增加的复杂性,K表示方法 O(m

。

3. 考虑一组文档。假设所有的文档都已被标准化的单位长度是1。什么是“形状”

的群集包含的所有文档,其余弦相似性的质心是大于指定的某些常量吗? 换言

之,cos函数d

、

c)≥ δ、其中0 <δ ≤1。

一次文档引导程序已标准化,它们躺在我的 n维hypershpere。约束的所有文档

都具有最低限度的余弦相似性的中心是一种约束,该文件引导程序内的圆锥形,其

交集的领域是一种圆形表面上的领域。

4. 讨论的优点和缺点的治疗群集作为一种优化的问题。除其他因素外,考虑效率、

非确定性和是否有优化的方法捕获所有类型的clusterings感兴趣的。

两个关键优势治疗群集作为一种优化的问题,(1)它提供了一种明确的定义,什么

是群集的过程中所做的工作,和(2)它允许使用的功能强大的优化技术开发的各

种字段。不幸的是,大多数这些优化技术有着很高的时间复杂度。此外,它可以

显示,许多优化问题是NP难,因此,有必要对使用的启发式优化的办法,只能保证本

地的最优解决方案。往往这种技术的工作最好在使用随机初始化,因此,找到的解

决方案可能会有所不同从一台运行,另一台。另一项问题的优化方法是目标函数

使用倾向于大群集而牺牲较小的。

5. 什么是时间和空间复杂度的模糊c意味着什么? 亚太经合组织高官会的吗? 如

何dothese复杂的比较K意味着什么?

其时间复杂度为K的手段 O(I * K * m * n),在那里

我

是迭代的次数达到收敛所

需, K 是簇的数目, m 是的点的数目, n 为数字的属性。所需要的时间的模糊c的

方法基本上是相同的,K的意思,尽管不断的要高得多。时间复杂性的亚太经合组

织高官会也基本上是相同的,Kmeans因为它由多个通过指派的对象质心和重心

都会更新。但是,由于周围的重心也会进行更新和遍数可以很大,亚太经合组织高

官会将通常会低于K的手段。

6. 传统的手段有一定的限制,如敏感异常值和难以处理群集不同的大小和密度、或

与非球状的形状。评论能力,模糊c的手段来处理这些情况。

模糊的c意味着所有的限制,传统的手段,但它本身并不能使硬盘指派的对象添加

到群集。

7. 对模糊的c方法的算法描述在这本书的总和成员资格的任何点的所有群集上的

为1。相反的,我们只可以要求会员学位点在群集在0到1之间。什么是这种

做法的好处和坏处?

主要的优势,这种方法时一点是离群值并不真正属于非常坚决地对任何群集,因

为在这种情况下,点可以有较低的成员在所有群集。但是,这种办法往往是难以

正确地初始化和可执行差当群集并不都是不明显的。在这种情况下,群集的几

个中心可能会合并在一起,或群集的中心可能有很大差异。一次迭代到另一、而

不是更改仅略有增长,但作为普通的K的手段或模糊的c的方法。

8. 解释的差异可能性和概率。

概率是,根据一种共同的统计定义的频率。事件发生时的实验往往至无穷大。概

率是定义的是概率密度函数的函数的属性值的对象。通常,一种概率密度函数

取决于某些参数。考虑到概率密度函数是函数的参数产生的可能性的功能。

9. 等式9.12给出的可能性的一组点的高斯分布的函数的意思是

基于

0.13

微米工

艺

的标准偏差 σ。显示在数学上的最大的可能性估计的 0.13 μ 和 σ 的样本平均

值和样本的标准偏差。

首先,我们解决的问题

基于

0.13

微米工艺的

。

此设置为等于0和解决问题的,我们得到的。

同样,我们可以解决的 σ。

此设置为等于0和解决问题的,我们得到的。

10. 我们采取一样的成人并测量其高度。如果我们记录每个genderof人,我们可以

计算出的平均身高的差异的高度,分别为男子和妇女。假设,但是,这种信息是不

被记录的。才有可能仍在获取这一信息? 解释一下。

高度的男子和妇女都将有单独的高斯分布有不同的手段和可能的不同差异。

通过使用混合模型的方法,我们可以获得的估计数的平均值和方差的两个高度

的分布。由于有了足够大的样本大小的估计参数应当接近于那些可以计算的

如果我们知道了性别的每一个人。

11. 比较会员配重和概率的数字9.1和9.4,是分别从应用模糊和EM的群集到一组相

同的数据点。什么区别您检测、您如何解释这些差异?

在模糊群集方法仅分配给很高的权重的几点中心的群集。这些点较近的两个

或三个群集具有相对较低的权重。这几点都是在最边缘的群集、远离其它群

集也具有较低的权重比的中心要点,但不是低点附近的两个或三个群集。

在64群组的方式指派高权重的两个点在中心的群集和这些较远的边缘。的点

附近的两个或三个群集具有较低的权重,但不是很多,有的模糊不清的群集的步

骤。

两者主要的方法是,点在远边的群集获得更远的中心的群集上的重量与它是属

于群集将会变为更平等的群集的群集的模糊不清的办法,但对EM的方法的点往

往属于更强烈的群集,它是最接近的。

12. 图9.1显示了群集的一种二维的点数据集与twoclusters:最左边的群集的点标以

星号,有些分散,而最右边的群集的点的特点是圆、是紧凑的。右边的紧凑型群

集、有单点(标有箭头)属于分散群集,其中心是更远的紧凑的群集。请解释为什

么这种可能与64群集,但不能K意味着群集。

在64群集,我们计算的概率点属于群集。反过来,这种概率取决于这两个距离

的群集的中心和分布(方差)的群集。因此,某一点,更接近中心的一群比另一仍

然可以有更高的概率就更遥远的群集如果该群集具有较高的传播近的群集。 K

表示只考虑到距离最近的群集时指定的群集。这是相当于EM的方法在所有群

集都被假设为具有相同的差异。

图9.1。数据集的练习12。 64群集的二维点集与两个群集的不同的密度。

13. 显示群集的手动换档变速箱技术的节9.4.2生成sameclusters作为单一的链接。

为了避免并发症和特殊的情况下,假设所有的两两相同之处都是明显的。

在单一的链接,我们开始与群集的单个点然后依次加入两个群集上,有一对点

的最亲密的在一起。从概念上讲,我们可以查看合并的群集,如把一边的两个

最近的点的两个群集。请注意,如果两个群集上的当前连接,然后由此产生的

群集也将被连接。然而,由于群集形成的不相交的点的集合,并边仅放在不同

的群集、无周期可形成。从这些意见和指出,我们开始使用的群集(图),大小

为1的连接vacuously,我们可以推断出的感应,在任何阶段,都在单一的链接群

集的过程中,每个群集的连接的点集没有任何循环。因此,当最后的两个群集

均合并成为单一的群集包含的所有各点,我们也有相连接的图形的所有的点,

是一种生成树的图形。此外,由于每个点的图是连接到其最接近的点的?生成

树?必须是最小生成树。所有这仍然是建立在等价的手动换档变速箱和单一

的链接。请注意,手动换档变速箱基本上是相反的过程,在这个过程中,单链接

内置最小生成树;即打破的边缘开始时间最长的和继续,直到最小的。因此,

它会生成相同的群集作为单个链接,但请按相反的顺序进行。

14. 一种sparsify感应矩阵如下:对于每个对象的行矩阵)、设置所有项为0的除外

对象相应 k-最近的邻居。但是,近距离sparsified矩阵通常不是对称的。

(a) 如果对象 a 是 k-近邻的对象 b、为什么是 b 不一定会在 k-近邻的 ?

审议一项密集的 k得对象和其它对象的一种离群,这是从更远的对象比他

们从每个其他。没有对象的密集的设置将有离群值的 k-最近的邻居列表

中、但异常会有 k 的对象从密集集在其 k-近邻的列表。

(b) 建议至少有两种方法可用来使sparsified接近开关矩阵的对称。

一种方法是将 ijth 条目为0如果 jith 条目为0,反之亦然。另一种方法是

设置 ijth 条目为1如果 jith 条目为1,反之亦然。

15. 举个例子,一组组的合并根据closenessof群集将导致更多的自然组群集于合并

基础上的力量连接()的相互联系的群组。

例子之一是给定的变色龙纸,就可以找到在/ karypis/

出版物/文件/PDF/变色龙。该示例包含两个窄的矩形,点的两侧。顶部矩形被

拆分成两个组,有一组规模小得多的比其它的。即使两个矩形的顶部是接近的,

他们是没有强烈的连接由于它们之间的关系都是在很小的区域。在其他方面,

最大的矩形的顶部和矩形的底部的强烈关连。每个单独的连接不牢固,因为这

两个矩形的不近,但有更多的人,因为该地区的连接是很大的。因此,一种基于连

通性将合并的最大矩形的顶部与底部的矩形。

16. 表9.1列出了两个最近的邻国的4点。

计算SNN5793A相似的每一对点使用定义的相似性SNN5793A定义在算法9.10。

以下是相似SNN5793A矩阵。

17. 对于定义的相似性SNN5793A提供算法9.10的计算距离SNN5793A不考虑位

置的共享的表9.1。两个最近的邻国的4点。

点第一邻居第二个邻居

1 4 3

2 3 4

3 4 2

4 3 1

表9.2。两个最近的邻国的4点。

点

1 2 3 4

2 0 0 1

2 0 2 1 0

3 0 1 2 0

4 1 0 0 2

邻居的两个最近的邻居列表中。换句话说,它可能需要更高的相似性2点共享

相同的最近的邻国在相同或大致相同的顺序。

(a) 介绍您可以如何修改定义SNN5793A类似givehigher相似点,其共享的邻

居是在大致相同的顺序。

这可以通过分配的权重的几点基于他们的位置在最近的邻居列表中。例

如,我们可以在重量的点在最近的邻居列表中的 n - i +1。对于每个点,然

后我们采取的总和或产品的排在两个列表中。这些值然后相加来计算之

间的相似性的两个对象。这种方法是由贾维斯和帕特里克[5]。

(b) 讨论的优点和缺点,这种改动。

这种方法是更复杂的。但是,它是有利的,如果是这种情况,两个对象的更

多类似的如果共享的邻居都是大致相同的牌。此外,它还可能有助于补偿

任意选择 k。

18. 名称至少在一种情况下,您不希望使用群集基于SNN5793A相似或密度。

当您想要根据群集的绝对密度或距离。

19. 网格的群集技术不同于其它的群集技术inthat他们分区空间而不是点集的。

(a) 这将如何影响到这种技术的描述theresulting群集和群集类型,就可以找

到吗?

在基于网格的群集,该群集是叙述的集合相邻的单元格。在某些情况下,

例如在集团、更紧凑的描述是生成的。在任何情况下,描述群集是给定的

某一区域的空间,而不是设置的对象。 (不过,这种说明可以方便地生成。)

是必要的,因为它的工作的矩形区域,该形状的非矩形的群集只能是近似的。

但是,组相邻的单元格可以有孔。

(b) 哪种类型的群集可以找到基于网格的群集实时映像中无法找到的其他类

型的群集的办法吗? (提示:请参阅练习20第8章,第564页)。

通常,基于网格的群集技术仅注意到茂密的地区。但是,这种技术也可以用

来识别稀疏或空的区域,从而找到形态,没有点。但是请注意,这是不适当的

稀疏数据空间。

20. 在集团的阈值用于查找群集的密度保持不变,即使是维数的增加。这是一种潜

在的问题,因为密度低的维度性增加;即找到群集在更高的维度的阈值必须设置

在一定程度上很可能会导致合并的低维群集。评论您是否觉得这是真正的问题,

如果是的话,您可能如何修改集团为解决这一问题。

这是真正的问题所在。类似的问题存在于协会的分析。特别是支持协会模式,

大量的项目往往很低。找到这种模式使用的算法有Apriori是困难的,因为较低

的支助所需的阈值的结果是大量的关联模式有几个项目,就没有什么太大的兴

趣。换言之,关联模式的许多项目(模式在高维空间)的有趣的支持级别(密度),

不做的有趣图案的大小关联模式(尺寸)是低的。一种方法是减少支持的阈值

(密度的阈值)的项目(维数的增加。

21. 给定的一组点的欧几里德空间,正在群集使用的K指算法欧几里德距离、三角不

平等可以用在分配中的步骤以避免计算所有距离的每个点到每个群集的质心。

提供了常规的讨论如何实现这一工作。

Charles Elkan提出以下定理在主旨发言研讨会上的群集数据High-Dimensional

SIAM 2004。

Lemma 1:让 x 点,让 b 和 c 是中心。如果 d(b

、

c)≥2d(x,b) d(x,c)≥ d(x,B)。

证明:

我们知道 d(b

、

c)≤ d(b,x)+ d(x,c)。

所以 d(b

、

c)- d(x,b)≤ d(x,c)。

现在 d(b

、

c)- d(x,b)≥2d(x,b) d(x,b)= d(x,B)。所

以 d(x,b)≤ d(x,c)。

这一定理可以消除大量的不必要的距离计算。

22日。而不是使用该公式源于治疗见等式9.19的我们可以运行Monte Carlo模拟

直接估计的概率样本的大小 s 将至少包含一定比例的积分与群集的连接。使用

蒙特卡罗模拟计算的概率样本的大小 s 有50%的内容的群集大小100总点数量

为1000个,其中的值可以是100、200或500。

这个问题应该说是“包含

至少

50%”。

结果,我们的模拟包括10万审判0、0和0.54,样本大小为100、200和500元。

异常检测

1个。比较和对比不同的技术的异常检测,在第10.1节。特别是,试图确定在这

种情况下定义的异常使用的不同的技术可能等同于或在何种情况下可能会使

传感,但不会。一定要考虑到不同类型的数据。

第一,注意到,近距离和密度的异常流量检测技术是相关的。具体而言,高浓度

的邻居一点意味着,很多点都靠近它,反之亦然。在实践中,密度通常定义的距

离,但它也可以使用定义的基于网格的方法。

“基于模型的方法几乎可用于任何底层的技术,适合模型的数据。但是请注意,

特定的模型、统计或其他方式,必须假设的。因此,基于模型的方法是受到限

制的数据可以被应用。例如,如果该模型假设的高斯分布,则它不能应用到数

据的非高斯分布。

在其他方面,近距离和密度的办法不使任何特定的假设的数据,虽然定义的一

种不正常的现象也不同而有不同的感应——或密度为基础的技术。近距离的

方法可用于几乎任何类型的数据,但近距离的度量必须选择适当的。例如,欧

几里德距离通常用于密集型的、低维度的数据,而余弦相似性测量用于稀疏的、

高维数据。因为密度通常定义的接近、密度为基础的方法也可用于几乎任何

类型的数据。不过意思的密度较不明显的是,在非欧几里德空间的数据。

近距离和密度的异常检测方法通常可以产生类似的结果,虽然有相当大的差

异的技术,不考虑浓度差异在整个数据集或使用不同的感应的措施相同的数

据集。基于模型的方法往往会有很大的不同,从proximityand密度为基础的

办法。

2. 请考虑以下定义的异常:异常是一种objectthat非常有影响力的建立的数据模型。

(a) 比较一下此定义,标准模型为基础的definitionof反常的情况。

标准的基于模型的定义标注对象不适合模型非常以及不正常的现象。虽然

这些对象通常都是非常有影响的模型,它也可以是一项非常有影响力的对

象可以配合的很好。

(b) 是什么规模的数据集(小型、中型或大型的)是这definitionappropriate吗?

这一定义通常更适合较小的数据集,至少如果我们谈论的是一名非常有影

响力的对象。不过,相对较小的组有高度影响力的对象可以有重大影响的

一种模式,但仍然配合得好,即使是中等或较大的数据集。

3. 在一种异常检测、对象表示为点ina多维空间的点分为连续的炮弹,每个壳是一

层周围的一组点的,如外接多边形。对象是一种不正常的现象如果在外壳。

(a) 而定义的一种不正常的现象在部分10.1.2是这一定义最密切有关的吗?

这一定义的是关系最密切的距离的方法。 (二)名称的两个问题的这一定义

的一种不正常的现象。

i. 对于“外接多边形”的办法,远距离的con的搅扰多边形的中心点可以有

很大差异。如果该分发点的不是对称的。

ii. 这种方法并没有设定有意义的编号的ICAL中的反常现象的分数。

4. 关联分析可以用来查找异常情况如下所示。找到强大的协会模式,这涉及到某些

最小数量的对象。异常是那些对象不属于任何这种形态。为使这一更为具体的,

我们注意到,hyperclique关联模式的讨论在第6.8节“特别适合于采用这种办法。

具体地说,由于用户选择的h的信任级别、最大hyperclique模式的对象都找到。

所有的对象,并不出现在最大模式hyperclique至少三个大小可分为离群值。

(a) 此种技术属于任何类别的讨论,thischapter吗? 如果是这样,这一?

在hyperclique,所有成对的对象有保障的余弦相似性的信任或更高。因此,

这种方法也可以被看作是一种近距离的方法。但是,而不是一种状态的距

离的对象就某一特定的对象,有的要求在成对的组合中所有的对象。

(b) 名称一种潜在的力量和一种潜在的弱点,采取这一做法。

实力,这种方法是(1)的对象不属于任何大小3 hyperclique不强烈连接到其

他对象,并可能反常的现象,(2)它是计算的效率。潜在的弱点是(1)该方法不

指定数值异常的分数,但简单的分类对象为正常或异常,(2)它是不可能直接

控制对象的数目分为异常情况,因为只有参数是h的信任和支持的阈值和(3)

的数据需要Keyword for DISCRETIZED Method（将EQUAL_AREAS。

5. 讨论技术,结合多种异常检测技术提高了识别的异常对象。考虑这两个监督,不受

监督的情况下。

在监督的情况下,我们可以利用合奏分类技术。在这些不同的是,这一分类的对象

是由相结合的分类法的分类器的数量,例如,通过投票。在不受监督的方式、投票

的方法也可以使用。请注意这是假设,我们有二元赋值的对象是一种不正常的现

象。如果我们有异常的分数,那么分数可以合并在某些方式,例如平均或最小、产

生的总分数。

6. 描述可能的时间复杂度为异常检测approachesbased的以下方法:基于模型的使

用群集、proximitybased和密度。没有知识的具体方法是必需的。而是把重点

放在基本的计算需求的每个方法,例如所需的时间来计算密度的每个对象。

如果K意味着群集的复杂性是由查找群集。这需要一定的时间成比例的对象的

个数,即 O(m)。距离和密度的方法,通常需要计算所有的成对穿过天空,因此,复杂

。在某些情况下

例如

在低维数据、特殊技术

如

树或

k-d

树可用于计算最近的邻国的对象更有效

即

性往往是 O(m

O(m日志

m),这可以减少总体复杂性当该技术仅基于最近的邻居。另外,基于网格的方法

来计算密度可降低复杂性,密度为基础的异常检测到 O(m),但这种方法不准确,只

有有效的较低层面。

7. “Grubbs’检测,所描述的算法10.1,这是一种更statisticallysophisticated程序检测

异常值,定义 1030。这是迭代和也考虑到的是,在z分数不正常分布。这种算法

计算的z得分,每个值的样本平均值和标准偏差的当前设置的值。该值与最大程

度的z分数是被丢弃的如果其z分数大于 gc的临界值的测试的离群值的显著性

水平 α。重复这一过程直到没有对象的消除。请注意,样本平均值、标准偏差

和 GC 的更新在每次迭代。

算法10.1 Grubbs'的办法,消除异常。

输入的值和 α

的

值的个数, α 是参数, tc 是一种价值选择,使 α = prob(x ≥ tc)的 t 分布

的 m -2个自由度。

重复

计算样本平均值(x)和标准偏差(sx)。

计算值 gc 以

便 prob(|Z|≥ gc)= α。

(在 tc 和

计算z分数的每个值,即 z =(x - x)/sx。

让 g =max|Z|,即找到z分数的最大的规模和 g。

如果 g>gc 然后

消除对应的值 g。

M ← m -1

10:

End If

11:

直到没有对象的消除。

(a) 什么是限制的值

使用显著性水平为0.05。

用于Grubbs’测试的方法m无穷大吗?

请注意,这可能是更好的措词。该数值的表达方法、tc。但严格来说这

不是一种限制为 tc 取决于 m。

”

。

此外,该值的 tc 将继续增加, m,尽管速度缓慢。 M =1020, tc =93的意义价值

为0.05。

(b) 描述在词语的含义上的结果。

分发的 g 是变成 t 分布为 m

的

增加。

8. 许多统计测试异常值,环境whicha几百的意见有很大的数据集。我们研究的局

限性,这种解决办法。

(a) 对一组000值,怎么可能是我们的异常值25KG复合纸袋的测试说价值是一

种离群值如果大于三个标准偏差的平均值? (假定正态分布)。

这个问题应该问有多少离异我们会因为对象这一问题的目的是表明,即使

是很小的概率的一种离群的产量很大数目的异常值的大型数据集。概率是

不受影响的对象的数目。

的概率是0.00135的单侧偏移为3的标准偏差或0.0027英寸的双面的偏差。

因此,该数量的异常对象将是1350或2700。

(b) 没有办法,国家有异常值是对象的异常lowprobability需要加以调整,当处理

大型数据集的吗? 如果是这样的话,如何?

有上千个异常值(根据指定的定义)的对象。我们可以选择接受这些对象作

为异常值或愿意增加阈值以使较少的离群值的结果。

9. 概率密度的点 x 的多变量正态分布的平均微米和协方差矩阵 Σ 是由方程

μ)

”

。

(10.1)

(2π)

|Σ|

1/2

使用的是样本平均值 x 和协方差矩阵为估计的平均微米和协方差矩阵 Σ”分别

显示日志(prob(x))是同等的马哈拉诺比斯之间距离的数据点 x 和样本平均

值 x 加恒定的,并不取决于 x。

”

。

如果我们用的是样本平均值和协方差的估计的 0.13 μ 和Σ分别然后

不断的和经常性的因素并不影响该命令在这一数量中,只有它们的严重程度。

因此,如果我们想要的距离的数量,我们可以只保留变量的一部分,这是马哈拉诺

比斯的距离。

10. 比较下面两个措施在何种程度上对象的belongsto群集:(1)距离,可以从对象的

中心,其最近的群集和(2)的silhouette系数一节中所述的8.5 2。

第一项措施是比较有限的,因为它无视这一事实,该对象也可关闭到另一群集。

Silhouette系数既考虑到距离的对象以其群集及其距离的其它群集。因此,它可

以提供更多的信息如何强烈的对象所属的群集分配的。

11. 考虑(相对距离)K意味着计划的异常值检测中所述第10.5和随附的图、图10.10。

(a) 这点在底部的紧凑型群集图图10.10有较高的异常点的得分比那些点在

顶部的紧凑的群集。为什么?

这意味着点拉有点向上从中心的紧凑型群集的点D。

(b) 假设我们选择组的数目,要多很多,例如,10。将建议的技术仍然是有效的,

找到最极致的离群值在顶部的图吗? 为什么可以或不可以吗?

第这一点就会成为群集本身。

可能会导致错误的结论。

如果绝对的距离是非常重要的。例如,考虑心率监测的患者。如果心率

高于或低于指定范围的值,然后将该有的物理含义。这是不正确的不识别

任何病人超出该范围的异常,即使可能有一组的患者较为相似,都有不正常

的心率。

12. 如果概率是正常的对象是被归类为一种不正常的现象是0.01不懂概率的异常

对象是被归类为不正常的是0.99,那么什么是虚假报警率和检测率99%的对象

都是正常的吗? (使用定义如下。)

数量的异常检测

检测率 =

总数量的异常数量的虚假的异常

虚假报警率。 =

数量的对象分为异常情况

检测率只需99%。

虚假报警率=0.99m× 0.01/(0.99m× 0.01访问速度

。

米

× 0.99=0.50=50%。

13. 当一项全面的培训将是可用的、受控的异常检测技术通常可以超越了不受监督

的异常时的技术绩效评估是使用的措施,例如检测和虚假报警率。然而,在某些

情况下,例如,在欺诈检测、新类型的异常现象始终是发展的。性能可的评价根

据检测和虚假报警率,因为它通常是可以确定的,经调查后,是否有对象(交易)是

正常的。讨论的相对优点的监督与非监督异常检测,在这样的条件下。

当新的异常现象进行检测,不受监督的异常检测计划必须被使用。但是,监控异

常检测的技术仍很重要用于检测已知类型的异常。因此,这两种监督与非监督

异常检测方法应该被使用。有很好的例子,这种情况是网络入侵检测。配置文

件或签字可以创造良好的已知类型的入侵,但无法检测到新的类型的入侵。

14. 考虑一组文档已从一种多largerset各种不同的文档,使所选的文档都是不同的。

如果我们考虑文档,没有高度相关(连接、类似)在一起是不正常的,那么所有的文

档,我们选择了可能会被归类为不正常的现象。它是可能的数据设置为仅包括

有异常的对象或是此种滥用的名词吗?

的内涵是不正常的现象是很罕见的,许多的定义的一种不正常的现象纳入这一

概念在某种程度上。但是,在有些情况下,一种不正常的现象通常不经常出现,

如出现网络故障,但有十分具体的定义。这使它能够区分一种不正常的现象,是

绝对意义上的和的情况出现在大部分对象都是不正常的。此外,在提供的数学

或算法定义的一种不正常的现象,它可能发生,这些定义产生的情况下,很多或所

有对象的数据集可以被归类为不正常的现象。另一种观点可能会说,如果它是

无法界定的有意义的正常情况,然后再所有的对象都是不正常的。 (“独特”一词

是通常用在这方面。)总之,这可以被视为是一种哲学或语义的问题。良好的论

点(虽然可能不是无争议的一部分)可以说,这是有可能的集合中的对象大多是

或所有的异常情况。

15. 考虑的点集,大多数点所在区域的低密度、布塔的几点都是在各区域的密度高。

如果我们定义一种异常现象的点在某一区域的低密度、然后最点会被归类为不

正常的现象。这是一种适当的使用密度为基础的定义异常或不应该的定义进行

修改以某种方式吗?

如果浓度有绝对的意义,例如分配的域名,然后它可能是完全合理的考虑大部分

的点是不正常的。 (请参阅答案以前的练习。)然而,在许多情况下,适当的做法

是使用一种异常检测技术的相对密度。

16. 考虑的一组点的均匀地分布在时间间隔[0、1]。是统计概念的离群值的不常用

的观察值有意义的数据?

不是真的。传统的统计概念的过度依赖的概念与对象相对较低的概率都是可

疑的。均匀分布,没有这种区分。

17. 分析人士适用的异常检测算法的数据集和findsa的异常情况。奇怪的是,分析

师会对异常检测算法的不正常的现象。

(a) 讨论行为的异常检测方法本章所述。 (如果可能,请尝试此为真正的数据

集和算法。)

(b) 你认为的行为异常检测algorithmshould被应用到一组异常的对象吗?

在某些情况下,例如在统计学上的异常检测技术,它将是无效的应用该技术的第

二次,因为假设不再保留。这也可能是真的其他的基于模型的方法。行为的近

距离和密度为基础的方法将取决于具体的技术。有趣的是,该方法采用的是绝

对阈值的距离或密度很可能会进行分类,设置异常情况的异常情况,至少如果原

始参数。相对的办法很可能会把大部分的反常现象是正常的,有些是不正常的

现象。

某个对象是否为异常取决于整个组的对象,因此,它可能是不合理的期望,一种异

常检测技术将标识一组异常等在没有原始数据集。

参考书目

[1] W。 W·科恩。快速有效的规则简介。在 Proc

。第

届国际。

Conf

。在机器学习

”

页面115-123,市Tahoe、CA、1995年7月。

[2] 美国成本和美国Salzberg。一种加权的最接近的邻居的算法学习与象征性的功能。

机

器学习

中10:57 78、1993年。

[3] J。富指rnkranz和G Widmer。增量减少错误的修剪。在 Proc

。

11 Intl

。

Conf

。在

机器学习

中的页面70-77新不伦瑞克新泽西州1994年7月。

[4] J。 Hartigan。

群集算法

。 Wiley,纽约,1975年。

[5] R。 A贾维斯和E A·帕特里克。群集使用的相似性测量基于共同的最接近的邻居。 IEEE

计算机

、C 22(11):1025-1034、1973。

USB迷 | 专注于互联网分享

数据挖掘导论习题答案(中文版)

与本文相关的文章

评论列表 (0)