一种自适应的稳定高效的聚类方法和系统

暂无

一种自适应的稳定高效的聚类方法和系统
技术领域
[0001] 本发明涉及计算机信息处理技术领域,尤其涉及一种自适应的稳定高效的聚类方法和系统。
背景技术
[0002] 随着计算机信息的快速增长，人们对各类计算机信息的处理需求越来越强烈。聚类算法作为信息处理中非常重要的一类算法，为各种数据管理、人工智能、机器学习提供了基础的聚类功能，在各种信息处理中发挥着重要的角色，
[0003] 在智能移动终端应用普遍的今天，出现了各种各样基于智能移动设备的信息服务，它们需要对各种智能终端提供高效稳定的服务，其中大量的服务都需要用到聚类算法，如移动社交网络中对社交好友的聚类，购物应用中对商品的聚类等。目前大量移动设备终端通过GPS，基站，无线接入点等方式具备了定位能力，因此还产生了许多基于地理位置的服务，而聚类方法则可以为这类服务提供更加丰富和有用的功能，例如分类热点地区聚类。
简单举例，目前的电子地图上往往由用户添加了各类地理标签，如购物、美食、景点等，这些地理标签分散在整个电子地图上。当一个智能手机用户外出旅行或逛街时，他常常需要寻找自己感兴趣的热门商圈，即某一类标签密集的地点，如购物集中的商圈，并获取导航服务。但是通过目前的手机地图查询“购物”却只能得到分散在整个地图上的“购物”标签，让用户难以抉择路线了目标地址。然而通过将这些“购物”标签的有效聚类，即将标签划分为多个密集的子区域（聚类），则能快速发现热门的“购物”商圈。而通过对多个标签，如“购物”和“美食”，的聚类结果进行整合，则能有效的帮助用户发现满足其多种要求的热门商圈。聚类方法能为新 型移动设备带来大量丰富的应用，但是移动终端的应用多样化和计算资源受限的特点则对聚类方法的提出了自适应，稳定，高效的新需求。
[0004] 目前已有多种聚类方法，如常用的k-means和期望最大的方法，虽然它们实现简单快速，但是它们需要预先设置最终分区的数目，这显然使得这样的方法无法适应广泛的应用。因为在大多数应用中用户无法预先获知分区数目，如一个城市究竟有多少个美食聚集地。此外，这两种方法都存在不稳定的现象，即多次运行得到的聚类结果可能不一致。而另一种叫做QT的方法虽然不需预先设置分区数目，并且能获取到稳定的聚类结果，但是它却需要o【(n】3)的计算开销，面对庞大的信息量，对于计算资源受限的移动设备来说，这样的开销往往是难以承受的。
发明内容
[0005] 本发明的目的在于提出一种自适应的稳定高效的聚类方法和系统，以解决计算开销大的问题。
[0006] 为达此目的，本发明采用以下技术方案：
[0007] 一种自适应的稳定高效的聚类方法，包括：
[0008] a获取输入数据的集合为p＝{p1,...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ；
[0009] b将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi,输入数据pi表示集合中的第i个输入数据；
[0010] c令候选聚类Cpi中的输入数据为m个,函数d(pi,pj)为两个输入数据pi,pj之 间距离，计算输入数据pi作为聚类中心的概率为 1≤j≤m；
[0011] d从集合的输入数据中，选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0012] 进一步的，所述将该选出的输入数据对应的候选聚类加入最终聚类之后，进一步包括：
[0013] e从输入数据集合中删除加入最终聚类的输入数据，重新从当前输入数据集合中选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类；
[0014] 判断集合中的输入数据的数量是否为零，如果是，则结束，否则，继续步骤e。
[0015] 一种自适应的稳定高效的聚类系统，包括：
[0016] 初始化模块，用于获取输入数据的集合为p＝{p1,...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ；
[0017] 候选聚类建立模块,用于将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi,输入数据pi表示集合中的第i个输入数据；
[0018] 概率计算模块,用于令候选聚类Cpi中的输入数据为m个,函数d(pi,pj)为两个输入数据pi,pj之间距离,计算输入数据pi作为聚类中心的概率为
[0019] 聚类筛选模块，用于从集合的输入数据中，选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0020] 进一步的，还包括：
[0021] 删除模块，用于从输入数据集合中删除加入最终聚类的输入数据，重新从当前输入数据集合中选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类；
[0022] 第一检测模块，用于判断集合中的输入数据的数量是否为零，如果是，则结束，否则，继续步骤e。
[0023] 本发明的有益效果为：本发明通过提供一种自适应的稳定高效的聚类方法和系统，提出了一种新型的自适应的稳定高效的聚类方法。该方法无需预先设置分区的数目，能自适应输入数据实现恰当的分区。并且该方法针对相同输入能实现稳定的聚类结果。相比传统方法，该方法还具有计算高效性，能实现o(n2)的计算复杂度，使其能适用于目前的各种移动智能终端。
附图说明
[0024] 图1是本发明一种自适应的稳定高效的聚类方法的第一实施例流程图；
[0025] 图2是本发明一种自适应的稳定高效的聚类方法的第二实施例流程图；
[0026] 图3是本发明一种自适应的稳定高效的聚类系统的第一实施例框图；
[0027] 图4是本发明一种自适应的稳定高效的聚类系统的第二实施例框图。
具体实施方式
[0028] 下面结合附图并通过具体实施方式来进一步说明本发明的技术方案。
[0029] 本发明一种自适应的稳定高效的聚类方法的第一实施例流程如图1所示：
[0030] 步骤101，获取输入数据的集合为p＝{p1,...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ；
[0031] 步骤102，将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi,，输入数据pi表示集合中的第i个输入数据；
[0032] 步骤103,令候选聚类Cpi中的输入数据为m个,函数d(pi,pj)为两个输入数据pi,pj之间距离，计算输入数据pi作为聚类中心的概率为
[0033] 步骤104，从集合的输入数据中，选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0034] 本实施例提出一种自适应的稳定高效的聚类方法，该方法无需用户预先设置聚类的数目,可自适应的生成聚类结果，对相同输入数据能实现稳定的聚类结果,相比传统算法,该方法具有高效性,其计算复杂度为o(n2)。
[0035] 本发明一种自适应的稳定高效的聚类方法的第二实施例流程如图2所示：
[0036] 步骤201，获取输入数据的集合为p＝{p1，...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ。
[0037] 设每一个输入数据pi成为聚类中心的概率为qi，初始化所有qi为0。令Cpi为pi对应的聚类，并初始化 初始化聚类结果 令函数d(pi，pj)为两个输入数据pi，pj之间距离的度量。
[0038] 步骤202，将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi，输入数据pi表示集合中的第i个输入数据。
[0039] 步骤203，令候选聚类Cpi中的输入数据为m个，函数d(pi，pj)为两个输入数据pi，pj之间距离，计算输入数据pi作为聚类中心的概率为
[0040] 步骤204，从集合的输入数据中，选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0041] 步骤205，从输入数据集合中删除加入最终聚类的输入数据，重新从当前输入数据集合中选出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0042] 步骤206，判断集合中的输入数据的数量是否为零，如果是，则结束，否则，继续步骤205。
[0043] 本发明自适应的稳定高效的聚类系统的第一实施例框图如图3所示，该系统包括初始化模块310、候选聚类建立模块320、概率计算模块330、聚类筛选模块340。
[0044] 其中，初始化模块310，用于获取输入数据的集合为p＝{p1，...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ；候选聚类建立模块320，用于将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi，输入数据pi表示集合中的第i个输入数据；概率计算模块 330，用于令候选聚类Cpi中的输入数据为m个，函数d(pi，pj)为两个输入数据pi，pj之间距离，计算输入数据pi作为聚类中心的概率为聚类筛选模块340，用于从集合的输入数据中，选
出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。
[0045] 本发明自适应的稳定高效的聚类系统的第二实施例框图如图4所示，包括初始化模块310、候选聚类建立模块320、概率计算模块330、聚类筛选模块340、删除模块350、第一检测模块360。
[0046] 其中，初始化模块310，用于获取输入数据的集合为p＝{p1，...pn}，集合中包括n个输入数据，获取聚类半径的阈值θ；候选聚类建立模块320，用于将pi以及集合中的与输入数据pi的距离小于阈值θ的输入数据都加入输入数据pi对应的候选聚类Cpi，输入数据pi表示集合中的第i个输入数据；概率计算模块330，用于令候选聚类Cpi中的输入数据为m个，函数d(pi，pj)为两个输入数据pi，pj之间距离，计算输入数据pi作为聚类中心的概率为
1≤j≤m；聚类筛选模块340，用于从集合的输入数据中，选
出成为聚类中心概率最大的输入数据，将该选出的输入数据对应的候选聚类加入最终聚类。删除模块350，用于从输入数据集合中删除加入最终聚类的输入数据，重新从当前输入数据集合中选出成为聚类中心概率最大的输入数据，将该选出的输入数据对 应的候选聚类加入最终聚类；第一检测模块360，用于判断集合中的输入数据的数量是否为零，如果是，则结束，否则，继续步骤e。
[0047] 该发明提出的自适应的稳定高效的聚类方法的优点包括：第一，该方法无需预先设置最终聚类的数目，能自适应输入数据实现恰当的聚类，使其能广泛适用于多种应用场景；第二，该方法针对相同输入能实现稳定的聚类结果，可多次重复执行，保证服务的一致性；第三，相比传统方法，该方法具有计算高效性，能实现o(n2)的计算复杂度，使其能适用于目前的各种移动智能终端；第四，该方法得到最终聚类的同时，也得到了每个聚类的中心点。
[0048] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体（Read-Only Memory，ROM）或随机存储记忆体（Random Access Memory，RAM）等。
[0049] 以上结合具体实施例描述了本发明的技术原理。这些描述只是为了解释本发明的原理，而不能以任何方式解释为对本发明保护范围的限制。基于此处的解释，本领域的技术人员不需要付出创造性的劳动即可联想到本发明的其它具体实施方式，这些方式都将落入本发明的保护范围之内。