优秀网站欣赏,鲜花店的网站建设,网站开发工具有哪些,长沙广告网页设计最新招聘信息文章目录1.监督学习与无监督学习2. 聚类分析2.1簇的其他区别2.2类型2.2.1 基于中心的簇2.2.2 基于连续性的簇2.2.3 基于密度的簇2.2.4 基于概念的簇2.3 应用2.4 三要素3.距离函数3.1 距离函数的要求3.2标准化3.3其他相似、不相似函数4.评价指标4.1外部指标#xff08;有参考模…
文章目录1.监督学习与无监督学习2. 聚类分析2.1簇的其他区别2.2类型2.2.1 基于中心的簇2.2.2 基于连续性的簇2.2.3 基于密度的簇2.2.4 基于概念的簇2.3 应用2.4 三要素3.距离函数3.1 距离函数的要求3.2标准化3.3其他相似、不相似函数4.评价指标4.1外部指标有参考模型4.2无参考模型内部指标5 聚类算法5.1k-均值聚类收敛性k如何确定如何初始化K-means预处理和后处理局限性k-medoids5.2GMM高斯混合模型和EM参数学习极大似然估计--EMEMEM收敛性保证与k-means比较5.3层次聚类5.3.1 凝聚式自底向上5.4基于密度的聚类DBSCAN算法如何确定超参数epsminPts其他算法基于AutoEncoder基于CDNN1.监督学习与无监督学习
有监督学习 分类y是类别标签回归y-连续值排序y是序数 无监督学习 密度估计y密度聚类y类簇维度约简、可视化y是x的低纬表示原因 原始数据易得标注数据难节约内存和计算资源减少噪声有助于可解释的数据分析经常作为监督学习的预处理步骤
k-均值聚类GMM层次聚类基于密度的聚类算法随机中心迭代更新簇中心EM求解;E步是软划分的k-means;M步不仅估计了均值还有协方差属于所有簇概率均等时一样树凝聚式分列式连接性最大性的点属于簇局限性不同尺寸、密度、非球形不可用扰动影响大-贪心拆分和合并不可逆没有全局目标函数对噪声和离群点敏感难处理不同尺寸的簇和凸的簇成链误把大簇分裂参数确定困难 不适合密度差异大的数据集对变化的维度和高维数据不友好损失函数最小平方距离和最小化负对数似然没有优化一个全局的目标函数划分点到簇的硬划分从属关系的软划分层次划分,拆分合并不可逆优点--不需要确定k,聚类结果可能对应着有意义的分类体系不需要确定簇的数量任意形状对离群点稳定超参数确定间隔统计交叉检验簇的稳定性非参数方法eps;minPtsk:同一个簇的点到他们k最近邻的距离相同画出来找预处理归一化消除离群点后处理删除小簇分裂远合并近的收敛收敛J单调下降收敛最优局部极小局部极小假设簇是球的且每个簇的概率相等欧式距离、质心簇是高斯分布属于每个簇的概率不同但每个簇都有可能球或椭球形
2. 聚类分析
寻找样本中的簇使得同一簇内样本相似不同簇内样本不相似目标产生一个簇的集合类型 基于划分的聚类无嵌套层次聚类有嵌套 树形 三要素 定义远近 距离函数、相似度距离函数要求 非负、同一、对称、传递性 常用距离函数 欧氏距离马氏距离 尺度不一致标准化 不一定有效果可能反而不好 相似度 簇内相似度 平均距离avg(C)2∣c∣(∣c∣−1)Σ1≤ij≤∣C∣dist(xi,xj)avg(C)\frac{2}{|c|(|c|-1)}\Sigma_{1\leq ij\leq |C|}dist(x_i,x_j)avg(C)∣c∣(∣c∣−1)2Σ1≤ij≤∣C∣dist(xi,xj)最远距离diam(C)max1≤ij≤∣C∣dist(xi,xj)diam(C)max_{1\leq ij\leq |C|}dist(x_i,x_j)diam(C)max1≤ij≤∣C∣dist(xi,xj) 簇间相似度 最小距离KaTeX parse error: Undefined control sequence: \inC at position 38: …x_i \in C_i,x_j\̲i̲n̲C̲_j}dist(x_i,x_j…中心点距离dcen(Ci,Cj)dist(μi,μj),μi1∣Ci∣Σxi∈Cixid_{cen}(C_i,C_j)dist(\mu_i,\mu_j),\mu_i\frac{1}{|C_i|}\Sigma_{x_i\in C_i}x_idcen(Ci,Cj)dist(μi,μj),μi∣Ci∣1Σxi∈Cixi 评价聚类质量 评价函数由定义出发 如何获得聚类的簇 如何表示簇如何如何设计划分和优化的算法算法何时停止
特性基于中心的簇距离自己中心近其他中心远基于邻接连续的簇和簇内至少一个点距离最近基于密度的簇簇由高密度区域组成基于概念的簇同一簇共享某些性质
指标1指标2指标3有参考模型外部指标JCaabc,JC∈[0,1],JC↑,一致性↑JC\frac{a}{abc},\\JC\in[0,1],JC\uparrow,一致性\uparrowJCabca,JC∈[0,1],JC↑,一致性↑FMIaabaac,FMI∈[0,1],FMI↑,一致性↑FMI\sqrt{\frac{a}{ab}\frac{a}{ac}},\\FMI\in[0,1],FMI\uparrow,一致性\uparrowFMIabaaca,FMI∈[0,1],FMI↑,一致性↑RI2(ad)m(m−1),RI∈[0,1],RI↑,一致性↑RI\frac{2(ad)}{m(m-1)},\\RI\in[0,1],RI\uparrow,一致性\uparrowRIm(m−1)2(ad),RI∈[0,1],RI↑,一致性↑无参考模型内部指标* DBI1kΣi1kmaxi≠javg(Ci)avg(Cj)dcen(μi,μj),DBI↓,质量↑DBI\frac{1}{k}\Sigma_{i1}^kmax_{i\neq j}\frac{avg(C_i)avg(C_j)}{d_{cen}(\mu_i,\mu_j)}\\,DBI\downarrow,质量\uparrowDBIk1Σi1kmaxijdcen(μi,μj)avg(Ci)avg(Cj),DBI↓,质量↑DImin1≤ij≤kdmin(Ci,Cj)max1≤l≤kdiam(Cl),DI↑,质量↑DImin_{1\leq i j\leq k}\frac{d_{min}(C_i,C_j)}{max_{1\leq l \leq k}diam(C_l)}\\,DI\uparrow,质量\uparrowDImin1≤ij≤kmax1≤l≤kdiam(Cl)dmin(Ci,Cj),DI↑,质量↑-2.1簇的其他区别
独占Exclusive vs. 非独占的non-exclusive 在非独占的类簇中, 样本点可以属于多个簇 模糊Fuzzy vs. 非模糊的non-fuzzy 在模糊聚类中, 一个样本点以一定权重属于各个聚类簇权重和为1概率聚类有相似的特性 部分Partial vs. 完备 complete 在一些场景, 我们只聚类部分数据 异质Heterogeneous vs. 同质homogeneous 簇的大小、形状和密度的是否有很大的差别
2.2类型
基于中心的簇基于邻接的簇基于密度的簇基于概念的簇
2.2.1 基于中心的簇
簇内的点 距离其他中心远距离自己中心近 中心 质心所有点的平均或中心点表示有代表性的点
2.2.2 基于连续性的簇
基于连续性的簇相比其他任何簇的点每个点都至少和所属簇的某一个点更近
2.2.3 基于密度的簇
基于密度的簇簇是有高密的区域形成的簇之间是一些低密度的区域
2.2.4 基于概念的簇
同一簇共享某种性质这一性质是从整个结合推导出来的基于概念的簇难检测它通常不是 • 基于中心• 基于关系• 基于密度
2.3 应用
图像分割人类种族分析复杂网络分析用户画像商品分析文本分析计算生物学
2.4 三要素
定义远近 距离函数、相似度 评价聚类质量 评价函数由定义出发 如何获得聚类的簇 如何表示簇如何如何设计划分和优化的算法算法何时停止
3.距离函数
如何衡量样本之间的“远近”? 文档聚类时我们如何衡量文档间远近图像分割时我们如何衡量像素点之间的远近用户画像时我们如何衡量用户之间的远近 我们需要量化这些样本并计算它们之间的距离 距离Distance/相似Similarity/不相似Dissimilarity/邻近Proximity函数的选择与应用相关 需要考虑特征的类型 类别序值数值 可以从数据直接学习相似/距离函数距离函数要求 非负、同一、对称、传递性 常用距离函数 欧氏距离马氏距离 尺度不一致标准化 不一定有效果可能反而不好
3.1 距离函数的要求
函数dist() 是一种距离度量当且仅当 , ≥ 0 (非负性) , 0 (同一性) , , (对称性) , ≤ , , (直递性) Minkowski 距离:distmk(Σu1n∣xiu−xju∣p)1pdist_{mk}(\Sigma_{u1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}distmk(Σu1n∣xiu−xju∣p)p1 p2 Euclidean 距离: :distmk≝disteddist_{mk} ≝ dist_{ed}distmkdefdistedp1 Manhattan 距离: :distmk≝distmandist_{mk} ≝ dist_{man}distmkdefdistman 这类距离函数对特征的旋转和平移变换不敏感对数值尺度敏感如果样本特征值尺度不一致将数据标准化
3.2标准化
xijZ(xij)xij−xjˉσj,第j个特征的方差σj均值xjˉx_{ij}Z(x_{ij})\frac{x_{ij}-\bar{x_j}}{\sigma_j},第j个特征的方差\sigma_j均值\bar{x_j}xijZ(xij)σjxij−xjˉ,第j个特征的方差σj均值xjˉ 0,1 其他标准化方法 min-maxdecimal-scaling 标准化不一定起效果
3.3其他相似、不相似函数
针对二值数据的Jaccard 系数刻画变量之间的相关性系数作为相似性度量无序属性上的值差异性度量向量间的余弦相似度(Cosine similarity)
4.评价指标
有效性指标
指标1指标2指标3有参考模型外部指标JCaabc,JC∈[0,1],JC↑,一致性↑JC\frac{a}{abc},\\JC\in[0,1],JC\uparrow,一致性\uparrowJCabca,JC∈[0,1],JC↑,一致性↑FMIaabaac,FMI∈[0,1],FMI↑,一致性↑FMI\sqrt{\frac{a}{ab}\frac{a}{ac}},\\FMI\in[0,1],FMI\uparrow,一致性\uparrowFMIabaaca,FMI∈[0,1],FMI↑,一致性↑RI2(ad)m(m−1),RI∈[0,1],RI↑,一致性↑RI\frac{2(ad)}{m(m-1)},\\RI\in[0,1],RI\uparrow,一致性\uparrowRIm(m−1)2(ad),RI∈[0,1],RI↑,一致性↑无参考模型内部指标* DBI1kΣi1kmaxi≠javg(Ci)avg(Cj)dcen(μi,μj),DBI↓,质量↑DBI\frac{1}{k}\Sigma_{i1}^kmax_{i\neq j}\frac{avg(C_i)avg(C_j)}{d_{cen}(\mu_i,\mu_j)}\\,DBI\downarrow,质量\uparrowDBIk1Σi1kmaxijdcen(μi,μj)avg(Ci)avg(Cj),DBI↓,质量↑DImin1≤ij≤kdmin(Ci,Cj)max1≤l≤kdiam(Cl),DI↑,质量↑DImin_{1\leq i j\leq k}\frac{d_{min}(C_i,C_j)}{max_{1\leq l \leq k}diam(C_l)}\\,DI\uparrow,质量\uparrowDImin1≤ij≤kmax1≤l≤kdiam(Cl)dmin(Ci,Cj),DI↑,质量↑-
4.1外部指标有参考模型
参考模型 Jaccard系数 JCaabc,JC∈[0,1],JC↑,一致性↑JC\frac{a}{abc},JC\in[0,1],JC\uparrow,一致性\uparrowJCabca,JC∈[0,1],JC↑,一致性↑ FM指数 FMIaabaac,FMI∈[0,1],FMI↑,一致性↑FMI\sqrt{\frac{a}{ab}\frac{a}{ac}},FMI\in[0,1],FMI\uparrow,一致性\uparrowFMIabaaca,FMI∈[0,1],FMI↑,一致性↑ Rand指数 RI2(ad)m(m−1),RI∈[0,1],RI↑,一致性↑RI\frac{2(ad)}{m(m-1)},RI\in[0,1],RI\uparrow,一致性\uparrowRIm(m−1)2(ad),RI∈[0,1],RI↑,一致性↑
4.2无参考模型内部指标
质量好簇内相似度高簇外相似度低簇内相似度 平均距离avg(C)2∣c∣(∣c∣−1)Σ1≤ij≤∣C∣dist(xi,xj)avg(C)\frac{2}{|c|(|c|-1)}\Sigma_{1\leq ij\leq |C|}dist(x_i,x_j)avg(C)∣c∣(∣c∣−1)2Σ1≤ij≤∣C∣dist(xi,xj)最远距离diam(C)max1≤ij≤∣C∣dist(xi,xj)diam(C)max_{1\leq ij\leq |C|}dist(x_i,x_j)diam(C)max1≤ij≤∣C∣dist(xi,xj) 簇间相似度 最小距离KaTeX parse error: Undefined control sequence: \inC at position 38: …x_i \in C_i,x_j\̲i̲n̲C̲_j}dist(x_i,x_j…中心点距离dcen(Ci,Cj)dist(μi,μj),μi1∣Ci∣Σxi∈Cixid_{cen}(C_i,C_j)dist(\mu_i,\mu_j),\mu_i\frac{1}{|C_i|}\Sigma_{x_i\in C_i}x_idcen(Ci,Cj)dist(μi,μj),μi∣Ci∣1Σxi∈Cixi DB指数 DBI1kΣi1kmaxi≠javg(Ci)avg(Cj)dcen(μi,μj),DBI↓,质量↑DBI\frac{1}{k}\Sigma_{i1}^kmax_{i\neq j}\frac{avg(C_i)avg(C_j)}{d_{cen}(\mu_i,\mu_j)},DBI\downarrow,质量\uparrowDBIk1Σi1kmaxijdcen(μi,μj)avg(Ci)avg(Cj),DBI↓,质量↑ Dumn指数 DImin1≤ij≤kdmin(Ci,Cj)max1≤l≤kdiam(Cl),DI↑,质量↑DImin_{1\leq i j\leq k}\frac{d_{min}(C_i,C_j)}{max_{1\leq l \leq k}diam(C_l)},DI\uparrow,质量\uparrowDImin1≤ij≤kmax1≤l≤kdiam(Cl)dmin(Ci,Cj),DI↑,质量↑
5 聚类算法
5.1k-均值聚类
输入数据 1, 2, ⋯ , 簇数目K
随机选取K个种子数据点(seeds)作为K个簇中心
repeat foreach ∈ do计算与每一个簇中心的距离将指配到距离最近的簇中心endfor用当前的簇内点重新计算K个簇中心位置until 当前簇中心未更新K均值K-means聚类基于划分的聚类方法
如何表示簇 每个簇都用其质心centroid或者叫原型prototypeμk\mu_kμk表示 如何划分节点 距离使用欧式距离进行度量每个节点都划分到最近的那个质心的簇中rikr_{ik}rik ∈{0,1}为从属度指示样本是否属于簇且Σk1Krik1\Sigma_{k1}^Kr_{ik}1Σk1Krik1 优化目标 损失函数 JΣi1nΣk1Krik∣∣xi−μk∣∣2J\Sigma_{i1}^n\Sigma_{k1}^Kr_{ik}||x_i-\mu_k||^2JΣi1nΣk1Krik∣∣xi−μk∣∣2, 平方误差和(SSE)如何优化(chicken and egg problem) 如果中心点已知我们可以对所有点进行划分 固定μkΣirikxiΣirik,最小化J\mu_{k}\frac{\Sigma_ir_{ik}x_i}{\Sigma_ir_{ik}},最小化JμkΣirikΣirikxi,最小化J 如果从属关系已知我们可以计算中心点 固定rik,最小化Jr_{ik},最小化Jrik,最小化J 迭代计算
收敛性
k-means 是在损失函数上进行坐标下降(coordinate descent)的优化损失函数J 单调下降, 所以损失函数值会收敛, 所以聚类结果也会收敛k-means 有可能会在不同聚类结果间震荡但是在实际中较少发生局部极小J 是非凸的(non-convex), 所以损失函数J上应用坐标下降法不能够保证收敛到全局的最小值. 一个常见的方法是运行k-means多次选择最好的结果(局部极小
k如何确定
k是超参数J随k增大而递减方法 间隔统计会有拐点分析随k上升J下降的间隔交叉检验分两个子集一个估计中心一个求J簇的稳定性通过重采样和分裂度量簇的收敛程度非参数方法为k加一个先验概率
如何初始化K-means
不同的初始化选择造成不同的结果即便存在k个真实的簇正好选到k个簇的中心的概率也小启发式 随机选择k个数据点作为中心点选择第i1个中心时选择与距离之前选出的中心最远的点
预处理和后处理
预处理 归一化消除离群点 后处理 删除小的簇可能代表离群点分裂松散的簇簇内节点距离和大合并距离近的簇
局限性
尺寸不同、密度不同、非球形时得不到理想的结果扰动影响大消除 使用更大数量的簇k增加几个小的簇表示一个真实的簇使用基于密度的方法 离群点–自己成了一个簇尺寸不同 密度不同 非球形 离群点带来的问题
k-medoids
不用均值而是用中心点 均值作为原型容易受到影响 部分情况只知道数据样本见得相似矩阵 只需要数据间的相似度量就可迭代计算
5.2GMM高斯混合模型和EM 概率解释: 假设有K个簇每一个簇服从高斯分布以概率π随机选择一个簇 k 从其分布中采样出一个样本点如此得到观测数据N个样本点的似然函数(Likelihood) p(x;θ)ΠiNΣk1KπkN(xi∣μk,Σk),其中Σkπk1,0≤πk≤1p(x;\theta)\Pi_i^N\Sigma_{k1}^K\pi_kN(x_i|\mu_k,\Sigma_k),其中\Sigma_k\pi_k1,0\leq \pi_k\leq 1p(x;θ)ΠiNΣk1KπkN(xi∣μk,Σk),其中Σkπk1,0≤πk≤1引入隐变量指示所属类,k维独热表示 p(zk1)πkp(z_k1)\pi_kp(zk1)πkp(xi∣z)ΠkKN(xi∣μk,Σk)zkp(x_i|z)\Pi_k^KN(x_i|\mu_k,\Sigma_k)^{z_k}p(xi∣z)ΠkKN(xi∣μk,Σk)zk p(xi∣zk1)N(xi∣μk,Σk)p(x_i|z_k1)N(x_i|\mu_k,\Sigma_k)p(xi∣zk1)N(xi∣μk,Σk) p(xi)Σzp(xi∣z)p(z)Σk1KπkN(xi∣μk,Σk)p(x_i)\Sigma_zp(x_i|z)p(z)\Sigma_{k1}^K\pi_kN(x_i|\mu_k,\Sigma_k)p(xi)Σzp(xi∣z)p(z)Σk1KπkN(xi∣μk,Σk) 从属度(可以看做xi属于第k个簇的解释 γ(zik)p(zik1∣xi)p(zik1)p(xi∣zk1)Σk1Kp(zik1)p(xi∣zk1)πkN(xi∣μk,Σk)Σk1KπkN(xi∣μk,Σk)\gamma(z_{ik})\\p(z_{ik1}|x_i)\\\frac{p(z_{ik}1)p(x_i|z_k1)}{\Sigma_{k1}^Kp(z_{ik}1)p(x_i|z_k1)}\\\frac{\pi_kN(x_i|\mu_k,\Sigma_k)}{\Sigma_{k1}^K\pi_kN(x_i|\mu_k,\Sigma_k)}γ(zik)p(zik1∣xi)Σk1Kp(zik1)p(xi∣zk1)p(zik1)p(xi∣zk1)Σk1KπkN(xi∣μk,Σk)πkN(xi∣μk,Σk)
参数学习极大似然估计–EM
极大似然估计 难log里面有求和所有参数耦合似然函数取最大值时满足的条件log(P(x∣θ)对μk求导log(P(x|\theta)对\mu_k求导log(P(x∣θ)对μk求导 0−Σi1NπkN(xi∣μk,Σk)Σk1KπkN(xi∣μk,Σk)Σk(xi−μk)0-\Sigma_{i1}^N\frac{\pi_kN(x_i|\mu_k,\Sigma_k)}{\Sigma_{k1}^K\pi_kN(x_i|\mu_k,\Sigma_k)}\Sigma_k(x_i-\mu_k)0−Σi1NΣk1KπkN(xi∣μk,Σk)πkN(xi∣μk,Σk)Σk(xi−μk) μkΣiγ(zik)xiγ(zik)\mu_k\frac{\Sigma_i\gamma(z_{ik})x_i}{\gamma(z_{ik})}μkγ(zik)Σiγ(zik)xiπkΣiγ(zik)N\pi_k\frac{\Sigma_i\gamma(z_{ik})}{N}πkNΣiγ(zik)ΣkΣiγ(zik)(xi−μk)(xi−μk)Tγ(zik)\Sigma_k\frac{\Sigma_i\gamma(z_{ik})(x_i-\mu_k)(x_i-\mu_k)^T}{\gamma(z_{ik})}Σkγ(zik)Σiγ(zik)(xi−μk)(xi−μk)T 这不是封闭解–》EM E给定当前参数估计值求后验概率γ(zik)E(zik)\gamma(z_{ik})E(z_{ik})γ(zik)E(zik)M依据后验概率γ(zik)\gamma(z_{ik})γ(zik)求参数估计μk、πk、Σk\mu_k、\pi_k、\Sigma_kμk、πk、Σk迭代收敛到局部极小
EM
通用EM 目标函数极大似然函数logP(X∣θ)logΣzP(x,z∣θ)logP(X|\theta)log\Sigma_zP(x,z|\theta)logP(X∣θ)logΣzP(x,z∣θ)用于不完整数据的对数似然函数 不知Z的数据只知道Z的后验分布P(z∣x,θold)P(z|x,\theta^{old})P(z∣x,θold)考虑其期望Q(θ,θold)Ep(z∣x,θold)(logP(x,z∣θ))Q(\theta,\theta^{old})E_{p(z|x,\theta^{old})}(log P(x,z|\theta))Q(θ,θold)Ep(z∣x,θold)(logP(x,z∣θ))最大化期望θnewargmaxθQ(θ,θold)\theta^{new}argmax_\theta Q(\theta,\theta^{old})θnewargmaxθQ(θ,θold) E求P(z∣x,θold)P(z|x,\theta^{old})P(z∣x,θold)MθnewargmaxθQ(θ,θold)\theta^{new}argmax_\theta Q(\theta,\theta^{old})θnewargmaxθQ(θ,θold) why是启发式的但却存在似然函数 Q(θ,θold)Ep(z∣x,θold)(logP(x,z∣θ))p(x;θ)Q(\theta,\theta^{old})E_{p(z|x,\theta^{old})}(log P(x,z|\theta))p(x;\theta)Q(θ,θold)Ep(z∣x,θold)(logP(x,z∣θ))p(x;θ) 完整数据和不完整数据的比较不完整数据logp(x)ΣilogΣzp(xi∣z)p(z)ΣilogΣk1KπkN(xi∣μk,Σk)logp(x)\Sigma_ilog \Sigma_zp(x_i|z)p(z)\Sigma_ilog \Sigma_{k1}^K\pi_kN(x_i|\mu_k,\Sigma_k)logp(x)ΣilogΣzp(xi∣z)p(z)ΣilogΣk1KπkN(xi∣μk,Σk) 不完整数据中参数之间是耦合的不存在封闭解 完整数据 logp(x,z∣θ)logp(z∣θ)p(x∣z,θ)ΣiΣkzik(logπklogN(xi∣μk,Σk))logp(x,z|\theta)logp(z|\theta)p(x|z,\theta)\Sigma_i\Sigma_k z_{ik}(log\pi_klogN(x_i|\mu_k,\Sigma_k))logp(x,z∣θ)logp(z∣θ)p(x∣z,θ)ΣiΣkzik(logπklogN(xi∣μk,Σk))Ez(logp(x,z∣θ))ΣiΣkE(zik)(logπklogN(xi∣μk,Σk))ΣiΣkγ(zik)(logπklogN(xi∣μk,Σk))E_z(logp(x,z|\theta))\\\Sigma_i\Sigma_kE(z_{ik})(log\pi_klogN(x_i|\mu_k,\Sigma_k))\\\Sigma_i\Sigma_k\gamma(z_{ik})(log\pi_klogN(x_i|\mu_k,\Sigma_k))Ez(logp(x,z∣θ))ΣiΣkE(zik)(logπklogN(xi∣μk,Σk))ΣiΣkγ(zik)(logπklogN(xi∣μk,Σk))
EM收敛性保证
目标最大化P(x∣θ)Σzp(x,z∣θ)P(x|\theta)\Sigma_zp(x,z|\theta)P(x∣θ)Σzp(x,z∣θ) 直接优化P(x∣θ)P(x|\theta)P(x∣θ)很困难但优化完整数据的p(x,z∣θ)p(x,z|\theta)p(x,z∣θ)容易 证明 分解对任意分布q(z),下列分解成立 lnp(x∣θ)L(q,θ)KL(q∣∣p)其中L(q,θ)Σzq(z)ln(p(x,z∣θ)q(z))KL(q∣∣p)−Σzq(z)ln(p(z∣x,θ)q(z))KL(q∣∣p)≥0,L(q,θ)是lnp(x∣θ)的下界lnp(x|\theta)L(q,\theta)KL(q||p)\\其中\\L(q,\theta)\Sigma_zq(z)ln(\frac{p(x,z|\theta)}{q(z)})\\KL(q||p)-\Sigma_zq(z)ln(\frac{p(z|x,\theta)}{q(z)})\\KL(q||p)\geq0,L(q,\theta)是lnp(x|\theta)的下界lnp(x∣θ)L(q,θ)KL(q∣∣p)其中L(q,θ)Σzq(z)ln(q(z)p(x,z∣θ))KL(q∣∣p)−Σzq(z)ln(q(z)p(z∣x,θ))KL(q∣∣p)≥0,L(q,θ)是lnp(x∣θ)的下界 E最大化L(q,θ),q(z)P(z∣x,θold)最大化L(q,\theta),\\q(z)P(z|x,\theta^{old})最大化L(q,θ),q(z)P(z∣x,θold)M:原来的下界L(q,θ)ΣzP(z∣x,θold)ln(p(x,z∣θ)q(z))Q(θ,θold)const−−−正好是期望M:原来的下界L(q,\theta)\Sigma_zP(z|x,\theta^{old})ln(\frac{p(x,z|\theta)}{q(z)})Q(\theta,\theta^{old})const---正好是期望M:原来的下界L(q,θ)ΣzP(z∣x,θold)ln(q(z)p(x,z∣θ))Q(θ,θold)const−−−正好是期望下界提升了
与k-means比较
高斯混合模型的E步是一个软划分版本的 K-means. ∈ [0,1]高斯混合模型的M步估计除了估计均值外还估计协方差矩阵当所有π 相等Σkδ2I,当δ→0,γik→0,1\Sigma_k\delta^2I,当\delta\rightarrow 0,\gamma_{ik}\rightarrow{0,1}Σkδ2I,当δ→0,γik→0,1,那么两个方 法是一致的
5.3层次聚类 产生树形嵌套的聚类簇 可以被可视化为树状图(dendrogram)树形的示意图记录了簇合并或分割的序列 优点 不需要提前假定聚类的簇数 通过选择树状图的某一层可以获得任意簇数量的聚类结构用户可以在层次化的聚类中选择一个分割得到一个最自然的聚类结果 例如各个簇的簇间相似性高于一定阈值 聚类结果可能对应着有意义的分类体系 例如在生物科学中 (e.g., 门纲目科, 人类种系, …) 分类 自底向上(凝聚式): 递归的合并相似度最高/距离最近的两个簇自顶向下 (分列式): 递归地分裂最不一致的簇例如具有最大直径的簇
凝聚式分列式更流行近似程度更流行更流行
5.3.1 凝聚式自底向上
相较于分列式凝聚式是更加流行的层次聚类技术基本算法非常直观 关键是如何计算簇之间的近似程度(proximity ) →不同的定义簇间距离的方 法将得到不同的聚类算法算法 起始状态 一个点一个类 中间过程 经过一些合并步骤后可以得到一些簇合并最近的两个簇C2,C5),并更新相似度矩阵–如何更新 缺点 贪心: 一旦簇被合并或者拆分过程不可逆没有优化一个全局的目标函数不同方法存在一个或多个以下问题: 对噪声和离群点敏感比较难处理不同尺寸的簇和凸的簇成链, 误把大簇分裂 相似度矩阵如何更新如何定义簇间相似度
优点缺点最小距离min)可形成非球形、非凸的簇链式效应最大距离max)优点对噪声更加有鲁棒性不成链趋向于拆开大的簇偏好球形簇平均距离group average)折中中心点距离distance between centroids)-反向效应偶棉合并的簇间距离可能比之前合并的簇的簇间距离更近ward’s方法试用平方误差两个簇的相似性基于两个簇融合后的平方误差的增加偏向球形簇k-means的层次化版本(可用于初始化k-means)-5.4基于密度的聚类DBSCAN
概念 密度给定半径eps)内点的个数核心点密度大于minPts的点边界点密度少于minPts,但半径内的点都在某个核心点的范围内噪声点此外的点点q由p密度可达连接两个点的路径上所有的点都是核心点 如果p 是核心点那么由它密度可达的点形成一个簇 点q 和点p 是密度相连的如果存在点o 从其密度可达点q 和点p(间接抵达 聚类的簇满足以下两个性质: 连接性簇内的任意两点点是密度相连的;最大性如果一个点从一个簇中的任意一点密度可达那么该点属于该簇
算法 如何确定超参数epsminPts
直观想法同一个簇内的点它们第k个最近邻大约相同的距离。噪声点到其第k最近邻距离较远方法画出每个点到其第k最近邻的距离
其他算法
◼聚类公平性 • 意义聚类主体与人相关 • 多种公平性定义 • 多种聚类算法下的公平性 ◼Multi-View数据聚类 • 数据来自多个源 • 数据的属性不一致 • 例如text image voice ◼聚类算法的加速 • 例如DBSCAN减少密度计算量提 升算法应用速度 • 提高密度聚类并行性
基于AutoEncoder
Deep Embedding Network(DEN)AE加入正则学习更适合的表示 步骤利用AE对原是数据降维再利用k-means聚类学到的表示局部性保持正则项聚类最近的点距离不变组稀疏正则项表示分为多组只有部分组激活 Deep Embedded Clustering(DEC)是一个典型的基于无监督的深度神经网络聚类算法步骤 先在AE预训练采用encoder参数进行初始化利用聚类损失进行训练利用自我训练目标
基于CDNN
网络仅仅通过聚类损失进行调节网络可以使CNNFCNDBN等
[参考文献] 1.国科大prml课程郭嘉丰老师ppt
