人智导（十五）：无指导学习

无指导学习与聚类分析

• 有指导学习与无指导学习：
  • 有指导：通过示例$\to$分类
  • 无指导：没有示例，如何分类？
• 聚类(clustering)：无指导学习的典型应用场景
  • 没有学习的样例
  • 对事物根据其相似性进行分组或分类（“物以类聚”）

聚类(clustering)分析

聚类的基本原则：类内高相似，类间低相似

无指导的聚类应用场景

• 市场分析：用购买模式刻画不同的顾客群
• 标识资源分布与使用
• 城市规划
• 地震规划
• 搜索引擎

数据表示

• 数据矩阵：对象与变量（元组与属性）
• 相异度矩阵：对象与对象
• 相似度矩阵：相异度衍生

相似性度量

• 欧几里得距离： d ( i , j ) = ( ∣ x i 1 − x j 1 ∣ 2 + ∣ x i 2 − x j 2 ∣ 2 + ⋯ + ∣ x i p − x j p ∣ 2 ) d(i,j)=\sqrt{(|x_{i1}-x_{j1}|^2+|x_{i2}-x_{j2}|^2+\dots +|x_{ip}-x_{jp}|^2)} d(i,j)=(∣xi1​−xj1​∣2+∣xi2​−xj2​∣2+⋯+∣xip​−xjp​∣2) ​
• 海明距离(Hamming)： d ( i , j ) = p − m p d(i,j)=\frac{p-m}{p} d(i,j)=pp−m​
• Jaccard距离： d ( i , j ) = b + c a + b + c d(i,j)=\frac{b+c}{a+b+c} d(i,j)=a+b+cb+c​

聚类是主观的

• 有多少簇？
  

• 六个簇
  

• 两个簇
  

• 四个簇
  

划分式聚类方法

划分式聚类算法

• 划分方法：针对数据集D其中包含了n个数据记录，发现一个有效划分使得数据集被分为k组
• 事先给定k值，寻找一种划分，以把数据集划分成k组，使其最优化一个划分准则（目标函数）
  • 全局优化：划分涉及了每一条数据记录
  • k-means（k-均值算法）：每一个簇由其中心值（平均值）来表示
  • k-medoids（k-中心点算法）：每一个簇由其距中心值最近的数据点来表示

K-means算法

• 输入：拟聚类的个数k和n个数据
• 输出：k个聚类，最小化误差平方准测（目标函数）

Select K points as the initial centroids
repeatForm K clusters by assigning all points to the closest centroidRecompute the centroid of each cluster
until The centroids don't change

• 目标函数：误差平方和最小 E = Σ i = 1 k Σ p ∈ C i ∣ p − m i ∣ 2 E=\Sigma^k_{i=1}\Sigma_{p \in C_i}|p-m_i|^2 E=Σi=1k​Σp∈Ci​​∣p−mi​∣2
  • p: 数据对象
  • m i m_i mi​: 簇 C i C_i Ci​的平均值
• 算法的局限
  • 算法是可应用的，仅当“平均”赋有意义
  • 须事先明确给出待分组（聚类）的数目
  • 较适合于发现球状的簇
• 初始中心点选择问题
  • 进行多次运行和观察，选择合适的
  • 选择数倍于k的初始中心点，然后采用层次聚类方式决定k个初始点
  • 二分(Bisecting)K-means算法
• K-means算法的局限性
  • 处理非球状的数据分布

二叉K-means算法

• K-means算法的一种变体
• 每次一份为二，逐次划分，直到产生k个簇

Initialize the list of clusters to contain the cluster containing all points
repeatSelect a cluster from the list of clustersfor i=1 to number_of_iterations doBisect the selected cluster using basic K-meansend forAdd the two clusters from the bisection with the lowest SSE to the list of clusters
until the list of clusters contains K clusters

K-Medoids算法

用最接近簇中心位置的数据记录代表其簇的中心点，而非平均值

• 任意选择k个数据作为初始中心点
• 分配每一个其余的数据点给到最近的中心点
• 随机选择一个非中心点 O r a n d o m O_{random} Orandom​
• 接替目前的中心点观察聚类结果
• 若聚类效果改善，就用 O r a n d o m O_{random} Orandom​替换原有的中心点
• 过程迭代地进行直到聚簇结果没有变化为止

层次式聚类方法

层次聚类方法

两种主要类型的层次聚类方法：

• 凝聚法(Agglomerative)
  • 开始时，每一个数据记录作为一个单一的聚簇cluster
  • 然后每步合并两个最接近的簇作为一个聚簇，直到满足结束条件或者归并成最终一个簇
• 分裂法(Divisive)
  • 开始时，只有一个簇，包含了所有数据记录
  • 然后每步分裂一个簇，直到满足结束条件或者最终分裂成每个簇都只包含单一的数据记录

层次聚类方法示意图

层次聚类方法不需要事先给出聚类的数目，但须给出结束条件

凝聚式聚类算法

compute the proximity matrix
Let each data point be a cluster
RepeatMerge the two closest clustersUpdate the proximity matrix
Until only a single cluster remains

关键是如何计算两个簇间的相似度
聚类过程：

• 开始时，每个数据记录作为一个单一簇，其相似度矩阵
• 经过几步合并后，我们获得一些聚簇
• 连续地合并两个最接近的簇，须进一步更新相似矩阵
• 簇合并后如何修改相似度矩阵？
• 需要计算两个簇间的相似度
  • 最小法(MIN)
  • 最大法(MAX)
  • 组平均法(Group Average)
  • 中心点间距离度量法
  • 目标函数法

簇间相似度计算

• 最小法(MIN)
  • 能够发现不规则形状的簇
  • 对噪音数据敏感，易出现“链接效果”(chain effect)
• 最大法(MAX)
  • 两个簇的相似度计算：基于这两个簇中的两个最远点的距离
  • 较少受噪音数据的影响
  • 数据分布不平衡时，易导致较大的簇被拆分
• 组平均方法
  • 两个簇的相似度计算：基于这两个簇中所有组对点的平均距离 KaTeX parse error: Undefined control sequence: \* at position 112: …j)}{|Cluster_i|\̲*̲|Cluster_j|}
• 目标函数法
  • 两个簇的相似度计算：以这两个簇合并后的平方误差作为距离
  • 较少受噪音数据影响
  • 偏向于处理球状簇分布

层次聚类算法的局限

• 两个簇被决定合并后，就不能回溯（一步错，步步错）
• 没有目标函数来指示优化
• 不同的簇间相似性计算策略会导致出现不同的问题：
  • 对噪音数据敏感
  • 不适合于处理不同尺度、不同形状的聚簇
  • 拆分较大的簇，等等

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！