基于仿射传播的数据流主动聚类算法研究

⃝可在www.sciencedirect.com在线获取ScienceDirectICTExpress 8（2022）276www.elsevier.com/locate/icte基于仿射传播的数据流主动Sameh Abdulah（博士）a，Walid Atwa（Ph.D.）作者声明：David M.Abdelmoniem（Ph.D.）Ba埃及Menoufia大学计算机和信息学院计算机科学系b埃及艾斯尤特大学计算机与信息学院计算机科学系接收日期：2021年6月4日;接收日期：2021年7月30日;接受日期：2021年8月11日2021年9月4日网上发售摘要大多数现有的应用程序都有大量不断发展的数据流。聚类数据流仍然是这些应用程序的一个关键问题，因为数据是不断发展和变化的。现有的大多数算法都是无监督学习，其中背景信息是无用的。提出了一种基于亲和传播方法的数据流主动聚类算法，作为AAPStream。相似度传播的目的是识别样本并基于这些样本创建聚类。因此，目标是以获得信息量最大的样本来创建流模型并预测新到达的数据。我们在真实数据集上进行了一组实验，将我们的算法与最先进的算法进行了比较，实验结果表明了所提出的算法的有效性。c2021韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：仿射传播;流数据;标记数据1. 介绍数据流是指实时连续产生并快速演化的大量数据。近来，大多数现有应用涉及数据流，例如，无线传感器网络、股票市场分析、智能手机和物联网（IoT）[1此外，所有这些应用程序都有一个很大的数据集，很难适应主内存。数据流聚类对处理时间、存储容量和计算建模都是一个挑战。数据流聚类面临的一个重要问题是新数据的不断演化。因此，算法应实现以下要求：（1）应用增量和快速处理的数据对象;（2）检测数据的动态变化;（3）检测离群值，并采取相应的行动亲和传播（AP）是一种聚类算法，它基于数据点之间的消息传递来生成一组代表聚类的样本。AP算法可以对多类、大规模的数据集进行聚类。此外，本发明还提供了一种方法，∗ 通讯作者。电子邮件地址：sameh. ci.menofia.edu.eg（S.阿卜杜勒），瓦利德ci.menofia.edu.eg。Atwa），ahmedcs@aun.edu.eg（上午10时）Abdelmoniem）。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2021.08.017AP不存在初始化集群数量的问题[5]。与其他聚类算法相比，流式亲和传播算法更准确，更有效，特别是对于大数据集[6]。然而，大多数现有的基于仿射传播的算法是无监督的聚类，其中背景信息是无用的。为了提高聚类精度，提出了包含监督信息的半监督聚类方法，所述监督信息包括标记数据（即，已经用一个或多个标签标记的一组样本）或以必须链接和不能链接约束的形式的成对约束。主动学习是许多机器学习问题的最佳解决方案。其目的是确定最具代表性和信息量的数据进行监督。本文提出了 一 种 挖 掘 数 据 流 的 主 动 式 仿 射 聚 类 方 法（AAPStream）。我们扩展的亲和传播方法聚类数据流与现有的先验知识，以提高聚类性能如下：首先，确定最具信息量和代表性的样本，创建集群。然后，用现有样本查询到达的数据点，样本之间的一组必须链接和不能链接约束。最后，通过更新流模型，实现流数据的在线聚类.2405-9595/2021韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276277表1数据流聚类算法的关键特征算法名称聚类方法计算框架主动学习处理高维处理群集形状中文（简体）分层离线-在线没有没有球度CluStream [8]分区离线-在线没有没有球度[10]第10话：你是谁？密度离线-在线没有没有任意[12]第13话，密度和网格在线没有没有任意[14]第15话：密度离线-在线没有是的任意[16]《易经》：“以德为本，以德为先。分区在线没有没有球度我们在一组真实数据集上与最先进的算法进行了多次实验，实验结果表明了所提出的算法的有效性。论文的其余部分按如下顺序排列。在第二节中，概述了相关的工作，并仔细讨论。在第3节中讨论了主动亲和传播算法。第四节详细讨论了流数据的AAPStream算法。第5节显示了实验装置，并详细解释了所获得的结果。最后，在第6节中对本文进行了总结。2. 相关工作数据流聚类问题已经引起了众多分析人员和研究人员的关注。大多数现有的流数据算法被分类为基于层次的[7]，基于分区的[8，18-[16，17，22]O’callaghan et al. [然而，该算法假设通过整个数据流生成聚类。Aggarwal等人。[8]建议使用CluStream，这是一种用于处理流数据的系统，它使用微集群来连续收集数据并提供按需聚类输出。然而，在聚类之前，该算法必须指定微簇的数量已经提出了几种基于密度的聚类Cao等人[9]介绍了一种基于密度的算法，称为DenStream。该算法应用微簇的概念定义稠密数据对象邻域。基于DenStream，Chen和Tu引入了另一种基于密度的算法，称为D-Stream，目的是对流数据进行聚类[10]。该算法利用一个在线组件，将输入传输到一个网格，然后使一个离线组件，计算网格密度和进一步集群的网格。实验结果表明，D-Stream具有良好的质量和效果。Amini等人介绍了一种基于多密度的算法，称为MuDi-Stream，它可以在在线和离线阶段工作。在线阶段存储关于演进的多密度的概要信息，并且离线阶段生成关于演进的多密度的概要信息。在线阶段，读取并划分新的数据点。在离线阶段，更新每个时间间隔间隙的聚类。Hyde等人。[13]提出了一种CEDAS算法，该算法生成微集群并将数据添加到当前微集群中。然后将微团簇分为核区和壳区。CEDAS可以适应不断变化的数据流以及噪声的属性，以提供高质量的聚类性能。因此，该算法可以发现不规则形成的聚类和发现离群点。然而，CEDAS在计算上更昂贵，需要更多的时间来更新和更多的内存来存储集群。Ntoutsi 等 人 [14] 提 出 了 一 种 称 为 HDDStream 的 算 法Braverman等人。[15]还提出了用于高维流数据的基于k-中值的算法。然而，该算法需要用户指定的聚类数k之前，应用聚类过程。Zhang等人[16，22]提出了一种基于一个名为STRAP的亲和传播算法，该算法已经实现，用于跟踪和发现网格计算基础设施中的异常。然而，该算法不能应用于重复出现和删除聚类。Sui等人[17]提出了一种改进的STRAP算法，可以实时识别新出现的聚类并删除过时的聚类。然而，它无法处理高速变化的数据流。在表1中，我们比较了上面讨论的数据流聚类算法的关键特性。现有的算法是无监督聚类，其中以标记数据的形式的背景信息是无用的。因此，我们应用了一种算法，该算法使用可用的标记来提高流数据的聚类精度。3. 主动仿射传播亲和传播（AP）[5]是一种聚类方法，旨在识别样本并基于这些样本创建聚类。每个样本的特征在于代表样本本身的数据项和一些其他类似的项。AP的目的是通过将每个数据点xi分配给其最接近的样本来优化以下目标函数。最后一组[11]。MuDi-Stream增强了聚类精度N N特别是在多密度环境中。然而，这些人--租赁涉及两阶段离线-在线框架。在S（ c）=∑s（xi，c（xi））+∑δk（c）（1）i=1k=1S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276278j= k⎨⎡{=k||=||==\联系我们=1Σ：=M∑1−i拉吉吉i=max[0，r（i′，k）]我我我我r（ i， k）=S（ xi， xk）−max{S（xi， xj）+a（i，j）}（4）a（ i， k）i′k =k= ⎪∑[（′）]（五）最小值r（k，k）+max 0，r i，ki′∈/{i，k}iFig. 1. 派遣责任。图二. 发送可用性。δ（c）−∞，i f c（ xk）<$xk但<$xi：c（xi）=xk0，其他智慧（二）如上所述，亲和传播算法是无监督的聚类，不能利用可用的标记数据来提高聚类精度。在这里，我们使用监督信息必须链接和不能链接的约束。两个数据点之间的必须链接约束意味着它们必须被分组在同一个集群中。而具有不能链接约束意味着数据点必须在不同的聚类中。因此，如果我们在点（xi，xj）之间有必连，在点（xi，xk）之间有必连，那么我们得到点（xj，xk）之间新的必连此外，如果我们在点之间有必须链接，（xi，xj）和点之间的cannot-link（xi，xk），那么我们得到点之间的cannot-link（xj，xk）。主动学习方法的目标是选择即使注释较少也能表现得更好的数据。对于给定的参数分类模型，学习算法通过最大化联合概率P（ X， Yθ） P（ Xθ） P（ Y X，θ）来频繁地学习参数θ，其中X和Y由训练数据及其对应的标签表示，P（X）和P（Y X）分别表示X和Y的边缘和条件概率分布。在本节中，我们通过从未标记数据中选择一组活动点（即样本）来解决这个问题，使得由所选点和标记数据表示的分布类似于活动点的概率分布。s（x，c（x））= − <$x −c（x）<$2。（三）无标签数据集具体来说，我们选择了一组最有用的和重要点（S），以便其中S（xi， c（xi））是数据项xi与其样本c（xi）之间的相似性，并且δk（c）是样本一致性约束，使得如果数据项xi已经选择xk作为其样本，即，c（xi） xk，则数据项xk必须选择其自身作为样本，即，c（xk）xk.首先，亲和传播算法通过在数据点之间迭代地交换消息来识别样本，直到出现一组好的样本。有两种类型的这些消息，称为责任和可用性消息，它们是使用方程计算的。（4）及（5）分别由具有选定点S的标记数据（DL）表示的联合概率分布类似于没有选定点S的未标记数据（DU）。换句话说，DL S和DU S彼此相似。最大平均离散度（MMD）是比较其边际概率分布的有用度量[23]。该度量基于在再生核希尔伯特空间中嵌入概率的概念[24]。设Xx1，x2. . . .，xm和Zz1，z2. . . .，Z N从目标人群中随机抽取的两组样本，最大平均离散度定义为：从数据项xi发送到候选样本项xk的责任消息r（i，k）反映了项xk有多适合用作项x k的MMMD [φ，X， Z]i=1nΦ（x） ni=12Φ（z）ZH（六S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276279S=（）1）Xi.而从候选样本项xk发送到项xi的可用性消息a（i，k）反映了项xi选择项x i有多合适现在，我们可以使用MMD来定义目标函数f（S）从未标记的数据集中选择数据点，以最小化DL\S和DU\S之间的不匹配。xk作为其范例，考虑到其他项目支持xk应该是范例。图1和2分别显示了责任和可用性消息1l+bj∈∑DL<$SΦ（xj）−u−bi∈∑DU\S2Φ（xi）ZH（七）S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276280（）下一页∈⏐⏐⎝∑∑−=Cd我其中，DU是具有u个点的未标记数据，DL是具有l个点的标记数据，S是具有b个点的选定集合，Φ（xi）和Φxj是xi和xj的特征映射函数。我们定义一个大小为u的二进制向量α，其中每个条目αi表示数据xi U是否被选中。如果选择了一个点，则相应的条目αi为1，否则为0。因此，最小化问题简化为找到最小化成本函数f（S）：其最近的样本ei，并更新流模型，否则将数据项xt放入缓冲器中。步骤3：当缓冲区已满时，使用AAP算法重新创建流模型。步骤4：删除小于权重下限的样本，并更新流模型，如下所述。步骤5：在停止要求完成之前返回步骤2min 不1⎛保加利亚l+ bΦ（xj）+∑αiΦ（xi）被满足了。我们删除了很长时间没有使用的样本。数据流行度是一种众所周知的对范例进行排名的方法α：αi∈{0，1}，α1=bj∈DLi∈DU1u− bi∈DU2（1−αi）Φ（xi）（八）根据每次的使用量。它被用来衡量样本在不久的将来被访问的可能性[25，26]。因此，如果没有新的数据点被合并到现有的样本ei中，ei的权重最终会降低，α表示大小为u的二进制向量，1表示与α相同维数的向量，所有元素均为1。并且它可以被丢弃以释放存储器空间用于新的样本。在本文中，我们使用阻尼窗口模型来控制当前样本的权重在阻尼窗模型中，样本的权重按照衰减函数f（t）随时间t而减小2 −λ。t，其中λ >0是衰减因子。因此，具有时间戳ti的样本ei在时间tk的权重计算如下：w（ei，tk）=2−λ（tk−ti）（ 9）因此，我们将样本权重评估为其权重下限（表示为η）。如果样本的重量低于重量下限，我们可以将其移除。其中重量下限计算如下：1− 2−λ（tc−ti+1）η（tc， ti）=1−2−λ（10）在选择了信息量最大的点（S）的集合之后，我们开始用每个样本ei查询S中的每个点s，并且在得到s和样本ei之间的必须链接时停止查询。否则，我们对所有样本e设置不能链接约束，并使用数据点s生成一个新样本。重复该过程，直到我们查询所有选择的点S。最后，我们返回活动样本集。该算法的细节总结在算法1中4. AAPStream框架AAPStream算法实现了流数据的在线聚类。AAPStream根据以下内容更新流模型：其中tc和ti是当前和上次升级时间，示例岛5. 实验在本节中，我们将AAPStream算法与最先进的算法DenStream [9]，StrAP [16]和CluStream [8]在来自UCI机器学习存储库的一组真实数据集上进行比较，每个数据集的对象，属性和聚类的数量如表2所示。为了评估算法的性能，我们使用纯度度量来衡量流聚类算法的准确性。纯度指标定义如下：∑ni=buffer的大小。通常，AAPStream的过程可以摘要如下：纯度i=1|Ci|n×100%步骤1：在时间t0：第一数据集由下式表示：主动相似性传播算法（AAP），以获得最具信息量的样本并创建流模型。步骤2：当数据进来时，用当前样本测试数据点x t;如果数据点xt和最近的样本ei（d（xt，ei））之间的距离小于某个值，则使用当前样本测试数据点xt。其中n表示真实聚类的数量，Cd表示分配给集群i的数据对象的数量，并且Ci表示簇i中的数据对象的真实数量。为了进行公平比较，竞争基线算法及其参数设置遵循表3中列出的原始论文：HS. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276281阈值ε（理论上，设置为初始模型中的数据项和样本），将xt合并到1http：//www. ics. 乌奇岛edu/mmlearn/MLepository。HTML.S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276282图3.第三章。不 同 聚 类 算 法 的聚类纯度。表2数据集。数据集#对象#属性#集群KDDCUP99 494 020 42 23CoverType 581 012 54 7魔术19 020 11 2图像分割2310 19 7见图4。KDDCUP99数据集上不同速度下的聚类纯度。5.1. 实验结果AAPStream和其他基线算法的聚类纯度如图所示。3 .第三章。结果是用恒定流速每时间单位1000点计算的，表3算法及其参数值。算法值DenStreamInitNumber= 1000，λ= 0。25，μ=16，μ=10，β= 0。2.StrAPInitNumber= 1000，M= 100，△ = 50和λ= 0。01.CluStreamInitNumber= 1000，m= 100，k= 10 AAPStream缓冲区大小= 100，λ = 0。98.图像分割数据集（每时间单位100点）。一般来说，AAPStream 在 所 有 数 据 集 上 获 得 最 高 的 纯 度 值 。AAPStream的性能明显优于StrAP和CluStream等聚类方法。例如，在KDDCUP99数据集上，AAPStream获得的平均纯度= 81%，比DenStream高5%，比StrAP算法高14%。此外，在CoverType数据集上，AAPStream获得了纯度=84%，比DenStream高7% 然而，在一些数据集上，如magic，AAPStream算法的纯度不如CluStream算法。影响聚类效果的主要因素是在初始模型中选择的样本集如果样本选择不当，聚类结果可能会下降。因此，在更新流模型时，删除不提供信息的示例。我们还评估了AAPStream的纯度，KDDCUP 99数据集上的流速率（1000、5000、10 000点/单位），如图4所示。结果解释了S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276283图五、 不同衰减因子值的聚类纯度。图第六章 不同缓冲液大小下的聚类纯度。纯度在不同流速下是稳定的。但随着转速的增加，纯度下降不大。然而，AAPStream即使在更高的速率下仍然稳定。5.2. 敏感性分析衰减因子和缓冲区大小这两个参数控制AAPStream的聚类性能。衰减因子λ参数的值决定了历史数据对当前聚类的重要性。我们通过λ从0.1到3的范围来评估聚类纯度。图5显示了改变λ时的聚类纯度。较小的λ值会对所有数据集产生较差的聚类纯度。此外，较大的λ值获得较低的聚类纯度。从图5，当λ值在0.8 ~ 1.2范围内时，纯度非常稳定。我们解释了缓冲区大小对聚类纯度的影响，并将设置值从50更改为500。如图6所示，聚类质量达到最佳纯度，直到缓冲区大小= 100。当缓冲液容量增大时，纯度降低。因此，缓冲区大小参数的小值6. 结论和今后的工作针对数据量不断增加和动态变化的流数据，提出了一种AAPStream算法。我们建立了基于主动亲和传播的流模型。它可以检测到最丰富的样本，利用可用的标记数据，提高聚类精度。此外，AAPStream还控制模型中样本的数量。因此，新的样本被添加，旧的样本被从模型中删除。在真实数据集上的实验结果表明了AAP-Stream算法对数据流聚类的有效性。然而，由于手动调整参数和高维数据流 的 挑 战 ， AAPStream 仍 然 存 在 一 些 挑 战 。 扩 展AAPStream以解决这些挑战是我们未来工作的一部分。竞合利益作者声明，他们没有已知的可能影响本文所报告工作引用[1] Y. W.阿米尼，H。基于密度的数据流聚类算法综述，J。Comput.Sci. Tech. 29（1）（2014）116[2] J.P. Barddal，H.M. Gomes，F. Enembreck，Sncstream：基于社交网络的数据流聚类算法，在：第30届ACM应用计算年会论文集，萨拉曼卡，西班牙，2015年4月13日至17日，pp. 935-940[3] W. Fan，黄毛菊A. Bifet，挖掘大数据：当前状态和未来预测，SIGKDD Explor。14（2）（2012）1[4] H. Liu，J. Han，F. Nie，X.李，平衡聚类与最小二乘回归，在：第31届AAAI人工智能会议论文集，2月（2017）4-9，旧金山，加利福尼亚州，美国。2017年，页2231-2237[5] B. Frey，D. Dueck，“通过在数据点之间传递消息进行聚类”，Science（2007）972-976。[6] X. Zhang，W. Wang，K. Norvag，M. Sebag，K-AP：GeneratingspecifiedK clusters by efficient affinity propagation ， in ： ICDM ，2010，pp. 1187 -1192年。[7] L. O'callaghan ， N. 米 什 拉 A. Meyerson ， S. 古 哈 河 Motwani ，Streaming-dataalgorithmsforhigh-qualityclustering ， in ：Proceedings 18th International Conference on Data Engineering（685-694），2002。[8] C.C. Aggarwal，J. Han，J. Wang，P.S. Yu，81比92[9] F. Cao，M. Ester，W. Qian，中国山核桃A. Zhou，“基于密度的聚类，一个不断发展的数据流与噪声“，在：SIAM会议上数据挖掘（SDM），2006年，第。326-337。[10] Y.陈湖，澳-地涂，基于网格密度和吸引力的流数据聚类，ACMTrans. 知道。发现。数据3（3）（2009）27，12：1[11] A.阿米尼，H。Saboohi，T. Herawan，T.Y. Wah，MuDi-stream：Amultidensity clustering algorithm for evolving data stream，J. Netw.Comput. 59（2016）370-385。[12] M. Ernest，窄化流中的大数据：计算限制和回归，Inform。Sci.486（2019）379_392.[13] R. Hyde，P. Angelov，A.R. MacKenzie，演化数据流到任意形状集群的完全在线集群，通知。Sci. 382-383（2017）96-114。S. Abdulah，W.Atwa和A.M.阿卜杜勒·莫尼姆ICT Express 8（2022）276284[14] I. Ntoutsi，A. Zimek，T. Palpanas，P. Kr otoger，H. Kriegel，基于密度的高维数据流投影聚类，在：第12届SIAM国际数据挖掘会议论文集，阿纳海姆，加利福尼亚州，美国，4月（2012）26-28。2012年，第页987-998.[15] V. Braverman，G. Frahling，H.朗角，澳-地Sohler，L.F.杨，聚类高维动态数据流，在：第34届国际机器学习会议论文集，ICML2017，悉尼，新南威尔士州，澳大利亚，6-11 2017，2017年，pp.576-585[16] X. Zhang C.，中国古猿科富特勒纳角Germain-Renaud，M. Sebag，Datastreamclusteringwithaffinitypropagation，IEEETrans.Knowl.Data Eng.26（7）（2014）1644_1656。[17] J. Sui，Z. Liu，中国粘蝇A.荣格湖Liu，X. Li，动态聚类方案基于改进的STRAP，IEEE Access 6（2018）46157-46166。[18] Y. Li，H. Li，Z.王湾，澳-地Liu，J. Cui，H.杨文，等.数据流聚类算法的研究.北京：计算机科学出版社，2000. （2020年）。[19] M. Escherin，H. Trautmann，Evostream-利 用 空 闲 时 间 的 进 化 流聚类 ，大 数据 研究 。14（2018）101[20] Z. Song，L.F. Yang，P. Zhong，动态几何数据流的灵敏度采样及其在k-聚类中的应用，2018，CoRR，abs/1802。00459.[21] M. Tareq，E.A. Sundararajan，M. Mohd，N.S. Sani，在线聚类使用基 于密 度网 格的 方法 发展数 据流 ，IEEEAccess 8 （2020 ）166472-166490。[22] X. Zhang C.，中国古猿科Furtlehner，M. Sebag，具有亲和传播的数据流，在：关于数据库中的机器学习和知识发现的联合欧洲会议，2008年，第10 0 页。628_643。[23] K.M. Borgwardt，A.Gretton，M.J.Rasch，H.P.克里格尔湾舍尔科普夫，A.J.Smola ， Integratingstructuredbiologicaldatabykernelmaximummeandiscrimination ， Bioinformatics 22 （ 14 ） （ 2006 ）e49-e57。[24] B.K. Sriperumbudur ， A. Gretton ， K. 清 水 湾 Schölkopf ， G.R.Lanckriet，Hilbert空间嵌入与概率测度度量，J. 马赫学习. Res. 11（2010）1517[25] C. Hamdeni，T. Hamrouni，F.B. Charrada，分布式系统中的数据流行性测量：调查和设计方向，J. Netw。Comput. 72（2016）150-161。[26] G. Reali ， M. Femminella ， Two-layernetworkcaching fordifferentservicerequirements，Future Internet 13（4）（2021）85.