《2011计科三班吕良》由会员分享，可在线阅读，更多相关《2011计科三班吕良（2页珍藏版）》请在金锄头文库上搜索。
1、第四次作业1. 假设数据挖掘的任务是将如下的八个点（用（x，y）代表位置）聚类为三个簇。A1（2,10），A2（2,5），A3（8,4）， B1（5,8），B2（7,5），B3（6,4），C1（1,2），C2（4，9）距离函数是欧几里得距离。假设初始我们选择，和分别为每个簇的中心，用k均值算法给出：1) 在第一轮执行后的三个簇中心点为多少？ 2) 最后的三个簇是什么? 答：（a）在第一次循环执行后的三个簇中心分别为（6，6），（1.5,3.5），（2，10）重新指派各个对象到离其最近的质心，与上面方面相同，形成的三个簇为A3,B1,B2,B3，C1，A2，A1,C2三个簇的质心分别为（6.5，
2、5.25），（1.5，3.5），（3，9.5）;重新指派各个对象到离其最近的质心,形成的三个簇为:A3,B2,B3C1,A2A1,B1,C2三个簇的质心分别为：（7，4.3），（1.5，3.5），（3.67，9）；重新指派各个对象到离其最近的质心,形成的三个簇为:A3,B2,B3C1,A2A1,B1,C2三个簇的质心分别为：（7，4.3），（1.5，3.5），（3.67，9）；至此质心不发生变化；（b）最后三个簇即为A3,B2,B3C1,A2A1,B1,C2; 2. 证明：在DBSCAN中，对于固定的MinPits值和两个邻域阈值e1e2，关于e1和MinPits的簇C一定是关于e2和MinP
3、its的簇C的子集。证明：假设一个对象集合D，关于MinPits值和邻域阈值e1任一满足核心对象条件的数据对象p，数据库D中所有从p密度可达的数据对象o所组成的集合构成了一个完整的聚类C，且p属于C；其中对象p在e1邻域内的样本点数大于等于MinPts；其他对象链，对于，是从关于e1和 MinPts直接密度可达， 如果簇C中存在核心对象P，且P不属于簇C，则点对象P的e2邻域的样本点数小于MinPts，若对象P的e2邻域的样本点数小于MinPts，由于e1e2,那么对象P的e1邻域的样本点数小于MinPts，这与P是簇C的核心对象矛盾，所以簇C中的核心对象一定是簇C中核心对象的子集；如果簇C中
4、存在非对象N，且N不属于簇C，则对象N不是从对象P关于e2和 MinPts密度可达的，由于e1e2,那么对象N也不是从对象P关于e1和 MinPts密度可达的，这与N属于簇C 矛盾，所以簇C中的非核心对象一定是簇C中非核心对象的子集；因此，关于e1和MinPits的簇C一定是关于e2和MinPits的簇C的子集3. 按如下标准对下列每种聚类方法进行描述：可以确定簇的形状；必须指定的输入参数；局限性。a. k-均值b. k-中心点c. CLARA d. BIRCH e. CHAMELEON f. DBSCAN答：a. k-均值（1）不适合发现非凸面形状的簇，对噪声和孤立点数据是敏感的（2）簇的数
5、目k和包含n个对象的数据库（3）不适合分类属性的数据，必须给定k，对初始值k比较敏感b. k-中心点（1）消除了k-平均算法对于孤立点的敏感性（2）簇的数目k和包含n个对象的数据库（3）对小的数据集非常有效，对大数据集效率不高c. CLARA （1）凸形或球形（2）簇的数目k和包含n个对象的数据库（3）准确度取决于抽样算法d. BIRCH （1）对非球状的簇聚类效果不好。这取决于簇直径和簇间距离的计算方法（2）包含n个对象的数据库，聚类个数和簇直径限制k（3）需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行e. CHAMELEON （1）可以发现任意形状的簇（2）包含n个对象的数据库，用户指定的阀值TRI，TRC（3）最坏情况下对高维数据的处理代价可能需要O（n*n）的时间f. DBSCAN（1）可以发现任意形状的簇（2）包含n个对象的数据库，半径 ，最少数目MinPts（3）对用户定义的参数敏感
