智能系统与应用16：ABARC：基于Agent的粗糙集聚类算法及其在数据处理中的应用

智能系统与应用16（2022）200117ABARC：一种基于Agent的粗糙集聚类算法拉杜湾[1]A.B. Pop3，a，CostelSarbu4，ba计算机科学系，Babes Bolyai大学，str. Mihail Kogalniceanu nr. 1，Cluj-Napoca，400084，Romaniab化学系，BabesSchoen-Bolyai大学，str. AranyJa'nosnr. 11，Cluj-Napoca，400028，RomaniaA R T I C L EI N FO关键词：聚类Agent粗糙集重叠聚类A B S T R A C T聚类是模式识别中的一项重要任务，在自然科学和医疗保健领域有着广泛的应用。然而，在实际场景中，通常情况下，由于以下几个原因，数据不能容易地分成区分良好的组：聚类的形状、离群值的存在或重叠聚类问题（可能属于多个聚类的实例）。为了处理这样的问题，我们提出了一个凝聚聚类方法，确定可能属于一个以上的集群的实例，并明确分离的离群值从其余的实例，通过整合粗糙集理论的概念。整个分组和重组过程由并行执行的软件代理驱动。我们的方法是计算友好和标准数据集上的实验表明其优势。1. 介绍分类和聚类的问题在于将数据集划分为组，每个组对应一个输入类别。因此，它试图将每个实例分配给一个可能的类或聚类。在现实生活中，类的完整描述是未知的，虽然有限的，通常是较小数量的实例（训练集），这往往提供了分类或聚类系统的优化设计的部分信息。各种模式识别模型的参数值是根据训练集的信息确定的聚类是一种无监督学习问题，它处理以这样一种方式划分未标记的数据集，即来自同一组的两个对象尽可能相似，而来自不同组的对象尽可能不相似分类和聚类现在应用于广泛的活动领域，包括一般医疗保健，图像识别，假新闻检测，情感分析，仅举几例（Onan，2018a; 2018 b; 2019 a; 2019b; 2019 c; 2020; 2021 a; 2021 b; 2022; Onan和Korukoko lu，2017;Onan等人，2016; 2017; Onan and Toçolu，2021）。有一些特性需要考虑，设计聚类算法。许多算法在小的数据集，但当应用于较大的（图像识别，网络挖掘，基因表达数据），他们可能是不切实际的。这就是为什么可扩展性是聚类和分类中需要考虑的一个重要方面其他需要考虑的问题是：发现任意形状和密度的集群的能力，处理重叠集群，处理噪声数据。聚类系统的一个重要属性，特别是从最终用户的角度来看，是结果的可解释性（Han等人， 2011年）。不确定性管理是现实数据分析中的重要问题之一，在聚类场景中，不确定性管理包括重叠聚类、任意形状聚类和噪声数据等问题。在这方面，模糊集理论（Zadeh，1965年）和粗糙集理论（Pawlak，1992年）的概念已被应用，以处理不精确和不精确。可能最广泛使用的聚类算法是k-Means（Macqueen，1967），其中每个对象都被分配到一个聚类中。但是，通常情况下，集群没有很好地定义，这就是为什么这个问题可能会被重新表述为模糊或粗糙的集群。在模糊c均值算法（FCM）（Bezdek，1981）中，根据隶属度，实例可以属于多个聚类。FCM算法可以处理重叠的聚类，但它可能* 通讯作者。电子邮件地址：radu. ubbcluj.ro（R.D. GaPasticceanu），arnold. ubbcluj.ro（A. Szederjesi-Dragomir），horia.pop@ ubbcluj.ro（H.F. Pop），Costel.sarbu@ubbcluj.ro（C. Sarbu）。1 [orcid = 0000-0002-0977-4104]2[orcid = 0000-0002-1106-526X]3 电话：0000-0003-2777-75414 [orcid = 0000-0001-9374-2078]https://doi.org/10.1016/j.iswa.2022.200117接收日期：2022年5月25日;接收日期：2022年7月17日;接受日期：2022年8月23日2022年8月27日在线提供2667-3053/© 2022作者。由Elsevier Ltd.发布。这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表智能系统及其应用杂志主页：www.journals.elsevier.com/intelligent-systems-with-applicationsR.D. GaPasteanuetal.智能系统与应用16（2022）2001172∈在嘈杂的环境中不准确（Krishnapuram和Keller，1993年）。粗糙集理论采用不同的方法来处理不确定性，它利用了关于某些相似性测度的不可约性概念。最近，粗糙集已经应用于许多场景，包括：解决四维运输问题（Bera等人，2018）（使用粗糙区间），从决策表中归纳if-then规则 （Kato et al. ， 2018） ，决 策（ Liu et al. ， 2018;Pamucar 等 人，2018），解决最小权重顶点覆盖问题（Xie et al.，2018年），股价预测（雷，2018年），医疗保健（王等人，2011; Yang和Wu，2009）（使用特征选择），关系事实分类（Bharadwaj和Ramanna，2019）。显然，粗糙集主要用于特征选择，而它们在聚类中的应用似乎不太常见，尽管也有一些有趣的划分聚类算法的粗糙混合。粗糙c均值算法（Roughc-Means algorithm，RCM）（Lingras and West，2004）就是这样一个例子，其中聚类是根据原型以及上下近似来描述的。为了处理噪声数据，提出了粗糙可能性c均值算法和c均值算法的广义形式（Maji和Jiang，2007）。Chen等人（2006）提出了一种基于粗糙集的作者模拟了聚类使用决策表（U，A{d}）的问题，其中U是话语（所有实例xi U），A是属性集合，并且d是引入的决策属性。在粗糙集理论术语中，属性d确定了将U划分为等价类的不相容关系。该算法适用于分类数据的聚类。本文提出了一种粗糙集聚类方法，以处理数据中的不确定性，如重叠聚类或离群值。据我们所知，我们的方法是不同于其他粗糙聚类方法在几个方面。整个聚类过程由软件代理（Wooldridge，2009）执行，这些代理相互合作并自组织成包含相似个体的组。代理实现为EliX ir编程语言中的轻量级过程，从而产生高度可扩展的解决方案。评估重叠数据的质量和算法的离群点发现能力被证明是一项具有挑战性的任务，因为缺乏针对这种特定背景的基准数据集。这就是为什么我们提出我们认为是一个客观的方法来评估的聚类解决方案的质量重叠的集群和离群值的情况下。标准和合成数据集上的EX实验概述了所提出的方法的优点。本文的主要贡献是：基于粗糙集理论和软件Agent处理重叠聚类和噪声数据的能力在重叠聚类和离群值的情况下评估聚类解决方案质量的客观方法• 一种可扩展的聚类方法论文的其余部分结构如下：第2节介绍了我们的工作动机，强调了所提出的方法的重要性。第3节介绍了粗糙集的理论背景，并阐述了粗糙集聚类问题。我们提出的主要算法在第4节中描述。同一节提出了一个客观的方法，我们提出的聚类结果的情况下，重叠的集群和离群值进行评估，认为一些广泛使用的集群评估措施是有偏见的。标准数据集上的EX实验在第5节中详述，与相关方法的比较在第6节中给出。最后，第7节得出本文的结论，并提出了未来工作的想法。2. 动机聚类是将元素的集合组织成以类似的元素在相同的簇中而不同的元素在不同的簇中的方式来进行相干组。最流行的聚类算法之一是k-Means（Macqueen，1967），这是一种划分聚类方法，具有许多扩展，包括一些最近的扩展（Bagirov等人，2016; 2011; Gribel和Vidal，2019;Ism-khan，2018）。分区方法的主要缺点是必须事先知道聚类的数量，而分层（凝聚或分裂）对应物的情况并非如此。许多算法在聚类明显分离时表现良好，但在实际场景中具有不重叠的聚类是例外而不是规则。有几个原因可能导致重叠：数据中可能存在噪声，特征可能无法捕获所有必要的信息以明确区分聚类，或者重叠可能是产生数据的过程所固有的（Adam和Blockeel，2015）。模糊集理论（Zadeh，1965） 已经被广泛应用以处理不确定性和不确定性（Luo等人，2022; Maneckshaw和Mahapatra，2022;Sakhardande和Gaonkar，2022; Shang等人，2022; Yang等人，2022年）， 以及用于提供更自然和详细的数据解释。例如，在Popet al. （1996）;S. （1996）周期表的化学元素是根据它们的一些物理、化学和结构特征进行分类的，在某些情况下与官方的分类略有不同。该方法的优点是可以更好地分析元素之间的相似性以及产生这些相似性所涉及的属性。模式识别中的一个主要问题是离群值管理，如果处理不当，可能会对结果产生重大影响。例如，在回归分析的背景下，即使是一个离群值也会极大地影响结果，如Pop和Sarbu（1996）所示，为了解决这个问题，提出了一种模糊回归算法，该算法能够识别离群值的存在和回归线的线性。在模式识别中，粗糙集理论（Pawlak，1992）解决了与模糊集理论相同的问题，但以不同的方式，通过用下近似集和上近似集来近似不可区分的集合。下近似集包含肯定属于不可区分集的元素，而上近似集包含可能属于不可区分集的元素。从数据分析师的角度来看，这种方法可能比模糊集更有优势，因为肯定属于不可区分集合的数据是明确分离的，允许分析师只关注剩余的元素，这些元素的成员资格是不确定的。粗糙集主要用于特征提取，如第1节所示，并在较小程度上直接建模集群。事实上，除了我们以前关于这个问题的工作（Szederjesi-Dragomir等人，2020; 2019），我们所知道的唯一使用粗糙集来表示聚类的算法是 Li et al. （ 2019 ） ; Lingras and West （ 2004 ） ; Maji and Wendy（2007，2012 a），它们都是基于分区的方法。另一方面，我们的算法是一个层次的，它能够检测离群点和重叠聚类使用粗糙集。此外，通过采用能够并行执行的软件代理（Wooldridge，2009），它也是可扩展的。3. 问题陈述模式识别是人类通常擅长的活动，但由于整个过程中涉及的不确定性，它对于计算机程序来说不是一项微不足道的任务。不确定性的来源包括不完整的数据、类别定义的不准确以及离群值的存在。模糊集（Zadeh，1965）和粗糙集（Pawlak，1992）理论已被应用于处理模式识别过程中不同层次的不确定性。尽管这两种理论都是为了解决vaguness而开发的，但它们通常是复杂的，因为模糊集解决了知识的渐进性···R.D. GaPasteanuetal.智能系统与应用16（2022）2001173RxR xX。我RxR xX。⃒⊆ ×我JIJ⋃2我〈〉⃒（用隶属度表示），粗糙集解决了粒-•卢恩RCk=X知识的多样性（由不可否认的关系表示）（Maji和Joshua，2012b）。3.1. 粗糙集粗糙集理论（Pawlak，1992）是处理不确定性的一个主要数学工具，它通过一对表示原始集合的上、下界给定一组对象U（称为论述论域）、等价关系R U U和U的一个子集（用X表示），为了相对于R来近似X，我们考虑以下定义：定义1.集合X关于R的下近似是 设置 的 所有 对象 这当然属于到 X：RX为x∈U{（）：（）<$}定义2.集合X关于R的上近似是可能属于X的所有对象的集合：RX=x∈U{（）：（） =闪烁}备注1. 上下部的appro ximation集是脆的。定义3.一个集合X关于R的边界区域是所有不能肯定地被分类为属于X或不属于X的对象的集合：RB=RX-RX。备注2.如果边界区域是空的，则集合X是清晰的，即，精确到R。定义4. 粗糙集是一个元组RX，RXX，其中RX是目标集X的下近似（定义1），RX是目标集X的上近似（定义2）。3.2. 粗糙集聚类聚类分析是一种在数据集中发现自然组的技术这个概念可以用定义5来形式化。定义5.聚类是找到集合C={Ck|k=1，p}的给定对象集合X={xi=1，n，1≤p≤n}的子集，使得：1k，l=1，p，kscin=l：CkCl=1k=1• p：RCk=闪烁• k=1，p：RCk<$RCk• k=1，p，i，j=1，|RCk|：xiRxj<$xi，xj∈Ck• k=1，p，i，j=1，|R Ck|：xRx{x，x}≥0。备注4.基于定义6，以下属性成立：• xi∈RCk，i=1，n，k=1，p<$xi∈scinRCl，nl=1，p，kscinl=l• xi∈RCk <$xi∈RCk，i=1，n，k=1，p• xi∈scinRCk，i=1，n，k=1，p<$l，l=1，p<$xi∈R Cl.因此，在粗糙集聚类方法中，每个聚类Ck是根据下近似和上近似来定义的从较低的approximation的物质肯定属于集群Ck关于一些相似性度量。来自上近似的实例可能属于Ck，但根据所考虑的相似性度量，我们不能确定这一点。如果一个实例是一个较低的近似，那么它不属于任何其他粗糙集。另一方面，如果一个实例在一个集群Ck的边界区域中，那么它可能属于其他几个边界区域。此外，如果一个实例属于一个集群的下近似，那么它也属于该集群的上近似整个想法可以在图1中可视化，其中示出了两个不明显可分离的集群。即使它们不能被精确地识别，这两个集群仍然可以通过它们的下近似（椭圆）和它们的上近似（矩形）来描述。在这个例子中，边界区域是重叠的，并且来自图像的红色实例属于两个上部近似，因此在某种程度上属于两个聚类。4. 该方法本节介绍我们的集群方法。我们介绍ABARC（代理基础RoughC聚类），该算法通过使用粗糙集理论的概念建模集群，解决了重叠集群问题。该算法成功地识别离群值，并通过使用软件代理，它也是可扩展的。第4.1节提供了算法的详细描述以及更好地激励我们的方法的示例。在第4.2节中，我们介绍了我们认为是一个客观的方法来评估质量的一个nk=1Ck=X在重叠聚类和离群值的情况下，聚类结果。 我们也3k=1，p：Ck=闪烁4 k=1，p，i，j=1，|Ck|：sim（xi，xj）-保持，其中：sim（xi，xj）表示两个项目xi和xj之间的相似性。备注3.集合C是给定的对象集合X的一个划分（参见定义5中的属性1、2和3），使得来自每个子集Ck的对象彼此相似（参见属性4）。设RCK和RCK表示a的上下近似，聚类Ck，设RB=RCk-RCk为Ck的边界区域。元组RCk，RCk被称为关于某个等价关系R与Ck相关联的粗糙集（参见定义4）。然后，粗糙集聚类问题可以如定义6中所定义。定义6.粗糙集聚类是寻找一个集合RC的过程={RCk，R Ck|k=1，p}的给定对象集合X={xi=1，n， 1≤p≤n}，使得：• k，l=l，p，kscinc=l：RCkRCl=l• k，l=l，p，kscin=l：|R CkR Cl|≥0讨论一些广泛使用的聚类评价方法（第二节4.2.2），我们认为他们在某些情况下可能有偏见4.1. 基于粗糙集的本节介绍ABARC算法，我们的方法粗糙图1. 具有重叠上部近似的粗糙簇。R.D. GaPasteanuetal.智能系统与应用16（2022）2001174‖（）A（k）=∑使用软件代理设置群集。算法1中描述了主要的聚类过程，其中X是包含待聚类的实例的数据集，imax和λ是表示特定任务的试验次数的整数（细节如下），σ1是相似性极限，δ是距离度量（例如，欧几里德距离）。相似性极限σ1是每个数据集所特有的，它是一个实数，表示两个实例被认为相似的最大值（它们肯定属于同一组）。第一步是初始化代理并将一个代理与每个实例关联。此外，每个代理被分配到不同的集群，因此，在开始时，集群的数量等于代理的数量，代理的数量等于实例的数量。代理在单独的进程中并行执行，这种行为由第4行的操作符指示。算法2显示了每个代理的异步行为：给定代理k，它试图通过直接消息交换找到关于σ1和δ的一旦它找到一个类似的代理，它就移动到它的集群（第3行）。算法3描述了寻找相似代理的过程。参数λ表示代理为了找到相似的代理而应该执行的最大尝试次数在第4行上，以非确定性方式选择代理，如由代理操作符所指示的，并且如果两个代理不在同一集群中，则计算它们的相似性如果这个值低于相似性限制σ1，那么找到一个相似的代理，并且函数通过返回selectedAgent而终止。否则，搜索继续，并且在λ次寻找类似代理（其不位于当前集群中）的尝试失败之后，函数返回空，这意味着不存在与给定代理（代理k）类似的代理，或者该过程只是花费了太多时间，在这种情况下，任务留给其他代理或另一次迭代（算法1的第2行），此时搜索过程可能更快，因为集群更少。来自第6行的computeSimilarity函数计算给定距离度量δ的两个代理之间的相似性。如果该值低于相似性限制σ1，则意味着这两个智能体肯定属于同一个聚类，因此它们处于当前聚类的较低近似值算法4代表了我们方法的第二阶段。由于只有当代理肯定属于同一个簇时（基于相似性限制σ1），代理才被分组在一起，因此我们方法的第一阶段（算法1，2和3）可能会产生大量的簇。第二阶段（算法4）统一相似的集群产生粗糙的集群。该算法接收作为第一参数的一组集群代表。聚类代表Rk=<$C k，A（C k）<$，是一个元组，其中AC k是聚类Ck的质心，计算它如下：C1（1）|xi ∈ C k|xi ∈Ck第二个参数σ2是一个粗略的相似性极限，表示两个智能体可能相似到什么程度。该参数不同于σ1值（用于算法1，2和3），σ 1值表示两个代理肯定相似的点。最后一个参数unified表示统一簇的集合，它最初等于空集。聚类相似性是基于质心值以与执行代理相似性相同的方式计算的。如果一个代表类似于几个代表，则相应的数据将属于上近似中的几个 聚 类 。 结 果 是 一 组 统 一 集 群 的 代 表 。 来 自 第 8 行 的updateRepresentations函数使用Eq. 1.即使在执行算法4之后，可能仍然存在大量的集群，但是它们中的大多数通常由非常少量的实体组成，这些实体与“正常”集群中的任何一个都不相似。来自这些小集群的实例将被标记为可能的离群值。然而，在算法5中，我们的方法的第三阶段，我们将把它们分配到最接近的聚类中，并得到最终的聚类结构。算法5接收作为输入数据的聚类，如之后得到的。数据：X、imax、λ、σ1、δ结果：RC//粗糙聚类1 @设AG为代理的集合i=1，imaxdo对于k = 1，|AG|做AgendoCluster（agentk，λ，σ1，δ，AG）4算法1. 代理群集。5端6端部R.D. GaPasteanuetal.智能系统与应用16（2022）2001175如果相似度≤σ1，则数据：因子k、λ、σ1、δ、AGsak=searchForS imilar（agentk，λ，σ1，δ，AG）1234如果sak为空，则ChangeCluster（agentk，sak）端算法2. 执行群集。数据：因子k、λ、σ1、δ、AG结果：sa//类似药物如果λ=0，则返回null端1234567891011121314“e{ selectedAgent = a j，n j = 1，|一|，aj∈ AG}如果getCluster（agent）不支持getCluster（selectedAgent），则returnselectedAgent其returnsearchForS imilar（agent，λ−1，σ1，δ，AG）结束elsereturnsearchForS imilar（agent，λ−1，σ1，δ，AG）端算法3. 寻找相似。R.D. GaPasteanuetal.智能系统与应用16（2022）2001176如果representatives=0，则 返回unified端Rk=f irst（代表）S=getS imilar（ Rk，representatives\{Rk}，σ2）如果S是，则数据：代表性，σ2，unified结果：均匀123456789101112updateCluster（Rk（Ck），S）新代表 =updateRepresentatives（representatives）returnSimilarList Uni f ication（newRepresentatives，σ2，σ2）其returnS imilarbitterUni f ication（representatives\{Rk}，σ2，unified\{Rk}）端算法4. 相似的统一。数据：聚类，ε结果：f inalClusters{outliers，clusters}=detectOutliers（clusters，ε）123f inalClusters=joinOutliers（outliers，clusters）returnf inalClusters算法5. 离群值消除。R.D. GaPasteanuetal.智能系统与应用16（2022）2001177--}联系我们||RCkK∑应用算法4。在第1行中，离群值（本身就是聚类）与“正常”聚类分开。这个决定是基于ε的值和集群大小：如果集群中的实例数量小于ε，则该集群被标记为离群值。ε的值设置为数据集中实例总数的5%。在第2行中，每个离群值都与最接近的“正常”聚类统一4.1.1. 例如为了更好地解释和激励我们的方法，我们考虑了一个合成数据集，该数据集包含10个实例，每个实例具有两个属性，如表1所示。这个例子并没有说明算法的所有步骤，而是为了展示一个可能的场景，与其他方法相比，它可能更有用属性值在0和0.25之间的从1到4的集合彼此非常相似，显然应该属于一个聚类。 相同的观察对于属性值在0.75和1之间的实例5到8是有效的，这些实例应该明显属于不同的聚类。这两个集群应该彼此很好地分离，因为来自第一组（1 - 4）的实例与来自第二组（5）的实例非常不同 8）。问题出其中实例9和10的属性值（在0.4和0.6之间）足够接近来自两个组的某些实例。整个概念可以在图2中可视化，其中实例9和10用绿色表示。我们的聚类方法的第一阶段（算法1和3）实际上将产生三个聚类：C1={1，2，3，4}，C2={5，6，7，8}和C3R=C{9，10}。这些聚类的代表（参见算法4）是：图2. 混合数据的合成数据集。Ruby编程语言4.2.1. 验证标准的分类或聚类方法没有考虑到数据的混合性质：一些实例被标记为粗糙，其他可能的离群值。即使在这个意义上已经提出了一些指标，我们仍然希望能够声称，我们确定为粗糙或离群值的一些实例确实如此。这就是为什么我们提出了一个额外的分析来验证结果。我们在实验中考虑了几个案例研究，每个数据集一个案例研究，在本节中，我们描述了每个案例研究中执行的步骤，以及建议的混合数据验证1={0. 1375，0。1375}，R C2={0. 8625，0。8625}和RC3={0。四十五岁，0的情况。55}。在我们的聚类方法的第二阶段之后，方法论我们在进行每一项集群C3将与来自集群C1和C2的数据统一：实例9将被添加到C1和C2两者，因为实例9与集群代表RC1和RC2之间的相似性在两种情况下都是0.26，这低于粗略的相似性限制0.3;实例10将被添加到C1和C2两者，因为实例10与集群代表RC1和RC2之间的相似性在两种情况下都是0.28，这也低于粗略的相似性限制。平方欧几里德距离是用于计算两个实例之间的相似度因此，我们的方法的最终结果是两个聚类：C11， 2， 3， 4，9，10，C25， 6， 7， 8，9，10，其中实例9和10属于两个聚类的上近似，并且被清楚地标记为这样。4.2. 拟议方法我们为实验考虑了几个数据集，本节概述了我们为每个案例研究执行的步骤。由于我们的算法输出一组粗糙聚类，即，一些实例被分配到上近似，我们需要一种方法来评估这个结果的可靠性。我们为每个案例研究执行验证步骤，其中我们将报告的混合数据与实际（根据数据集文档）聚类进行比较。所得到的结果也进行了评估的分类错误和其他广泛使用的指标，在评估质量的聚类过程。验证部分在表1合成数据集。ID的1一个210020.10.130.20.240.250.2550.750.7560.80.870.90.981190.50.5100.40.6案例研究包括：1. 对给定的数据集执行4.1节 结果将是一组粗略的聚类，上面的近似实例被清楚地勾勒出来。2. 验证结果a计算聚类代表（数据集文件报告的聚类）。除非本实验中另有规定例如，聚类代表Rk=Ck，A（Ck）是一个元组，其中A（Ck）是聚类Ck的质心，它被计算为：A（C k）= 1xi ∈C xi.b计算用于质心计算的数据的标准偏差。c基于聚类代表和实例之间的相似性，识别每个聚类的最不相似的实例。除非实验中另有说明，否则平方欧几里德距离用于计算相似性水平。d基于步骤2b计算的标准偏差，我们可以决定从数据集中删除一些被认为是混合的实例，并重复步骤2b，2b和2b。e将我们的算法报告的混合数据与步骤2c的实例进行比较。3. 使用标准度量来评估聚类质量，可能会考虑步骤2中的分析为了更好地分析通过我们的算法获得的混合数据以及分类错误（在步骤2e中），我们应用了额外的程序，并且我们在这方面引入了定义7，8，9和10定义7.聚类Ck的粗略阈值\boldmathTk是聚类Ck中最不相似的实例与其代表之间的距离。备注5.在混合数据被消除之后，即在执行步骤2d之后，计算粗略阈值。定义8.如果满足以下条件，则来自集群Cj的实例xi应该是粗略的R.D. GaPasteanuetal.智能系统与应用16（2022）2001178ik j i iK∑--O（）[-]pKC|C|J（）DU=≤ij ≤cK=，KKRRK1b（i）-a（i）（）克雷奇|d-最小d|<不+T，k=1，p，kscinc=argmind（2）n其中p表示聚类的数量，di是从实例xi到聚类Ck的距离。定义9.对于一个固定的数据集，具有n个实例xi（i 1，n）和p个聚类Ck（k 1，p）的数据集的离群值阈值\boldmath T 0由下式给出：argmTaxf（TO）受f（TO）T0，∈k，=，平方误差之和，如k-Means，也往往会自然产生在指数计算中该标准的良好值，但不一定保证一致的结果（Lamirel等人，2011年）。此外，当比较基于这样的索引的两个算法时，定义10. 如果满足以下条件，则实例xi应该是离群值：满足条件：di>T0，k=1，p。我们应用以下步骤来分析报告的粗略实例、离群值和分类错误：1 从每个集群中识别最不相似的实例（参见步骤2c）。R测量方法应该相同，否则结果可能会有偏差。这就是为什么我们更喜欢根据第4.2.1中描述的分析程序进行比较。另一方面，可以考虑采用熵（Shannon，2001年）等外部评价措施：E= ∑ |Ci |E（C i），计算混合后所有聚类的粗略阈值Tk根据定义7和注释5消除数据。i=1n2 根据定义8检查所有报告的粗略实例。3 根据定义10检查所有报告的离群值。除非其他-如果在实验中具体说明，则将λ的值设定为0.15。因此，TO的值被计算为使得最多15%的来自其中c表示簇的数量，n是实例的数量并且E（Ci）表示第i个聚类的个体熵，并且由下式给出：原始数据集可以被认为是异常值。∑|C iC j|（|C iC j|）、4 任何分类错误也将使用这些信息进行分析在本节中介绍。E（Ci）=-j=1日志|C i||C i|4.2.2. 类集评价措施为了评估所获得的聚类的质量，我们采用以下度量：DB（Davis-Bouldin Index）（Davies and Bouldin，1979），DU（Dunn Index）（ Bezdek and Werner ， 1998 ） 和 SI （ Silhouette ） （ Schlosseuw ，1987）。Davis-Bouldin指数是根据类内距离和类间距离之间的比率计算的，如下所示：其中，Ci是所考虑的聚类，Ci是地面实况聚类（由数据集文档给出）。在热动力学中，熵度量系统的“无序”量，因此直观地说，好的聚类算法应该使该指数尽可能低。调整后的兰德指数（ARI）是兰德指数（Rand，1971）的机会修正版本，它基本上是根据 成对实例的关系。 设a是 的放置在同一类C和DB1∑max{Δi+Δk}联系我、相同的集群C，b是在集群C中的实例对的数量=ci=11 K Cδ（Ci，Ck）相同的类C但不在同一簇C中，c是在同一集群C中但不在同一类C中的实例，以及d其中c表示簇的数量，Δi是簇Ci的簇内距离，δCi，Ck表示簇间距离。一个好的聚类过程应该使这个指数尽可能低。与考虑所有聚类之间的距离的DB索引相反，Dunn索引仅考虑最小聚类间距离和最大聚类内距离。Dunn指数越高，聚类结果越好。它由以下公式给出：1min δ（Ci，Ck）maxΔk1≤k≤cSilhouette索引衡量实例与其集群相比其他集群的相似程度，并由以下公式给出：在两个分区中处于不同类和不同簇中的对象对的数量。则ARI定义如下：ARI2（ad-bc）（a+b）（b+d）+（a+c）（c+d）5. 实验在本节中，我们提供了我们的方法的实验评估。在标准数据集上进行实验，并采用几个指标来评估我们算法的性能（见第4.2.2节）。此外，为了更好地评估结果（特别是粗糙聚类），我们对每个案例研究进行了额外的分析（在第4.2.1节中介绍）。这个验证部分的目的是分析，例如，分配给上界的实例是否真的可以表示混合数据。我们进行了三个案例研究的三个著名的数据集从UCI（杜阿：CKSI⃒R.D. GaPasteanuetal.智能系统与应用16（2022）2001179[客户端]01.和Graff，2017），即Iris、Seeds和Wine，我们使用第4.2.1节中提出的验证方法对结果进行了验证。出于基准测试的原因，我们还对UCI的其他数据集进行了实验（第5.5节），并计算了几个评估指标，以便将我们的方法与相关工作进行比较。5.1. 案例研究-虹膜数据集虹膜数据集（Fisher，1936）是模式识别中最广泛使用的数据集之一，包含150个实例，具有4个属性，分别表示三种虹膜植物的萼片和花瓣的长度和宽度。有三个类，每个类有50个实例，其中一个类与其他两个类是线性可分的数据在 0， 1范围使用最小-最大归一化并且在第4.1节中描述的算法应用于以下参数设置：imax=100，λ=100，σ1=0。0115，σ2=.为了更好地理解算法和建议的验证方法，我们补充了这个案例研究与过程的视觉元素。在图3中，我们显示了Iris数据集的官方聚类，如数据集文档中所指定的。为了用图形表示数据，我们首先进行了PCA分析（S。 和P，1901）使用Scikit-learn（Pedregosa等人，2011）显示前两个分量捕获了总变化的97%以上，我们使用这两个分量绘制数据。从图3中可以看出，只有第一类（Setosa）与其他两类明显分开。因此，如果一个无监督学习算法会产生两个甚至三个以上的聚类，这并不奇怪。我们愿意承认有三个类，但至少最后两个类包含一些特殊的实例，这些实例要么看起来更可能属于另一个类，要么离任何类都很远。我们的目标是识别这些混合实例，同时仍然接受有三类。我们的方法的主要优点是，它通过识别可能的离群值（例如，测量中可能的错误）和粗略的实例，即，与两个以上的纲有某些共同方面的实例，但不能肯定地被接受为属于任何一个纲（在这种情况下可能是杂交种）。算法的第一阶段产生大量的聚类在图4中以不同的颜色示出。可以看出，已经有三个明显可区分的大集群。在算法的第二阶段之后，聚类的数量显著减少（图5），大多数实例属于三个大的聚类，其他实例形成非常小的组。由于此阶段的结果，一些实例可能属于多个集群（粗略实例），但在最后一个阶段之后，它们将仅使用不同的颜色进行标记。算法的最后阶段的结果（不标记混合图3. 根据官方文档，Iris数据集中的聚类。图第四章算法第一阶段后 Iris数据集中的聚类 。图5. 算法第二阶段后Iris 数据 集中的 聚类。例），如图所示。第六章 图 7我们还标记了离群值和第4节中描述的粗略实例。5.1.1. 结果和讨论我们得到了三个聚类：C1的所有实例从1到50，C2的大多数实例从51到100，C3的大多数实例从101到100。150. 106、107、120、123、134、135被分配到集群C2，但根据数据集文档，它们应该在C3中。此外，实例58、60、61、69、71、73、88、94、99被分配给集群C3，而文档指定它们属于集群C2。如果我们见图6。聚类后的虹膜数据集是第三阶段算法中不含混合数据的部分。R.D. GaPasteanuetal.智能系统与应用16（2022）20011710〈〉R+---图7. 聚类后的Iris数据集与算法第三阶段的混合数据。将所有上述实例视为分类错误，则准确度为90%。然而，由于我们使用粗糙的聚类，我们也得到了更精细颗粒信息。该算法将以下实例放置在聚类C2和C3的上近似中：58，60，61，69，73，88，94，99，106，107，120，123，135。因此，这些实例实际上被分配到正确的集群，但是因为它们也足够接近另一个集群，所以它们被放置在两个集群中，在它们相应的上层近似中。所以这些并不是分类错误。唯一的错误（相对于数据集文档）是实例71和134，它们没有被算法识别为粗略实例，放置在错误的簇中（较低的近似值）。这一点，可以说，导致98的准确性。百分之六十六此外，以下实例被标记为可能的离群值：15、16、33、34、42、63、110、118、119、132、136.混合数据（粗略实例，离群值），以及分类错误（71和134），准确性将在接下来的章节中进行更详细的分析。5.1.2. 验证为了更好地了解结果，并检查我们报告的属于上近似的实例是否确实应该被视为上近似，我们进行了更深入的分析，如第4.2.1所述。在表2中，我们显示了聚类代表以及计算每个代表的分量所涉及的数据内的标准偏差。每个聚类的内容与官方数据集文档中指定的内容完全相同。因此，例如，聚类C1的代表（具有来自数据集的内容文档）为0。196，0。595，0。078，0。061号。在表3中，我们显示了最远离每个集群的代表。表3Iris数据集中每个聚类中最不相似的实例秩第1组第2组第3组例如距离例如距离例如距离1420.242610.2061070.3092160.205580.1521320.2723340.123940.1511180.2574150.108510.1261200.1875330.085990.1211190.1856140.078530.1081100.145790.077780.0941230.1398190.063860.0841360.1