通过在数据点之间传递消息进行聚类外文翻译资料

 2022-04-26 10:04

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

Clustering by Passing Messages Between Data Points

通过在数据点之间传递消息进行聚类

(Brendan J.Frey* and Delbert Dueck)

摘要：在处理感知信号和检测数据中的模式中，通过识别代表性示例的子集来对数据进行聚类是十分重要的。这种“聚类中心”可以通过随机选择数据点的初始子集，然后迭代地改进它来找到，但是只有当最初的选择接近良好的解决方案时，这才起作用。我们设计了一种称为“affinity propagation”（ 仿射传播/亲和传播）的方法，该方法将数据点对之间的相似度作为输入量度。数据之间交换实值消息，直到一个高质量“聚类中心”的集合和其对应的簇逐渐产生。我们使用仿射传播对脸部图像进行聚类，检测微阵列数据中的基因，识别本手稿中的代表性句子，并确定航空公司有效访问的城市。 亲和力传播发现聚类的误差比其他方法低得多，并且花费不到百分之一的时间（与其他方法比较）。

正文：

基于测量相似度的聚类在科学的数学分析和工程系统都是关键的一步。一个共同的做法就是用数据去获得一组中心，这样数据点和它最近的中心之间的平方差是很小的。当聚类中心从实际数据点中被选出，它们就被称为“exemplars”。流行的K-centers聚类技术是随机地选择一组中心点作为exemplars进行初始化，并且迭代地提取聚类中心来减少平方差总和。簇中心点的初始化对K-centers 聚类算法是很重要的，所以为了找到一个好的聚类方案常常要返回去重新初始化多次。然而，只有当簇的数量少的时候它的聚类效果才会很好并且很可能一次随意的初始化就可以得到一个近乎好的聚类方案。我们采取了一个极其不同的方案并且介绍一个同时考虑将所有数据点作为潜在的簇中心的方法。通过将每个数据点视为一个网络节点，我们设计一个方法--沿着网络边缘，递归地传输实数值的信息直到出现一组好的簇中心和产生相应的集群。正如之后的描述，信息都会基于寻找一个适合的选择能量函数的最小值的简单公式被更新。在任何时间点，每个信息的大小反映了当前一个数据点选择另一个数据点作为它的簇中心的亲和度，所以我们把我们的算法称为亲和度传播算法（affinity propagation）。（figure1,A）举例说明了在信息传递的过程中簇是怎样渐渐产生的。

AP看作输入一批数据点间的实数值的相似度，相似度s(i,k)用实数表明点k多么适合作为数据点i的聚类中心。当目标是去最小化平方差，每个相似度都被设置成一个负平方差（欧式距离的负数）：对于点和 , 。事实上，当最优化标准更一般时，这里描述的算法是可以被应用的。后来，我们描述的任务是相似度从多对的图像、多对微矩阵测量、多个英语句子，多个城市中产生。

当得到一个依赖于簇中心的概率模型时，s(i,k)会被设置成点i的簇中心是点k的 log-likelihood。（对数似然，对数似然估计函数值一般取负值，实际值（不是绝对值）越大越好。第一，基本推理。对于似然函数，如果是离散分布，最后得到的数值直接就是概率，取值区间为0-1，对数化之后的值就是负数了；如果是连续变量，因为概率密度函数的取值区间并不局限于0-1，所以最后得到的似然函数值不是概率而只是概率密度函数值，这样对数化之后的正负就不确定了。第二，Eviews的计算公式解释。公式值的大小关键取之于残差平方和（以及样本容量），只有当残差平方和与样本容量的比之很小时，括号内的值才可能为负，从而公式值为正，这时说明参数拟合效度很高；反之公式值为负，但其绝对值越小表示残差平方和越小，因而参数拟合效度越高。或者，可以手动输入合适的相似度。AP看作输入一个实数s(k,k)给每个点k,这样数据点的s(k,k)值越大，它就越可能被选作簇中心。这些值（s（k,k））被称为“preferences'。所定义的簇中心的数量是由输入的preference参数所影响的，但也从消息传递的过程中产生。有一个先验（先于经验的，但为构成经验所不可或缺的）--所有的点都同等地适合作为簇中心，起初preferences应该设置为一个共同的值--能够通过改变这个值去产生不同个数的簇。共同的值可以是输入相似度的中心值(median)(结果产生簇的数量较适合)，或者是输入相似度的最小值（结果产生簇的数量少）。数据点之间有两种消息交换并且每个消息交换都考虑了不同的种类的竞争。在任何阶段，消息都与决定哪个点作为簇中心相关联，并且对于每个其他的点它都属于某个簇中心。' responsibility' r(i,k),从点i传递消息到候选的簇中心点k,反映点k是多么适合作为点i的簇中心的累积证据，考虑了点i的别的潜在簇中心（Figure1，B）。“availability” a(i,k),从候选簇中心点k传递消息到点i,反映了点k多么适合被点i选择作为它的簇中心的累积证据，考虑了除点i外别的点对点k作为簇中心的支持（Figure1,C）。r(i,k)和a(i,k)被视为log-probability ratios（对数机率）。首先，availabilities被初始化为0,a(i,k)=0。然后用下面规则计算出

第一次迭代时，因为availabilities是0，r(i,k)被设置成输入的点i，k之间的相似度作为它的exemplar,减去点i和其他候选聚类中心之间的最大相似度。这个竞争更新是数据驱动的并且不考虑有多少其他的点支持每个候选聚类中心。在后面的迭代中，由下面的更新规则规定，当一些点被有效地分配给其他聚类中心，他们的availabilities将会降到零下。这些负的availabilities会减小上面规则中的一些输入相似度s(i,k′) 的有效值，从竞争中去掉相应的候选聚类中心。由于k=i,responsibilities r(k,k)被设置成k被选作为聚类中心的输入的preference（s(k,k)）减去点i和其他所有候选聚类中心的最大相似度。这个'self-responsibility'基于输入合适的preference，通过表明k多么不合适分配给另一个聚类中心，来反映k是一个聚类中心的累积证据。鉴于上面的responsibility的更新让所有的候选簇中心竞争数据点的控制权，下面的availibility更新从数据点积累关于是否每个候选聚类中心都会是一个好的聚类中心的证据。

availability a(i,k)被设置成self-responsibility r(k,k)加上从其他点获得的正responsibilities候选聚类中心k的总和。只有正responsibilities部分是会被添加进来的，因为对于一个好的聚类中心正responsibilities是必要的。不管负的responsibilities多么不适合的程度。如果self-responsibility r(k,k)是负的（表明点k目前更适合作为另一个簇中心点的归属点比作为一个簇中心点）。如果一些其他点支持点k作为它们的簇中心，k作为一个簇中心点的availibility能够增加。

为了限制得到的正responsibilities的强烈影响，这个总和是被限定的，它不能大于0.”self-availability”a(k,k)的更新是不一样的：

基于正responsibilities从其他点传递给候选聚类中心，这个信息反映了点k是一个聚类中心的积累证据。

以上更新规律要求是最简单的，本地计算机很容易实现，并且消息只需要在已知的相似度的点之间交换。在AP算法实现的过程中任何点的availabilities和responsibilities都与定义聚类中心相关联。对于点i，a(i,k) r(i,k)取最大值时的k值，如果k=i时，确定点i作为一个聚类中心，否则确定数据点k是点id聚类中心。超过一个固定的迭代次数或消息的变化小于一个阈值或本地决定对一些迭代数量保持不变时，消息的传递过程将会被终止。当更新消息时，它们被阻尼去避免出现在某些情况下的数据振荡是重要的。每个消息被设置为先前迭代里它的值的l倍加上它规定的更新值的（1- l）倍，且阻尼系数l的值在0和1之间。在我们所有的实验里，我们用一个缺省的阻尼系数l=0.5，并且每个AP迭代都由更新所有被给了availabilities的responsibilities，更新所有被给了responsibilities的availabilities以及结合availibilities和responsibilities去监视聚类中心的决定和当这些决定不再改变时终止算法。

Figure1A展示了AP应用于25个两维数据点的运动过程，用负平方差作为相似度。AP的一个优点是聚类中心的数量不用预先指定。反而，合适的聚类中心的数量从信息传递方法中产生并且取决于聚类中心参数（preference）。这能够自动化模型选择是基于前面的对每个点如何作为聚类中心才合适的描述。Figure1D展示了输入的共同的preference的值对产生簇的数目的影响。这个关系几乎和通过精确地最小化平方差去发现的关系是一样的。

AP如何工作。

（A）AP用于说明二维数据点，其中负数欧几里德距离（平方误差）是用来衡量相似度。每个点都是根据目前的证据进行着色它是一个集群中心（示例）。该从点i开始的箭头的黑暗到点k对应的强度传送的消息指出我属于示范点k。

（B）r（i，k）从数据点发送到候选人的范例，并指出如何每个数据点强烈支持其他候选点的范例。

（C）发送a（i，k）从候选范例到数据点并指出每个候选范例在什么程度上可用作数据点的集群中心。

（D）输入偏好的值的影响（对于所有数据点通用）显示了所识别样本的数量（群集量）。

（A）中使用的值也显示出来，这是从成对相似性的中位数计算。

然后, 利用平方误差标准优化判据, 研究了面簇图像的聚类问题。我们利用亲和传播和 k 中心聚类来识别从 Olivetti 面数据库 (3) 提取的900灰度图像中的样本。亲和传播发现样本的平方误差远低于 k 中心聚类的 100runs (图 2A), 它的计算机时间大约相同。我们问, k 中心聚类的大量随机重启是否能达到相同的平方误差。图2B 显示了一组亲和传播所实现的错误, 以及 k 中心聚类的10,000runs 所实现的错误分布, 并对簇数进行了绘制。在两个以上数量级的时间内, 亲和传播均匀地实现了更低的误差。另一个流行的优化准则是绝对像素差异 (更好地容忍外围像素强度) 的总和, 因此我们使用此错误度量重复上述过程。亲和传播再均匀地达到了较低的误差 (图 2C)。

许多任务要求在稀疏相关数据中标识样本, 即大多数相似性未知或较大且为负数。为了检验这种情况下的亲和传播, 我们用微阵列数据中的稀疏相似矩阵和报告 (4) 来讨论聚类假定外显子查找基因的任务。在这项工作中, 75066 段 DNA (60 基长) 对应于假定的外显子是从基因组的老鼠染色体1。他们的转录水平被测量了12个组织样本, 和每对假定的外显子 (数据点) 的相似度计算。所假定的外显子之间的相似性度量是基于它们在基因组中的接近度以及它们在12组织中转录水平的协调程度。为了解释非外显子的假定外显子 (例如, 内含子), 我们包括了一个额外的人工样本, 并通过对整个数据集所做的统计数据, 确定了彼此之间的相似性。产生的 75067 x 75,067similarity 矩阵 (3) 由99.73% 个相似度组成, 其值为.infin;, 对应于不可能是同一基因的一部分的遥远的脱氧核糖核酸片段。我们将亲和传播应用于这个相似矩阵, 但因为如果 s (i、k) =., 则不需要在点 i 和 k 之间交换消息.infin;, 每个关联传播的迭代都需要在数据点对的小子集 (0.27% 或 15million) 之间交换消息.

图3A 说明了基因簇的识别, 以及将一些数据点分配给非外显子范例。在图3B 中比较了亲和传播和 k 中心聚类的重建误差。对于每个簇的数量, 亲和传播运行一次, 并采取6分钟, 其中询问中心群集运行1万次, 花了208小时。为了解决这些方法在检测善意基因片段方面的表现, 图3C 使用 RefSeq 数据库中提供的标签, 将真实正 (TP) 速率与假阳性 (FP) 率进行绘制。亲和性传播显著提高 TP 率, 特别是在低 FP 率, 这是最重要的生物学家。在 FP 率为3% 的情况下, 亲和性传播达到了 TP 率的 39%, 而最佳 k 中心聚类结果为17%。比较而言, 在相同的 FP 率下, 分层集聚聚类 (2) 的最佳 TP 率为 19%, 而在 (4) 中描述的工程工具则达到了43% 的 TP 率。

亲和传播在非标准优化标准的基础上进行操作的能力使得它适合于使用异常的相似性度量方法进行探查数据分析。与度量空间聚类技术 (如 k 表示聚类 (1)) 不同, 亲和传播可以应用于数据不位于连续空间的问题。事实上, 它可以适用于那些相似性不对称的问题 [即, s (i、k) ne; s (k, i)] 以及相似性不满足三角形不等式的问题 [即 s (i、k) lt; s (i、j) s (j、k)]。为了在总结其他句子的手稿草稿中找出少量的句子, 我们把每句话当作一个 '单词袋' (6), 并根据句子中单词的编码成本计算句子 i 的相似性。s 在句子 k。我们发现, 产生的相似性 (2, 3) 的97% 是不对称的。对偏好进行了调整, 以识别 (使用 l = 0.8) 不同数量的代表性范例句 (2), 四句的解决方案如图4A 所示.

我们还应用了亲和传播来探讨在估计的商业航空公司旅行时间方面, 确定受限制的加拿大和美国城市的数量, 这一问题最容易被其他城市的大子集所访问。每个数据点都是一个城市, 相似的 (i, k) 被设置为从城市 i 到城市 k 乘航空公司旅行所需的负时间, 包括估计中途延误 (3)。由于逆风, 运输时间在

全文共10276字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[13280]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章