*癌症特征的K-均值和聚类模型

第3节我们讨论了i）我们使用的癌症基因组数据，ii）我们对*K-均值的应用，以及iii）我们的实证结果的解释。第4节包含一些总结，包括对*K-均值在定量金融中的潜在应用的讨论，其中我们概述了*K-均值可能有用的一些具体问题。附录A包含*K-means和集群模型的R源代码。2聚类模型本文的主要目的是介绍一种利用聚类方法识别癌症特征的新方法。事实上，正如我们下面详细讨论的，我们的方法不仅仅是集群。事实上，从get-Got可以明显看出，盲目使用非确定性聚类算法（通常会产生（难以管理的）大量局部最优解）会给最终的癌症特征带来很大的变化。另一方面，确定性算法（如凝聚层次聚类）通常（实质上）较慢，并且需要基本上“猜测”初始聚类，这在实际应用中往往是次优的。因此，为了激励和解释我们采用聚类方法的新方法，我们首先可以说“分解”了NMF方法，并认为它实际上是一种伪装的聚类方法！2.1“分解”NMF当前的“lore”-从发生计数矩阵Gis（见上文）[Alexandrov等人，2013a]中提取K癌症特征的普遍接受的方法-是通过非负矩阵分解（NMF）[Paatero和Tapper，1994年]，[Lee和Seung，1999年]。在NMF下，矩阵G通过G近似≈ W H，其中W是权重的N×K矩阵，Has是曝光的K×d矩阵，Wand H均为非负。

然而，签名K的数量不仅不是NMF（必须猜测或通过试错获得），NMF也是一种非确定性算法，通常会产生大量的局部最优解。因此，在实践中，人们别无选择，只能执行大量的NSF运行（我们称之为抽样），然后以某种方式从这些抽样中提取癌症特征。在没有猜测K应该是什么的情况下，对K的一系列值（比如Kmin）执行nssamplings≤ K≤ Kmax，其中Kmin和Kmax基本上是基于一些合理的直觉考虑进行猜测的），对于每个K提取扫描者签名（见下文），然后选择K和具有最佳总体特征的对应签名到基础矩阵G中。对于给定的K，不同的采样通常产生不同的权重矩阵W。所以，要为K的每个值提取一个矩阵w，就要对样本进行平均。然而，在平均之前，必须在不同样本中匹配K癌症特征——事实上，在agiven样本X中，矩阵WiAare中的列不一定与K均值对齐【Steinhaus，1957】，【Lloyd，1957】，【Forgy，1965】，【MacQueen，1967】，【Hartigan，1975】，【Hartigan and Wong，1979】，【Lloyd，1982】。正如我们下面讨论的，在这方面，NMF没有什么不同。E、 g.、SLINK【Sibson，1973】等（例如，参见【Murtagh and Contreras，2011】、【Kakushadze and Yu，2016c】以及其中的参考文献）。E、 例如，将数据拆分为两个初始集群。例如，定量交易，可以客观衡量样本外的绩效。经验证据表明，只要深思熟虑地使用非确定性算法，这种确定性算法的性能就会不佳【Kakushadze和Yu，2016c】。矩阵中的列为不同的采样Y。

为了在NSSampling中对齐矩阵W中的列，once经常使用聚类算法，如k-means。然而，由于k-means是不确定的，因此Wcolumns的这种对齐不能保证——事实上也不能——产生唯一的答案。在这里，可以尝试对该对齐运行多个k-means采样并将其聚合，尽管这种聚合本身需要另一个级别的对齐（使用其自身的不确定性聚类，如k-means）。一个人可以做到这一点。在实践中，必须在某种程度上打破这条链，即通过随机（基本上通过启发式观察有效稳定性和“收敛”）或通过使用确定性算法（见fn.16）。不管怎样，所有这些总是（公开或隐蔽地）在结果癌症特征中引入系统性和统计性错误，如果不援引某种经验生物学“经验”或“直觉”，通常不清楚它们是否有意义（通常基于众所周知的影响，例如，暴露于各种众所周知的致癌物，如astobacco、紫外线辐射、氟碳毒素等）。归根结底，这一切归结于提取癌症特征的最终方法的有用性或预测性，包括特征的稳定性。对于NMF，答案一点也不明显。。。2.2变相聚类？因此，在实践中，NMF已经使用了聚类方法。然而，它比这更深。虽然NMF一般不会为给定签名产生消失权重，但有些权重（远）比其他权重小。E、 g.，oftenone有几个重量集中度高的“峰”，其余的变异类别的重量相对较低。事实上，许多权重甚至可以在（统计加系统）误差条内。在所有实际用途中，这种权重都可以设置为零。

事实上，我们可以更进一步，问问低体重的增加是否增加了解释力。解决此问题的一种方法是运行NMF，并附加一个约束，即权重（通过平均值获得–见上文）应高于i）相应误差的某些倍数或ii）一些预设的最小权重。这听起来当然合理，那么为什么在实践中不这样做呢？一个平淡无奇的答案似乎是，这将使已经非常重要的NMF算法更加复杂，需要额外的编码和计算资源等。然而，arguendo，让我们假设我们需要，比如说，权重高于预设的最小权重wminorelse权重设置为零。随着wmin的增加，修改后的NMF将产生越来越多的零。这并不意味着生成的矩阵WiAWe应该指出，在某种程度上，可以使用确定性（例如，凝聚层次-见上文）聚类算法来终止恶意循环，假设数据中有足够的稳定性，这是一种合理的方法。然而，这给结果签名增加了一个（n通常难以量化，因此是隐藏的）系统错误。而且这种误差条在流行的文献中很少出现。。。这需要一个高度递归的算法。将具有二元簇结构，即WiA=wiδG（i），a，其中δABis aKronecker delta和G：{1，…，N}7→ {1，…，K}是从N=96个突变类别到K个簇的映射。换句话说，这并不意味着在给定i（即突变类别）的结果矩阵wiafo中，对于a（即签名）的一个且仅一个值，我们会有一个非零元素。

然而，随着我们逐渐增加wmin，通常情况下，矩阵WiAis看起来越来越像一元簇结构，尽管有一些“重叠”的特征（即，在给定的一对特征中，一个或多个突变的权重为非零）。我们可以通过多种方式实现二进制结构。因此，一个基本的算法是取矩阵WiA（通过非零wmin在矩阵中实现一些零之前或之后同样成功），对于给定的值i，将所有权重WiAto设置为零，但签名a中的WiA=max（WiA | a=1，…，K）除外。请注意，这可能会导致一些空签名（簇），即对于i的所有值，WiA=0的签名。这可以通过i）以太简单地将此类签名删除到最后，并在最后具有更少的K<K签名（二进制簇）来解决，或者ii）增强算法以避免空簇，这可以通过以下几种方法来实现，我们在这里将不深入讨论。归根结底，NMF本质上可以通过合理的修改，包括去除无处不在且信息量不大的低权重，使其成为一种聚类算法。然而，缺点是更人为的算法，所以这不是我们在这里建议的。相反，我们观察到聚类已经在NMF中交织在一起，问题是我们是否可以通过直接使用聚类方法来简化事情。2.3让集群愉快地工作，答案是肯定的。我们不仅可以有更简单、更稳定的聚类算法，而且它们的计算成本也比NMF低得多。如上所述，使用流行的非确定性聚类算法（如k-Means）的最大问题是，它们会产生大量的局部最优解。

为了在本文的其余部分更加明确，我们将重点关注k-means，尽管本文描述的方法是通用的，并且可以应用于其他此类算法。幸运的是，在【Kakushadzeand Yu，2016c】中，在构建用于定量交易的统计行业分类（即股票聚类模型）的背景下，已经解决了这个问题，因此，我们仅从中借鉴，并进一步扩展和调整该方法以应对癌症特征。2.3.1 K-meansA流行的聚类算法是K-means【Steinhaus，1957】【Lloyd，1957】【Forgy，1965】【MacQueen，1967】【Hartigan，1975】【Hartigan and Wong，1979】【Lloyd，1982】。k-均值背后的基本思想是将N个观测值划分为k个簇，使每个观测值都属于具有最近均值的簇。基于上述原因，每种NWhich都优于确定性NWhich。观测值实际上是一个d向量，所以我们有一个N×d矩阵Xis，i=1，N，s=1，d、 设K簇，Ca={i | i∈ Ca}，a=1，K、 则K表示尝试最小化eg=KXa=1Xi∈CadXs=1（Xis- Yas）（1）其中Yas=纳西族∈CaXis（2）是簇中心（即横截面平均数），na=| Ca |是簇Ca中的元素数。在（1）中，“贴近度”的度量被选择为Rd中点之间的欧几里德距离，尽管其他度量是可能的。k-means的一个“缺点”是它不是一个确定性算法。一般来说，g在（1）中存在大量的局部极小值，该算法只保证收敛到局部极小值，而不是全局极小值。作为一种迭代算法，除非预设了初始中心，否则k-means从初始迭代的一组随机中心Yas开始，并在每次运行中收敛到不同的局部最小值。

这里没有灵丹妙药：在实际应用中，通常尝试“猜测”初始中心并不比“猜测”全局最小值所在的位置更容易。那么，一个人该怎么办呢？一种可能是简单地接受这样一个事实，即每次跑步都会产生不同的答案。事实上，这在许多应用中都是可以接受的。然而，在提取癌症特征的背景下，这将导致徒劳无功。我们需要一种方法来消除或大大减少不确定性。2.3.2聚合集群这个想法很简单。如果我们将多次运行的不同聚类（我们称之为抽样）聚合为一个，会怎么样？问题是怎么做。假设我们有mrun（M 1） 。每次运行都会生成一个包含K个群集的群集。允许Ohmria=δGr（i），a，i=1，N、 a=1，K（此处Gr：{1，…，N}7→ {1，…，K}是突变类别和簇之间的映射，是每个运行的二进制矩阵，用r=1，M、 对于我们来说，这是一种对相应聚类信息进行编码的便捷方法；因此OhmRIA仅包含一个等于1的元素（其他元素为零），Nra=PNi=1Ohmria（即列和）是属于a标记的簇的突变数（注意PKA=1Nra=N）。在这里，我们假设我们知道如何从每次运行中正确排序（即对齐）K个集群。这是一个偏心假设，我们稍后会回到这里。然而，假设我们知道如何做到这一点，我们可以聚合二进制矩阵，下面我们将讨论癌症特征的xis应该是什么。在本文中，“横截面”指的是“超过指数i”。注意这里的上标rOhmria、Gr（i）和Nra（见下文）是一个指数，而不是幂。Ohmriainto单个矩阵Ohmia=PMr=1Ohmria。

现在，这个矩阵看起来不像二进制聚类矩阵。相反，它是一个发生计数矩阵，也就是说，它表明在M个采样过程中，给定的突变多次分配给给定的簇。我们需要构建一个图G，这样每个K簇都只有一个突变。最简单的标准是将给定的突变映射到OhmIa为最大值，即所述突变最频繁发生的位置。需要注意的是，这样的集群可能不止一个。解决这种模糊性的一个简单标准是将所述突变分配给累积发生次数最多的聚类（即，我们将所述突变分配给最大值为PNi=1e的聚类Ohmia）。此外，在不太可能出现的情况下，仍然存在歧义，我们可以尝试做更复杂的事情，或者我们可以简单地将这种突变分配给指数a值最低的集群——通常，系统中存在大量噪音，停留在这样的细节点上根本不起作用。然而，我们仍然需要解决一个松散的问题，也就是说，我们的假设是，来自不同运行的聚类在某种程度上是一致的。实际上，每次运行都会产生sk集群，但i）它们不是相同的集群，没有简单的方法来映射它们，尤其是当我们有大量的运行时；和ii）即使集群相同或相似，它们也不会被排序，即一次运行的集群的顺序通常与另一次运行的集群的顺序不同。因此，我们需要一种从不同样本中“匹配”聚类的方法。同样，这里也没有什么灵丹妙药。我们可以做很多复杂而做作的事情，但最后却没有太多东西可以展示出来。一个简单实用的解决方案是使用方法将不同运行的集群对齐。每次运行标记为r=1，M、 除其他外，还产生了一组集群中心Yras。

我们可以将它们逐行“引导”到一个（KM）×d矩阵中，其中ea=a+（r- 1） K取值sea=1，（KM）。我们现在可以通过K-means将眼睛聚类为K个聚类。这将把ea的每个值映射到{1，…，K}，从而将K个集群从每个运行映射到{1，…，K}。这样，我们就可以对齐所有簇。“陷阱”是，无法保证每个M次运行的K个集群中的每个集群都将唯一映射到{1，…，K}中的一个值，即，我们可能在一天结束时有一些空集群。然而，这是确定的，我们可以简单地丢弃此类空簇并聚合（通过上述程序）数量较少的K<K簇。一、 最后，我们将使用Kclusters进行聚类，这可能会超过目标聚类数K。这不一定是坏事。丢弃的集群可能首先是多余的。另一个明显的“陷阱”是，即使产生的集群数量也不确定。如果我们多次运行该算法，我们将得到不同的K值。恶意循环？2.3.3修复“终极”群集不是真的！我们还可以使用另一个技巧来确定“最终”聚类，从而使我们的方法本质上具有确定性。上面的想法是聚集足够多的M个样本。每个聚合都会产生一个带有一些K≤ K个集群，这将从一个聚合切换到另一个聚合。然而，如果我们进行大量的聚合（每个聚合基于M个采样），会怎么样？通常情况下，我们会通过这种方式获得相对大量的差异集群。然而，假设数据具有一定程度的稳定性，这个数字远小于我们通过运行普通k均值算法获得的先验差异局部极小值的数量。

更好的是，聚集聚集的发生计数并不一致，但通常在少数（或可管理的）聚集聚集数量周围有（急剧）峰值分布。事实上，正如我们将在下面看到的，在我们的经验基因组数据中，我们能够精确定位“最终”聚类！所以，概括一下，我们在这里所做的就是这样。我们可以通过普通的k-means获得无数的聚类，但对于选择哪一个几乎没有指导。我们通过将大量此类集群聚合到我们的聚合集群中来减少这种扩散。然后，我们通过检查此类聚集聚类的出现次数，进一步放大到少数甚至唯一的聚类，我们认为这可能是“最终”聚类，最终得出的结果是具有（急剧）峰值分布。由于vanilla k-means是一种相对快速的收敛算法，因此每个聚合在计算上并不繁重，运行大量聚合比运行类似数量（甚至一小部分）的NMF计算更耗时（见下文）。2.4集群的内容？所以，现在我们知道了如何进行聚类，我们需要决定什么是聚类，即取什么作为我们的矩阵Xisin（1）。出于多种原因，naive choice Xis=Giissubo最优（如【Kakushadze和Yu，2016b】所述）。首先，矩阵GIS的元素由非负发生计数填充。具有大量样本的非负量倾向于具有高值长尾的偏斜分布。一、 例如，这种分布不是正态分布，但（在许多情况下）大致为对数正态分布。解决这个问题的一个简单方法是用Gis（而不是Gis本身）的（自然）对数来识别XI。一个小问题是Giscan的某些元素可以是0。我们可以做很多复杂甚至复杂的事情来处理这个问题。