A.如何修改基本决策树算法，以便考虑每个广义数据元组（即每个行）的count？ 基本的决策树算法应该作如下修改，以便考虑每个广义数据元组（即每个行）的count，每个元组的count必须综合考虑属性的选择测量计算：
（1）首先分析类标号属性status有两个不同的值senior、junior，因此有两个不同的类m=2，设类C1对应于senior，而类C2 对应于junior。类senior有30+5+3+10+4=52个元组。类junior有40+40+20+3+4+6=113个元组。共有165个元组。
m
（2）使用Info（D）=－∑i=1Pilog2Pi，计算D对元组分类所需的期望信息。 Info(D)??5252113113log2?log2?0.899 165165165165（3）计算属性department，age和salary的期望信息需求：
?department Department Infodep(D)?Sales Systems marketing secretary 110 31 14 10 senior junior senior junior senior junior senior junior 30 80 5 23 10 4 4 6 1103030808031882323(?log2?log2)?(?log2?log2)16511011011011016531313131
14104104466?(?log2)?(?log2?log2)?0.85165141416510101010Gain(dep) = Info(D)?Infodep(D)?0.899?0.850?0.049
?age age 31~35 26~30 21~25 41~45 36~40 46~50 79 49 20 3 10 4 senior junior senior junior senior junior senior junior senior junior senior junior 35 44 0 49 0 20 3 0 10 0 4 0 第25页，共29页
793535444449004949(?log2?log2)?(?log2?log2)1657979797916549494949 2000202033300?(?log2?log2)?(?log2?log2)1652020202016533331010100044400?(?log2?log2)?(?log2?log2)?0.474165101010101654444Infodep(D)?Gain（age）?Info(D)-Infodep(D)?0.899-0.474?0.425
?salary Salary Infodep(D)?46k~50k 26k~30k 31k~35k 66k~70k 41k~45k 36k~40k 63 46 40 8 4 4 senior junior senior junior senior junior senior junior senior junior senior junior 40 23 0 46 0 40 8 0 0 4 4 0 634040232346004646(?log2?log2)?(?log2?log2)1656363636316546464646
4000404044400?(?log2?log2)?(?log2?log2)?0.362165404040401654444Gain（age）?Info(D)-Infodep(D)?0.899-0.362?0.537
考虑count来决定元组中最普遍的分类。
B.使用修改过的算法构造给定数据的决策树。
由于Salary在属性中具有最高信息增益，因此选作分裂属性。节点N用salary标记，并对于每个属性值生长出一个分支，然后元组据此划分，如图所示： Salary 26k~30k 31k~35k 36k~40k 46k~50k 66k~70k 41k~45k junior junior senior junior senior 第26页，共29页
department age salary status
sales 31~35 46k~50k senior
systems 21~25 46k~50k junior
systems 26~30 46k~50k junior
marketing 36~40 46k~50k senior
The Resulting Tree Is: (salary=26k…30k： junior = 31k…35k： junior = 36k…40k： senior = 41k…45k： junior = 46k…50k：（department=secretary：
junior =sales：
senior =systems：
junior = marketing：
senior ） = 66k70k：
senior）
C.给定一个数据元组，它的属性department，age和salary的值分别为“systems”“26~~30”，和“46~~50k”。该元组status的朴素贝叶斯分类是什么？ 根据题，我们希望分类的元组为X=（department=systems,age=26-30,salary=46k-50k）,我们需要大化P X|Ci P Ci，i=1,2。每个类的先验概率P Ci可以根据训练元组计算： P(status=senior)=52/165=0.315 P(status=junior)=113/165=0.685
计算P X|Ci P Ci，i=1,2，要先求条件概率： P(department=systems|status=senior)=8/52=0.154 P(department=systems|status=junior)=23/113=0.204 P(age=26-30|status=senior)=1/(52+6)=0.017 P(status=26-30|status=junior)=49/113=0.434
P(salary=46k-50k|status=senior)=40/52=0.769 P(salary=46k-50k|status=junior)=23/113=0.204 使用上面概率的到：
P(X|status=junior)=P(department=systems|status=senior)*P(age=26-30|status=junior)*P(salary=46k-50k|status
第27页，共29页
=junior)=0.204*0.017*0.204=0.018.
为了发现最大化P X|Ci P Ci 的类，计算：
P(X|status=senior)P(status=senior)=0.002*0.315=0.00063 P(X|status=junior)P(status=junior)=0.018*0.685=0.01233
因此，对于元组X,朴素贝叶斯分类器预测元组X的类为status=junior。
三．假设你打算在一个给定的区域分配一些自动取款机（ATM），使得满足大量约束条件。住宅或工作场所可以被聚类以便每个簇分配一个ATM。然而，该聚类可能被两个因素所约束：（1）障碍物对象，既有一些可能影响ATM可达性的桥梁，河流，公路。（2）用户指定的其他约束，如每个ATM应该能为10000户家庭服务。在这两个约束限制下，怎样修改聚类算法（如k-均值）来实现高质量的聚类？ 答：约束的存在会使得原来被定义在同一个簇的对象之间的距离发生变化。这时可以考虑将 这些约束因素融入到距离的计算公式中，如在存在桥梁、河流和公路的区域中，可通过 对象之间的连通性以及路径来计算距离；而地域ATM 数目的限制问题则可在聚类的初 始化阶段解决，如在K-MEANS 的初始化时，可根据区域的个数来确定簇个数K 的值， 然后所选择的初始化种子尽可能分布在距离各个ATM 附近的地方。 对K-中心点空间聚类算法进行修改后如下：
① 首先用数学模型提取聚类对象和限制条件的空间信息。
② 若涉及的聚类对象数据量较大，可先对其进行微聚类。采用微小簇的中心点所包含的点的数目来表示这些微小簇，并定义其中心点坐标为簇中所有点坐标的平均值，可用点集P=[p1,p2,...,pn]来表示。 ③ 建立距离查找表。建立查找表为便于聚类时直接调用。必须考虑到聚类对象所存在的障碍实体和联
第28页，共29页
通点给中心点与非中心点的距离所带来的影响 若两个微小簇之间没有障碍物，其间的距离为：
d(pj,pk)?[(xpi?xpk)?(ypj?ypk)]2122
若两个微小簇受障碍物的影响，完全不可视，其间的距离为： d(pj,pk)?md(pj,pk) m表示阻碍因子权值。若两个微小簇受障碍物的影响，但经联通点连接后可达，其间的距离
d(pj,pk)?d(pj,Li)??d(Li,Li?1)?d(Ln,Pk)i=1n?1式中，Li表示第i个联通点。
④ 设定中心点的初始集合并聚类。从所有的对象中随机选择k个对象作为当前的聚类中心，然后根据与中心点的距离，将每一个非中心点对象分配给离它最近的中心点。
⑤ 置换中心点对象，重新聚类。用距离某个簇的平均点坐标最近的非中心点对象，代替改簇的中心点，然后重新聚类。
第29页，共29页