页面树结构

2017-11-09 ApacheCN 开源组织,第二期邀请成员活动,一起走的更远 : http://www.apachecn.org/member/209.html


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始

可以使用模块执行双组分 sklearn.cluster.bicluster。双集群算法同时聚集数据矩阵的行和列。行和列的这些簇被称为双簇。每个确定具有一些所需属性的原始数据矩阵的子矩阵。

例如,给定一个矩形的形状,一个可能的三列和两列的双核心诱发一个子矩阵的形状:(10, 10)(3, 2)

>>> import numpy as np
>>> data = np.arange(100).reshape(10, 10)
>>> rows = np.array([0, 2, 3])[:, np.newaxis]
>>> columns = np.array([1, 2])
>>> data[rows, columns]
array([[ 1,  2],
       [21, 22],
       [31, 32]])

 

为了可视化的目的,给定一个双核,数据矩阵的行和列可以被重新排列,以使得双核连续。

算法在如何定义双核的方面有所不同。一些常见的类型包括:

  • 常数值,常量行或常量列
  • 异常高或低的值
  • 低方差的子矩阵
  • 相关的行或列

算法的不同之处在于可以将行和列分配给双簇,这导致不同的双簇结构。当行和列分成分区时,会发生块对角线或棋盘结构。

如果每行和每列都属于一个双核,则重新排列数据矩阵的行和列会显示对角线上的双核。这是一个这样一个结构的例子,其中biclusters具有比其他行和列更高的平均值:


通过划分行和列形成的二聚类的一个例子。

在棋盘案例中,每行都属于所有列集群,每列都属于所有行集群。这是一个这样一个结构的例子,其中每个双核的值的方差很小:


棋盘双核的一个例子。

在拟合模型之后,可以在属性rows_columns_属性中找到行和列集群成员资格。rows_[i]是一个二进制向量,其中非零条目对应于属于双核的行 i。同样,columns_[i]表示哪些列属于双核i

一些型号也有row_labels_column_labels_属性。这些模型分隔行和列,如块对角线和棋盘二叉结构。

 

注意:双聚类在不同领域有许多其他名称,包括协同聚类,双模式聚类,双向聚类,块聚类,耦合双向聚类等。一些算法的名称,如光谱共聚簇算法,反映这些备用名称。

光谱共聚集

SpectralCoclustering算法找到的值比相应的其他行和列中的值高。每列和每列属于一个双核,因此重新排列行和列以使分区连续显示沿对角线的这些高值:

 

注意:算法将输入数据矩阵视为二分图:矩阵的行和列对应于两组顶点,每个条目对应于行和列之间的边。该算法近似于该图的归一化切割以找到重的子图。

 

数学公式

可以通过图形的拉普拉斯算子的广义特征值分解来找到最佳归一化剪切的近似解。通常这将意味着直接使用拉普拉斯矩阵。如果原始数据矩阵一个具有形状,则对应的二分图的拉普拉斯矩阵具有形状。然而,在这种情况下,可以直接工作一个,这是更小更有效率的。

输入矩阵一个预处理如下:

具有条目的对角矩阵在哪里一世等于 并且C是具有入口Ĵ等于的对角矩阵

奇异值分解,提供行和列的分区一个。左奇异向量的一个子集给出行分区,右边奇异向量的子集给出列分区。

从第二个开始的奇异向量提供所需的分区信息。它们用于形成矩阵ž

哪些列ü,和类似的V

然后ž使用k-means聚类这些行。第一个n_rows标签提供行分区,其余n_columns标签提供列分区。

例子:

参考文献:

 

光谱双聚类

SpectralBiclustering算法假设输入数据矩阵具有隐藏的棋盘结构。具有该结构的矩阵的行和列可以被分区,使得行簇和列簇的笛卡尔乘积中的任何双聚类的条目近似恒定。例如,如果有两个行分区和三个列分区,则每行将属于三个双核,每列将属于两个双核。

该算法分割矩阵的行和列,使得相应的块式常数棋盘矩阵提供对原始矩阵的良好近似。

数学公式

首先对输入矩阵一个进行归一化,使棋盘图案更加明显。有三种可能的方法:

  1. 独立的行和列归一化,如光谱共聚集。这种方法使得行总和为常数,并且列与不同的常数相加。
  2. Bistochastization:重复行和列归一化直到收敛。该方法使得行和列之和相等于相同的常量。
  3. 日志归一化:计算数据矩阵的日志。然后列是什么意思,行平均 ,和整体平均大号计算。根据公式计算最终矩阵

归一化后,首先计算奇异矢量,就像光谱共聚类算法一样。

如果使用对数归一化,则所有奇异向量都是有意义的。然而,如果使用独立的正常化或bistochastization,第一奇异向量,U_1V_1。被丢弃 从现在起,“第一”奇异向量是指 除了在日志正常化的情况下。

给定这些奇异向量,它们被分级,根据其可以通过分段常数向量最好地近似。使用一维k-均值并使用欧几里德距离进行评分,发现每个向量的近似值。选择最佳左和右奇异矢量的一些子集。接下来,将数据投影到单个向量的最佳子集并进行聚类。

例如,如果p计算奇异矢量,则 q最好的是如所述,其中。让 ü列为q最佳左奇异向量的矩阵,V对于右边是类似的。要划分行,将行一个投影到q维空间: 米将该 矩阵的行作为采样和使用k-means的聚类处理产生行标签。类似地,将列投影到矩阵并使其聚类得到列标签。

例子:

参考文献:

 

双聚类评估

有两种评估双组分结果的方法:内部和外部。诸如群集稳定性等内部措施只依赖于数据和结果本身。目前在scikit-learn中没有内部的二集群措施。外部措施是指外部信息来源,例如真正的解决方案。当使用真实数据时,真正的解决方案通常是未知的,但是,由于真正的解决方案是已知的,因此人造数据的双重分析可能对于评估算法非常有用。

为了将一组已发现的双组分与一组真正的双组分进行比较,需要两个相似性度量:单个双色团体的相似性度量,以及将这些个体相似度结合到总分中的方法。

为了比较单个双核,已经采用了几种措施。现在,只有Jaccard索引被实现:

在哪里一个乙两个群集,是他们的交叉点的元素的数量。当双核不完全重叠时,Jaccard指数达到最小值,当它们相同时,其最大值为1。

已经开发了几种方法来比较两组双组分。现在只有consensus_score(Hochreiter et al。,2010):

  1. 使用Jaccard索引或类似措施,计算双组对数的双核相似性,每组一个。
  2. 以一对一的方式将双组分从一组分配给另一组,以最大化其相似性的总和。该步骤使用匈牙利算法执行。
  3. 相似性的最终总和除以较大集合的大小。

最小共识得分0发生在所有双核群体完全不相似时。当两组相同时,最大分数为1。

参考文献:

 

  • 无标签