6第六章非监督学习方法——选.ppt

第六章 非监督学习方法 郝红卫 第六章 非监督学习方法 6.1 引言 6.2 动态聚类方法 6.3 讨论 引 言 前面讨论的各种方法都是首先利用已知类别标号的样本集进行分类器设计，然后再进行分类 如果样本集没有类别标号，怎么办？ 这就引出了非监督学习方法 引 言 研究非监督方法的必要性 收集并标记大型样本库非常费时费力（如语音） 原始数据没有明显的类别信息，或事先不知道待处理数据的具体情况，缺少形成模式类过程的知识（如卫星遥感图像、数据挖掘方面的大型应用） 待分类模式的性质会随着时间发生缓慢的变化（如卫星云图） 非监督方法可以揭示观测数据的一些内部结构和规律，便于有针对性地设计分类器 可以用于预分类（多级分类） 引 言 非监督学习方法实际上是对数据进行分组(grouping) 或聚类 (clustering) 的过程 尽管得到的聚类算法没有明显的理论性，但它们确实是模式识别中非常有用的技术 具体方法有很多，最常用的是动态聚类方法 动态聚类方法 动态聚类方法是一种最常用的方法，要点： 选定某种距离度量作为样本间的相似性度量 确定某个评价聚类结果质量的准则函数 给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果 动态聚类方法 C－均值算法（K－均值算法） 距离度量：欧式距离 准则函数：误差平方和 初始分类：先选一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中 动态聚类方法 准则函数 若Ni是第i 个聚类Di中的样本数目，mi是这些样本的均值，把Di中的各样本x与均值mi间的误差平方和对所有类相加后为 Je是误差平方和聚类准则，度量了用C个聚类中心代表C个样本子集时所产生的总的误差平方。对于不同的聚类， Je的值是不同的，使Je极小的聚类就是误差平方和准则下的最优结果，这种类型的聚类通常称为最小方差划分。 动态聚类方法 初始划分代表点的选择 凭经验选代表点，根据问题的性质、数据分布，选择从直观上看来比较合适的代表点 将全部样本随机分成c类，计算每类重心，把这些重心作为每类的代表点 用前c个样本点作为代表点 动态聚类方法 按“密度”选择代表点 以每个样本为球心，用某个正数d为半径做一个球形邻域，落在该球内的样本数称为该点的“密度”。计算所有样本的密度后，按大小排序。首先选密度最大的作为第一个代表点。再考虑第二大密度点，若它距第一代表点的距离大于某个人为规定的正数d，则把它作为第二代表点，否则依次考虑其他点，以避免代表点可能集中在一起的问题。其余代表点的选择以此类推。 动态聚类方法 初始分类方法 选择一批代表点后，其余的点离哪个代表点最近就归入那一类。从而得到初始分类 选择一批代表点后，每个代表点自成一类，将样本依顺序归入与其距离最近的代表点的那一类，并立即重新计算该类的重心以代替原来的代表点。然后再计算下一个样本的归类，直至所有的样本都归到相应的类中为止 每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类 动态聚类方法 Ｃ-均值聚类算法 动态聚类方法 算法步骤 选初始聚类中心 将样本依近邻规则分别归入各个聚类 计算新的聚类中心 若聚类中心没有发生变化，则算法结束，否则转第二步 动态聚类方法 例：已知有20个样本，每个样本有2个特征，数据如下 动态聚类方法 第一步： 　　　令Ｃ=2，选初始聚类中心为 第三步： 　　根据新分成的两类计算新的聚类中心 更新聚类中心 聚类结果 聚类中心分别为 讨　　论 与监督学习相比，非监督学习方法具有更大的不确定性，主要原因在于没有了已知类别的样本集，甚至可能不知道类别数，可以利用的信息量大大减少 样本数量、距离度量、聚类准则、聚类数等都会影响距离结果 在实际应用中，应设法有效利用领域的专门知识，以弥补信息的不足 最终所得聚类的实际含义往往依靠有关应用领域的知识来解释和确定 * 6 6 2 2 2 1 1 1 0 0 特征x2 7 6 3 2 1 2 1 0 1 0 特征x1 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1 样本序号 9 9 8 8 8 7 7 7 7 6 9 8 9 8 7 9 8 7 6 8 x20 x19 x18 x17 x16 x15 x14 x13 x12 x11 第二步： 第四步： 转第二步。 　　　重新计算 　　到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类， 更新聚类中心 * * *