四川理工-数据挖掘详解.docxVIP

I Inoooo 聚类算法分为 1.层次聚类： 1）凝聚算法 a.单连接AGENS（最近邻聚类算法） B.全连接（最远邻聚类算法） c.平均连接 分裂算法（DIANA） a.单元分裂 b.多元分裂 2.划分聚类：K-means(K-均值或K-平均) K-中心点（pam算法） 3.基于密度：DBSCAN 精确度 4.基于网格：STING 、 WaveCluster K-均值K-中心优点简单不受极值影响缺点受极值影响无法处理大数据复杂度O(nkt)O(k(n-k)^2)综合 速度 比较 K-均值算法 （1）K-均值算法描述 K-均值算法性能分析 主要优点：是解决聚类问题的一种经典算法，简单快速；对处理大数据集，该算法是相对可伸缩和高效率的；当结果簇是密集的，而簇与簇之间区别明显时，它效果较好。 主要缺点：在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用；必须事先给出K（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 K-均值算法实例 平均误差准则函数 欧式距离 PAM算法 （1）PAM算法描述 输入：簇的数目k和包含n个对象的数据库 输出：k个簇，使得所有对象与其距离最近中心点的相异度总和最小 任意选择k个对象作为初始的簇中心点 （2） Repeat （3） 指派每个剩余对象给离他最近的中心点所表示的簇 （4） Repeat （5） 选择一个未被选择的中心点Oi （6） Repeat （7） 选择一个未被选择过的非中心点对象Oh （8） 计算用Oh代替Oi的总代价并记录在S中 （9） Until 所有非中心点都被选择过 （10） Until 所有的中心点都被选择过 （11） If 在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合； （12） Until 没有再发生簇的重新分配，即所有的S都大于0.（2）PAM算法性能 (1) 消除了k-平均算法对于孤立点的敏感性。 (2) K-中心点方法比k-平均算法的代价要高 (3) 必须指定k (4) PAM对小的数据集非常有效，对大数据集效率不高。特别是n和k都很大的时候。 （3）用PAM算法对例5.1的样本数据库进行聚类（k=3）。 根据给定的样本数据库，可以算出各点之间的距离关系，如表1所示。 表1 样本点间距 样本点1234567810111.43.64.54.252101.412.83.63.64.2311.4013.24.13.64.541.41102.33.22.83.653.62.83.22.30111.464.53.64.13.2101.4174.23.63.62.811.401854.24.53.61.4110 算法执行步骤如下： 第一步 建立阶段：从8个对象中随机抽取3个点为中心点{1，4，7}，则样本被划分为{1，2，3}，{4}和{5，6，7，8}。 第二步 交换阶段：假定中心点1、4、7分别被非中心点2、3、5、6、8替换，分别计算下列代价TC12、TC13 、TC15 、TC16 、TC18，TC42、TC43 、TC45 、TC46 、TC48和TC72、TC73 、TC75 、TC76 、TC18。 先求TC12。 (1) 1被2替换以后，1不再是中心点，因为1离2最近，所以1被分配到2中心点代表的簇，C112=d(1,2)-d(1,1)=1 (2) 2 原先属于1中心点所在的簇，现在2是一个中心点，C212=d(2,2)-d(2,1)=-1 (3) 3原先属于1中心点所在的簇，现在３离４最近，所以３被分配到４中心点代表的簇，C312=d(3,4)-d(3,1)=1-1=0 (4) 4原先属于４中心点代表的簇，现在不发生变化，C412=0 (5) 5原先属于7中心点代表的簇，现在不发生变化，C512=0 (6) 6原先属于7中心点代表的簇，现在不发生变化，C612=0 (7) 7原先属于7中心点代表的簇，现在不发生变化，C712=0 (8) 8原先属于7中心点代表的簇，现在不发生变化，C812=0 因此TC12= C112+ C212+ C312+ C412+ C512+ C612+ C712+ C812=0 同理，求得TC133=1+0+(-1)+0+0+0+0+0=0 TC15=1.4+0+0+0+(-1)+(-0.4)+0+0=0 TC16=1.4+0