沙特国王大学学报一种有效的基于k-均值聚类的移动网络小区站点管理方案Jocelyn Edinio Zacko Gbadoubissaa，c，Ado Adamou Abba Arib，c， Abdelhak Mourad Guerouiba非洲数学科学研究所（AIMS-喀麦隆），P.O. Box 608，Limbé，喀麦隆bLI-PaRAD Lab，Université Paris Saclay，University of Versailles Saint-Quentin-en-Yvelines，45 Avenue des États-Unis，78035 Versailles cedex，Francec马鲁阿大学LaRI实验室，邮政编码。Box 814，Maroua，喀麦隆阿提奇莱因福奥文章历史记录：接收日期：2018年2018年10月8日修订2018年10月30日接受在线发售2018年关 键 词 ：聚类K均值圆的几何形状移动网络OpenCellIDA B S T R A C T非洲和中东地区的电信网络基础设施是在具有挑战性的环境中部署和运营的，这些环境高度分散，特别是在农村地区。此外，相当数量的小区站点位于难以接入的区域中。此外，农村地区的低收入不允许快速的投资回报，因为小区站点的部署和运营成本相当可观。这些问题导致人力资源管理困难，特别是在将技术人员分配到小区站点进行维护时。本文提出了一种优化小区站点维护成本的方案。我们使用的k-means聚类算法分配-ING现场技术人员的细胞网站的池。此外，为了减轻k-means对初始化的敏感性，我们提出了一种基于球体几何形状的初始化方法。我们进行了一系列的实验与样品的数千个细胞塔从OpenCellID和结果证明了该建议的有效性。©2018作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍1.1. 背景信息和通信技术在非洲和发展中国家的发展中发挥着关键在过去的十年中，非洲和中东的电信市场的渗透率增长和盈利能力远远高于平均水平。 这些地区在2015年占全球电信市场的8%，并贡献了近20%的经济利润池（Boniecki等人，2016年）。根据国际金融公司2013年进行的一项研究，尼日利亚和加纳的移动用户数量分别达到107和25* 通讯作者：LI-PaRAD实验室，巴黎萨克雷大学，凡尔赛圣昆廷大学，45 Avenue desÉtats-Unis，78035 Versailles cedex，France。电子邮件地址：adoadamou. gmail.com（A.A.A. Ari），Mourad. uvsq.fr（上午）。Gueroui）。沙特国王大学负责同行审查百万分别。这一基础是由移动普及率的强劲增长和80%人口的移动覆盖率推动的。这两个国家加起来总共有35000个站点，其中50%位于没有商业电网的地区，大多数位于农村偏远地区，通常难以进入。这妨碍了运营商有效地对网络进行维护操作。因此，这种情况会影响维护操作的成本、网络可用性、服务质量和体验质量。在 发 展 中 国 家 ， Vodaphone 、 Vodacom 、 Orange 、 MobileTelephone Network（MTN）和Airtel等移动网络运营商倾向于放弃手机信号塔管理，以专注于服务提供。 爱立信、非洲太阳神塔、伊顿塔、IHS塔和美国塔公司等塔公司都承包了电信塔的管理。不幸的是，非洲的MNO和铁塔公司面临着许多挑战，例如现有被动基础设施的设备监测和维护、操作泄漏（柴油盗窃）、安全、监视和环境控制。尽管如此，智能站点资产管理解决方案已经开发出来，其目标是最大限度地提高服务交付潜力和效益，同时最大限度地降低相关风险和成本（Dietrich，2016）。https://doi.org/10.1016/j.jksuci.2018.10.0151319-1578/©2018作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com1064J.E.Z. Gbadoubissa等人/沙特国王大学学报DK第1页XX.XðÞK.Σ2尽管有这些解决方案，铁塔公司还是使用现场技术人员来确保现场资产管理工具无法执行的一些维护任务。这些任务可以是加燃料、修复小区站点上的物理损坏以及与维护和操作小区站点相关的其他活动。因此，一些铁塔公司采用将现场技术人员分配到小区站点池的策略;并且技术人员被定位到预定位置，使得他可以容易地移动到每个站点。在小区站点由于例如物理损坏而不能工作的情况下，需要负责的现场技术人员到关键站点来解决问题。然而，在非洲和中东，几个小区站点位于难以访问的区域，特别是在农村偏远地区，使得将技术人员移动到这些站点在时间和金钱上是非常昂贵的操作。因此，在本文中，我们研究了技术人员的最佳预定位置和小区站点的最佳分配，使得由于现场技术人员和维护操作的成本最小化。这个问题可以被认为是基于它们的相似性的分组对象。换句话说，这个问题可以被同化为聚类问题。给定d维空间中的n个对象的集合和整数kP2，k-聚类问题被定义为找到k个组中的n个对象的划分，称为聚类，以这种方式，1.3. 文件的结构本文的其余部分组织如下：第2节，我们研究了使用的k-means算法;在第3节中，k-聚类问题和适应度函数的推导;第4节提出了我们提出的几何初始化方案;然后这是后续的性能评估在第5节;最后，结论和未来的工作方向在第6节中给出。2. K-means算法k-means算法属于排他性聚类类。由于其简单性，它是在过去几十年中已经研究的著名聚类方法之一（Celebi等人，2013年，2012年）。它是一种矢量量化方法，最初用于信号处理。k-means算法首先随机选择k个聚类中心。然后，它将每个数据点分配到相对于欧几里德距离度量的最近中心。接下来，它重新计算所有聚类中心的位置。它重复最后两个步骤，直到没有点可以从一个簇移动到另一个簇。算法1：k-means优化目标函数（Ari等人，2016; Rahman等人，2015; Wu，2012; Moussaoui等人，2006; Tan等人，2005年）。找到优化目标函数的理想分区是困难的，并且使得k聚类问题是NP困难的（Ari等人，2018; Titouna等人， 2018年; Kel 'manov和Pyatkin，2015年; Zeroev等人，2014年）。然而，一些研究人员提出了寻求近似分区的方法，也称为局部最优（Lloyd，1982）。k-means 算 法 是 著 名 的 k- 聚 类 算 法 之 一 ， 它 寻 求 近 似 解（Steinley，2006）。k-means使用欧氏距离作为相似性度量，将对象聚集到同一个聚类中。它被广泛研究和使用。尽管它的流行，k-均值遭受一些问题，如它的初始聚类中心的敏感性。考虑到在一个2维空间中的n个对象和技术人员的数量为整数k的小区站点，我们的工作是适应k-均值算法相对于在此解决的问题，本文1.2. 作者的贡献本文的目的之一是解决电信领域的资源在我们的背景下，我们认为技术人员是资源。在本文中，我们解决了在农村地区的移动网络小区站点集群的问题。我们将k-聚类作为一个图论问题。我们采用k-means算法将一组数据点划分为多个聚类，同时最小化平方误差和（SSE）或聚类间。我们提出了一种基于球体几何的初始化方法，称为几何初始化，以定位k个初始聚类中心。我们进行了密集的模拟和结果表明，我们的方法优于随机初始化。简而言之，我们的主要贡献可以总结如下：基于图论的k-聚类问题公式化k-means算法在聚类划分中的应用。基于圆几何的几何初始化方案的提出。模拟所提出的方案，以证明其有效性相比，现有的计划。其中：● cj表示聚类中心，其中cj2R;16j6k和kn;<● 其中Cj=S;\j<$1Cj<$;S16j6k;每个集群与成本Intra C j相关联由方程式（一）.帧内Cj½ kx-cjk2：101x2Cjk-means算法的目标是将n个数据点的集合S划分为k个聚类，使得在等式（1）中给出（2）最小化。KFS;kkx-cjk21x2Cj从定理1的证明中，我们可以找到一个实数a>0，使得由F的最小化所表示的问题被简化为P2。2.1. k-均值算法尽管k-means算法很受欢迎，但它存在一些问题。主要的一个是它对初始化的敏感性。实际上，k个初始聚类中心的随机选择影响●●●●J.E.Z. Gbadoubissa等人/沙特国王大学学报1065-.XþKtthKK¼ttht1获得的集群的质量。为了克服这个问题，在（Zhang et al.，2015）基于阈值参数创建一组传感器节点候选到初始中心。然后，初始聚类器中心以它们彼此最远的方式被选择。作者（Ray和De，2016）提出了一种用于初始聚类中心选择的中点算法。对于每个点，它找到到原点的距离，然后将点（按距离排序）划分为k组。k个初始中心是它们群的中点。为了改善k-means的结果，一些研究人员使用了种子技术。特别是在k-means++中，随机种子技术被用作标准k-means的初始化方法（Arthur和Vassilvitskii，2007）。为了选择k个初始聚类中心，它首先以随机均匀的方式选择一个中心。然后，以概率p选择剩余的k1个中心（Arthur和Vassilvitskii，2007）。Reddy等人（2012）提出了一种初始化k-means的技术，该技术使用Voronoi图以获得全局最优结果。一些作者提出了确定性方法，如KKZ和PCA部分，用于初始化k均值Su和Dy（2007）。KKZ背后的想法是关注最多的数据点这些数据点彼此相距甚远，因为这些数据点更有可能属于不同的集群（Su和Dy，2007年）。PCA部分从一个聚类（具有最大欧几里德距离平方和的聚类）开始，并将其切成两半。然后，它选择下一个要分区的clus- ter，并重复该过程，直到获得k（Su和Dy，2007）。2.2. k-means聚类算法具有类似行为的客户;在生物学中，对植物和动物进行分类;在保险学中，识别平均索赔成本较高的汽车保险保单持有人群体，并识别欺诈行为。此外，聚类算法应该满足以下要求（Gupta，2014; Kononenko和Kukar，2007）：可扩展性，即，它们可以应用于大量的数据;处理不同类型特征的能力;发现具有任意形状的聚类的能力;确定输入参数对领域知识的最小要求;处理噪声和异常值的能力;对输入记录的顺序不敏感;高维性，这意味着如果我们增加维度的大小，算法仍然可以执行;聚类结果的互操作性和可用性，即，算法的输出此外，聚类分析或聚类存在许多问题，例如：聚类算法不能充分解决所有要求;由于大量数据点和大维度，这些技术的时间复杂度很大;这些算法的有效性取决于度量的定义;以及聚类算法的结果可以以不同的方式解释（Zhang et al.，2017;Rashid，2011）。我们将聚类定义为相似对象的分组，度量相似性的方法主要有两种：距离度量和相似性度量。在这里，我们专注于距离度量来估计数据点之间的相似性。默认情况下，在k-means中，数据点之间的相似性度量是基于欧几里得距离或平方欧几里得距离（参见等式2）。（5））。1k-means聚类算法收敛。为了证明k均值收敛，只要证明Dkx-yk¼1/1xi-yi2号！2其中x;y2Rd：105时间t的目标函数 1小于或等于其值时间t为了解释为什么，考虑如果它是真的，那么没有分区可以被访问两次，因为可能的分区的数量是有限的，并且由等式中给出的斯特林公式给出（三）、1XK J. 金K n3.2. 基于图论的k-聚类问题公式化这个问题可以用图论来表述，其中顶点由欧几里得空间的点定义边的长度由两条边之间的距离国王！j¼ 0-1JJ 快！ ：103点顶点也可以被认为是要聚类的数据点边的权值表示点的接近度（k = ev让我们表示为：● Ft<$S;k<$t时刻的目标函数，● Ck 的k群集在时间t，● Ck 在时间t处的k聚类的中心，● Ft<$1jt <$S;k表示在时间t<$1的目标函数，具有聚类C和中心ct。也就是说，一些数据点已经迁移，但聚类中心的位置尚未更新。我们想证明Ft<$1<$S;k<$2。（KelF1：所有聚类的元素之间的欧几里得距离平方和的总和。F2：聚类的元素到其质心（或聚类中心）的距离平方和之和。3.3. 适应度函数推导让我们通过导出适应度函数来给出上述目标函数F1和F2●●1066J.E.Z. Gbadoubissa等人/沙特国王大学学报ð- Þn¼ ðÞx2C1.ΣX3P2ð- Þ）Xkxi-xk2¼Xkxi-ckk2nkck-xk210kx-yknkkx-ckkþkck-ykn2k-12k-13.3.1. 目标函数F1给定Rd中的n个点x的集合S，找到S分成两个非空子集C1和C2的划分，使得目标函数F1<$S;2<$（参见等式2）。（6）最小化。F1S;2XXkx-yk2XXkx-yk264. 几何初始化方案我们提出了一种新的方法来初始化k-means算法。我们的方法基于Voronoi 图 的 思 想 （ Reddy 等 人 ， 2012 ） 、 k- 均 值 ++ （ Arthur 和Vassilvitskii，2007）、应用于矢量量化的劳埃德x2C1y2C1x2C2y2C2d维欧氏空间中球面的曲率的目的该算法是选择K个初始聚类中心，即， 技术上，3.3.2. 目标函数F2给定Rd中的n个点x的集合S，找到S分成两个非空子集C1和C2的划分，使得目标函数F2<$S;2<$（参见等式2）。（7）最小化。F2S;2n1×Xkx-ckk2n2×Xky-ckk27其中nk^jCkj是Ck的元素数，ck是Ck的质心。3.4. 目标函数让我们把问题P1和P2分别称为由F1和F2的最小化表示的问题（注：也存在着F1和F2最大化的问题）定义1. hx;yi是x和y的内积。定理1. 问题P1和P2是NP难的。为了证明这一点，让我们考虑目标函数F1。然后，我们有：F1S;2XXkx-yk2XXkx-yk2这样的话，他们就可以尽可能的远离对方。4.1. 二维几何初始化给定n个数据点（或对象）和k个初始聚类中心的集合S，首先我们选择第一个聚类中心作为所有点的质量，称之为c0。然后，我们评估欧几里得C0和最远点之间的距离。该距离将被视为圆心为c 0的圆的半径。选择如果我们不考虑剩余的簇中心，我们将需要一些几何考虑。我们把圈子分成K1同行业大小;并将圆心放在将圆分成扇区的线上。每个聚类中心，即，现场技术人员被放置在距质心相等的距离处，并且每两个连续中心之间的距离相等。图图1和图2详细介绍了这一模式的运作。这种初始化技术在算法2中进行了总结。算法2：初始化方案输入：S组n个数据点x x1;x2和k=聚类中心的数量。步骤1：选择第一个聚类中心c0，c0¼1 Px2Sx.x2C1y2C1x2C2y2C2步骤2：找到r：1/4maxx2Skx-c0k，使得1/4Xx2SXy2Skx-yk2-XXy2C2kx-ykð8Þy1-z12y2-z22r2，其中c0z1;z2，且2|fflfflfflfflfflfflfflfflfflfflfflfflfflfflFfflfflqfflmfflffl{cpzðSfflffl;ffl2fflÞfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl}| fflfflfflfflfflfflfflfflfflfflfflfflfflfflFffl fflqfflmfflffl{cpzðSfflffl;ffl2fflÞfflfflfflfflfflfflfflfflfflfflfflfflffl fflffl}是R的任意点。第三步：选择一个中心，即，的所有点其中Const是作为S的点之间的平方距离的总和的常数，并且Fqmcp是二次最大割问题的目标函数。因此，问题P被简化为QMCP。证明坐标cj<$dcoshj;d sinhj，其中d>>：>Fig. 1. 我们的初始化方法的几何描述。4.3. d维几何初始化（d>3）当d> 3时，其余1家中心如下：dcos/1dsin/1cos/2cj¼>dsin/1sin/2cos/3.dsinθ/1π···sinθ/n-2πcosθ/n-1πdsin/1···sin/n-2sin/n-1哪里/1;· · ·;/n-22½0;p]，/n-1½hj，Xkx-ct1k2;）X Xkx-ctk2JJJMoussaoui，O.，Ksentini，A.，Naimi，M.，Gueroui，M.，2006.无线传感器网络中一种新的高效节能分簇算法，2006Kx2Ct1Kx2Ct1KKj¼0x2Ct1计算机网络国际研讨会。IEEE，pp. 六十六比七十二OpenCellID贡献者，2018年。OpenCellID贡献者。http://wiki.opencellid。org/wiki/查看数据，[在线; 2018年5月23日访问]。引用>kx-ct 1k2;i：eFt1jtS;kj¼0x2Ct1> Ft1 S; k：A：5Rahman，M.A.，伊斯兰，M.Z.，Bossomaier，T.，2015. Modex和seed-detective：两种通过在k- means中使用好的初始种子来实现高质量聚类的新技术。 J. 沙特国王大学Comput. INF. Sci. 27（2），113-128。拉希德，T.，2011. 集群。Ray，A.，De，D.，2016年。 基于k-means-midpoint算法的无线传感器网络能量有效分簇协议。IET无线传感系统，6（6），181-191。Reddy，D.，Jana，P.K.，例如，2012.基于Voronoi图的k-means聚类算法。ProcediaTechnol. 4，395-400.Daghev，A.，Kel'manov，A.，Pyatkin，A.，2014.欧氏最大割问题的NP-困难性。数学博士斯普林格343- 345阿里匿名戒酒会Labraoui，N.，Yenke，B.O.，Gueroui，A.，2018.无线传感器网络分簇算法：基于蜂群巢址选择过程的方法。Int. J. Sens. 网络 27（1），1-13。阿里匿名戒酒会Yenke，B.O.，Labraoui，N.，达马科阿岛Gueroui，A.，2016年。无线传感器网络中一种能量有效的分簇路由算法：基于蜜蜂群智能的 方法。 J.网络Comput. Appl. 69，77-97。Arthur，D.，Vassilvitskii，S.，2007年仔细播种的好处在：第十八届年度ACM-SIAM离散算法研讨会论文集。工业与应用数学学会，pp。 1027- 1035Boniecki，D.，马卡蒂角，Abou-Zahr，W.，Alatovic，T.，哈马姆西岛，2016年。中东和非洲：电信业处于悬崖边缘。是时候大胆决定了TMT Practice 1，1-64.切莱比法医Kingravi，H.A.，贝拉，P.A.，2013. k-means聚类算法有效初始化方法的比较研究。Exp. System.Appl.40（1），200-210。Cygan，M.，Lokshtanov，D.，Pilipczuk，M.，Pilipczuk，M.，Saurabh，S.，2014.最小二分法是固定参数的易处理的。在：第四十六届年度ACM计算理论研讨会论文集。ACM，pp.323-332.Dietrich，N.，2016年。铁塔公司和智能站点资产管理。IMQSwww.imqs.co.za 1，1Gupta，G.，2014.介绍数据挖掘与案例研究。深圳市金源科技有限公司Kel'manov，A.，Pyatkin，A.，2015.一类二次欧氏2-聚类问题的NP-困难性。数学博士斯普林格634- 637科诺年科岛，库卡尔，M.，2007.机器学习与数据挖掘：原理与算法导论。霍伍德出版社。Lloyd，S.，1982.脉码调制中的最小二乘量化。IEEE Trans. Inf. Theory 28（2），129-137.Steinley，D.，2006年。K-means clustering：a half century synthesis.Br. J. Math. Stat.Psychol. 59（1），1Su，T.，Dy，J.G.，2007.初始化k-means和高斯混合聚类的确定性方法。内特尔数据分析11（4），319-338.Tan，P.- N.，Steinbach，M.，库马尔，V.，2005.聚类分析：基本概念与算法。在：数据挖掘导论。Pearson International Edition. Pearson Addison Wesley，Boston，pp.487-568.数据科学实验室，2014年。改进了k-means++的聚类种子。https://datasciencelab.wordpress.com/2014/01/15/improved-seeding-for-clustering-with-k-means/，[在线; 2018年5月28日访问]。Titouna角，阿里匿名戒酒会Moumen，H.，2018. Fdra：无线传感器网络故障检测与恢复算法。在：Younas，M.，阿万岛Ghibs，G.，Catalan Cid，M.（编），移动Web与智能信息系统。戴维斯。计算机科学讲义，第10995卷。Springer，Cham，pp. 72比85维基百科贡献者，2018年。奥平塞利-维基百科，自由的百科全书奥平塞利。https://en.wikipedia.org/w/index.php? title=OpenCellID& oldid=840269231，[在线; 2018年5月23日访问]。吴，J.，2012.聚类分析与k均值聚类：导论。上一篇：Advancesin K-means Clustering施普林格，pp. 1-16号。张，G.-是的，王角D、黄，D.，郑文美国，2017年。基于minkowski度量的多视图协作局部自适应聚类。专家系统Appl. 86，307- 320.张玉，孙，H.，余，J.，2015.基于改进k-均值算法的水下无线传感器网络路由协议，2015IEEE自动化、控制和智能系统网络技术国际会议（CYBER）。IEEE，pp. 1304-1309。赵，Q.，2012.聚类方法中的聚类有效性。东芬兰大学出版物。
