Android平台下基于改进的K－means酒店信息聚类算法＊

钱 政

（安徽电子信息职业技术学院 信息与智能工程系，安徽 蚌埠 233030）

0 引言

我国“十二五”规划指出，要加快推动现代服务业创新发展。作为关键支撑技术，信息化网络技术和服务领域应进一步融合。特别是随着移动互联网技术逐步成熟并进入应用阶段，手机、平板电脑及移动网络的发展使人们进行住宿、餐饮消费时在预订方式上有了新的选择。在这种趋势下，酒店服务已经从传统媒介宣传逐步转变到通过直销平台、团购平台、各知名网络销售平台实现时空全方位的销售和服务。当前的在线预订主要是发布预订信息，由用户主动进行线上预订。在信息发布方面，当前的主流平台如“去哪儿”“艺龙”及各种团购平台均能提供并支持文字检索，客户可根据地理位置、价格、房型、食谱等条件进行综合筛选。只有部分平台提供地图订房和订餐服务。但在大数据时代，这种方式存在着使消费者陷入海量预订信息而不能够有效获得预订目标的困境，为此预订信息优化的必要性异常突出。本课题研究通过对PC端程序进行移植改进，在Android移动端实现K－means聚类算法对酒店预订信息优化挖掘，为其他服务业网络营销及电子商务等类似网络信息检索推荐提供参考。

1 Android移动平台下的酒店预订信息特点分析及预处理

1.1 移动平台下的酒店预订信息特点

为验证大数据情况下酒店预订信息聚类算法，本课题作为某公司预订平台程序优化程序的一部分，对移动平台下酒店预订信息进行分析研究，发现其有以下特点。

（1）数据量大，完整性不高。相对于酒店直销平台，专门的网上预订平台集成了本地大部分酒店资源，数据量较大。以“去哪儿”预订平台为例，2014年8月21日北京市就集成了12 396家酒店信息，考虑到酒店房型、价格、介绍、配置等信息，信息量达到近百万条。由于信息量大，信息来源复杂，导致信息完整性不高。图1是某公司预订平台合肥市酒店信息完整性对比情况。

图1 合肥市酒店信息缺失率Fig.1 Missing rate diagram of hotel information in Hefei

（2）数据更新速度快，数据结构不统一。因酒店信息直接关系到预订能否成功，故平台信息更新速度普遍较快。经统计，98%的酒店直销平台提供的信息能在15min内通过电话及网络方式送达，96%的其他网络平台能在30min到2h内提供更新数据。更新数据接收后，目标平台能在1h内响应，故消费者最慢在3h内就能获得最新的酒店数据。

1.2 酒店信息预处理

由于来源复杂、更新速度快等因素导致酒店信息数据存在完整性和数据冗余等问题，直接采用各种技术手段来提高聚类分析结果的准确性效率较低［1］。通过数据预处理可以处理脏数据，以较高的效率为移动平台下的酒店预订聚类分析提供结构化的数据源。

（1）通过数据清洗解决酒店信息缺失和噪声。在数据缺失方面，针对不同性质的属性采用不同的处理方法。酒店预订价格是关键属性之一，且缺失率较低，因此采用手动填充法通知信息提供方补充，否则整体信息不参与下一步的聚类分析过程。对于位置缺失的情况采用最近邻填充法，该方法会产生一定误差，但结合较低的缺失率考虑对于整体影响较小。对于房型、设施、星级等信息缺失采用价格、位置分类后进行均值填充法补充缺失信息。

（2）数据集成降低数据冗余度，解决数据冲突。对于异类数据源的属性进行数据集成，首先通过对各属性变换性判断后合并同类属性降低数据冗余度，再对同类冲突属性从数据单位、比例和相关性建立冲突解决公式［2］。除此之外对于如酒店评价需要集成为单一数据的信息进行集成，综合各平台信息发布者设立权重Wi，评估该酒店质量。FM为目标平台酒店评分满分数值，FMi和Evaluationi为源平台酒店评价信息满分值及实际得分值，具体计算公式为

（3）通过数据变化和数据归约形成格式统一，有效压缩酒店信息。数据变化可以统一数据格式，为进一步处理提供规范［3］。如位置信息可以转换为经纬度数值，统一处理；酒店评价分值可以转换为满意度的5个等级等。酒店信息数据规约主要进行聚类属性确定，即采用向前选择的方式从经过清理和集成后的属性中选择最佳的若干数据进行聚类，最终参加聚类的酒店信息属性为酒店位置、价格、评价、房型4类。

2 基于改进的K－means的酒店预订信息聚类算法应用

2.1 基于地理位置的酒店信息聚类分析

当消费者选择在地图上选择目标酒店时，算法的目标是在有限的移动端屏幕上合理地显示经过聚类分析的酒店信息。

进行聚类分析时，将所有数据划分为K个聚类，通过迭代法来逐次更新各聚类中心的值以达到较好的聚类效果。K值和中心点的选择对聚类的最终结果影响很大。PC端的屏幕较大，聚类后的信息可以顺利地显示出来，因此K值相对选择大一些的值即可，但移动平台目前很难将这些信息完全显示出来。为达到在保证区分度的前提下地图上酒店信息显示尽量美观，对移动平台上的K值选择从3开始进行试验，保证在试验K值下地图上酒店信息区分度良好且显示美观，没有重叠显示现象。试验获得的K值区间分布如图2所示。

图2 酒店信息合理K值分布Fig.2 Distribution of reasonable K－value about hotel information

原始的K－means算法在K值确定后采用随机的中心点展开聚类［4］，但在移动平台下发现使用这种方式得到的最终结果有较大差异，为此本课题对原始的K－means算法中心点确定方式进行改进。

首先确定质心。将现有数据集按照屏幕显示酒店位置区域划分为K个区块。比较区块中各点之间距离并取位置最短的2家酒店信息形成信息集合纳入聚类Ki，如区块中只有1个位置点则直接设为质心，如果区块中无位置点则在其他区块聚类中心形成后取最近的点设为质心。

形成初始聚类中心后，清除区块信息，将剩余的点按照原始的K－means算法分配给不同的聚类并进行迭代。采用本算法可以在保证准确性的前提下降低迭代次数，提升运算速度，对于硬件资源相对较少的移动平台能有效提升聚类效率。

在地图上确定酒店信息聚类时，经过预处理的酒店位置信息以经纬度表示。此时样本数据可表示为（位置，价格，评价）。设有样本点A，B，则通过样本点的价格和评价属性确定权重系数WA，WB，计算其欧式距离d（A，B），再取其加权距离值确定中心点，并按改进的中心点确定算法进行迭代聚类。

2.2 屏幕滑动情况下酒店信息聚类分析

在地图上进行滑动来改变显示的区域是Android系统下一种常见操作。此时显示地图区域的改变导致显示的酒店信息有所更新，需要去除被遮盖的酒店信息并加入新显示的信息，对更新后的酒店信息重新进行聚类分析。

设滑动前屏幕显示信息为S1，滑动后将显示的信息为S2。判断滑动距离和屏幕尺寸，如果滑动距离超过屏幕尺寸，则S1和S2无重叠部分，此时直接显示新数据。否则S1和S2有公共区域S′，此时系统只需处理新增数据Sadd＝S2－S′。

显示信息确定后，如S1和S2无重叠部分，直接按照改进的中心点确定算法进行迭代聚类；如果存在公共区域S′，此时计算公共区域S′占整个屏幕比例，并依次重新划分区块，对于S′区域内信息进行重用，新增显示区域Sadd则按照改进的中心点确定算法进行迭代聚类。

3 实验与结果分析

基于改进的K－means的酒店预订信息聚类算法及思想通过某公司预订平台移动客户端酒店预订部分程序进行验证。该平台数据集来源于其合作平台检索结果，因此将数据预处理放在平台服务器端进行。测试移动平台为小米手机，型号为1S，屏幕尺寸4英寸，分辨率为854×480（FWVGA），CPU为高通Adreno220，该手机配置在当前属于中等水平，具有较强的代表性。实验首先确定酒店信息检索条件，再运行移动客户端，分别记录采用本课题聚类算法前后数值，得出聚类前后酒店信息运算量对比，如表1所示。其中成功率指单次点击酒店图标成功操作的比例。

表1 聚类前后运算量对比Table 1 Ccomparison of computation cluster

从表1可以看出，进行聚类分析后，数据流量和用户体验均有所提升，其中用户点击焦点优化为原始数据的13.7%，从而大大提升了用户在移动端的操作便捷程度。测试对比如图3所示。

同时还测试了屏幕滑动时客户端运算时间。测试首先对移动前后屏幕公共区域占比进行划分，选择其中7组样本，分别测试按照K－means聚类算法重新聚类或者按照改进的聚类算法进行分析，测试结果见表2。

从测试结果可以看出，根据移动端滑动操作改进后的聚类算法在移动后公共区域达40%以上时，执行效率提升达到49.4%及以上，效果明显。

图3 聚类前后酒店显示对比Fig.3 Comparison of hotel information clustering

表2 屏幕滑动时聚类性能Table 2 Clustering performance based on sliding screen

4 总结

实验结果表明，通过基于改进的K－means的酒店预订信息聚类算法对移动端酒店预订程序进行聚类，数据运算量有明显提升。克服了将PC端程序直接移植到移动端的情况下导致的操作不便，通过提供聚类的结果减轻用户操作难度。并对移动端常见的屏幕滑动操作进行优化处理，提出数据重用及该情况下迭代聚类的思想，取得较好的效果。

本文针对移动终端硬件资源弱于PC机和主显示屏较小的不足，提升用户在手机上进行大数据浏览的操作。实现将酒店信息和地图位置有效结合显示，为移动互联网现代服务业中的电子商务、在线营销等进行大批量数据分类显示提供了参考方案。

［1］ 胡朝清.K－means算法研究［J］.长春工业大学学报：自然科学版，2014，35（4）：139－142.

［2］ 李萍.基于Hadoop的K－Means聚类算法在高校图书馆工作中的应用研究［J］.图书情报论坛，2014，108（2）：30－35.

［3］ 王朔，顾进广.基于K值改进的K－means算法在入侵检测中的应用［J］.工业控制计算机，2014，27（7）：93－97.

［4］ 唐春生，金以慧.基于聚类特性的大规模文本聚类算法研究［J］.计算机科学，2002，29（9）：13－15.