第10章-非监督学习方法.pptVIP

C-均值算法 样本集初始划分 代表点的几种选择方法： (4) 从(c-1)聚类划分问题的解中产生C聚类划分问题的代表点 先从一类聚类的解找两聚类划分的代表点,再依次增加一个聚类代表点。 对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。 依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。 C-均值算法 样本集初始划分 在选定代表点后要进行初始划分，下面列出几种确定初始划分的方法 样本集初始划分 (1) 对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。 (2) 在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点，因此代表点在初始划分过程中作了修改。 C-均值算法 样本集初始划分 样本集初始划分 (3) 一种既选择了代表点又同时确定了初始划分的方法 (4) 先将数据标准化 ,再按照某个指标平均分布样本 C-均值算法 迭代计算 c-均值算法的迭代计算过程在原理上与梯度下降法是一样的 即以使准则函数值下降为准则。 但是由于c-均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则  C-均值算法 迭代计算方法 如果原属第k类中的一个样本y从k类移入j类时，它会对误差平方和产生影响 k类在抽出样本y后用，其相应均值为 j类在加入样本y后用，其相应均值为 C-均值算法 迭代计算方法 k类在抽出样本y后用，其误差平方和 j类在加入样本y后用，其误差平方和 C-均值算法 迭代计算方法 如果满足下式，则表明样本变动是合乎准则要求的。 C-均值算法 C—均值算法 综上所述C—均值算法可归纳成： (1) 选择某种方法把N个样本分成C个聚类的初始划分，计算每个聚类的均值和误差平方和jc (2) 选择一个备选样本y，设其在第i类 (3) 若Ni=1，则转(2)，否则继续 C-均值算法 C—均值算法 (4) 计算 (5) 对于所有的j，若ej最小，则把y放入第j类 　 C-均值算法 C—均值算法 (6) 重新计算第i，j类的均值和jc (7) 若连续迭代N次(即所有样本都运算过) 不变，则停止，否则转到2。 上述C—均值算法都是在类别c已知条件下进行的，在类别数未知情况下使用C—均值算法时，可以假设类别数是逐步增加的，例如对c＝1，2，3，…分别使用该算法 C-均值算法 C—均值算法 显然准则函数jc是随c的增加而单调地减少 如果样本集的合理聚类数为c类，当类别数继续增大时，相当于将聚类很好的类别又分成子类，则值虽然继续减少但会呈现平缓趋势 如果作一条jc值随c变化的曲线，如下图所示，则其拐点对应的类别数就比较接近于最优聚类数。 C-均值算法 C—均值算法 c＝3是较合适的聚类数 但是并非所有的情况都能找到明显的转折点。 ISODATA算法 c-均值算法的一个主要问题 划分类别数必须事先确定 主观确定数据子集数目并不一定符合数据集自身的特点 ISO-DATA算法, 将硬性确定聚类数目改成给出这个数目的期望值，作为算法的一个控制量。在算法中又加上分类与合并机制，因而能使聚类结果比较适应数据集的内在特性。 对于ISODATA算法只要求大体看懂 ISODATA算法 ISODATA算法的功能与C—均值算法相比，在下列几方面有改进 1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。 合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。 为此设有最小类内样本数限制θN，以及类间中心距离参数θc。若出现两类聚类中心距离小于的情况θc ，可考虑将此两类合并。 ISODATA算法 分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。 给出一个对类内分量方差的限制参数θs，用以决定是否需要将某一类分裂成两类。 2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。 ISODATA算法 ISODATA算法的步骤 步骤1(确定控制参数及设置代表点) 需确定的控制参数为： K： 聚类期望数； QN: 一个聚类中的最少样本数 θs : 标准偏差控制参数，用于控制分裂 θc : 类间距离控制参数，用于控制合并 L： 每次迭代允许合并的最大聚类对数；I： 允许迭代的次数。 设初始聚类数为c及聚类中心 ISODATA算法 步