非监督学习方法之聚类分析(ppt 55页).ppt

1、第一章无监督学习方法：聚类分析、基本概念相似性度量和基于集群的探索的集群搜寻演算法系统集群分解集群动态集群，1.1基本概念，分类和集群的差异分类：使用已知类别中的示例培训集组织分类器(教练学习)集群(集群):将分类器(集群)组织到不知道字典示例的类别中。相似性和距离簇相似性：模式之间有相似性。这既表现在实物的突出特征上，又表现在抽象后特征空间内的特征矢量分布状态上。聚类分析定义：对于未显示类别的模式样本集，根据样本之间的相似性分类，不相似的类别分类为其他类别，这些分类也称为聚类分析分类或无监督分类。分类依据：样例的要素矢量对应于要素空间中的一个点，整个模式样例集合的要素矢量可以看作要素空间中的

2、一个点，点之间的距离函数可以用作阵列相似性的测量，并且可以将其用作阵列的分类基础。聚类分析是徐璐根据不同对象之间的差异，根据距离函数的规律对模式进行分类的。距离函数的定义特征向量的特性，聚类分析的有效性：聚类分析方法牙齿是否有效与模式特征向量的分布形式有很大关系。向量点的分布是一组，同一采样组密集(距离近)，徐璐其他采样组较远，则很容易聚集。样本组的矢量分布聚集在一起，徐璐其他组的样本混合，很难分类。(威廉莎士比亚，模板，矢量，矢量，矢量，矢量，矢量，矢量，矢量，矢量，矢量，矢量)聚类分析特定对象的关键是选择合适的要素。特征选择好，矢量分布容易区分，选择不好，矢量分布难分离。要素空间维要素信息

3、冗馀：在对象分析和要素提取中，经常提取重复要素以增加对象识别信息的数量。高维特征空间分析的复杂性：特征空间维度越高，聚类分析复杂性越高。高维特征空间降维方法：相关分析：特性矢量的相关矩阵r，分析相关性主成分分析：基于正交变换的独立成分分析：独立性基础，特征表示数值表示：对于实际问题，为了便于电脑分析和计算，特征必须量化。量化方法取决于分析对象。连续量的量化：仅需要量化值(例如长度、重量等)的情况下，作为连续量测量的特性。等级量的量化：测量分析对象等级的数量，并以学生成绩的优秀、良好、中、差为1、2、3、4等的量化形式进行量化。定性量的量化：定性指标，没有数量关系，没有顺序要求。例如，性别特征：

4、男性和女性可以用0和1来表示。两种茄子类型的图案分类的例子，以黑白围棋选择颜色为特征分类，白色分为“1”，黑色分为“0”，容易分类。以大小为特征分类，白瓷和黑子的特征相同，不能分类。1.2相似性度量和聚类准则，1，相似性度量欧氏距离：特性空间中两个模式样本的Euclid距离，模式X和Z之间的距离越小，相似性越大。x和Z的尺寸必须一致地消除尺寸不匹配对群集的影响。要素数据的规格化(标准化，也称为规格化)，马尔可夫距离：表相模式矢量X和平均矢量M之间的距离平方，C通过将协方差矩阵作为阵列的整个协方差矩阵引入，从而消除了样例之间的关联性。如果要素矢量在欧洲距离处的分量值很大，则可能会遮挡值较小的项目

5、的作用。这是欧式距离的不足。采用马尔可夫距离时，可以屏蔽牙齿点。由于关联性强的分量，协方差矩阵C的对角线的对应值更大。再把牙齿项目倒过来，减少其影响。协方差为对角矩阵时，特征组件徐璐无关。如果协方差是单位矩阵，则马尔科夫距离和欧氏距离相等。其中是示例矢量的k分量。M2到明氏距离是欧氏距离。M1表示邻居距离：广义明氏距离，角度相似性函数：阵列向量X和Z之间角度的馀弦，反映几何图形的相似性。旋转坐标系或平移尺寸时，角度馀弦测量保持不变(对于变位和线性变换不成立)。第二，集群标准的确定，启发式直观、经验地选择实际问题的相似性度量，确定牙齿相似性度量的阈值，然后选择特定的训练样本，测试度量和阈值的可靠

6、性。最后，根据最近的邻居规则指定特定模式示例属于群集类别。例如：对于欧氏距离，反映了样本之间的亲近性，但是在将样本分成不同类别时，距离测量的阈值基准也必须指定为集群的判别基准。基于群集的函数方法群集是结合示例以最大限度地划分类别的方法，因此群集标准必须是反映类别间相似性(或可分离性)的函数。同时，由于类由示例组成，因此类的可分离性和示例之间的差异是直接相关的。因此，集群基准函数J表示模式样本集X和模式类别Sj，j=1，2，C的函数，即J表示属于C个集群类别的所有模式样本和该类别模式的平均值之间的误差平方和。J值取决于群集格式，群集的目的是使J值非常小。由此可见，聚类分析转换变成了寻找基准函数极

7、值的最优化问题。牙齿集群方法通常称为最小方差分割，适用于各类型样本密集、数量相似、类间样本明显分离(图例解释)的情况下确定类内距离和类间距离的问题。基于群集的函数有多种茄子不同的格式。1.3根据临时群集搜寻演算法，1，最近规则的简单探索法，提供N个要分类的模式样本。按距离阈值T算法群集中心的进程：使用Step 1:随机示例Xi作为群集的初始值。例如，z1=x1，D21T，新群集中心Z2=，步骤2:计算D31T和D32T(如果群集中心z1和Z2已存在)确定新群集中心Z3=X3。Step I:讨论牙齿方法的优点。计算很简单。如果已知模式样本的集合分布的字典知识，则可以得到更好的聚类结果。实际上，很

8、难获得高维模式样本的准确字典知识，因此可以徐璐使用不同的阈值和起始点进行测试和验证结果。牙齿方法在很大程度上依赖于第一集群中心的位置(初始化问题)分类模式样本排序顺序(集群样本选择问题)距离阈值T的大小(确定标准问题)样本分布的几何特性(样本的固有特性问题)、最大最小距离算法基本思想。根据实际问题选择距离函数，类之间的距离导航的核心是最大类之间的距离，最小类内的距离。算法过程说明：首先，根据距离最小的方法预先选择集群中心，根据最近的规则将模式分类到集群中心(详细步骤见蔡元龙版模式识别. 22)。算法性能分析：增加了算法复杂性，在群集中心选择过程中消耗了更多资源。1.4系统集群，系统集群：首先将

9、每个样本作为一个类，然后根据它们之间的相似性或接近性对类别进行多点聚集，直到获得适当的分类要求。相似性，接近性用距离表示。收敛的核心是在每次迭代中形成的簇间和与样本的距离计算，不同的距离函数可以得到不同的结果。两种茄子类型的距离计算依据：1。最短距离：两个类别中最近的两个采样之间的距离，2。最大距离：两个类别中最远的两个采样之间的距离。3.中间距离：最短距离和最长距离都是单向的，所以有时使用中间距离。类1和类23之间的最短距离为d12，最大距离为d13，类23的长度为d23，中间距离为：向上一般化：4。重心距离：平均之间的距离5。类别平均距离：两个类别中每个元素之间距离的平方相加后的平均值，6

10、。将I类的偏差平方之和定义为：偏差平方和增量：样例被划分为p，q，p，q与R类组合时，定义偏差平方增量：算法流程说明：步骤1:初始距离矩阵的计算D(0)说明：(1)；(2)距离矩阵，对称矩阵。对角线上的元值表示同类之间的距离，即0。步骤2:聚合第n次迭代的距离矩阵D(n)，说明：选择距离矩阵中的最小距离，如果存在相同的，则可以选择其中之一。忽略对角线的元素。Step3:根据第n个聚合结果计算新合并类之间的距离矩阵D(n 1)说明：合并类的距离计算必须遵循距离的计算规则。例如，距离反映两种茄子类型的重心距离，它是合并后仍然需要反映的重心距离。步骤4:确定收敛(设置距离阈值D)说明：确定算法收敛条

11、件判断标准。示例1:(简单的一维情况)1，将所有采样设置为6茄子类别，2，距离矩阵D(0)，3，查找最小元素：4，1，3合并7=(1，3) 4，6合并否则停止，如下图所示。3，查找最小元素：4，8，5，2合并，9=(2，5，4，6)，1.5分解群集，分解群集：将所有采样视为一种，并按相似性、接近性分解。目标函数两种茄子类型的平均方差，N:总样本数，类1样本数，类2样本数，簇框分解，示例2:已知的21个样本，每个样本的两个茄子特性，原始数据矩阵如下表所示：解释：第一分类时计算所有样本，每个当时的E值，1(约翰f肯尼迪，美国电视电视剧)继续计算，指定的E值最大。E(1)=56.6，第二次，第三次迭

12、代继续计算E(2)，E(3)，E值1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8，因此分为两个茄子类别每次分类后要重新计算的值。您可以使用以下迭代公式：1.6动态集群同时考虑系统集群和集群分解，1，动态集群的方法首先选择距离作为样本之间的相似性度量。确定聚类结果评价的基准函数；给出了特定的初始分类，并利用迭代方法找到了获得基准函数极值的最佳聚类结果。动态集群块图表，第二，表示点(种子点)的选择方法：代表点是初始分类的集群中心数K的经验代表点，根据问题的性质、数据分布直观地表示更合理的代表点K。随机将所有样例划分为K类别，

13、计算每种类型的重心，并用作每种类型的代表点。使用前k个采样点作为代表点。密度大小：选择每个采样作为球体中心，D作为半径作为球体。落在球内部的采样数称为点的密度，按密度大小排序。首先，选择密度最大的点作为第一个代表点，即第一个群集中心。再次考虑第二密度点，如果第二密度点与第一个代表点的距离大于D1(人为规定的正数)，则第二密度点将用作第二个代表点。否则不能用作代表点，因此可以根据密度大小考察。选定代表点之间的距离全部大于D1。D1牙齿太小意味着点太多，D1牙齿太大，点太小。通常，选择d12d。代表点内密度的一般要求大于t。T0是规定的正数。3，在选择初始分类和曹征代表点放置后，代表点是集群中心，

14、计算从其他样本到集群中心的距离，将所有样本归属最近的集群中心点以形成初始分类，重新计算每个集群中心称为批处理法。选择代表点后，依次计算其他样品的分类，计算第一个样品后，将其分类为最近的类别，形成新的分类。计算新群集中心，并通过计算从第二个示例到新群集中心的距离对第二个示例进行分类。也就是说，每个示例的分类将更改群集中心。牙齿方法一个接一个地称为处理方法。直接使用样本进行初始分类，首先确定距离D，将第一个样本用作第一类集群中心，调查第二个样本，如果第二个样本小于第一个集群中心的D距离，则将第二个样本分类为第一类，否则，将第二个样本作为第二类集群中心，考虑其他样本，并根据从样本到集群中心的距离是否大于D或小于D来确定是否进行分割。最佳初始分类：如图所示，随着初始分类K的增加，指导方针函数下降迅速，通过拐点A后下降速度减慢。拐点A是最好的初始分类。4，K-平均算法：批处理任务方法示例：已知20个示例，每个示例具有两个特征，数据分布如下图所示。第一步：K=2，选择初始群集中心为，第三步：根据两个新拆分的茄子类别设置新群集中心，第4步：重新计算到旋转第2步：z1(2)、z2(2)的距离，将其分类为最近的群集中心，将其分为两个茄子类别，然后(3)K值和初始集群中心对分类结果影响