05第五章非监督学习法5.3-5.4.ppt

§5.3 聚类方法 样本非球体分布的动态聚类算法 2、近邻函数准则算法 几种不同形状的数据构造的例子 特点：类内样本具有明显的近邻关系，因而可以利用这种关系，定义近邻函数，以执行动态聚类算法。 (1) 近邻关系描述 样本集中任何一对样本间的近邻关系可以用彼此是对方的第几个近邻的方式来描述。 例如： yi是yj的第I个近邻，而yj是yi的第K个近邻，则这一对样本之间的近邻函数值可定义为(I+K-2)。近邻函数值为： aij =I+K-2 (2) “连接”损失 用近邻关系进行聚类，可以看作是一种连接过程，即将具有适当近邻关系的样本连接成同一类，而避免在近邻关系较差的样本之间进行连接。 为了实现按近邻关系建立样本间的连接关系，可定义一个“连接”损失，以近邻函数值作连接损失值。采用这种定义，可以使连接趋向于发生在距离接近的样本之间。 为了防止样本自身实行连接，可将aij定义为2N或更大，其中N是样本集的样本数，这种定义是考虑到样本集内任何一对非自身的样本间的最大连接损失为(2N-4)即 样本之间的“连接”与“连接”损失 *中国矿业大学 计算机科学与技术学院 第五章 非监督学习法 聚类方法 不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，以使某种聚类准则达到极值为最佳。 两种对数据集进行聚类的方法： (1) 迭代的动态聚类算法 (2) 非迭代的分级聚类算法 例：使用聚类方法实现道路识别 §5.3.1 动态聚类方法 动态聚类方法的任务 将数据集划分成一定数量的子集，子集数目在理想情况下能体现数据集比较合理的划分。 要解决的问题 (1) 怎样才能知道该数据集应该划分的子集数目 (2) 如果划分数目已定，则又如何找到最佳划分。 由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。 动态聚类方法基本要点 动态聚类示意图 动态聚类算法的要点 (1) 选定某种距离度量作为样本间的相似性度量。 (2) 确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。 (3) 确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。 C-均值算法 1、准则函数—误差平方和准则 准则函数是以计算各类均值 ，与计算各类样本到其所属类均值点误差平方和为准则。 各类均值： (5.3-1) 误差平方和准则可表示为： (5.3-2) 最佳的聚类是使误差平方和准则为最小的分类。这种类型的聚类通常称为最小方差划分。 C-均值算法 2、样本集初始划分 初始划分的一般作法是先选择一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中去。 代表点的选择方法： (2) 将全部数据随机地分为C类，计算各类重心，将这些重心作为每类的代表点。 (1) 凭经验选择代表点。 根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。 (3) “密度”法选择代表点。 (4) 从(c-1)聚类划分问题的解中产生C聚类划分问题的代表点。 选“密度”为最大的样本点作为第一个代表点，然后人为规定距该代表点 距离外的区域内找次高“密度”的样本点作为第二个代表点，依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起。 对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。 确定初始划分的方法 (1) 对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。 (2) 在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点，因此代表点在初始划分过程中作了修改。 (3) 既选择了代表点又同时确定了初始划分的方法。 然后选ω1=y1，计算样本y2与y1的距离D(y1, y2)，如其小于d，则归入ω1 ，否则建立新的类别ω2。 首先规定一阈值d。 当轮到样本ye时，已有了K类即，ω1,ω2, … ,ωk，而每类第一个入类样本分别为y11, y21, … , yk1 ，则计算D(yi1, ye), i=1,2,…,k, 若D(yi1, ye) d 则建立新类。否则将ye归入与y11, y21, … , yk1距离最近的类别中。 (4) 先将数据标准化，用yij表示标准化后第i数据的第j个分量，令 如果欲将样本划分为c类，则对每个i计算 如所得结果非整数，则找到其最近整数K，将第i数据归入第K类。 3、迭代计