模式识别第四章第五章.pptVIP

* 哈尔滨工业大学电信院 宿富林 * 3.迭代计算 c-均值算法的迭代计算过程在原理上与梯度下降法是一样的，即以使准则函数值下降为准则。 但是由于c-均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则。　　 　　 * 哈尔滨工业大学电信院 宿富林 * 按准则函数极值化的方向对初始划分进行修改 如果原属Гk 中的一个样本y从Гk 移入Гj 时，它会对误差平方和产生影响, Гk类在抽出样本y后其相应均值为 而样本y新加盟的Гj 集合均值  * 哈尔滨工业大学电信院 宿富林 * 由于y的移动只影响到k与j这两类的参数改动，因此，计算Jc值的变动只要计算相应两类误差平方和的变动即可，此时 如果 则将样本y从Гk 移入至Гj 就会使误差平方总和Jc 减小，它表明样本变动是合乎准则要求的 　　 * 哈尔滨工业大学电信院 宿富林 * 4.C—均值算法 (1) 选择某种方法把样本分成C个聚类的初始划分，计算每个聚类的均值m1,…,mc和Jc (2) 选择一个备选样本y，设其在wi 中 (3) 若Ni=1，则转(2)，否则继续 (4) 计算　 * 哈尔滨工业大学电信院 宿富林 * (5) 对于所有的j，若ei≤ej ，则将y从wj 移到 wi中。 (6) 重新计算mi和mj，并修改Jc 。 (7) 若连续迭代N次(即所有样本都运算过) Jc不变，则停止，否则转到2。　　 * 哈尔滨工业大学电信院 宿富林 * 确定类别数的实验方法 上述C—均值算法都是在类别c已知条件下进行的。 在类别数未知情况下，可以假设类别数是逐步增加的，准则函数随c的增加而单调地减小。可选择平缓时转折处的C值。 * 哈尔滨工业大学电信院 宿富林 * 5.3.1.3 ISODATA算法 　　C—均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数不能改变，受代表点初始选择的影响也比较大。 全称‘迭代自组织数据分析技术’（Iterative Self-Organizing Data Analysis Technique ）。 ISODATA算法的功能与C—均值算法相比的改进。 1. 不是没调整一个样本就重新计算一次各类均值（逐个样本修正），而是每次把全部样本都调整完毕后再重新计算样本均值（成批样本修正） 。 2.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。从而可以得到较为合理的类别数。 　　 * 哈尔滨工业大学电信院 宿富林 * 合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。 为此设有最小类内样本数限制N，以及类间中心距离参数L 。若出现两类聚类中心距离小于L或样本数小于N的情况，可将此两类合并 分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数S，用以决定是否需要将某一类分裂成两类。 　　 由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。 * 哈尔滨工业大学电信院 宿富林 * * 哈尔滨工业大学电信院 宿富林 * ISODATA算法的步骤 步骤1：确定控制参数及设置代表点 需确定的控制参数为：　　K：聚类期望数；　　 QN： 一个聚类中的最少样本数；　　　 θs： 标准偏差控制参数，用于控制分裂；　　 θc ： 类间距离控制参数，用于控制合并；　　L： 每次迭代允许合并的最大聚类对数；　　I： 允许迭代的次数。　　设初始聚类数为c及聚类中心mi,i=1,2,…,C 。　　 　　 * 哈尔滨工业大学电信院 宿富林 * 步骤2(分类)　　对所有样本，按给定的c个聚类中心，以最小距离进行分类，即　　若 　　 步骤3(撤消类内样本数过小类别)　　若有任何一个类 ，其样本数 ，则舍去该类 ，令c＝c-1，将该类中原样本分配至其它类；　　 * 哈尔滨工业大学电信院 宿富林 * 步骤5(计算类内平均距离)每类各样本离开均值的平均距离 　　　　　 步骤6(计算整个样本集偏离均值的平均距离)　　 j * 哈尔滨工业大学电信院 宿富林 * 步骤7(入口选择)　　如这是最后一次迭代(取决于I)，则转步骤11，并设置θc =0，防止合并发生。　　如果cK/2 ，则转向步骤8，执行分裂步骤；　　如果c≥2K，则转向步骤11，执行合并步骤 步骤8(求各类内各分类标准偏差)　　对每个聚类j，求其标准偏差 　　 　　　　　　　　　　 * 哈尔滨工业大