Android平臺(tái)下基于改進(jìn)的K－means酒店信息聚類算法＊

錢 政

（安徽電子信息職業(yè)技術(shù)學(xué)院 信息與智能工程系，安徽 蚌埠 233030）

0 引言

我國(guó)“十二五”規(guī)劃指出，要加快推動(dòng)現(xiàn)代服務(wù)業(yè)創(chuàng)新發(fā)展。作為關(guān)鍵支撐技術(shù)，信息化網(wǎng)絡(luò)技術(shù)和服務(wù)領(lǐng)域應(yīng)進(jìn)一步融合。特別是隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)逐步成熟并進(jìn)入應(yīng)用階段，手機(jī)、平板電腦及移動(dòng)網(wǎng)絡(luò)的發(fā)展使人們進(jìn)行住宿、餐飲消費(fèi)時(shí)在預(yù)訂方式上有了新的選擇。在這種趨勢(shì)下，酒店服務(wù)已經(jīng)從傳統(tǒng)媒介宣傳逐步轉(zhuǎn)變到通過(guò)直銷平臺(tái)、團(tuán)購(gòu)平臺(tái)、各知名網(wǎng)絡(luò)銷售平臺(tái)實(shí)現(xiàn)時(shí)空全方位的銷售和服務(wù)。當(dāng)前的在線預(yù)訂主要是發(fā)布預(yù)訂信息，由用戶主動(dòng)進(jìn)行線上預(yù)訂。在信息發(fā)布方面，當(dāng)前的主流平臺(tái)如“去哪兒”“藝龍”及各種團(tuán)購(gòu)平臺(tái)均能提供并支持文字檢索，客戶可根據(jù)地理位置、價(jià)格、房型、食譜等條件進(jìn)行綜合篩選。只有部分平臺(tái)提供地圖訂房和訂餐服務(wù)。但在大數(shù)據(jù)時(shí)代，這種方式存在著使消費(fèi)者陷入海量預(yù)訂信息而不能夠有效獲得預(yù)訂目標(biāo)的困境，為此預(yù)訂信息優(yōu)化的必要性異常突出。本課題研究通過(guò)對(duì)PC端程序進(jìn)行移植改進(jìn)，在Android移動(dòng)端實(shí)現(xiàn)K－means聚類算法對(duì)酒店預(yù)訂信息優(yōu)化挖掘，為其他服務(wù)業(yè)網(wǎng)絡(luò)營(yíng)銷及電子商務(wù)等類似網(wǎng)絡(luò)信息檢索推薦提供參考。

1 Android移動(dòng)平臺(tái)下的酒店預(yù)訂信息特點(diǎn)分析及預(yù)處理

1.1 移動(dòng)平臺(tái)下的酒店預(yù)訂信息特點(diǎn)

為驗(yàn)證大數(shù)據(jù)情況下酒店預(yù)訂信息聚類算法，本課題作為某公司預(yù)訂平臺(tái)程序優(yōu)化程序的一部分，對(duì)移動(dòng)平臺(tái)下酒店預(yù)訂信息進(jìn)行分析研究，發(fā)現(xiàn)其有以下特點(diǎn)。

（1）數(shù)據(jù)量大，完整性不高。相對(duì)于酒店直銷平臺(tái)，專門的網(wǎng)上預(yù)訂平臺(tái)集成了本地大部分酒店資源，數(shù)據(jù)量較大。以“去哪兒”預(yù)訂平臺(tái)為例，2014年8月21日北京市就集成了12 396家酒店信息，考慮到酒店房型、價(jià)格、介紹、配置等信息，信息量達(dá)到近百萬(wàn)條。由于信息量大，信息來(lái)源復(fù)雜，導(dǎo)致信息完整性不高。圖1是某公司預(yù)訂平臺(tái)合肥市酒店信息完整性對(duì)比情況。

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

（2）數(shù)據(jù)更新速度快，數(shù)據(jù)結(jié)構(gòu)不統(tǒng)一。因酒店信息直接關(guān)系到預(yù)訂能否成功，故平臺(tái)信息更新速度普遍較快。經(jīng)統(tǒng)計(jì)，98%的酒店直銷平臺(tái)提供的信息能在15min內(nèi)通過(guò)電話及網(wǎng)絡(luò)方式送達(dá)，96%的其他網(wǎng)絡(luò)平臺(tái)能在30min到2h內(nèi)提供更新數(shù)據(jù)。更新數(shù)據(jù)接收后，目標(biāo)平臺(tái)能在1h內(nèi)響應(yīng)，故消費(fèi)者最慢在3h內(nèi)就能獲得最新的酒店數(shù)據(jù)。

1.2 酒店信息預(yù)處理

由于來(lái)源復(fù)雜、更新速度快等因素導(dǎo)致酒店信息數(shù)據(jù)存在完整性和數(shù)據(jù)冗余等問(wèn)題，直接采用各種技術(shù)手段來(lái)提高聚類分析結(jié)果的準(zhǔn)確性效率較低［1］。通過(guò)數(shù)據(jù)預(yù)處理可以處理臟數(shù)據(jù)，以較高的效率為移動(dòng)平臺(tái)下的酒店預(yù)訂聚類分析提供結(jié)構(gòu)化的數(shù)據(jù)源。

（1）通過(guò)數(shù)據(jù)清洗解決酒店信息缺失和噪聲。在數(shù)據(jù)缺失方面，針對(duì)不同性質(zhì)的屬性采用不同的處理方法。酒店預(yù)訂價(jià)格是關(guān)鍵屬性之一，且缺失率較低，因此采用手動(dòng)填充法通知信息提供方補(bǔ)充，否則整體信息不參與下一步的聚類分析過(guò)程。對(duì)于位置缺失的情況采用最近鄰填充法，該方法會(huì)產(chǎn)生一定誤差，但結(jié)合較低的缺失率考慮對(duì)于整體影響較小。對(duì)于房型、設(shè)施、星級(jí)等信息缺失采用價(jià)格、位置分類后進(jìn)行均值填充法補(bǔ)充缺失信息。

（2）數(shù)據(jù)集成降低數(shù)據(jù)冗余度，解決數(shù)據(jù)沖突。對(duì)于異類數(shù)據(jù)源的屬性進(jìn)行數(shù)據(jù)集成，首先通過(guò)對(duì)各屬性變換性判斷后合并同類屬性降低數(shù)據(jù)冗余度，再對(duì)同類沖突屬性從數(shù)據(jù)單位、比例和相關(guān)性建立沖突解決公式［2］。除此之外對(duì)于如酒店評(píng)價(jià)需要集成為單一數(shù)據(jù)的信息進(jìn)行集成，綜合各平臺(tái)信息發(fā)布者設(shè)立權(quán)重Wi，評(píng)估該酒店質(zhì)量。FM為目標(biāo)平臺(tái)酒店評(píng)分滿分?jǐn)?shù)值，F(xiàn)Mi和Evaluationi為源平臺(tái)酒店評(píng)價(jià)信息滿分值及實(shí)際得分值，具體計(jì)算公式為

（3）通過(guò)數(shù)據(jù)變化和數(shù)據(jù)歸約形成格式統(tǒng)一，有效壓縮酒店信息。數(shù)據(jù)變化可以統(tǒng)一數(shù)據(jù)格式，為進(jìn)一步處理提供規(guī)范［3］。如位置信息可以轉(zhuǎn)換為經(jīng)緯度數(shù)值，統(tǒng)一處理；酒店評(píng)價(jià)分值可以轉(zhuǎn)換為滿意度的5個(gè)等級(jí)等。酒店信息數(shù)據(jù)規(guī)約主要進(jìn)行聚類屬性確定，即采用向前選擇的方式從經(jīng)過(guò)清理和集成后的屬性中選擇最佳的若干數(shù)據(jù)進(jìn)行聚類，最終參加聚類的酒店信息屬性為酒店位置、價(jià)格、評(píng)價(jià)、房型4類。

2 基于改進(jìn)的K－means的酒店預(yù)訂信息聚類算法應(yīng)用

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

當(dāng)消費(fèi)者選擇在地圖上選擇目標(biāo)酒店時(shí)，算法的目標(biāo)是在有限的移動(dòng)端屏幕上合理地顯示經(jīng)過(guò)聚類分析的酒店信息。

進(jìn)行聚類分析時(shí)，將所有數(shù)據(jù)劃分為K個(gè)聚類，通過(guò)迭代法來(lái)逐次更新各聚類中心的值以達(dá)到較好的聚類效果。K值和中心點(diǎn)的選擇對(duì)聚類的最終結(jié)果影響很大。PC端的屏幕較大，聚類后的信息可以順利地顯示出來(lái)，因此K值相對(duì)選擇大一些的值即可，但移動(dòng)平臺(tái)目前很難將這些信息完全顯示出來(lái)。為達(dá)到在保證區(qū)分度的前提下地圖上酒店信息顯示盡量美觀，對(duì)移動(dòng)平臺(tái)上的K值選擇從3開始進(jìn)行試驗(yàn)，保證在試驗(yàn)K值下地圖上酒店信息區(qū)分度良好且顯示美觀，沒(méi)有重疊顯示現(xiàn)象。試驗(yàn)獲得的K值區(qū)間分布如圖2所示。

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

原始的K－means算法在K值確定后采用隨機(jī)的中心點(diǎn)展開聚類［4］，但在移動(dòng)平臺(tái)下發(fā)現(xiàn)使用這種方式得到的最終結(jié)果有較大差異，為此本課題對(duì)原始的K－means算法中心點(diǎn)確定方式進(jìn)行改進(jìn)。

首先確定質(zhì)心。將現(xiàn)有數(shù)據(jù)集按照屏幕顯示酒店位置區(qū)域劃分為K個(gè)區(qū)塊。比較區(qū)塊中各點(diǎn)之間距離并取位置最短的2家酒店信息形成信息集合納入聚類Ki，如區(qū)塊中只有1個(gè)位置點(diǎn)則直接設(shè)為質(zhì)心，如果區(qū)塊中無(wú)位置點(diǎn)則在其他區(qū)塊聚類中心形成后取最近的點(diǎn)設(shè)為質(zhì)心。

形成初始聚類中心后，清除區(qū)塊信息，將剩余的點(diǎn)按照原始的K－means算法分配給不同的聚類并進(jìn)行迭代。采用本算法可以在保證準(zhǔn)確性的前提下降低迭代次數(shù)，提升運(yùn)算速度，對(duì)于硬件資源相對(duì)較少的移動(dòng)平臺(tái)能有效提升聚類效率。

在地圖上確定酒店信息聚類時(shí)，經(jīng)過(guò)預(yù)處理的酒店位置信息以經(jīng)緯度表示。此時(shí)樣本數(shù)據(jù)可表示為（位置，價(jià)格，評(píng)價(jià)）。設(shè)有樣本點(diǎn)A，B，則通過(guò)樣本點(diǎn)的價(jià)格和評(píng)價(jià)屬性確定權(quán)重系數(shù)WA，WB，計(jì)算其歐式距離d（A，B），再取其加權(quán)距離值確定中心點(diǎn)，并按改進(jìn)的中心點(diǎn)確定算法進(jìn)行迭代聚類。

2.2 屏幕滑動(dòng)情況下酒店信息聚類分析

在地圖上進(jìn)行滑動(dòng)來(lái)改變顯示的區(qū)域是Android系統(tǒng)下一種常見操作。此時(shí)顯示地圖區(qū)域的改變導(dǎo)致顯示的酒店信息有所更新，需要去除被遮蓋的酒店信息并加入新顯示的信息，對(duì)更新后的酒店信息重新進(jìn)行聚類分析。

設(shè)滑動(dòng)前屏幕顯示信息為S1，滑動(dòng)后將顯示的信息為S2。判斷滑動(dòng)距離和屏幕尺寸，如果滑動(dòng)距離超過(guò)屏幕尺寸，則S1和S2無(wú)重疊部分，此時(shí)直接顯示新數(shù)據(jù)。否則S1和S2有公共區(qū)域S′，此時(shí)系統(tǒng)只需處理新增數(shù)據(jù)Sadd＝S2－S′。

顯示信息確定后，如S1和S2無(wú)重疊部分，直接按照改進(jìn)的中心點(diǎn)確定算法進(jìn)行迭代聚類；如果存在公共區(qū)域S′，此時(shí)計(jì)算公共區(qū)域S′占整個(gè)屏幕比例，并依次重新劃分區(qū)塊，對(duì)于S′區(qū)域內(nèi)信息進(jìn)行重用，新增顯示區(qū)域Sadd則按照改進(jìn)的中心點(diǎn)確定算法進(jìn)行迭代聚類。

3 實(shí)驗(yàn)與結(jié)果分析

基于改進(jìn)的K－means的酒店預(yù)訂信息聚類算法及思想通過(guò)某公司預(yù)訂平臺(tái)移動(dòng)客戶端酒店預(yù)訂部分程序進(jìn)行驗(yàn)證。該平臺(tái)數(shù)據(jù)集來(lái)源于其合作平臺(tái)檢索結(jié)果，因此將數(shù)據(jù)預(yù)處理放在平臺(tái)服務(wù)器端進(jìn)行。測(cè)試移動(dòng)平臺(tái)為小米手機(jī)，型號(hào)為1S，屏幕尺寸4英寸，分辨率為854×480（FWVGA），CPU為高通Adreno220，該手機(jī)配置在當(dāng)前屬于中等水平，具有較強(qiáng)的代表性。實(shí)驗(yàn)首先確定酒店信息檢索條件，再運(yùn)行移動(dòng)客戶端，分別記錄采用本課題聚類算法前后數(shù)值，得出聚類前后酒店信息運(yùn)算量對(duì)比，如表1所示。其中成功率指單次點(diǎn)擊酒店圖標(biāo)成功操作的比例。

表1 聚類前后運(yùn)算量對(duì)比Table 1 Ccomparison of computation cluster

從表1可以看出，進(jìn)行聚類分析后，數(shù)據(jù)流量和用戶體驗(yàn)均有所提升，其中用戶點(diǎn)擊焦點(diǎn)優(yōu)化為原始數(shù)據(jù)的13.7%，從而大大提升了用戶在移動(dòng)端的操作便捷程度。測(cè)試對(duì)比如圖3所示。

同時(shí)還測(cè)試了屏幕滑動(dòng)時(shí)客戶端運(yùn)算時(shí)間。測(cè)試首先對(duì)移動(dòng)前后屏幕公共區(qū)域占比進(jìn)行劃分，選擇其中7組樣本，分別測(cè)試按照K－means聚類算法重新聚類或者按照改進(jìn)的聚類算法進(jìn)行分析，測(cè)試結(jié)果見表2。

從測(cè)試結(jié)果可以看出，根據(jù)移動(dòng)端滑動(dòng)操作改進(jìn)后的聚類算法在移動(dòng)后公共區(qū)域達(dá)40%以上時(shí)，執(zhí)行效率提升達(dá)到49.4%及以上，效果明顯。

圖3 聚類前后酒店顯示對(duì)比Fig.3 Comparison of hotel information clustering

表2 屏幕滑動(dòng)時(shí)聚類性能Table 2 Clustering performance based on sliding screen

4 總結(jié)

實(shí)驗(yàn)結(jié)果表明，通過(guò)基于改進(jìn)的K－means的酒店預(yù)訂信息聚類算法對(duì)移動(dòng)端酒店預(yù)訂程序進(jìn)行聚類，數(shù)據(jù)運(yùn)算量有明顯提升?？朔藢C端程序直接移植到移動(dòng)端的情況下導(dǎo)致的操作不便，通過(guò)提供聚類的結(jié)果減輕用戶操作難度。并對(duì)移動(dòng)端常見的屏幕滑動(dòng)操作進(jìn)行優(yōu)化處理，提出數(shù)據(jù)重用及該情況下迭代聚類的思想，取得較好的效果。

本文針對(duì)移動(dòng)終端硬件資源弱于PC機(jī)和主顯示屏較小的不足，提升用戶在手機(jī)上進(jìn)行大數(shù)據(jù)瀏覽的操作。實(shí)現(xiàn)將酒店信息和地圖位置有效結(jié)合顯示，為移動(dòng)互聯(lián)網(wǎng)現(xiàn)代服務(wù)業(yè)中的電子商務(wù)、在線營(yíng)銷等進(jìn)行大批量數(shù)據(jù)分類顯示提供了參考方案。

［1］ 胡朝清.K－means算法研究［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，35（4）：139－142.

［2］ 李萍.基于Hadoop的K－Means聚類算法在高校圖書館工作中的應(yīng)用研究［J］.圖書情報(bào)論壇，2014，108（2）：30－35.

［3］ 王朔，顧進(jìn)廣.基于K值改進(jìn)的K－means算法在入侵檢測(cè)中的應(yīng)用［J］.工業(yè)控制計(jì)算機(jī)，2014，27（7）：93－97.

［4］ 唐春生，金以慧.基于聚類特性的大規(guī)模文本聚類算法研究［J］.計(jì)算機(jī)科學(xué)，2002，29（9）：13－15.