《计算智能》曾文艺

离散数学中的等价关系关系和有向图R = { (a, d), (a, e) } 是 A->B 上的关系（偶）序对（非）自反关系 (a, a)（非）对称关系 (a, b) (b, a)（非）传递关系 (a, b) (b, c) => (a, c)=> 等价关系关系矩阵🌰例子等价关系下的聚...

离散数学中的等价关系

关系和有向图

R = { (a, d), (a, e) } 是 A->B 上的关系

（偶）序对

  • （非）自反关系 (a, a)
  • （非）对称关系 (a, b) <-> (b, a)
  • （非）传递关系 (a, b) (b, c) => (a, c)

=> 等价关系

关系矩阵

🌰例子

等价关系下的聚类

A = { 1, 2, 3, 4 } 的划分

4类 {1} {2} {3} {4} (1)
1类 {1, 2, 3, 4} (2)
2类 {1}+{2,3,4} {1,2}+{3,4} (4, 3)
3类 {1,2}+{3}+{4} (6)

聚类

聚类是一种无监督学习方法，用于将数据集中的对象按照它们之间的相似性划分为不同的组或簇。聚类的目标是在同一组内的对象相似度较高，而不同组之间的相似度较低。聚类算法通过计算数据对象之间的相似度或距离，并将相似的对象放在同一个簇中，从而实现聚类。

聚类与分类

聚类是一种无监督学习方法，它试图在数据中发现固有的结构，而不需要先验的标签或类别。聚类算法旨在将数据集中的对象按照它们之间的相似性划分为不同的组或簇，聚类的目标是在同一组内的对象相似度较高，而不同组之间的相似度较低。

相比之下，分类是一种监督学习方法，它需要先验的标签或类别来训练模型。分类算法的目标是将数据集中的对象划分为预定义的类别之一。分类算法学习如何将数据映射到已知类别的标签上，以便对新数据进行预测。

簇

同一簇中对象彼此相似

不同簇中对象相异

相异度

根据描述对象的属性值评估，通常使用距离度量

  • 欧几里得距离：平方和再开方
  • 曼哈顿距离：各维度差的绝对值之和
  • 切比雪夫距离：各维度差的绝对值的最大值
  • 余弦相似度：向量夹角的余弦值
  • 马氏距离：两个向量之间的马氏距离
聚类分析的典型要求

可伸缩性 / 处理不同类型属性的能力 / 发现任意形状的簇 / 对于决定输入参数的领域知识需求最小 / 处理带噪声数据的能力 / 增量聚类和对输入记录的次序不敏感 / 高维性 / 基于约束的聚类 / 可解释性和可用性

划分方法

给定n个对象的数据集D，以及要生成的簇的数目k，将对象组织为k个划分（k<=n），每个划分代表一个簇

平方误差准则
  • 对于每个簇中的每个对象，求对象到其簇中心距离的平方，然后求和

使用这个准则，试图使生成k个结果的簇尽可能的紧凑和独立

「最小一乘」鲁棒性比最小二乘法更强

K-means
  • 优势
    • 快速简单
    • scalable
    • 时间复杂度O(nkt)接近于线性，该方法终止于局部最优解而且适合挖掘大规模数据集
      • n是对象总数，k是簇的个数，t是迭代次数
      • k<<n，t<<n
  • 局限性
    • k是事先给定的，k值的选定难以估计，很多时候，k未知
    • K-means算法中，需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心对选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果
    • 不适合发现非凸面型状的簇或者大小差别很大的簇。而且，它对于噪声和孤立点的数据是敏感的
  • 改进
    • K-medoids K-medoids使用曼哈顿距离而不是欧几里得距离，并选择每个簇的一个点作为中心，这些点称为medoids。K-medoids算法比K-means算法更健壮，因为它可以处理噪声和离群值。它的时间复杂度为O(k(n-k)^2)，其中k是簇数，n是数据点数
    • K-mode K-mode算法用于离散型数据的聚类，它使用了众数而不是均值来计算每个簇的中心，同时使用哈密顿距离（即两个向量中对应维度不同的数量）而不是欧几里得距离来衡量向量之间的相似度。K-mode算法适用于分类数据和文本数据等非连续型数据。它的时间复杂度为O(k(n-k)L)，其中L是属性数
    • K-prototype K-prototype算法结合了K-means和K-mode算法的优点，同时支持连续和离散型数据。它使用欧几里得距离来衡量连续型数据之间的相似度，并使用哈密顿距离来衡量离散型数据之间的相似度。K-prototype算法对于同时包含连续型和离散型数据的混合数据集非常有效。它的时间复杂度为O(k(n-k)L)，其中L是属性数

K-means是一种基于均值的聚类算法，将每个数据点分配到最近的质心（均值），然后更新质心位置，不断迭代直到收敛。但是，K-means算法只适用于数值型数据，不能处理分类变量和混合数据类型。

K-medoids是一种基于中心点的聚类算法，与K-means相似，但是将每个簇的中心点指定为簇中具有最小平均距离的样本，而不是使用均值。这使得K-medoids更适用于处理非数值型数据，但是由于每次迭代需要重新计算中心点，因此计算成本比K-means更高。

K-modes是一种聚类算法，专门用于处理分类数据。它使用频率最高的类别作为簇的代表，并通过最小化汉明距离（样本之间的不匹配数量）来确定簇。与K-means和K-medoids不同，K-modes算法使用非连续距离度量。

K-prototype是一种融合了K-means和K-modes的聚类算法，能够同时处理数值型和分类数据。它使用欧氏距离来度量数值型数据之间的距离，使用汉明距离来度量分类数据之间的距离，通过最小化距离和来确定簇。相比于K-means和K-medoids，K-prototype具有更广泛的适用性，但是也更加复杂。

全集 X
集合 A = { x | x ∈ A } ⊆ X

集合的特征函数（离散数学）

f_A: X → { 0, 1 }

集合的运算 -> 特征函数的变换

f_{A∩B}(x) = f_A(x) f_B(x) = min(f_A(x), f_B(x))
f_{A∪B}(x) = f_A(x) + f_B(x) - f_A(x) f_B(x) = max(f_A(x), f_B(x))

模糊集合A有隶属函数：

μ_A(x): X -> [0, 1]

定义模糊集合的交并运算，借助隶属函数

分解定理

表现定理

隶属函数的建立方法

1.7.1 模糊统计方法

2 模糊模式识别

区间值模糊集合

直觉模糊集 IFS

犹豫模糊集合

毕达哥拉斯模糊集 PFS

2.1 模式识别直接方法

2.1.1 最大隶属原则

2.1.2 阈值原则

2.2 贴近度与择近原则

  • 距离
  • 相似度 similarity measure

2.2.1 模糊集的内积与外积

  • 内积：两个集合先取小，结果再取上确界
  • 外积：两个集合先取大，结果再取下确界

2.2.2 格贴近度

  • 内积与相似度正相关
  • 外积与相似度负相关

2.2.3 择近原则

认为是正态分布，于是格贴近度第二项为1，只用求两正态分布曲线交点

然而格贴近度还是有很大问题

  • 自己跟自己的贴近度不一定为1
  • 如果两个模糊集上限下限相同，贴近度为1

贴近度的公理化定义

  1. 对称性
  2. 当且仅当A和B相同时，A与B贴近度达到最大值
  3. 和空集贴近度为0
  4. A⊆B⊆C，A与C的距离最远

利用闵可夫斯基距离定义贴近度