10.2
（a）第一轮执行后的三个簇分别是：（1）{A1}（2）{B1，A3，B2，B3，C2}（3）{C1，A2}
三个簇的中心分别是（1）（2,10）（2）（6,6）（3）（1.5,3.5）。
（b）最后的三个簇是（1）{A1,C2,B1}（2）{A3,B2,B3}（3）{C1,A2}
10.3
（0,2）（2,2）（4,2）
（0,1）（2,1）（4,1）
（0,0）（2,0）（4,0）
列和列之间距离大，行与行之间距离小，聚成三类的最优结果应该是每一列为一类，此时，类内方差最小。
但如果初始点选成中间的三个点，聚类结果就成了每一行为一类，显然是局部最优，不是全局最优。
10.6
（a）当存在噪声和离群点时，k -中心点方法比k -均值具有更强的鲁棒性，这是因为中心点不像均值那样容易受离群点或其他极端值影响。然而，当n（待聚类的对象数）和k的值较大时，k -中心点算法的计算开销远高于k -均值方法。
（b）k -均值和k -中心点都是划分方法。这种划分方法的优点是，可以撤销之前的聚类步骤（通过迭代迁移），而在层次聚类方法中，一旦执行了一次合并或分裂，就不能做出调整，下一步的处理将在新产生的簇上进行。因此，如果合并或分裂选择不当，层次聚类方法可能会导致低质量的簇。划分方法能够很好地找到球形簇，一般地，对于中小型数据库，它的聚类质量都不错。但是划分方法的一个弱点是需要在聚类之前指定聚类的数量。分层聚类方法可以自动地在聚类过程中决定聚类的数量，但是这种方法不具有很好地可伸缩性，因为每次合并或分裂的决定都需要考察和评估许多对象和簇。另外，层次方法可以与其他聚类方法集成（比如BIRCH，ROCK,Chameleon等），改进聚类结果。
10.7
假设用ε指定每个对象的领域半径，用MinPts指定稠密区域的密度（可以简单地用邻域内的对象数度量）阈值。则密度相连的概念：给定一个对象集D，如果存在对象q，p1,p2∈D，并且对象p1和P2都是从q关于ε和MinPts密度可达的，则对象p1,p2是关于ε和MinPts密度相连的。因为密度相连的两个对象并不要求为核心对象，所以当对象p1和p2关于对象q密度相连时，p2是从q关于ε和MinPts密度可达的，p1也是从q关于ε和MinPts密度可达的，所以p2和p1是关于ε和MinPts密度相连的。所以，密度相连满足对称性；又因为可以认为某一点和它自身是密度相连的，所以密度相连满足自反性；容易证明，对于对象o1、o2和o3，如果o1和o2是密度相连的，并且o2和o3是密度相连的，则o1和o3也是密度相连的，所以密度相连满足传递关系。因为密度相连满足对称性、自反性和传递性，所以密度相连是等价关系。
10.8
假设一个对象集合D，取稠密区域的阈值为MinPits值和邻域半径为阈值ε1时对任一满足核心对象条件的数据对象p，数据库D中所有从p密度可达的数据对象o所组成的集合构成了一个完整的聚类C，且p属于C；其中对象p在ε1邻域内的样本点数大于等于MinPts；
如果簇C中存在核心对象P，且P不属于簇C'，则点对象P的ε2邻域的样本点数小于MinPts，若对象P的ε2邻域的样本点数小于MinPts，由于ε1<ε2，那么对象P的ε1邻域的样本点数小于MinPts，这与P是簇C的核心对象矛盾，所以簇C中的核心对象一定是簇C’中核心对象的子集；
如果簇C中存在非对象N，且N不属于簇C'，则对象N不是从对象P关于ε2和MinPts密度可达的，由于ε1<ε2,那么对象N也不是从对象P关于ε1和MinPts密度可达的，这与N属于簇C矛盾，所以簇C中的非核心对象一定是簇C'中非核心对象的子集；
因此，当ε1<ε2时，关于ε1和MinPits的簇C一定是关于ε2和MinPits的簇C'的子集。
10.18
约束算法可以通过以下几个方面的修改得到满足题目要求的基于约束的聚类：
（1）微簇。为降低两个对象或点间距离计算的开销，可以使用一些预处理或者优化技术。一种方法是把邻近的点首先聚集到一些微簇中。此过程可以先用三角划分的方法把区域R分为若干三角形（对于此题而言，可以把障碍物视为划分边界，得到一个个小三角区域），然后使用类似于DBSCAN的方法把同一个三角形中相近的点划分到微簇中。通过处理这些微簇而不是个体点，降低总的计算量。
（2）距离度量。如果两个对象之间存在障碍物，则应该调整它们之间的距离。在这种情况下，可达距离比直线距离更合理。因为在实际问题中障碍物往往很难跨越甚至根本无法跨越，此时使用直线距离相当于忽略了障碍物，不符合实际。在本题中，如果两点之间不存在障碍物，那么两点之间的可达距离等于它们之间的直线距离；如果两点之间存在障碍物，那么这两点的可达距离为避开障碍物从一点至另一点的最短距离。
（3）基于中心点方法。在障碍物存在的情况下，如果选择K均值方法，簇中心可能是不可达的。例如，簇均值有可能会落在河流或者公路上。而k中心点方法选择簇中的对象作为簇中心，保证了簇中心的可达性。在本题中，对于给定的一个区域R，可以先初始化为k个聚类（k介于可以分配给此区域ATM的最大数量和最小数量之间）；通过考察每个聚类中障碍物的数量，家庭的数量等信息，对各个聚类进行合并和分裂操作，直至聚类稳定；如果此时聚类满足指定的约束（如每个ATM能为10000户家庭服务），并且聚类数小于或等于计划分配的ATM数量，则在各个聚类的中心点安装ATM。如果不满足约束，或者聚类数过大，则需要选择次优聚类方案进行聚类，使得聚类满足指定的约束（聚类数不超过计划分配的ATM数量，每个ATM应该能为10000户家庭服务）。
10.19
我们可以根据约束作用于何处对约束分类，可以分为：实例上的约束、簇上的约束和相似性度量上的约束。
实例上的约束说明一对或一组实例如何在聚类分析中被分组。如：必须联系约束，指定两个对象必须聚类到同一个簇中；不能联系约束，指定两个对象必须聚类到不同的簇中。
簇上的约束使用簇的属性，说明簇的要求。例如，指定每个簇中的客户的最大数目、指定每个簇中客户的平均收入。
相似性度量上的约束，例如规定采用欧式距离度量两个对象之间的相似性。
也可以考虑约束必须遵守的程度，将约束划分为硬性的和软性的。一个约束是硬性的，如果违反该约束的聚类是不可接受的。一个约束是软性的，如果违反该约束的聚类是不可取的，但是在找不到更好的解时还可以接受。
在聚类的指派过程中，硬性约束必须严格遵守。如指定了数据集上的必须联系约束，可以先计算一个必须联系约束的传递闭包，该闭包给出一个或多个对象子集，其中一个子集中的所有对象必须要分配到同一个簇中。
而处理软性约束时，可以对违反软性约束的聚类施加一个罚，将寻找最优聚类问题转化为一个优化问题。
补充：证明密度相连的传递性（欢迎交流）
首先：我们先证明一个小问题，对于a,b,c∈D，a->c,b->c,则ab均为核心对象且c均在邻域中，
网友评论