四川理工-数据挖掘.docx

聚类算法分为1.层次聚类：1）凝聚算法a.单连接AGENS（最近邻聚类算法）B.全连接（最远邻聚类算法）c.平均连接分裂算法（DIANA）a.单元分裂b.多元分裂2.划分聚类：K-means(K-均值或K-平均)K-中心点（pam算法）3.基于密度：DBSCAN精确度4.基于网格：STING 、 WaveClusterK-均值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=0TC15=1.4+0+0+0+(-1)+(-0.4)+0+0=0TC16=1.4+0+0+0+0+(-1.4)+0+0=0TC18=1.4+0+0+0+0+(-0.4)+0+(-1)=0TC42=0+(-1)+0+1+0+0+0+0=0TC43=0+0+(-1)+0+0+0+0+0=0TC45=0+0+0+(1.4)+(-1)+(-0.4)+0+0=0TC46=0+0+0+1.4+0+(-1.4)+0+0=0TC48=0+0+0+1.4+0+(-0.4)+