基于優(yōu)化模糊遺傳算法的地理信息個(gè)性化推送方法

邵改革，盧小平，杜耀剛，李國(guó)清

（1．河南理工大學(xué) 礦山空間信息技術(shù)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，河南 焦作454003；2．河南北斗空間科技有限公司，河南 鄭州450003；3．河南省遙感測(cè)繪院，河南 鄭州450003）

隨著“數(shù)字城市”成果的廣泛應(yīng)用及“智慧城市”建設(shè)的啟動(dòng)，物聯(lián)網(wǎng)和云計(jì)算等技術(shù)正在迅速發(fā)展，人們生產(chǎn)生活以及各類(lèi)傳感網(wǎng)產(chǎn)生的數(shù)據(jù)已從TB級(jí)增長(zhǎng)到PB級(jí)，進(jìn)入到了智慧城市的“大數(shù)據(jù)時(shí)代”［1－2］。因此，如何從海量數(shù)據(jù)中挖掘有用的信息、提高信息的應(yīng)用價(jià)值，成為當(dāng)前亟待解決的技術(shù)難題。

目前，LBS技術(shù)能夠讓用戶在附近位置根據(jù)興趣點(diǎn)進(jìn)行搜索，但仍沒(méi)有達(dá)到智慧城市的設(shè)想，地理信息應(yīng)該實(shí)現(xiàn)更加智能化、人性化的服務(wù)。面對(duì)龐大的地理空間信息，通過(guò)智能計(jì)算快速檢索和處理，并挖掘其中有用的信息為公眾服務(wù)，以達(dá)到在合適的時(shí)間、關(guān)注的地點(diǎn)，將正確的信息推送給需要的人個(gè)性化服務(wù)。本文通過(guò)運(yùn)用遺傳算法的最優(yōu)搜索特征，結(jié)合神經(jīng)網(wǎng)絡(luò)和模糊分類(lèi)，建立用戶的動(dòng)態(tài)模型，并對(duì)用戶的下一步行為進(jìn)行預(yù)測(cè)，將動(dòng)態(tài)模型過(guò)濾后的各類(lèi)地理空間信息推送給用戶，免去用戶自行搜索的煩惱。

1 關(guān)鍵技術(shù)

1．1 模糊遺傳算法

遺傳算法是一種模擬遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程計(jì)算模型，通過(guò)自然選擇、遺傳、變異等作用機(jī)制，形成全局最優(yōu)化算法［3］。在遺傳算子進(jìn)行選擇、交叉和變異的作用下，原來(lái)具有低階、短定義距和平均適應(yīng)度高于整個(gè)種群平均適應(yīng)度的模式在子代繁衍中得到指數(shù)級(jí)增長(zhǎng)［4］。一個(gè)模式Hi在選擇階段，各模式按照其適應(yīng)度在種群適應(yīng)度中所占的比例m進(jìn)行復(fù)制，若Hi的適應(yīng)度較大，其復(fù)制概率越高，反之則容易丟失。經(jīng)過(guò)選擇后，Hi理論上應(yīng)有m×f（Hi）／favg個(gè)樣本。交叉操作與Hi所定義的距離Di相關(guān)，Di越大，Hi產(chǎn)生交叉的概率就越高。遺傳算法從問(wèn)題解的子集開(kāi)始搜索，并同時(shí)對(duì)空間中的多個(gè)解進(jìn)行評(píng)估，從建立的模型中實(shí)現(xiàn)全局擇優(yōu)［5］。

地理空間數(shù)據(jù)不僅具有空間性、時(shí)間性、復(fù)雜性等特點(diǎn)，還包括空間的不確定性，以及人的思想、行為活動(dòng)等，也存在一定的不確定性，這可以利用模糊集理論引入多準(zhǔn)則決策來(lái)解決實(shí)際建模中的不確定性問(wèn)題［6］。模糊集可根據(jù)自組織、自適應(yīng)特點(diǎn)，采用模糊模型控制諸如時(shí)變、非線性、不確定等復(fù)雜關(guān)系，不斷完善非線性系統(tǒng)的建模與控制［7－8］。通過(guò)對(duì)用戶進(jìn)行分析，建立不同的評(píng)價(jià)指標(biāo)，然后對(duì)指標(biāo)值進(jìn)行模糊化，最后加權(quán)平均反模糊化，可得用戶的權(quán)重輸出：

式中：wi為規(guī)則權(quán)重；αi（x）為輸入值x的模糊度；Vi為集合的容積；ci為集合權(quán)重。每個(gè)權(quán)值計(jì)算過(guò)程中，可以通過(guò)隨機(jī)梯度下降方法調(diào)整權(quán)重，改善模糊系統(tǒng)中的不確定性規(guī)則。隱含層的多層神經(jīng)網(wǎng)絡(luò)解決了多層網(wǎng)絡(luò)中隱含單元連接權(quán)值的學(xué)習(xí)問(wèn)題，其方法是不斷調(diào)整權(quán)值使得整個(gè)網(wǎng)絡(luò)的總誤差最小。假設(shè)輸入的節(jié)點(diǎn)、隱含節(jié)點(diǎn)和輸出節(jié)點(diǎn)分別為Ik，Mk和Ok，wij為網(wǎng)絡(luò)節(jié)點(diǎn)權(quán)值，則輸入層和隱含層的關(guān)系表示為

隱含層到輸出層的權(quán)值矩陣為W，則W的計(jì)算方法：

1．2 改進(jìn)的模糊遺傳算法

遺傳算法雖然可以求解全局最優(yōu)，但收斂速率與局部最優(yōu)形成矛盾，導(dǎo)致因顧及收斂速率而陷入局部最優(yōu) 通過(guò)對(duì)變異算子進(jìn)行改進(jìn) 增加遺傳算法收斂全局最優(yōu)的概率，可快速找到全局最優(yōu)解。改進(jìn)后變異概率Pm自適應(yīng)變化為

式中：Pmax是最大的變異概率，f為變異個(gè)體的適應(yīng)度，fmax是種群最大的適應(yīng)度，favg為適應(yīng)度的平均值，k為自然環(huán)境的擾動(dòng)。當(dāng)試驗(yàn)個(gè)體的適應(yīng)度大于整個(gè)種群的適應(yīng)度時(shí)，該個(gè)體的適應(yīng)性就越強(qiáng)，其發(fā)生變異的概率就越?。环粗?，則適應(yīng)性就較弱，而且為增加種群的多樣性，其突變的概率也越大。改進(jìn)后的遺傳算法可使局部搜索能力顯著增強(qiáng)，達(dá)到全局收斂，提高效率。

本文提出一種基于改進(jìn)的遺傳算法、模糊理論和神經(jīng)網(wǎng)絡(luò)的集成算法，即充分結(jié)合遺傳算法的全局搜索最優(yōu)性、模糊理論處理非線性關(guān)系時(shí)的優(yōu)勢(shì)及神經(jīng)網(wǎng)絡(luò)的自適應(yīng)和學(xué)習(xí)能力等優(yōu)點(diǎn)。假設(shè)待處理數(shù)據(jù)為Y，其每條記錄包含n個(gè)自變量和1個(gè)因變量，其中自變量與因變量呈非線性關(guān)系。利用模糊集合的模糊函數(shù)處理自變量和因變量的映射關(guān)系，建立一個(gè)神經(jīng)網(wǎng)絡(luò)模型，網(wǎng)絡(luò)輸入的節(jié)點(diǎn)數(shù)為n，輸出層的節(jié)點(diǎn)數(shù)為1，隱含層根據(jù)樣本容量而定；然后以神經(jīng)網(wǎng)絡(luò)的輸出值構(gòu)建權(quán)值網(wǎng)絡(luò)，并利用改進(jìn)的遺傳算法優(yōu)化網(wǎng)絡(luò)權(quán)值模型，將遺傳算法和模糊神經(jīng)網(wǎng)絡(luò)模型整合在一起。優(yōu)化后的模糊遺傳算法流程如圖1所示，其中G是當(dāng)代數(shù)，M為每代種群中最大個(gè)體數(shù)。

2 信息個(gè)性化推送服務(wù)的實(shí)現(xiàn)

2．1 推送流程

運(yùn)用模糊遺傳算法建立針對(duì)每個(gè)用戶的動(dòng)態(tài)模型，根據(jù)用戶的興趣、行為習(xí)慣和社會(huì)需求等進(jìn)行地理信息個(gè)性推送服務(wù)。

1）充分收集用戶個(gè)人的興趣信息，利用模糊神經(jīng)網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)建立動(dòng)態(tài)模型，根據(jù)用戶的行為趨勢(shì)不斷進(jìn)行修正，從而建立預(yù)測(cè)模型。

2）將過(guò)濾后的地理空間信息根據(jù)用戶位置進(jìn)行推送，從而實(shí)現(xiàn)了推送個(gè)性化信息。

3）用戶對(duì)接受到的推送信息評(píng)價(jià)后自動(dòng)反饋到動(dòng)態(tài)模型，可對(duì)預(yù)測(cè)模型進(jìn)行不斷修正和完善，如圖2所示。

2．2 搜索匹配

圖1 優(yōu)化后的模糊遺傳算法流程

圖2 信息推送流程

當(dāng)用戶使用關(guān)鍵詞進(jìn)行搜索時(shí)，可自動(dòng)記錄用戶的檢索和查詢情況，通過(guò)分析用戶的查詢結(jié)果來(lái)獲取用戶的使用信息 采用向量模型匹配關(guān)鍵詞的方法可提高索引詞的選擇和語(yǔ)義提取，關(guān)鍵詞在文檔中的權(quán)重定義為

其中：fwi為關(guān)鍵詞w在文檔中的出現(xiàn)概率；N，nw為信息庫(kù)中文檔個(gè)數(shù)和包含關(guān)鍵詞的文檔個(gè)數(shù)；wi是文檔中所有關(guān)鍵詞的個(gè)數(shù)。如果一個(gè)詞條在文檔中出現(xiàn)的次數(shù)越多，其權(quán)重就越大；若一個(gè)詞條在不同的文檔中出現(xiàn)的次數(shù)越多，則其對(duì)于文檔庫(kù)中文檔的區(qū)分能力就越差，即詞條的權(quán)重受到lg（N／nw）的制約。

根據(jù)用戶使用關(guān)鍵詞檢索情況對(duì)用戶進(jìn)行分類(lèi)，這就需要判定用戶查詢與結(jié)果記錄詞條的相關(guān)性，可通過(guò)相似度函數(shù)進(jìn)行計(jì)算，即顧忌文本的長(zhǎng)度和查詢字符串的長(zhǎng)度，具體表達(dá)式為

式中：qi為q的第i個(gè)詞條的權(quán)重；wi為q的第i個(gè)詞條在文檔d中的權(quán)重；｜d｜和｜q｜分別表示文檔和查詢字符串的長(zhǎng)度。

2．3 推送模型

在用戶所處位置P點(diǎn)范圍R內(nèi)，搜索所有符合條件的信息，通過(guò)動(dòng)態(tài)模型進(jìn)行篩選，并按照預(yù)測(cè)模型推送給用戶個(gè)性化服務(wù)信息，這些信息可劃分為吃、住、游、購(gòu)、娛和美共六類(lèi)。根據(jù)用戶的興趣和類(lèi)型進(jìn)行區(qū)分后，可將不同類(lèi)別的信息推送給相應(yīng)的用戶，從而提高了信息推送的質(zhì)量。每條信息選取距離、類(lèi)別、價(jià)格、時(shí)效和好評(píng)共五項(xiàng)指標(biāo)，各個(gè)因子的權(quán)重可根據(jù)經(jīng)驗(yàn)賦予不同的權(quán)重，如表1所示。

表1 權(quán)重分配

表1中，距離采用反距離權(quán)法，即wd＝k／R；價(jià)格由用戶的使用記錄生成，按照t分布函數(shù)求出置信度為90%的置信區(qū)間，將其作為用戶價(jià)格的參數(shù)。為保證推送信息的實(shí)效性，采用反時(shí)間差法計(jì)算時(shí)間。

用戶查詢和瀏覽信息過(guò)程中，可通過(guò)對(duì)用戶的喜好和行為趨勢(shì)進(jìn)行模擬，運(yùn)用模糊遺傳算法不斷完善動(dòng)態(tài)模型，從而實(shí)現(xiàn)對(duì)用戶行為的預(yù)測(cè)。實(shí)驗(yàn)中 選取了六類(lèi)用戶進(jìn)行模擬實(shí)驗(yàn) 通過(guò)模糊神經(jīng)調(diào)整用戶的類(lèi)別權(quán)值，結(jié)果如表2所示。

表2 用戶類(lèi)型模型

2．4 推送策略

對(duì)用戶周?chē)畔⑦M(jìn)行過(guò)濾和篩選后推送地理信息個(gè)性化服務(wù)，雖然提高了推送信息的準(zhǔn)確性，但在實(shí)際操作過(guò)程中會(huì)出現(xiàn)符合條件的信息不足（不能完全匹配用戶特征）等問(wèn)題。信息推送決策樹(shù)可根據(jù)信息推送流程及篩選條件，在信息不足時(shí)加以補(bǔ)充，即推送其它相關(guān)信息內(nèi)容。決策樹(shù)按照二叉樹(shù)結(jié)構(gòu)設(shè)計(jì)，并采用后序遍歷方法（左右根）遍歷整個(gè)二叉樹(shù)。如果訪問(wèn)到右子樹(shù)即一旦出現(xiàn)信息不足，則停止遍歷，完成對(duì)用戶信息的推送。

2．5 結(jié)果評(píng)價(jià)

本文建立的模型可利用反饋機(jī)制來(lái)評(píng)價(jià)推送給用戶信息的質(zhì)量，即用戶對(duì)接收到的推送信息的評(píng)價(jià)自動(dòng)反饋到后臺(tái)服務(wù)器，據(jù)此修正用戶動(dòng)態(tài)模型。推送信息的預(yù)測(cè)率是指推送信息與用戶模型的相關(guān)性程度，而信息的召回率是指被用戶確認(rèn)為無(wú)用信息在總體中所占的比率。主動(dòng)推送度是對(duì)推送信息的有用度和無(wú)用度的綜合評(píng)價(jià)，該指標(biāo)反映了信息推送主動(dòng)可用性的程度。實(shí)驗(yàn)中，根據(jù)精度和性能兩個(gè)評(píng)價(jià)指標(biāo)對(duì)六類(lèi)用戶的反饋結(jié)果進(jìn)行統(tǒng)計(jì)，并選擇召回率和有用度進(jìn)行評(píng)定，結(jié)果如表3所示。

表3 推送質(zhì)量評(píng)價(jià) %

為評(píng)估該算法優(yōu)化前后對(duì)用戶模型的影響，本文選取預(yù)測(cè)率和推送度作為評(píng)價(jià)指標(biāo)，并將優(yōu)化前后結(jié)果進(jìn)行對(duì)比分析，結(jié)果如圖3所示。由圖3可知，優(yōu)化后的個(gè)性化信息推送提高了信息的針對(duì)性和應(yīng)用價(jià)值，為用戶的決策提供了可靠的參考依據(jù)。

圖3 優(yōu)化前后對(duì)比

3 結(jié)束語(yǔ)

本文綜合利用模糊理論、遺傳算法和神經(jīng)網(wǎng)絡(luò)等方法，并對(duì)這些算法進(jìn)行改進(jìn)，建立針對(duì)每個(gè)用戶的動(dòng)態(tài)模型，可根據(jù)用戶位置、個(gè)人行為和興趣、社會(huì)需求等檢索條件，主動(dòng)向用戶推送地理信息，實(shí)現(xiàn)對(duì)用戶的個(gè)性化信息推送服務(wù)。地理信息的個(gè)性化服務(wù)能夠滿足用戶對(duì)信息的需求，通過(guò)對(duì)用戶的個(gè)性、習(xí)慣等進(jìn)行分析，可向用戶主動(dòng)推送個(gè)性化信息，從而提供高質(zhì)量的地理信息服務(wù)［9］。為提高地理信息個(gè)性推送服務(wù)的質(zhì)量，還需要綜合利用更多的智能算法，不斷完善用戶動(dòng)態(tài)模型，增加信息之間的關(guān)聯(lián)性，以提高信息推送的準(zhǔn)確度和信息服務(wù)的質(zhì)量。

［1］ 李德仁，姚遠(yuǎn)，邵振峰．智慧城市中的大數(shù)據(jù)［J］．武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2014，39（6）：631－640．

［2］ 劉經(jīng)南，方媛，郭遲，等．位置大數(shù)據(jù)的分析處理研究進(jìn)展［J］．武 漢 大 學(xué) 學(xué) 報(bào)：信 息 科 學(xué) 版，2014，39（4）：379－385．

［3］ 馬永杰，云文霞．遺傳算法研究進(jìn)展［J］．計(jì)算機(jī)應(yīng)用研究，2012，29（4）：1201－1206．

［4］ 于海璁，陸鋒．一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法［J］．測(cè)繪學(xué)報(bào)，2014，43（1）：89－96．

［5］ 羅亞中，袁端才，唐國(guó)金．求解非線性方程組的混合遺傳算法［J］．計(jì)算力學(xué)學(xué)報(bào)，2005，22（1）：109－114．

［6］ 李卓，李永樹(shù)，梁磊．基于多級(jí)模糊與GIS的天然氣管道風(fēng)險(xiǎn)評(píng)估［J］．測(cè)繪工程，2013，22（1）：78－80．

［7］ 張東波，王耀南，易靈芝．粗集神經(jīng)網(wǎng)絡(luò)及其在智能信息處理領(lǐng)域的應(yīng)用［J］．控制與決策，2005，20（2）：121－125．

［8］ 杜世宏，王橋，李順．模糊對(duì)象粗糙表達(dá)及其空間關(guān)系研究［J］．遙感學(xué)報(bào)，2004，8（1）：1－7．

［9］ 陳軍，武昊，李松年，等．面向大數(shù)據(jù)時(shí)代的地表覆蓋動(dòng)態(tài)服務(wù)計(jì)算［J］．測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2013，30（4）：369－374．