非线性结构检测的生物启发算法及软件EPP-Lab

沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.comJournal of King Saud University使用探索性投影寻踪实验室（EPP-Lab）软件检测和可视化大型数据集中的非线性苏阿德·拉拉比沙特阿拉伯沙特国王大学计算机和信息科学学院信息技术系接收日期2015年6月5日;修订日期2016年3月28日;接受日期2016年4月18日2016年5月11日在线发布摘要本文包括使用生物启发的算法，以检测潜在的有趣的结构，在大型和多维数据集。数据探索和感兴趣的结构的检测是基于投影寻踪的使用，它涉及与每个方向或投影相关联的索引的定义和优化投影指数的优化应该提供一组多个最优值，期望这些最优值对应于低维空间中有趣的图形表示。生物启发算法与投影寻踪的实现开发了一个名为EPP-Lab的新软件。投影寻踪被广泛应用于不同的科学领域（生物学，药学，生物信息学，生物统计学等），但并不广泛存在于著名的软件。EPP-Lab是专门用于识别和可视化集群和离群观测一维高维和多元数据集。它包括用于结果分析的不同统计技术它提供了几个功能，并为用户提供了调整所选生物启发方法的参数或使用默认值的选项EPP-Lab是一款独特的软件，用于非线性结构的检测、该工具的性能已通过测试不同的真实和模拟数据集进行了验证。©2016作者。制作和主办：Elsevier B.V.代表沙特国王大学 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在计算机科学，特别是人工智能，Meta启发式是一种技术，旨在找到一个近似的解决方案，沙特国王大学负责同行审查制作和主办：Elsevier在合理的时间内解决困难和组合优化问题。元启发式方法包括自然启发的社会行为（粒子群优化，蚁群优化，蜂群，萤火虫等）或达尔文进化生物学（遗传算法，遗传编程，进化策略等）。他们中的大多数解决困难和组合问题（Sevkli等人，2014; Goswami和Mandal，2013; Upadhyay等人， 2014年）通过处理一组解决方案并保持多样化（解决方案空间的探索）和集约化（积累的知识的利用）之间的平衡。这项研究工作涉及http://dx.doi.org/10.1016/j.jksuci.2016.04.0031319-1578© 2016作者制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词探索性投影寻踪遗传算法;粒子群优化;部落;聚类;离群值大数据集中3¼ð Þ使用生物启发算法在大型多维数据集中发现潜在的有趣结构。从大维度数据中提取隐藏信息涉及采用探索性数据分析方法。Prin-UNR分量分析是一种已知的统计分析方法，其基于将数据投影到最大化观测分散的维度上。然而，使色散最大化并不总是导致感兴趣的结构的检测。在本研究中，投影寻踪（PP），探索性投影寻踪方法之一。它包括寻找高维多元数据的有趣的低维投影（Jones andSibson，1987; Huber，1985）。基于人类的可视化，低维意味着（一-二-三）维。PP专注于定义以及与每个方向或投影空间相关联的索引的优化。为了优化投影指数，应用精确优化方法（牛顿法、最陡爬坡法等）。这些方法需要大多数投影指数所不具备的规律性。另一方面，PP所需的主要特征是找到对应于不同有趣结构的多个最优解（Friedman，1987; Morton，1989;Sun，1993）。然而，这些精确的方法不能提供多个最优解。 因此，生物启发算法的使用令人鼓舞。它们不仅可以找到一个全局最优解（近似解），而且可以找到几个局部最优解（使用几次运行），对应于不同的潜在感兴趣的投影。在不同的生物启发式算法，遗传算法（GA），粒子群优化（PSO）和混合粒子群优化方法称为部落。Berro等人（2010年）和Mari-Sainte等人（2011年）已经验证了这些选定方法与PP结合的性能。（ 2010年）。本研究的重点是检测集群和离群观测。 聚类是数据挖掘的主要任务之一，并且主要在不同的领域中被要求（Alghamdi等人，2014; Aljumah等人， 2013年）。离群值检测涉及从数据中删除异常观测值（Hogge和Austin，2004）。由于机械故障、欺诈行为、人为错误、设备故障或群体中的自然偏差而它们的检测可以消除对数据集的污染影响。尽管PP已经在不同领域（生物学、生物信息学、图像处理、生物统计学等）中用于此目的，但其实现并不令人满意（Caussinus和Ruiz-Gazen，2009）。因此，在许多使用这种统计分析方法的科学学科中，拥有一个包含PP的软件已成为不可或缺的。在本文中，一维投影寻踪方法，包括五个投影指标，实现与选定的生物启发的方法，以获得一个强大的工具，称为探索性投影寻踪实验室（EPP-Lab）。EPP-Lab致力于在高维数据集中寻找隐藏的非线性结构，特别是聚类和离群观测。本软件是由统计学家共同设计的。它为用户提供了调整所实施的生物启发方法的参数或使用默认值的选项。此外，它还为结果的分析提供了新的途径。EPP-Lab是一个独特的聚类离群值检测、可视化和分析工具。为了验证该软件的性能，我们处理了几组真实数据和模拟数据，其中一些数据集的数据量较大，结构复杂。本文的其余部分组织如下。第二部分介绍了专业英语的基本概念和定义。第三节介绍了相关的工作。第4节讨论了所实施技术的方法学。第5节介绍了EPP-Lab及其主要功能。第6节说明了EPP-Lab的应用程序和结果，使用几个真实和模拟数据集来确定聚类和检测离群值，以及一小部分比较研究和收敛研究。第7节讨论了EPP-Lab的计算时间和局限性。最后第8节对本研究工作进行了总结。2. 投影寻踪PP方法寻求寻找低（一，二，三）维投影，提供潜在的有趣的结构隐藏在多维和大型数据集。“感兴趣“结构的概念该指数试图发现投影分布中存在的非线性结构的程度。用X：N×P表示N个病例和P个变量的数据集矩阵。设Xi是与第i个观测相关联的ffip中的第i个列向量本研究的重点是一维投影。投影向量可以从ffip到ffi定义为z Xa;a是定义线性变换的P维向量，并且z是对应于投影观测的坐标的N因此，确定投影等价于确定a。换句话说，这件事相当于优化了一个选定的投影指标。目前的工作集中在四个特定的一维指数。Friedman-Tukey指数（Friedman and Tukey，1974）是在EPP背景下提出 的 第 一 个 Friedman 峰 度 指 数 基 于 四 阶 矩 ， 并 已 在PenRena和Prieto（2001）和Achard等人（2004）中进行了研究我们还考虑了一种新的适合于检测聚类的方法，称为“判别指数“（Berro等人，2010年）。所有这些指标都定义良好，并应用于检测的集群和/或离群值在Berro等人。（2010）和Mari-Sainte et al. （2010年）。PP方法的一个重要特点是数据的球化。球化步骤通常应用于PP步骤之前的数据它包括消除数据集中的规模和层次结构，以便找到数据的其他方面。它还确保PP发现的任何结构与主成分分析发现的结构之间的差异该特性在EPP-Lab中实现。与PCA相比，PP的使用不太广泛，但在许多情况下比PCA更强大，因为PCA只考虑二阶矩，可能会错过其他EPP 技 术 很 容 易 发 现 的 有 趣 的 隐 藏 结 构 （ Jones 和Sibson，1987）。事实上，数据结构的重要方面可能不会出现在任何一个主要子空间中，如图1所示。假设整个维数大于2，直线平行于2维的子空间。PCA的第一个主平面，在这个例子中大致是水平轴，显然不能4S.L. 玛丽桑特图1EPP和PCA的例子。来揭示这两个星团。这些簇只能偶然出现在进一步的投影上，而离群值不能出现在任何主要的二维子空间上，只能通过投影在斜线上。3. 相关作品PP的优化程序已经由几位作者开发。Friedman和Tukey（1974）使用爬山优化方法优化了它们的投影指数。然而，由于“Hill clumbing“（Jones和Sibson，1987）的平坦性缺点，投影数据随投影方向平滑地变化。Friedman（1987）使用了最陡上升和拟牛顿优化方法;Morton，1989; Sun，1993）修改了Friedman算法。PenRena和Prieto（2001）提出使用两种优化方法：牛顿算法的修改版本和基于一阶最优性条件的优化方法。然而，他们表明，如果只计算一个方向的投影，那么一些集群可能会掩盖其他集群的存在。对于其他投影指数，例如Morton（1989）; Yenyukov（1989）;Nason（1992）; Posse（1995 a）; Posse（1995 b）提出的投影指数，他们建议的方法也基于梯度信息（最陡上升，共轭梯度方法等），而（Crawford，1991; Achard等人，2004）使用启发式优化方法。如上所述，PP方法的主要目标是检测和可视化与投影索引的不同局部最优值相关联的若干感兴趣的投影。大多数现有的PP优化算法不能找到一个以上的最优解。因此，已经提出了不同的替代方案来实现该目的。一种替代方案集中在连续正交子空间中的投影指数的优化，如PCA中（在PenPena和Prieto（2001）中使用）。实际上，在找到投影指数的最优值之后，在初始最优值的方向的正交子空间中重新优化该指数，等等。另一种称为结构移除的替代方法包括对数据应用转换，该转换移除解决方案（投影）中存在的结构，同时保留未被其捕获的多变量结构。然后将PP优化算法应用于这些转换后的数据，以找到可能产生进一步洞察的其他视图。然而，每次找到解决方案时都要执行数据的转换，这使得这种交替的时间消耗。这一观点首先由弗里德曼（Friedman，1987）提出，然后由莫顿（Morton，1989）和孙（Sun，1993）提出。PP用于解决实际问题，例如检测药物试验领域的异常值（Baker，1991）;生态学中的植被模式（Clements和Jones，1991年）;高光谱图像（Achard等人，2004;Malpika等人，2008），生物信息学（Faith和Brockway，2006）和生物识别（Ghodami和Larabi，2015）。因此，当注意到可用软件 的 数 量 很 少 时 ， 仍 然 需 要 开 发 这 样 的 方 法（Caussinus和Ruiz-Gazen，2009）Jones和Sibson（1987）提出了用Fortran语言编写的计算Friedman和Tukey（1974）的单变量和双变量改进指 数 的 程 序 。 Friedman （ 1987 ） 还 提 出 了 一 个 用Fortran编写的软件。Nason（1992）编写了一个Splus函数来计算他提出的三维指数所有这些程序都可以在Guy Nason关于PP的网站上找到孙佳阳还用Fortran和C实现了弗里德曼索引，她的程序可以作为S-Plus的库安装。该方法采用了最陡上升法和Friedman提出的结构去除法该软件被称为交互投影寻踪，可在他的网站上获得（参见Caussinus和Ruiz-Gazen（2009））。自2001 年 以 来 ， PP 技 术 也 出 现 在 Matlab 中 Martinez 和Martinez（2001）在Matlab中开发了一个计算统计工具箱，其中包含一些EPP程序。他们使用的指数被称为卡方指数，由Posse（1995 a，b）开发。通过随机搜索，Posse成功地确定了投影指数的全局最优值，并将其与Friedman（1987）的结构去除相结合，以获得一系列有趣的二维投影。已经开发了另一种称为自主投影映射（APM）的数据分析工具，用于分析来自半导体环境的数据（Rohatsch等人， 2006年）。它实现了几个指标，如Posse提出的一个和几个优化算法，如遗传算法。实现了几种结构去除方法：Friedman提出的结构去除方法和正交子空间上的投影方法.该接口是用Delphi编写的，但似乎不可用。所有上述实现都遵循基于迭代局部精确优化方法和结构去除步骤的通常策略。XGobi和Gogbi是用于高维数据可视化的交互式和动态软件系统，其中PP是动态实现的（Swayne等人，2003年）。GGobi是直接从XGobi衍生而来的。GGobi包含几个专门用于揭示不同结构的投影指数（聚类、离群值、空洞，.. . ）.初始值可以随机选择，也可以由查看点云旋转的用户选择。因此，该策略与其他实现中使用的策略不同优化算法搜索局部最优解，不需要去除结构然而，对于具有复杂结构的高维数据集，为了发现一些潜在的感兴趣的起始点而长时间观察旋转云可能是乏味的。我们注意到，现有为数不多的EPP实现并不完全令人满意。首先，大多数优化算法依赖于梯度信息，这意味着投影指数的正则性条件。其次，优化算法通常被调整为仅获得一个此外，结构去除可能会错过一些感兴趣的投影或/和也是耗时的。GGobi/XGobi提出了另一种策略，但如前所述，数据分析师必须在整个追踪过程中呆在计算机前大数据集中5¼¼该过程对于高维数据集也可能非常耗时。在本研究的下文中，讨论了一种不同的策略。我们提出了一个新的软件，包括算法，不依赖于规则性条件的指标，并提供不同的局部最优。这项研究工作是作者博士学位的一部分。论文4. 基于生物启发算法的投影寻踪算法PP依赖于投影索引和称为投影追踪算法的优化方法。这种优化算法应该是有效的和灵活的，在寻找全局和局部最优，易于揭示可能的有趣的投影在一个合理的时间。进化算法和生物启发算法在解决困难和组合优化问题中是众所周知的在这项工作中，遗传算法（GA），粒子群优化（PSO）和一个变种的粒子群优化称为部落。4.1. 遗传算法遗 传 算 法 （ Genetic Algorithms ， GA ） 是 由 Holland（1975）提出的一种受达尔文进化生物学启发的进化算法.遗传算法包括遗传、选择、变异和交叉。个体的群体是随机生成的，以覆盖搜索空间。这些个体必须以特定的编码（如二进制编码）表示。每个个体通过代表待优化的目标函数的适应度函数来评估。在每次迭代中，每个个体都被评估，并且可以被选择和修改（与可能的突变重组）以产生新的种群。这个新的种群将用于算法的下一次迭代。通常，一旦达到最大迭代次数，算法就结束。在这项研究中，我们集中在Fogel等人概述的论点。（1966）、Rechenberg（1973）、Schwefel（1981）和Holland（1975）。种群的初始化是随机进行的，种群的大小在实验部分中设置。每个个体都以实数编码，并表示第2节中定义的投影向量。适应度函数由第2节中提到的投影指数表示。为了选择个人，应用3个参赛者的锦标赛选择。然后，将pc0： 65的2点交叉应用于所有群体。在选择和交叉完成后，直接复制或通过交叉产生一个新的个体群体为了保证个体间的差异性，对pm0： 05的所有个体采用突变算子，即随机选择一个基因，并用一个随机实值替换它算法1总结了建议的GA版本。的窗口2指数、算法和参数选择。数据转换。图形和显示频率的选择收敛曲线.窗口1投影寻踪：模式与结构选择。数据集。或结果文件中的投影分析窗3离群值标准。输入数据。图形选择（直方图/内核密度）。指数、余弦和离群值图。使用选定部分数据的投影。图2 Epp-Lab软件的全球展示。6S.L. 玛丽桑特我的天算法1.遗传算法伪代码本研究中遗传算子参数的选择是基于一些实验。个体的数量和训练迭代的数量被选择为使得所达到的最优值不能被容易地改进（通过若干试验和实验）。这些参数取决于数据集和投影指数（Holland，1975）。4.2. 粒子群优化粒子群优化算法（Particle Swarm Optimization，PSO）是Kennedy和Eberhart（1995）提出的一种基于种群的随机优化算法，它的灵感来自于鸟群或鱼群的社会行为。粒子群算法与遗传算法的不同之处在于它没有交叉、变异等进化算子。在粒子群算法中，粒子群是由随机初始化的潜在解组成的每个粒子通过拟和函数进行评估以进行优化。群体的运动由粒子本身、最佳粒子（具有最佳性能的粒子）和速度来指导换句话说，在每次迭代中，每个粒子位置根据其迄今为止达到的最佳位置（称为pbest）来更新，群的最佳粒子的最佳位置（称为全局最佳，并表示为pbest）被更新。（注：gbest）和速度。此外，粒子的运动还可能受到其近邻粒子的影响，特别是最佳近邻粒子（称为局部最佳粒子，记为lbest）的影响。在这种情况下，粒子在搜索空间中移动到接近局部最佳的邻域集合中，并且不探索搜索空间的其余部分。邻域的定义取决于搜索目的。小的邻域导致较慢的收敛（到局部最佳），而大的邻域导致较快的收敛（到全局最佳）。与一个全局最佳，表示一个邻居组成的整个群体。此外，粒子群算法需要利用一些参数，他们的操纵可能会导致令人惊讶的变化，在系统粒子群算法需要使用最大速度参数（用Vmax表示）或惯性参数。Vmax是固定的，以避免粒子在搜索空间中从一个区域快速移动到另一个区域。此外，它还可以防止爆炸，并扩展粒子搜索的探索。惯性系数控制前一步中获得的速度的影响。大的惯性因子导致搜索空间的大探索，而小的惯性因子将搜索集中在小空间上。许多扩展已经被提出来改进PSO算法。本研究采用了Kennedy和Eberhart（1995）提出并由Clerc（2006）修改的原始版本。在该实现中，粒子表示P维的投影向量速度和粒子是随机初始化的。应用Vmax参数Vmaxprojection max projection min= 2和V minV max.适应度函数用投影指数和遗传算法表示。为了同时探索搜索空间的几个区域，找到局部最优解之前找到一个全局最优值，一个新的邻域版本称为余弦邻域。其思想是将群划分为若干组，使得同一组中的每个投影向量（粒子）之间的余弦角不应超过30度（更多细节参见Berro等人，2010年）。在每个组中，粒子都受到严格控制，并遵循其最佳位置（pbest）和其组的最佳位置（lbest）移动一旦所有的粒子位置都更新了，这个结构将通过创建新的组来更新。算法2总结了所提出的PSO。算法2.粒子群算法伪码大数据集中7算法3.Tribes伪代码4.3. 部落Tribes是Clerc（2006）提出的一种混合自由参数PSO方法。Tribes方法涉及一群称为Tribes的几个在每个部落中，粒子相互连接，以了解部落中最好的粒子（部落内通信）。部落之间的联系是为了做出一个全球性的决定（部落间的沟通）。这个结构可以通过粒子和部落的创造、进化和删除来发展和更新这种发展取决于通过适应度函数的评估确定的部落（好的或坏的）和粒子（好的或中性的）的质量的度量。与粒子群算法相反，粒子在搜索空间中的运动是基于超球概率分布的，可以是有噪声的，也可以是无噪声的，也可以是独立的高斯分布。这种配置允许同时探索几个有希望的领域，通常在做出全局决策之前围绕局部最优值。有 关 更 多 细 节 ， 读 者 可 以 参 考 Mari-Sainte 等 人（2010）和Clerc（2006）。该方法不需要确定参数，只需要定义粒子（投影向量）、适应度函数（投影指数）和迭代次数。算法3简要描述了整个方法。注意，position表示粒子的当前位置，pbest是粒子记忆的最佳位置，gbest是群的最佳粒子记忆的最佳位置表1意大利的石油产区和地区。区域意大利南部普利亚、卡拉布里亚和西西里撒丁岛撒丁岛意大利北部利古里亚和翁布里亚5. EPP-Lab的全球代表EPP-Lab是一个专门用于检测高维数据集中隐藏的非线性结构的软件。它是专为处理EPP通过使用生物启发优化算法。它包含三种优化方法（GA，PSO和Tribes）和五 个 投 影 指 标 （ Friedman ， FriedmanTukey ，Discriminant，Maximum和Minimum Kurtosis indices）。关于 投 射 指 数 的 更 多 细 节 ， 读 者 可 以 参 考 Berro 等 人（2010）、Ruiz-Gazen等人（2010）和Mari-Sainte等人（2010）。EPP-Lab的代码是用JAVA 6语言实现的，可在 （ https://www.researchgate.net/publication 或 DOI ：http://dx.doi.org/10.13140/RG.2.1.4522.2480）上获得。界面是图形和数字表示的组合。EPP-Lab包括三个主要窗口，每个窗口都有其主要作用，如图所示。二、EPP-Lab为用户提供投影追踪或投影分析的选项。在第一种情况下，用户可以选择“ m o d e “ （ 专 家 模 式 为用 户 提 供 了 广 泛 的 选 择 ， 半 自 动 模 式 仅 提 供 参数 的 选 择 ） ， 要 查 找 的 结 构 （ 聚 类 或 离 群 观测 ） ， 并 且 除 了 投 影 索 引 和 优 化 方 法 之 外 ， 还可 以 定 义 数 据 集 。它为用户提供了对数据进行球面化和设置参数的选项。在第二种情况下，EPP-Lab为用户提供了从结果文件显示投影分析的选项。该方法不需要经过投影寻踪和优化步骤，直接得到分析窗口。由于保存了结果文件，因此可以随时对其进行分析，以便可视化结果，这对于该应用程序来说是一个很大的优势。结果文件（以文本形式）包括关于输入的所有信息（例如创建文件的日期/时间、数据文件名、数据尺寸、所选投影索引、所应用的优化方法及其参数、迭代和运行次数）以及输出，例如投影索引的最佳值及其每次迭代和每次运行的相关解（提供的投影向量）。请注意，输入文件是一个文本文件，包含第2节中描述的数据集矩阵及其维度。通过图形显示优化过程后获得的有趣结构。该图形使用与投影索引的最优（或局部最优）相关联的投影数据的分布来寻址。它可以是核估计器或直方图。直方图图形构建如下。一旦数据被投影，我们设置投影数据的最小和最大坐标的整数值然后我们决定要切割的片段数量每个段的长度取决于该段中的元件的数量对于核估计器，我们使用等式中定义的三权重核（Klinke，1997（一）.8S.L. 玛丽桑特Ribes2ð× Þ35Kz3231-z化）（Berro等人，2010年）。因此，计算所选投影向量与其他投影向量之间的角度的余弦。如果余弦值接近1，则这些投影方向可能提供相同的感兴趣的结构。绘制余弦值以可视化两个投影方向的距离（角度）。此外，数据集的结构通常非常复杂，包含大量的类。通过使用一维EPP发现所有这些是具有挑战性的。EPP-Lab提供的一种可能性是通过将数据集分为两部分并分别分析每一部分来识别其他感兴趣的投影。该策略由Friedman（1987）发起，称为“隔离方法“，然后以不同的名称应用于各种研究，例如PPTree（Lee et al.，2013年）。本研究的第二个目标是异常值检测。EPP-其中，RX表示与集合相关联的虚拟变量X，z是投影数据的坐标。为了分析几个投影和理解数据的几个单变量表示之间的差异，研究了任意两个投影向量之间的投影索引值和角度的余弦根据投影指数的递减值对投影进行排序，并绘制指数值，以便容易检测到局部最优值我们还记得，EPP-Lab中包含的所有投影指数都是最大化的，除了用于搜索聚类的判别指数和峰度指数不失一般性，我们最大化负峰度和负判别指数。局部最优可以揭示不同的结构。然而，在某些情况下，不同的投影索引值可以对应于相同的结构。与两个投影向量相关联的两个线性组合之间的相关系数可以指示这两个投影方向是否产生相同的投影。该系数等于这两个投影向量之间的角度的余弦（假设数据是球形的并且投影向量是法向的）。实验室软件为实现这一目标提供了有效的途径我们提出了一个规则的基础上k-西格玛原则，涉及考虑一个观察离群，如果它的距离的平均值（预测数据）是大于k倍的标准偏差kr的预测数据。当k值增加时，离群值的数量减少。此参数由用户设置，我们建议至少设置为3。6. EPP-Lab应用和结果本节的目的是展示EPP-Lab在检测对应于以下情况的局部最优值方面的效率：to projects预测revealing揭示interesting有趣structure结构of the data数据sets集.为此，测试了五个数据集。数据集由具有N行（样本）和P列（变量或特征）的矩阵表示。采用五个投影指标，并使用三种优化方法进行优化。为了更好地可视化解决方案，为每个检测到的组分配颜色。LubischewMinkurtosisTribesLubischew最小峰度粒子群算法卢比肖·弗里德曼部落LubischewFriedmanPSOLubischew歧视部落Lubischew判别粒子群算法LubischewMinkurtosisTribesLubischew最小峰度粒子群算法卢比肖·弗里德曼不LubischewFriedmanPSOLubischew歧视部落Lubischew判别粒子群算法图3Lubischew示例：排名指数的图（左图）和每个投影向量与“ 最 佳 “ 投 影 向 量 的 关 联 余 弦 （ 右 图 ） ， 使 用T r i b e s （ 每 个 图 的 左 侧 ） 和 P S O （ 每 个 图 的 右 侧 ） 用 于 最 小 峰 度 （ 顶 部 曲 线 ） ， F r i e d m a n （ 中 间曲 线 ） 和 判 别 指 数 （ 底 部 曲 线 ） 。表2遗传算法和粒子群算法的参数。方法参数小数据集：大型数据集：卢比绍橄榄，可靠性&模拟GA个人50100迭代2050PSO颗粒2050迭代50100健身10005000评价大数据集中9¼¼¼¼不不不不ðÞ不不不不不- --561728最佳选择选择最佳Lubischewopt83 MinKurtosis部落LubischewMinkurtosisTribes最佳Lubischew opt 76Friedman部落卢比肖·弗里德曼部落最佳Lubischewopt70判别式部落Lubischew歧视部落图4Lubischew示例：“最佳“投影（左）和第二”最佳“投影（右）上的投影数据分布的直方图，其中Tribes用于最小峰度（顶部图），Friedman（中间图）和判别指数（底部图）。图5 Olive数据：使用Tribes的峰度指数的全局最优值（左图）和局部最优值（中图和右图）对应的直方图。6.1. 数据集Lubischew：由N74昆虫和P6形态测量（Lubischew，1969）组成，分为3个类群.第一个（分别为第二个和第 三 个 ） 包 含 观 察 1 至 21 （ 分 别 为 22 至 43 和 44 至74）。该数据文件已经在EPP的背景下进行了研究（ 参 见 Friedman 和 Tukey ， 1974; Caussinus 和 Ruiz-Gazen，2009）。橄榄数据：由在N1/4572意大利橄榄的脂质级分中发现的P=8脂肪酸的百分比组成组成模拟数据集：我们生成了两个数据集的N1000观察和P5变量。观测值根据正态分布的各种混合分布进行分布，定义如下：Normal4：包含四个聚类，每个聚类包含250个高斯观测值分布N5li;I5with1;. . . （四）其中l 11 1/4 0;.. . ;000;l2 1/4 10; 0;.. . ;000; l3 1/4; 10; 0; 0; 000; l4 1/40; 0; 10; 0; 0是5维向量。Normal 10：包含10个聚类，每个聚类包含100个观测值，具有高斯分布N5li; I5，i1/41;. 。 . ; 10，其中l1 1/4 =0;. . ;000; l2 1/4 10; 0;.. . ;000; 1300; 10;... ;000; l4 ¼油. 这572个样本来自意大利3个不同的地区（意大利南部、撒丁岛、意大利北部）又细分为6个地区，如表1所示。数据集的结构非常复杂，有6个簇（见表1），它们在六维空间中具有不同的形状。00; 0; 10; 0; 000，l/400;... ; 0; 1000; l ¼-l; l ¼-l; l ¼l3; l9l4，l10l5 是5维向量。可靠性数据：是根据保密协议从行业获得的真实数据集。它由996项高科技10S.L. 玛丽桑特GA正常4PSO正常4部落正常4GA正常10PSO正常10部落正常10最佳opt78最佳opt78图6 Olive数据：排名指数（左上）和相关余弦（右上）的图。直方图（分别为核密度估计器）对应于全局最优值（左中，左下）和局部最优（第78次运行，右中，分别为右下角）的峰度指数。图7模拟数据：Normal4（顶部曲线）和Normal10（底部曲线）的最小峰度指数的排序值与GA（左侧曲线）、PSO（中间曲线）和Tribes（右侧曲线）的图。芯片和10个变量。分析的目的是检测可能代表有缺陷芯片的多元离群观测值。这些芯片被卖掉了，但在262号芯片上出现了一些问题。6.2. 结果遗传算法和粒子群算法需要设置一些参数。对于像Lubischew这样的小数据集，GA和大数据集中11最佳I =-0.4669cos = 1最佳I =-0.4669cos = 1最佳选择选择选择图8正常4模拟数据：直方图对应于使用Tribes的判别指数的全局最优值（左上）和局部最优值（右上和底部图）。图9正态10模拟数据：直方图（左）和核估计量（右）对应于使用GA的判别指数的全局最优值。PSO的粒子不需要很大。对于较大的数据集，如橄榄，可靠性和模拟数据集，这些值会增加。迭代次数是通过对每个数据集进行一些初步运行并检查指数的收敛性而获得的。表2总结了GA和PSO方法的这些值。为了使GA和PSO的结果具有可比性，个体/粒子和迭代的数量的选择被设置为使得GA和PSO导致表2中给出的相同数量的适应度评估。与遗传算法和粒子群算法不同的是，Tribes方法中粒子的数量是变化的，这导致适应度评估的数量无法控制。在对每个数据集进行一些初步运行并检查投影指数的收敛性之后，将迭代次数设置为我们在不同的数据集上运行了100次每个优化算法。我们有以强调对于个体/粒子和迭代的数目的不同值，结果将不完全相同。但总的来说，当考虑100次运行时（就像我们所做的那样），该方法在五个数据集中检测到的结构对于这些参数的不同值是相同的这个意义上是相当稳健的。6.2.1. Lubischew示例图3绘制了具有“最佳“投影向量的每个投影向量与最优值相关），使用Tribes（每个图的左曲线）和PSO （每个 图的右曲线 ）用于最小 峰度（顶 部曲线）、Friedman（中间曲线）和判别指数（底部曲线）。对于使用这两种方法的前两个指数，显示非常相似。它们揭示了对于超过100次的70次运行，获得的投影向量是相同的（余弦等于1），但对于其他30次运行是不同的（余弦不同于1），这意味着至少有两个潜在的有趣的数据视图这一结果在Tribes方法中通过指数和余弦曲线的两个着陆点得到了很好的体现。对于判别指数，曲线是相当不同的。PSO的索引值下降速度比Tribes快得多当看余弦曲线时，PSO比Tribes有更多的可变性，这导致我们看3或4个投影。请记住，曲线上的大点对应于100次运行中索引的最大值，而垂直线对应于已选择的第二最佳投影的目标值对应于最大值的投影数据的分布的直方图（分别为：第二选择的最大值）的最小峰度、弗里德曼和判别指数显示在左侧（分别为图4是用Tribes方法绘制的我们注意到这三个指数并不领先12S.L. 玛丽桑特投影最好的投影26投影74投影75投影76图10正态10模拟数据的散点图矩阵（var1=最佳投影，var2=与第26个局部最优值相关的投影，var3=与第74个局部最优值相关的投影，var4=与第75个局部最优值相关的投影，var5=与第76个局部最优值相关的投影）。识别相同的集群。在“最佳“投影（图4的左侧直方图）上，弗里德曼指数和最小峰度（分别为：判别式）索引检测第三个（相应地，第二个）簇不同于其他两个簇。在第二个“最佳“投影（图4的右侧直方图）上，最小峰度和弗里德曼指数检测第二个聚类，而判别指数用Tribes检测第一个聚类，用GA和PSO检测第二个聚类。使用Friedman- Tukey和最大峰度指数没有检测到聚类结构。这一结果证实了这样一个事实，即这些指标更足以检测离群值比集群。索引和余弦曲线的结果（分别为感兴趣的结构）与GA（分别. GA和PSO）在这个例子中是非常相似的与PSO（分别。除了上面为判别指数获得的投影之外的部落），并被省略。从这个结果中，我们得出结论，集群识别弗里德曼，最小峰度和判别指标。此外，这个例子建议对较大或较复杂的数据集以互补方式6.2.2. Olive数据对于Olive数据，使用PSO和GA（分别）的峰度指数的余弦和排名值的一个部落（分别）屈服于一个登陆点三个人，一个人，一个人。至少三个）可能感兴趣的投影。Friedman和判别指数给出了与PSO和Tribes方法的峰度指数相同的曲线，但使用GA，这些指数提供了至少有三个着陆点的曲线（图未显示）。图5显示了三个有趣的投影，对应于使用直方图图形的部落方法的峰度指数的不同局部最优值。在这些图上，数据分为两部分，对应于不同的石油区域 更准确地说，当观察图1左侧图的直方图时，在图5中，右边的组对应于来自意大利南部地区的橄榄油，其包含3个区域，而左边的组对应于来自撒丁岛和意大利北部的橄榄油，其包含2个区域（参见表1）。GA和PSO方法给出相同的投影。中间和右边的图对应于其他的投影;它们引导我们发现另一个群体结构。注 意 ， 还 可 以 通 过 考 虑 其 他 投 影 指 数 （ 例 如Friedman-Tukey或判别指数）的局部最优值来识别其他聚类识别其他感兴趣的结构（聚类）的另一种可能性是应用数据选择。选择图5所示的最佳投影的左侧部分（与最佳投影相关，参见左侧图），并使用EPP-Lab进行图 6显示了100个排名索引（左上）和每个投影向量与最佳投影向量的关联余弦（右上），以及直方图（分别为核估计器）的最佳投影（左中，右中）和另一个投影（左下，右下角）的峰度与GA。指数和余弦曲线表明至少存在两个有趣的投影。当查看对应于最优和局部最优的直方图和核估计器时，数据被分成两组。更多细节，投影图将意大利北部地区与撒丁岛分开6.2.3. 模拟数据在图7中，我们使用GA（左曲线）、PSO（中曲线）和Tribes（右曲线）的模拟数据绘制了具有“最佳“投影向量的最小kurtosis指数的100个排名值。而PSO方法导致的小变异的投影指数值的100发射，部落和GA提供不同的局部最优解。对于Normal4，PSO方法不产生几个着陆点，因此不允许检测四个聚类。相反，Tribes和GA方法给出了对应于图1中左右曲线的三个着陆点的多个局部最优解。7.第一次会议。对于Normal10数据集，左侧和右侧曲线（对于GA和Tribes）由几个着陆点组成，这些着陆点对应于不同的局部最优值，易于揭示有趣的结构。对于这些特定的示例，弗里德曼和判别指数给出了与使用GA、PSO和Tribes优化方法的峰度指数相同的曲线（对于指数和余弦值），除了弗里德曼指数之外，弗里德曼指数给出了使用PSO针对Normal10的具有两个着陆点的曲线。在图8中，我们使用Tribes方法和Normal4模拟数据可视化了四个有趣的投影，对应于左上角的全局最优值和右上角和底部图的判别指数的不同局部最优值在图8的每个图中，数据被清楚地组织成组，并且其中一个对应于三个已知聚类中的一个考虑到判别指数的全局和局部最优值对应的四个图，Tribes成功地大数据集中13PSO可靠性部落可靠性PSO可靠性部落可靠性图11可靠性数据：排名指数（顶部曲线）和相关的余弦曲线（底部曲线）的图，用于PSO（左）和Tribes（右）方法的Friedman指数。在一维上