网站建设是编程吗,网页制作教案,国内外优秀网站,WordPress制作小说网站1.什么是聚类任务#xff1f;
类别#xff1a;无监督学习 目的#xff1a;通过对无标记训练样本的学习来揭示数据的内在性质及规律#xff0c;为进一步的数据分析提供基础。
1.1K均值聚类
步骤#xff1a;
随机选取样本作为初始均值向量(初始值:k的值【即几个簇】)分别…1.什么是聚类任务
类别无监督学习 目的通过对无标记训练样本的学习来揭示数据的内在性质及规律为进一步的数据分析提供基础。
1.1K均值聚类
步骤
随机选取样本作为初始均值向量(初始值:k的值【即几个簇】)分别计算每个样本点到初始均值向量的距离距离哪个点最近就属于哪个簇每个簇重新计算中心点重复第二步直到收敛
距离计算 距离度量/非距离度量若它是一个距离度量则应该满足以下性质
非负性dist(x,y)0同一性dist(x,y)0,当且仅当xy对称性dist(x,y) dist(y,x)直递性dist(x,z) dist(x,y)dist(y,z)
1.1.1 曼哈顿距离 d i s t m a n ( x i , x j ) ∥ x i − x j ∥ 1 ∑ μ 1 n ∣ x i μ − x j μ ∣ {\rm{dis}}{{\rm{t}}_{man}}({x_i},{x_j}) {\left\| {{x_i} - {x_j}} \right\|_1} \sum\limits_{\mu 1}^n {\left| {{x_{i\mu }} - {x_{j\mu }}} \right|} distman(xi,xj)∥xi−xj∥1μ1∑n∣xiμ−xjμ∣
1.1.2欧氏距离 dist e d ( x i , x j ) ∥ x i − x j ∥ 2 ∑ u 1 n ∣ x i u − x j u ∣ 2 \operatorname{dist}_{\mathrm{ed}}\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)\left\|\boldsymbol{x}_i-\boldsymbol{x}_j\right\|_2\sqrt{\sum_{u1}^n\left|x_{i u}-x_{j u}\right|^2} disted(xi,xj)∥xi−xj∥2u1∑n∣xiu−xju∣2
1.1.3 切比雪夫距离
切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说它就是沿着一个轴的最大距离。切比雪夫距离通常被称为棋盘距离因为国际象棋的国王从一个方格到另一个方格的最小步数等于切比雪夫距离。 D ( x , y ) max i ( ∣ x i − y i ∣ ) D(x,y) \mathop {\max }\limits_i (|{x_i} - {y_i}|) D(x,y)imax(∣xi−yi∣)
切比雪夫距离通常用于特定的用例这使得它很难像欧氏距离或余弦相似度那样作为通用的距离度量。因此在确定适合用例时才使用它。
1.1.4 闵式距离
给定样本 x i ( x i 1 ; x i 2 ; … ; x i n ) {x_i} ({x_{i1}};{x_{i2}}; \ldots ;{x_{in}}) xi(xi1;xi2;…;xin)与 x j ( x j 1 ; x j 2 ; … ; x j n ) {x_j} ({x_{j1}};{x_{j2}}; \ldots ;{x_{jn}}) xj(xj1;xj2;…;xjn)最常用的就是闵可夫斯基距离。 d i s t m k ( x i , x j ) ( ∑ u 1 n ∣ x i u − x j u ∣ p ) 1 p dis{t_{mk}}({x_i},{x_j}) {(\sum\limits_{u 1}^n {{{\left| {{x_{iu}} - {x_{ju}}} \right|}^p}} )^{{1 \over p}}} distmk(xi,xj)(u1∑n∣xiu−xju∣p)p1
p1时闵可夫斯基距离即为曼哈顿距离( Manhattan distance )p2时闵可夫斯基距离即为欧式距离 Euclidean distance )p ∞ \infty ∞时闵可夫斯基距离即为切比雪夫距离(Chebyshev Distance )
1.1.5 余弦相似度(Cosine Similarity )
余弦相似度经常被用作抵消高维欧式距离问题。余弦相似度是指两个向量夹角的余弦。
两个方向完全相同的向量的余弦相似度为1而两个彼此相对的向量的余弦相似度为- 1。注意它们的大小并不重要因为这是在方向上的度量。 D ( x , y ) cos ( θ ) x ⋅ y ∥ x ∥ ∥ y ∥ D(x,y) \cos (\theta ) {{x \cdot y} \over {\left\| x \right\|\left\| y \right\|}} D(x,y)cos(θ)∥x∥∥y∥x⋅y
用例:当我们对高维数据向量的大小不关注时可以使用余弦相似度。列如对于文本分析当数据以单词计数表示时经常使用此度量。例如当一个单词在一个文档中比另一个单词更频繁出现时这并不一定意味着文档与该单词更相关。可能是文件长度不均匀或者计数的重要性不太重要。我们最好使用忽略幅度的余弦相似度。
1.1.6 汉明距离(Hamming Distance )
汉明距离是两个向量之间不同值的个数。它通常用于比较两个相同长度的二进制字符串。它还可以用于字符串通过计算不同字符的数量来比较它们之间的相似程度。
缺点:当两个向量长度不相等时汉明距离使用起来很麻烦。
用例∶典型的用例包括数据通过计算机网络传输时的错误纠正/检测。它可以用来确定二进制字中失真的数目作为估计误差的一种方法。此外你还可以使用汉明距离来度量分类变量之间的距离。
1.2密度聚类(Density-based Spatial Clusteringof Applications with Noise )
基于密度的聚类此类算法假设聚类结构能通过样本分布的紧密程度确定
密度聚类算法从样本密度的角度来考察样本之间的可连接性并基于可连接样本不断扩展聚类簇以获得最终的聚类结果
层次聚类高斯混合模型聚类聚类效果的衡量指标
1.3层次聚类(hierarchicalclustering)
试图在不同层次对数据集进行划分从而形成树形的聚类结构.数据集的划分可采用自底向上的聚合策略也可采用自顶向下的拆分策略.
AGNES是一种采用自底向上聚合策略的层次聚类算法.它先将数据集中的每个样本看作一个初始聚类簇然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并该过程不断重复直至达到预设的聚类簇个数。
AGNES算法步骤: ( 1初始化每个样本当做一个簇 ( 2计算任意两簇距离找出距离最近的两个簇合并这两簇 (3重复步骤2… 直到最远两簇距离超过阈值或者簇的个数达到指定值终止算法
DIANA算法步骤: ( 1初始化所有样本集中归为一个簇 ( 2在同一个簇中计算任意两个样本之间的距离,找到距离最远的两个样本点a,b 将a,b作为两个簇的中心; ( 3计算原来簇中剩余样本点距离a , b 的距离距离哪个中心近分配到哪个簇中 ( 4重复步骤2、3… 直到最远两簇距离不足阈值或者簇的个数达到指定值终止算法
层次聚类(Hierarchical Clustering )在生物信息学中的应用
层次聚类是一种比较实用的聚类方法应用于不同领域的数据分析算法中。 在生物医学信息学领域层次聚类方法常常用于蛋白质序列数据聚类和基因表达数据的聚类。结构相似的蛋白质功能也相似通过聚类将相似功能的蛋白质聚为一类为研究蛋白质的功能提供帮助。基因表达数据聚类就是将具有相似表达谱的基因聚为一类称为共表达基因根据基因的共表达现象推断这些基因的生物学功能从而对新的基因功能进行注释对基因的生物学功能研究具有重要意义。
1.4 高斯混合聚类模型
已知样本集D D { x 1 , x 2 , . . . , x m } D \{ {x_1},{x_2},...,{x_m}\} D{x1,x2,...,xm}要将这些样本聚成k类我们认为样本服从混合高斯分布 p M ( x ) ∑ i 1 k α i ⋅ p ( x ∣ μ i , Σ i ) {p_M}(x) \sum\limits_{i 1}^k {{\alpha _i}} \cdot p(x|{\mu _i},{\Sigma _i}) pM(x)i1∑kαi⋅p(x∣μi,Σi)
第一步初始化高斯混合分布的模型参数 α i {{\alpha _i}} αi, μ i {\mu _i} μi, Σ i {\Sigma _i} Σi
第二步计算x 由各混合成分生成的后验概率即观测数据 x j {x_j} xj由第i个分模型生成的概率 p ( z j i ∣ x j ) p({z_j} i|{x_j}) p(zji∣xj)并记为 γ j i {\gamma _{ji}} γji γ j i a i ⋅ p ( x j ∣ μ i , Σ i ) ∑ i 1 k a i p ( x j ∣ μ i , Σ i ) {\gamma _{ji}} {{{a_i} \cdot p({x_j}|{\mu _i},{\Sigma _i})} \over {\sum\limits_{i 1}^k {{a_i}p({x_j}|{\mu _i},{\Sigma _i})} }} γjii1∑kaip(xj∣μi,Σi)ai⋅p(xj∣μi,Σi)
第三步计算新的横型参数: μ i ′ ∑ j 1 m γ j i x j ∑ j 1 m γ j i Σ i ′ ∑ j 1 m γ j i ( x j − μ i ′ ) ( x j − μ i ′ ) T ∑ j 1 m γ j i α i ′ ∑ j 1 m γ j i m \begin{aligned} \boldsymbol{\mu}_i^{\prime} \frac{\sum_{j1}^m \gamma_{j i} x_j}{\sum_{j1}^m \gamma_{j i}} \\ \boldsymbol{\Sigma}_i^{\prime} \frac{\sum_{j1}^m \gamma_{j i}\left(x_j-\mu_i^{\prime}\right)\left(x_j-\mu_i^{\prime}\right)^{\mathrm{T}}}{\sum_{j1}^m \gamma_{j i}} \\ \alpha_i^{\prime} \frac{\sum_{j1}^m \gamma_{j i}}{m} \end{aligned} μi′Σi′αi′∑j1mγji∑j1mγjixj∑j1mγji∑j1mγji(xj−μi′)(xj−μi′)Tm∑j1mγji
第四步按照新的模型参数重复23步直到满足停止条件
第五步将每个样本按照入 λ j arg max i ∈ ( 1 , 2 , . . . , k ) γ j i {\lambda _j} \mathop {\arg \max }\limits_{i \in (1,2,...,k)} {\gamma _{ji}} λji∈(1,2,...,k)argmaxγji, 划入对应的簇。即对每个样本来自哪个分模型的概率大就划入哪个分模型的簇中最终就得到了k个聚类
总结
分层聚类擅长于发现数据中的嵌入式结构。基于密度的方法在寻找具有相似密度的未知数量的聚类方面表现优异。K-means考虑在整个数据集中找到共识”K-means考虑数据集中的每个点并使用该信息在一系列迭代中进化聚类。高斯混合模型考虑重合数据的聚类。
2.性能度量
什么是好的聚类?
目的∶1评估聚类结果的好坏②确立优化的目标
结论︰簇内的样本尺度尽可能彼此相似簇间的样本尽可能不同。
外部指标∶将聚类结果与某个参考模型进行比较称为外部指标”。 a ∣ S S ∣ , S S { ( x i , x j ) ∣ λ i λ j , λ i ∗ λ j ∗ , i j ) } , b ∣ S D ∣ , S D { ( x i , x j ) ∣ λ i λ j , λ i ∗ ≠ λ j ∗ , i j ) } , c ∣ D S ∣ , D S { ( x i , x j ) ∣ λ i ≠ λ j , λ i ∗ λ j ∗ , i j ) } , d ∣ D D ∣ , D D { ( x i , x j ) ∣ λ i ≠ λ j , λ i ∗ ≠ λ j ∗ , i j ) } , \begin{aligned} \left.a|S S|, \quad S S\left\{\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) \mid \lambda_i\lambda_j, \lambda_i^*\lambda_j^*, ij\right)\right\}, \\ \left.b|S D|, \quad S D\left\{\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) \mid \lambda_i\lambda_j, \lambda_i^* \neq \lambda_j^*, ij\right)\right\}, \\ \left.c|D S|, \quad D S\left\{\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) \mid \lambda_i \neq \lambda_j, \lambda_i^*\lambda_j^*, ij\right)\right\}, \\ \left.d|D D|, \quad D D\left\{\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) \mid \lambda_i \neq \lambda_j, \lambda_i^* \neq \lambda_j^*, ij\right)\right\}, \\ \end{aligned} a∣SS∣,SS{(xi,xj)∣λiλj,λi∗λj∗,ij)},b∣SD∣,SD{(xi,xj)∣λiλj,λi∗λj∗,ij)},c∣DS∣,DS{(xi,xj)∣λiλj,λi∗λj∗,ij)},d∣DD∣,DD{(xi,xj)∣λiλj,λi∗λj∗,ij)},
