第六章 数据挖掘基本算法-3

1数据仓库与数据挖掘第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统2第六章数据挖掘基本算法6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法36.4数据挖掘的聚类算法聚类分析是对群体及成员进行分类的递归过程。一个簇是一组数据对象的集合，在同一簇中的对象彼此类似，而不同簇中的对象彼此相异。将一组物理或抽象对象分组成由类似对象组成的多个簇的过程被称为聚类。聚类就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。距离是经常采用的度量方式。46.4数据挖掘的聚类算法聚类分析的应用：市场或客户分割、模式识别、生物学研究、空间数据分析、Web文档分类等。聚类分析可以用作独立的数据挖掘式工具，来获得对数据分布的了解，也可以作为其他数据挖掘算法的预处理步骤。聚类的质量是基于对象相异度来评估的。相异度是描述对象的属性值来计算的。相异度可以对多种类型的数据来计算，包括区间标度变量、二元变量、标称变量、序数型变量和比例度型变量类型的组合。56.4数据挖掘的聚类算法聚类分析的算法可以分为：划分方法：首先得到初始的K个划分的集合。如K-平均、K-中心点、CLARANS以及对它们的改进。层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程可以分为凝聚（自底向上）或分裂（自顶向下）。基于密度的方法：根据密度的概念来聚类对象，如DBSCAN、DENCLUE、OPTICS。基于网格的方法：首先将对象空间量化为有限数目的单元，形成网格结构，然后在网格结构上进行聚类，如STING、CLIQUE、WaveCluster。基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配，如COBWEB、CLASSIT和AutoClass。66.4数据挖掘的聚类算法类别算法分裂/划分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法）层次法BIRCH算法（平衡迭代规约和聚类）、CURE算法（代表聚类）、CHAMELEON算法（动态模型）基于密度的方法DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCURE算法（密度分布函数）基于网格的方法STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换）基于模型的方法统计学方法、神经网络方法表6.9主要的聚类算法的分类76.4数据挖掘的聚类算法6.4.1聚类分析的概念6.4.2聚类分析中两个对象之间的相异度计算方法6.4.3划分方法6.4.4层次方法*6.4.5基于密度的方法*6.4.6基于网格的方法*6.4.7基于模型的聚类方法*6.4.8模糊聚类算法*86.4.1聚类分析的概念聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大。聚类是一个无监督学习的过程，它与分类的根本区别在于，分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征。因此在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。聚类是一种对具有共同趋势和模式的数据元组进行分组的方法，试图找出数据集中的共性和差异并将具有共性的元组聚合在相应的类或段中。96.4.1聚类分析的概念数据挖掘对聚类的典型要求如下：1）可伸缩性：算法能够处理海量的数据库对象。2）处理不同类型属性的能力3）发现具有任意形状的聚类的能力4）输入参数对领域知识的弱依赖性5）处理噪声数据或离群数据的能力6）结果对于输入记录顺序的无关性7）处理高维度数据的能力8）结果的可解释性和可用性9）基于约束的聚类分析能力106.4.2聚类分析中两个对象之间的相异度计算方法基于内存的聚类算法多选择如下两种有代表性的数据结构：（1）数据矩阵（datamatrix）数据矩阵用m个变量（也称属性）来表现n个对象，这种数据结构是关系表的形式，或nm维（n个对象m个属性）的矩阵。nmnnmmxxxxxxxxx212222111211(6-12)116.4.2聚类分析中两个对象之间的相异度计算方法（2）相异度矩阵（dissimilatorymatrix）存储n个对象两两之间的近似性，通常用一个nn维的矩阵表示。02,1,02,31,301,20ndndddd其中d(i,j)是对象i和对象j之间的测量差或相异度，通常它是一个非负的数值。对象i和j之间越相似，其值越接近0；两个对象越不同，其值越大。由于d(i,j)=d(j,i)；且d(i,i)=0，可以得到（6-13）。(6-13)126.4.2聚类分析中两个对象之间的相异度计算方法数据矩阵的行和列代表不同的实体，也被称为二模矩阵。相异度矩阵的行和列代表相同的实体，也被称为单模矩阵。许多聚类算法都是以相异度矩阵为数据源运行的，如果数据是用数据矩阵的形式存储的，在使用聚类算法之前要将其转化为相异度矩阵。136.4.2聚类分析中两个对象之间的相异度计算方法计算相异度的常用方法有：区间标度变量计算方法，二元变量计算方法，标称、序数和比例标度计算方法，或这些变量类型的组合来描述对象的相异度计算方法。146.4.2聚类分析中两个对象之间的相异度计算方法（1）区间标度变量计算方法区间标度变量是一个粗略线性标度的连续度量。度量单位的选用将直接影响聚类分析的结果。一般而言，所用的度量单位越小，变量可能的值域就越大，这样对聚类的结果影响就越大。因此为了避免对度量单位选择的依赖，应该对数据进行标准化。标准化度量值试图给所有的变量相等的权重，当没有关于数据的先验知识时，这样做是十分有效的。156.4.2聚类分析中两个对象之间的相异度计算方法为了实现度量值的标准化，一种方法是将原来的度量值转化为无单位的值。给定一个变量f的变量值，可以进行如下的变换。其中，x1f,x2f,…,xnf是f的n个度量值，mf是f的平均值，即fnffffffmxmxmxns211nffffxxxnm2111）计算均值绝对偏差sf166.4.2聚类分析中两个对象之间的相异度计算方法均值绝对偏差sf比标准的偏差f对于孤立点具有更好的鲁棒性。在计算均值绝对值偏差时，度量值与平均值的偏差没有被平方，因此孤立点的影响在一点程度上减小了。采用均值绝对偏差的优点在于孤立点的z-score值不会太小，因此孤立点仍可别发现。ffififsmxz2）计算标准化的度量值176.4.2聚类分析中两个对象之间的相异度计算方法标准化后，或者在某些应用中不需要标准化，区间标度变量描述的对象间的相异度（或相似度）通常基于对象间的距离来计算。常用的距离度量方法如下：1）欧几里德距离2/112,nkjkikxxjid其中，jnjjiniixxxjxxxi,,,,,,2121和是两个n维的数据对象。186.4.2聚类分析中两个对象之间的相异度计算方法2）曼哈顿距离nkjkikxxjid1,3）明考斯基距离是欧几里德距离和曼哈顿距离的推广。pnkpjkikxxjid/11,其中，p是一个正整数。p=1时，它表示曼哈顿距离；p=2时，它表示欧几里德距离。196.4.2聚类分析中两个对象之间的相异度计算方法如果对每个变量根据其重要性赋予一个权重，加权的欧几里德距离可以计算如下：2/112,nkjkikkxxjid同理，加权也可以用于曼哈顿距离和明考斯基距离。206.4.2聚类分析中两个对象之间的相异度计算方法例6.7x1=(2,9)和x2=(4,6)表示两个对象，计算x1和x2的欧几里德距离和曼哈顿距离。x1和x2的欧几里德距离x1和x2的曼哈顿距离61.36942,2221xxd56942,21xxd216.4.2聚类分析中两个对象之间的相异度计算方法（2）二元变量计算方法一个二元变量只有两个状态：0或1，其中0表示该变量为空，1表示该变量存在。如果所有的二元变量具有相同的权重，可以得到一个两行两列的可能性如表6.10所示。226.4.2聚类分析中两个对象之间的相异度计算方法表6.10中，q表示对象i和对象j的值都为1的变量的数目；r表示在对象i中值为1，但在该对象j中值为0的变量的数目；s表示在对象i中值为0，但在该对象j中值为1的变量的数目；t表示对象i和对象j的值都为0的变量的数目。变量的总数是p，p=q+r+s+t。对象j10求和对象i1qrq+r0sts+t求和q+sr+tp=q+r+s+t表6.10二元变量的相依表236.4.2聚类分析中两个对象之间的相异度计算方法评价两个对象i和j之间的相异度标准如下。（1）简单匹配系数（2）Jaccard系数（3）Rao系数tsrqsrjid,srqsrjid,srqppjid,246.4.2聚类分析中两个对象之间的相异度计算方法例6.8二元变量之间的相异度使用实例假设一个病人记录表（表6.11）包含属性姓名、性别、发烧、咳嗽、test-1、test-2、test-3和test-4，其中姓名是对象标识，属性都是二元变量。值Y和P被置为1，值N被置为0。求病人间患病的相似情况。表6.11二元属性的关系变量姓名性别发烧咳嗽test-1test-2test-3test-4ZhangMYNPNNNLiFYNPNPNWangMYNNNNP……………………256.4.2聚类分析中两个对象之间的相异度计算方法根据Jaccard系数公式，三个病人Zhang，Li和Wang两两之间的相异度如下：d(Zhang,Li)=(0+1)/(2+0+1)=0.33d(Zhang,Wang)=(1+1)/(1+1+1)=0.67d(Li,Wang)=(1+2)/(1+1+2)=0.75因此，Wang和Li患有相似的疾病可能性较低，因为他们有着最高的相异度，而Zhang和Li最可能有类似的疾病。266.4.2聚类分析中两个对象之间的相异度计算方法（3）标称型、序数型和比例标度型变量计算方法1）标称变量标称变量是二元变量的推广，它可以具有多于两个状态的值。假设一个标称变量的状态数目是M。这些状态可以用字母、符号，或者一组整数来表示（注意：这些整数只是用于数据处理，并不代表任何特定的顺序）。两个对象i和j之间的相异度可以用简单匹配方法来计算：pmpjid,这里m是匹配的数目，即对i和j取值相同的变量的数目；而p是全部变量的数目。可以通过赋权重来增加m的影响，或者赋给有较多状态的变量的匹配更大的权重。276.4.2聚类分析中两个对象之间的相异度计算方法2）序数型变量一个离散的序数型变量类似于标称变量，不同在于序数型变量的M个状态是以有意义的序列排序的。序数型变量对记录那些难以客观度量的主观评价是非常有用的。一个连续的序数型变量看起来像一个未知刻度的的连续数据的集合，即值的相对顺序是必要的，而其实际的大小则不重要。将区间标度变量的值域划分为有限个区间，从而将其值离散化，可以得到序数型变量。一个序数型变量的值可以映射为排序。例如，一个变量f有Mf个状态，这些有序的状态定义了一个序列1,…,Mf。286.4.2聚类分析中两个对象之间的相异度计算方法处理序数型变量：在计算对象的相异度时，序数型变量的处理与区间标度变量的处理方法类似。假设f是用于描述n个对象的一组序数型变量之一，关于f的相异度计算步骤如下：Step1第i个对象的f值为xif，