位置信息挖掘中差異化服務機制設計

位置信息挖掘中差異化服務機制設計

移動智能設備的廣泛應用和互聯(lián)網技術的快速進步促進了基于站點服務的開發(fā)（lbs）技術的蓬勃發(fā)展。lbs技術不僅可以應用于定位旅行的旅行，還可以應用于用戶感興趣點的建議，以及基于社交網絡信息的共享，如圖1所示。然而，用戶通過積極報告地理位置為服務提供必要的服務，如圖1所示。當用戶試圖提供服務時，他們的個人信息不可避免地會被泄露，這會影響用戶的生活和工作。用戶向服務提供的信息是分散的，但服務提供方可以利用這些信息來挖掘用戶的生活習慣、興趣和社交網絡等個人信息來獲得收入。從商業(yè)角度分析,服務提供方希望通過提供服務換取用戶位置信息獲益,而用戶則通過上報自身位置信息獲得所需的服務等級,雙方均可從LBS系統(tǒng)中獲益.但在實際的服務方和被服務方所構成的聯(lián)合體中雙方都被視為理性個體,即雙方各自傾向于自身收益的最大化.此外,不同用戶對服務水平和位置隱私的偏好存在差異,而服務提供方對特定用戶的真實偏好類型未知,導致信息的不對稱,所以服務提供方在提供服務時難以實現(xiàn)更好的個性化服務,從而獲得最佳收益.合同理論是解決信息不對稱場景的一種有效機制現(xiàn)有的位置信息挖掘領域的研究工作中,文獻作為經濟學理論的一個重要的分支,同博弈論、拍賣理論一樣,合同理論得到了十分廣泛的應用.合同理論研究的是當其中一方知道某些信息而另一方不知道這些信息時,如何設計合理的合同契約來解決這一信息不對稱問題.通常合同理論的建立基于以下2個條件1)合同契約雙方存在一定的利益沖突;2)合同契約雙方之間存在信息不對稱問題.因此,許多場景也可以運用合同理論來解決偏好未知等信息不對稱問題.比如如何針對小區(qū)緩存系統(tǒng)中視頻內容提供商的實際偏好類型未知的問題,構建服務提供商和視頻內容提供商的收益函數(shù)以及最優(yōu)合同本文研究的主要內容及創(chuàng)新點如下:1)考慮LBS場景下不同用戶對服務水平和位置隱私的偏好存在差異,針對偏好的差異性設計合適的機制,使得服務提供方的收益最大化;2)針對LBS場景下的信息不對稱問題,提出使用合同理論方法,為不同偏好類型的用戶設計不同的最優(yōu)合同組合,建立最優(yōu)合同模型并使用拉格朗日乘子法進行求解,提供差異化的服務.1用戶方社會服務的提供方和n種偏好類型的用戶關系用戶在使用LBS系統(tǒng)中通常具有隱私保護意識,本文假設用戶普遍采取的位置信息保護策略為模糊法假設服務提供方無法準確獲取每個用戶的具體偏好信息,但可以知道用戶的服務水平偏好分布情況.針對服務提供方對用戶偏好類型未知引起的信息不對稱性問題,提出使用合同理論方法,對服務提供方和N種偏好類型的用戶進行建模分析.A.服務提供方模型服務提供方制定合同組合為{P,SL},由服務水平和用戶享受服務時需要提供的個人位置隱私組成.其中SL代表服務方提供的服務水平,而P代表LBS用戶方使用服務時需要付出的個人位置隱私的等級.P={P服務提供方的收益主要來源于用戶在使用服務時付出的個人位置信息.假設服務提供方獲取用戶位置信息的單位收益為Φ,提供服務水平需要的單位成本為Ψ,則服務提供方為偏好類型π其中αB.用戶方模型用戶的收益主要來源于所獲得的服務,不同用戶對服務等級的偏好不同,因而單位服務水平帶給不同用戶的收益也有差異,假設偏好類型π其中:h(π所以h(π2基于同理論的最優(yōu)合同組合設計考慮到LBS系統(tǒng)中用戶對服務等級和位置隱私的偏好類型不同,服務提供方也無法準確獲知各自偏好信息,故提出構建最優(yōu)合同模型.合同理論作為不完全信息場景的有效機制算法,可以解決信息不對稱問題.服務提供方的目標是如何為各個偏好類型的用戶設計一系列最優(yōu)的合同組合,使得每個類型的用戶只能選擇其中一種最優(yōu)合同最大化自身收益.在設計最優(yōu)合同過程中,考慮N種類型的用戶滿足個體理性(IndividualRationality,IR)和激勵兼容(IncentiveCompatibility,IC)2.1基于激勵兼容ic的偏好類型定義1個體理性定義2激勵兼容基于IR和IC約束條件,最優(yōu)合同模型描述如下:基于文獻證根據(jù)激勵兼容IC的約束條件,偏好類型π證根據(jù)激勵兼容IC的約束條件獲得偏好類型π由于函數(shù)h(π引理3LBS場景下,用戶方與服務提供方之間的任意一個可行合同(P證如果用戶對服務水平的偏好類型為π故用戶使用LBS服務過程中,當服務水平的偏好類型滿足π2.2最優(yōu)合同求解本小節(jié)是對逆向選擇問題(5)進行求解.為了降低求解的復雜度,首先減少約束條件的個數(shù),在減少的同時需要保證問題解的準確性.從優(yōu)化問題(5)中可以發(fā)現(xiàn)最優(yōu)合同模型總共有N個IR約束條件,下面通過消除其中的N-1個IR約束條件簡化優(yōu)化問題.根據(jù)激勵兼容IC條件,對于偏好類型為π即對于任意偏好類型π此時,式(3)個體理性約束條件可轉化為式(10),最低偏好類型的用戶將獲得零收益.文獻從激勵兼容約束條件以及優(yōu)化問題(5)中發(fā)現(xiàn),本模型總共有N考慮偏好類型為π根據(jù)式(11),可得以下條件:同理,考慮偏好類型為π根據(jù)式(13),可得以下條件:根據(jù)上述LUICs和LDICs條件(12)和(14),可將激勵兼容IC約束條件進行轉化,得到:提供更好的服務水平需要更高的成本,服務提供方在最大化自身收益時,必須滿足用戶個體理性條件與激勵兼容條件,再盡量降低自身提供服務的成本,即提供的服務水平在符合條件的情形下應取最小值.故根據(jù)上式(15),不等式的下界是理性的服務提供方在確定服務水平SL經過上述IC和IR約束條件的減少,原始優(yōu)化問題(5)的約束條件變更為(10)和(16),新的最優(yōu)合同模型定義為:對于優(yōu)化問題(17),采取拉格朗日乘子法針對上述優(yōu)化問題,分別考慮i=1,i=2,3,…,N-1和i=N3種情況,迭代求解最優(yōu)合同.下面首先分別對變量求偏導數(shù),令偏導數(shù)為0,求解式(18)的最大值,即優(yōu)化問題(17)的最優(yōu)解:1)當i=N時,分別對P根據(jù)式(20),可求得用戶在使用服務時上報的個人位置隱私P根據(jù)式(20)、(21)還可以計算出i=N時,υ2)當i=2,3,…,N-1時,對式(19)進行求解,可得:利用υ3)當i=1時,對式(19)進行求解,可得:根據(jù)等式-α求得個人位置隱私P3不同用戶偏好類型時的仿真結果對本文所提出的最優(yōu)合同機制進行仿真實驗,以驗證合同理論在LBS場景下的性能.假設用戶位置信息的單位收益與服務的單位成本之比Φ/Ψ=3.為簡單起見,假設LBS用戶的偏好類型服從均勻分布,即α首先設定用戶對服務水平的偏好類型數(shù)N=5,參考文獻[21]中對用戶偏好類型的設定,5類偏好類型{π在下面的實驗仿真中,設定用戶對服務等級的偏好類型數(shù)N=12,且這12(i=1,2,…,12)種偏好類型呈現(xiàn)遞增趨勢.圖3～圖6分別將信息不對稱情形(即服務提供方無法獲知用戶的偏好類型)時設計的最優(yōu)合同與完全信息(服務提供方了解每一個用戶的偏好類型)時進行仿真對比.圖3描述的是不同用戶偏好類型下用戶保護策略模糊法中的模糊等級(策略k的選擇)以及最優(yōu)合同中用戶所能獲得服務等級.可以發(fā)現(xiàn),當用戶對服務等級的偏好程度增強時,用戶更愿意付出自己的部分位置隱私,此時模糊等級k的數(shù)值越來越小,即用戶在上報自身位置時的模糊程度降低,而所能獲得的服務等級越來越高.圖4描述的是信息不對稱與完全信息兩種情形時用戶收益與用戶偏好類型的關系.從圖中發(fā)現(xiàn),完全信息時,用戶方的收益始終為0,這是因為此時的服務提供方了解每個用戶的偏好,所以設計合同時,為了最大化自身收益,使得每個用戶的獲得的收益均為0.相反,當LBS用戶的偏好類型未知時,用戶方可以從隱藏的位置信息中獲得非負的收益,從圖可知用戶對服務水平的偏好類型越高,所能獲得的收益也越高,這一結果也正好驗證了引理3所給出的結論.圖5(見第248頁)描述的是服務提供方的收益與用戶偏好類型之間的關系,在信息不對稱時服務方所獲得的收益一直低于完全信息情形.同樣,這也是因為用戶對服務等級和個人位置隱私的偏好類型未知時,服務提供方在不完全信息下所設計的合同無法達到完全信息情形下的理想收益,導致部分收益損失.圖6(見第248頁)描述的是雙方總收益與用戶偏好類型的關系,可以發(fā)現(xiàn),本文所設計的信息不對稱情形下最優(yōu)合同的總收益接近完全信息時的總收益.由于完全信息情形下,服務提供方直接為每個用戶設計最大化自身收益的合同,使得每個用戶收益均為0;而信息不對稱情形下,服務提供方只能根據(jù)個體理性和激勵兼容性質為各個類型用戶設計合理的合同,使得非最低偏好類型的用戶均能獲得比最低偏好類型用戶更高的收益.因此,隱藏的具體偏好信息幫助用戶方從服務提供方獲得信息收益,完全信息情形下總收益略高于信息不對稱情形,圖4和圖5也可驗證這一點.因而,從雙方總收益角度可以發(fā)現(xiàn),本文利用合同理論為各個偏好類型所設計的最優(yōu)合同是可行并且有效的.4基于位置服務場景的仿真結果本文針對LBS系統(tǒng)中服務提供方與用戶之間的信息不對稱問題,在位置信息挖掘過程中,提出了基于合同理論的差異化服務的算法機制設計.該算法機制提出為每一種偏好類型的用戶分別設計各自的最優(yōu)合同,使得用戶方在收益非負的情況下無法通過選擇其他類型的合同提高自身收益,從而實現(xiàn)服務提供方和用戶方各自收益的最大化.仿真結果表明,當用戶對服務水平的偏好上升時,用戶愿意共享更多的個人位置隱私以獲得更高的服務水平,同時獲得的收益也隨之提升.可見,本算法機制同時可以激勵LBS用戶共享更多個人位置隱私.此外,通過比較發(fā)現(xiàn),不對稱信息下雙方的總收益接近完全信