哈工大模式识别课程10.非监督学习市公开课一等奖省赛课微课金奖

主要内容1.引言2.单峰子集（类）分离方法3.类别分离间接方法4.分级聚类方法1第1页1.引言2第2页引言有监督学习（supervisedlearning)：分类器设计方法是在样本集中类别标签已知条件下进行，这些样本称为训练样本。在样本标签已知情况下，能够统计出各类训练样本不一样描述量，如其概率分布，或在特征空间分布区域等，利用这些参数进行分类器设计。用已知类别样本训练分类器，以求对训练集数据到达某种最优，并能推广到对新数据分类。3第3页无监督学习（unsupervisedlearning)：样本数据类别未知，需要依据样本间相同性对样本集进行分类(聚类，clustering)，试图使类内差距最小化，类间差距最大化。利用聚类结果，能够提取数据集中隐藏信息，对未来数据进行预测和分类。应用于数据挖掘、模式识别、图像处理、经济学……引言4第4页广泛应用领域商务：帮助市场分析人员从客户信息库中发觉不一样客户群，用购置模式来刻画不一样客户群特征土地使用：在地球观察数据库中识别土地使用情况相同地域保险业：汽车保险单持有者分组，标识那些有较高平均赔偿成本客户。城市规划：依据房子类型，价值和地理分布对房子分组生物学：推导植物和动物分类，对基因进行分类地震研究:

依据地质断层特点把已观察到地震中心分成不一样类。5第5页有监督学习与无监督学习区分有监督学习方法必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习没有训练集这一说，只有一组数据，在该组数据集内寻找规律。有监督学习方法目标就是识别事物，识别结果表现在给待识别数据加上了标号。所以训练样本集必须由带标号样本组成。而非监督学习方法只有要分析数据集本身，预先没有什么标号。假如发觉数据集展现某种聚集性，则可按自然聚集性分类，但不以与某种预先分类标号对上号为目标。6第6页无监督学习方法在寻找数据集中规律性，这种规律性并不一定要到达划分数据集目标，也就是说不一定要“分类”。这一点是比有监督学习方法用途要广泛。譬如分析一堆数据主分量，或分析数据集有什么特点都能够归于无监督学习方法范围。用无监督学习方法分析数据集主分量与用K-L变换计算数据集主分量又有区分。应该说后者从方法上讲不是一个学习方法。所以用K-L变换找主分量不属于无监督学习方法，即方法上不是。而经过学习逐步找到规律性这表达了学习方法这一点。在人工神经元网络中寻找主分量方法属于无监督学习方法。有监督学习与无监督学习区分7第7页无监督学习方法分类基于概率密度函数预计方法：指设法找到各类别在特征空间分布参数再进行分类。基于样本间相同性度量方法：直接按样本间相同性，或彼此间在特征空间中距离长短进行分类。其原理是设法定出不一样类别关键，然后依据样本与这些关键之间相同性度量，将样本聚集成不一样类别。怎样聚类则取决于聚类准则函数，以使某种聚类准则到达极值为最正确。两种聚类方法：

迭代动态聚类方法和非迭代分级聚类方法

8第8页2.单峰子集（类）分离方法9第9页思想：把特征空间分为若干个区域，在每个区域上混合概率密度函数是单峰，每个单峰区域对应一个类别。【基本思想】10第10页直接

方法一维空间中单峰分离:对样本集KN={xi}应用直方图/Parzen窗方法预计概率密度函数，找到概率密度函数峰以及峰之间谷底，以谷底为阈值对数据进行分割。【一维空间中单峰子集分离】11第11页【多维空间投影方法】基本思绪：多维空间中直接划分成单峰区域比较困难，而一维空间中则比较简单。寻找一个坐标系统，在该系统下，数据混合概率密度函数能够用边缘概率密度表示。假如某边缘概率密度函数展现多峰形式，则在此坐标轴上（一维）作分割。做法：把样本投影到某一一维坐标轴（按某种准则），在这一维上求样本概率密度（边缘概率密度），依据这一概率密度函数单峰划分子集。（假如这一维上只有一个峰，则寻找下一个投影方向。）投影方向：使方差最大方向，即协方差阵本征值最大本征向量方向。12第12页【投影方法】基本步骤13第13页【投影方法】直方图法求概率密度函数：14第14页问题：这么投影有时并不能产生多峰边缘密度函数

-方差最大准则有时并不一定最有利于聚类。【存在问题】失败例子15第15页【基于对称集性质单峰子集分离法】对称集定义：16第16页【基于对称集性质单峰子集分离法】基本步骤：17第17页【基于对称集性质单峰子集分离法】基本步骤：18第18页【单峰子集分离迭代算法】概念：19第19页【单峰子集分离迭代算法】20第20页【单峰子集分离迭代算法】目标：步骤：21第21页3.类别分离间接方法22第22页【引言】回顾：直接方法：1.预计概率密度函数——困难2.寻找密度函数中单峰间接方法：考查样本这间相同性，依据相同性把样本集划分为若干子集，使某种表示聚类质量准则函数最优。不一样聚类方法实际上反应了对聚类不一样了解：混合模型：数据服从混合分布，聚类对应于各分布单峰子集：聚类即概率分布中单峰，即样本分布相对集中区域间接方法：相同样本聚类，不一样聚类样本不相同23第23页【引言】相同性度量：以某种距离定义直观了解：同一类样本特征向量应是相互靠近。——前提：特征选取合理，能反应所求聚类关系。与基于密度函数方法关系：概念上相互关联，因密度预计也是在样本间距离基础上。详细关系取决于详细数据情况。24第24页动态聚类方法任务：

将数据集划分成一定数量子集，比如将一个数据集划分成三个子集，四个子集等。所以要划分成多少个子集往往要预先确定，或大致确定，这个子集数目在理想情况下能够表达数据集比较合理划分。需要处理问题：怎样才能知道该数据集应该划分子集数目

假如划分数目已定，则又怎样找到最正确划分。因为数据集能够有许各种不一样划分方法，需要对不一样划分作出评价，并找到优化划分结果。因为优化过程是从不甚合理划分到“最正确”划分，是一个动态迭代过程，故这种方法称为动态聚类方法。

【动态聚类方法】25第25页对计算机来说，所确定初始代表点很可能不甚合理，以至于影响到聚类结果。这就需要有一个对聚类结果进行修改或迭代过程，使聚类结果逐步趋向合理。迭代过程需要一个准则函数来指导，使迭代朝实现准则函数极值化方向收敛。聚类过程：从确定各聚类代表点开始（比如，确定三个质心点）按各样本到三个质心最短距离将样本分到该类【动态聚类方法】26第26页三个关键点选定某种距离度量作为样本间相同性度量；确定样本合理初始分类，包含代表点选择，初始分类方法选择等；确定某种评价聚类结果质量准则函数，用以调整初始分类直至到达该准则函数极值。【动态聚类方法】

C均值算法（k均值，C-meansork-means）ISODATA方法惯用算法：27第27页1.

准则函数—误差平方和准则

这个准则函数是以计算各类均值，与计算各类样本到其所属类别均值点误差平方和为准则。

反应了用c个聚类中心代表c个样本子集所带来总误差平方和。

目标:

最小化Je，即类内元素相同性高，类间元素相同性低，实现最小方差划分。【C均值算法】28第28页2.样本集初始划分

初始划分普通作法是先选择一些代表点作为聚类关键，然后把其余样本按某种方法分到各类中去。代表点几个选择方法：凭经验选择代表点。依据问题性质，用经验方法确定类别数，从数据中找出从直观上看来是比较适当代表点。将全部数据随机地分为C类，计算各类重心，将这些重心作为每类代表点。【C均值算法】29第29页“密度”法选择代表点。这里“密度”是含有统计性质样本密度。一个求法是对每个样本确定大小相等邻域(如一样半径超球体)，统计落在其邻域样本数，称为该点“密度”。在得到样本“密度”后，选“密度”为最大样本点作为第一个代表点，然后人为要求距该代表点一定距离外区域内找次高“密度”样本点作为第二个代表点，依次选择其它代表点，使用这种方法目标是防止代表点过分集中在一起。用前c个样本点作为代表点．【C均值算法】30第30页从(c-1)聚类划分问题解中产生C聚类划分问题代表点。其详细做法：对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远点，由该点及原均值点组成两聚类代表点。依一样方法，对已经有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距全部这些均值点最小距离为最大，这么就得到了第c个代表点。【C均值算法】31第31页【动态聚类】C均值算法初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入这类，不然建新类，……4.将特征归一化，用样本各特征之和作为初始分类依据。说明：初始划分无一定之规，多为启发式方法。

C均值方法结果受初值影响，是局部最优解。32第32页【动态聚类】C均值算法33第33页【动态聚类】C均值算法34第34页【动态聚类】C均值算法35第35页【动态聚类】C均值聚类方法用于非监督模式识别问题：1.要求类别数已知；2.是最小方差划分，并不一定能反应内在分布；3.与初始划分相关，不确保全局最优。C均值算法36第36页在类别数未知情况下使用C—均值算法时，能够假设类别数是逐步增加，比如对c＝1，2，3，…分别使用该算法。准则函数是随c增加而单调地降低。假如样本集合理聚类数为c类，当类别数继续增大时，相当于将聚类很好类别又分成子类，则值即使继续降低但会展现平缓趋势，假如作一条值随c改变曲线，则其拐点对应类别数就比较靠近于最优聚类数。【C均值算法-类别数未知】37第37页不过并非全部情况都能找到显著转折点。在无显著转折点时，这种选择最正确分类数方法将失效。普通需要利用先验知识对不一样聚类结果进行分析比较。

【C均值算法-类别数未知】38第38页C均值算法比较简单，但它自我调整能力也比较差。这主要表现在类别数必须事先确定，不能改变，这种主观确定数据子集数目并不一定符合数据集本身特点，受代表点初始选择影响也比较大。类似于C

均值算法，ISODATA算法聚类中心也是经过样本均值迭代运算来决定。与C均值算法不一样是，ISODATA算法将硬性确定聚类数目改成给出这个数目标期望值，作为算法一个控制量。在算法中又加上分裂与合并机制，增加了一些试探性步骤和人机交互“自组织”处理方式，因而能使聚类结果比较适应数据集内在特征。ISODATA算法与C

均值算法相比，在以下几方面有改进。1.考虑了类别合并与分裂，因而有了自我调整类别数能力。

合并主要发生在某一类内样本个数太少情况，或两类聚类中心之间距离太小情况。

【迭代自组织数据分析算法-ISODATA】39第39页

分裂则主要发生在某一类别某分量出现类内方差过大现象，因而宜分裂成两个类别，以维持合理类内方差。给出一个对类内分量方差限制参数，用以决定是否需要将某一类分裂成两类。2.因为算法有自我调整能力，因而需要设置若干个控制用参数。

迭代自组织算法流程图如图5-7所表示。【迭代自组织数据分析算法-ISODATA】40第40页ISODATA算法详细步骤以下：【迭代自组织数据分析算法-ISODATA】41第41页【迭代自组织数据分析算法-ISODATA】42第42页【迭代自组织数据分析算法-ISODATA】43第43页【迭代自组织数据分析算法-ISODATA】44第44页【迭代自组织数据分析算法-ISODATA】45第45页步骤9(求每类含有最大标准偏差分量)步骤10(分裂计算步骤)【迭代自组织数据分析算法-ISODATA】46第46页合并处理：

步骤11(计算全部聚类中心之间距离)

【迭代自组织数据分析算法-ISODATA】47第47页步骤12(列出类间距离过近者)

步骤13(执行合并)

【迭代自组织数据分析算法-ISODATA】48第48页步骤14(结束步骤)

假如迭代运算次数已达最大迭代次数I，即是最终一次迭代，则算法结束；不然，假如需要由操作者改变输入参数，转入步骤1，设计对应参数；不然，转入步骤2。到了本步运算，迭代运算次数加1。以上是整个ISODATA算法计算步骤。能够看出ISODATA算法与C

均值算法一样，都是以与代表点最小距离作为样本聚类依据，所以比较适合各类物体在特征空间以超球体分布方式分布，对于分布形状较复杂情况需要采取别度量。ISODATA算法与C均值算法主要不一样在于自我控制与调整能力不一样。【迭代自组织数据分析算法-ISODATA】49第49页ISODATA算法流程图【迭代自组织数据分析算法-ISODATA】50第50页【基于样本和核相同性度量动态聚类算法】51第51页【基于样本和核相同性度量动态聚类算法】52第52页【基于样本和核相同性度量动态聚类算法】53第53页【近邻函数准则算法】定义54第54页【近邻函数准则算法】55第55页【近邻函数准则算法】56第56页4.分级聚类方法（HierachicalClustering）57第57页分级聚类方法目标并不把N个样本分成某一个预定类别数C，而是把样本集按不一样相同程度要求分成不一样类别聚类。最极端情况是每个样本各自为一类，N个样本共有N类，没有任何聚类，另一极端则是将全部样本归一类。在这两个极端之间是类别数从N逐步降低，每类数量对应增加，而类内样本相同程度要求也随之下降。这种聚类就是分级聚类，它能够用一树形结构表示。【分级聚类方法--类别数未知

】58第58页这是一棵含有6个样本分类树。图中左边表示分级层次，第一层次各样本自成一类，其类内相同度自然是百分之百，在第二层次y3与y5合成一类，第三层次y1与y4也合并成一类，依次下去。一经合并成一类样本不再分裂，类别数也随之逐步降低，类内相同程度逐步降低。这种聚类方法在科学技术领域中得到了广泛应用，如生物分类就是分级聚类应用一个例子。【分级聚类树表示方法

】59第59页【分级聚类方法

】思想：从各类只有一个样本点开始，逐层合并，每级只合并两类，直到最终全部样本都归到一类。Hierarchicaltree--dendrogram聚类过程中逐层考查类间相同度，依此决定类别数60第60页树枝长度：反应结点/树枝之间相