《模糊聚类分析》PPT课件.ppt

第七章模糊聚类分析 一 模糊聚类分析 聚类分析 按照一定要求和原则对事物进行分类 聚类 普通分类 清晰事物模糊分类 带有模糊性的事物三种模糊聚类方法 传递闭包法 基于模糊等价关系 直接聚类法 基于模糊相似关系 模糊聚类法 基于模糊划分 二 模糊聚类分析的步骤 1 选取特征指标特征要有明确的意义 要有较强的分辨力 有代表性 并确定描述特征的变量 分类事物的特征指标选择的如何 对分类结果有直接的影响 2 数据标准化 正规化 令 其中 xi为原始数据 是原始数据的均值 是原始数据的标准差 是数据处理后的数据 3 标定 设 为待分类的对象 uj有m个刻划其特征的 数据 就是根据实际情况 按一个准则或某一种方法 给论域U中的元素两两之间都赋以区间 0 1 内的一个数 叫做相似系数 它的大小表征两个元素彼此接近或相似的程度 然后对于ui与uj 用 rij表示ui与uj的 当rij 0时 表示ui与uj截然不同 当rij 1时 表示ui与uj可以等同 不能说是完全相同 rij可根据具体问题来选取 方法有 的相似程度 要求 1 数量积法 其中 显然 如果rij中出现负值 可采用下面方法 将全体rij进行重新调整 方法1令 则 方法2令 其中 于是 2 夹角余弦法 如果rij中出现负值 也可采用上面方法调整 3 相关系数法 其中 4 最大最小法 5 算术平均最小法 6 几何平均最小法 8 指数相似系数法 其中sk适当选择 9 绝对值倒数法 M适当选取使rij在 0 1 中且分散开 7 绝对值指数法 11 非参数法 中正数个数 中负数个数 令 则 10 绝对值减数法 12 贴近度法 如果特征 则ui uj可看作模糊向量 以它们的贴近度D ui uj 为其相似程度 i 格贴近度 其中 ii 距离贴近度 其中c a为适当选择参数值 d ui uj 为模糊集各种距离 iii 算术平均最小贴近度 13 主观评定法 请有实际经验者直接对ui uj的相似程度评分 作为rij的值 通过标定求出相似系数后 便可得到以rij为元素的模糊相似矩阵R rij 4 聚类 选择一种合适的聚类方法 便可得到分类结果 三 传递闭包法 1 传递闭包法 根据标定所得模糊矩阵R 求出其传递闭包 为模糊等价矩阵 对 令 从1降到0得到 根据 进行分类 归为一类 2 最佳阈值 的选取 聚类图给出各 值对应的分类 形成一种动态聚类 便于全面了解元素聚类 然后根据实际需要选择其阈值 便可确定元素的一种分类 至于如何选择阈值 使分类更加合理 除了凭经验外 还可用F 统计量来选取 F 统计量 为待分类事物的全体 设 xjk为描述元素uj第k个特征的数据 设c为 对应于 值的类数 ni为第i类元素的个数 第i类元素记为 记 为第i类元素的第k个特征的平均值 而称 为第i类的聚类中心向量 为全体元素的中 心向量 而 于是 称 为F 统计量 其中 为第i类中元素 与中心 的距离 可见 F 统计量的分子表征类与类间的距离 分母表征类内元素间的距离 因此 F值越大 说明分类越合理 与此分类相对应的F 统计量最大的阈值 为最佳值 求传递闭包的简便方法 设 为模糊相似矩阵 求t A 1 求 假定 把A中的a1m am1 a11 amm用圆圈 圈起来 并记 2 在A中第一行 第m行中剩下的元素中 找最大元素 即 且设 在第p列 用 即分别代替a1p与amp以及它们的对称元素 最后用圆圈将它们及圈起来 3 假定A中有圈的k行 是 行 而 所在的列是ij列 在这些行中剩下的元素中 找最大元 并设在第l行 用 分别代替 继续此过程 到k n 1 得到t A 还有逐步平方法 及其对称矩阵 并把all圈起来 四 基于模糊相似关系的直接聚类法 1 最大树法 聚类原则是 ui与uj在 水平同类当且仅当在相似矩阵R的图中 存在一条权重不低于 的路联结ui与uj 画出以被分类元素为结点 以相似矩阵R的元素rij为权重的一颗最大树 2 取定 砍断权重低于 的枝 得到一个不连通图 各连通分支变构成了在 水平上的分类 2 编网法 对给定的模糊相似矩阵R 取定水平 作截矩阵 R 在R 的主对角线上填入元素的符号 在对角线下方以结点号 代替1 而 0 则略去不写 由结点向主对角线上引经线和纬线 称之为编网 通过经线和纬线能互相连接起来的元素 属于同类 从而实现了分类 五 基于模糊划分的模糊聚类法 1 c 划分 1 普通c 划分 如果划分把普通集合分成c类 则此划分就叫普通c 划分 即 若设 的特征可表为 那么U的普通c 划分是指U的c个子集 满足 1 2 其中 且满足 1 2 表示每个uj必属于且仅属于一类 表示每类Ai至少有一个元素 反过来 任一满足条件 1 2 3 的矩阵对应着U的一个分类 1 2 3 这样的分类结果可以用一个c n矩阵 称为c 划分 来表示 例如 设U u1 u2 u3 u4 若分类结果为 u1 u2 u3 u4 则对应的分类矩阵为 如果分类矩阵为 则对应着U的分类为 u1 u2 u3 u4 记V为c n实矩阵的集合 且 显然 对于给定的U及分类数c 类的分法不是唯一的 Mc包含了U的所有可能c类划分的结果 Mc称为将U分成c类的分类空间 这样的分类是通常的分类 称为硬分类 2 模糊c 划分 设 一个c n模糊矩阵 若满足 1 2 表示每个uj属于c个模糊子集Ai的程度总和为1 表示每类Ai不等于空集或U 则称A称为U的模糊c 划分矩阵 记 Mfc称为U的c类软分类空间 显然 若将Mc和 Mfc定义中的条件 放宽为 则这样的分类空间分别称为退化的硬分类空间和退化的软分类空间 分别记为Mco和Mfco 显然 2 目标函数聚类法和硬c 均值算法划分 1 目标函数法 目标函数是对给定的c的所有候选类进行度量 最优的类就是使目标函数达到局部最小值的类 对于硬分类情形 通常所选取的目标函数是总体组内误差平方和 其定义为 这里将每类Ai中元素各特征分别取平均值 所得的聚类中心向量记为vi 也称为Ai的聚类中心 由于Ai类中元素个数 Ai类中元素向量和为 因此聚类中心向量 记 V称为聚类中心矩阵 若 则uj到聚类中心vi的距离为 Ai中全体元素到中心距离平方和为 而V中所有元素到其所在类中心距离平方和为 最理想的c 划分显然是使J A V 取极小的A 2 硬c 均值算法 步骤1 假设给出n个数据点 其中 取定 并初始化 步骤2 当迭代次数为 时 计算聚类中心向量 其中 步骤3 用下式将A l 更新为 步骤4 比较A l 和A l 1 若 则停止算 法 否则 令l l 1 返回步骤2 直观上看 硬c 均值算法 猜想c的硬分类 步骤1 寻找各分类的中心 步骤2 重新分配类的隶属度以减少数据和当前中心的误差平方 步骤3 当循环不再能显著的降低J A V 时 停止算法 步骤4 3 模糊c 均值算法 定义目标函数 其中是一个加权指数 模糊c 均值算法的目标在于找到 和 使得Jm A V 最小 下面 首先建立这个最小化问题的必要条件 然后根据此条件提出模糊c 均值算法 定理令 为一给 定数据集 设定 假设对所有 则仅当 和 时 才是Jm A V 的局部最小值 模糊c 均值算法 ISODATA方法 步骤 步骤1 给定数据集 设定 并初始化 步骤2 当迭代次数为 时 计算聚类中心向量 步骤3 用下式将 更新为 步骤4 若 则停止算法 否则令l l 1 返回步骤2 注意 本方法要求 因此取初始分类A 0 时 遇到 只有一个样本的类 要在聚类前先排除 待聚类后再加上该类 而参数r一般常取r 2 4 模糊划分清晰化 在实际问题中 最后的分类结果都要求是明确的 因此 在使用模糊c 划分分类后 都必须将模糊划分清晰化 可用下述方法进行 方法1对 若 则将uj归入Ai类 方法2对 若 则将uj归入Ai类