基于貪婪算法的拍照定價問題的計量分析

王 婷，朱 磊，張月蕾，貢楊泰

（1.安徽財經大學 金融學院；2.安徽財經大學 統計與應用數學學院，安徽 蚌埠 233030）

“拍照賺錢”是移動互聯網下的一種自助式服務模式.這種基于移動互聯網的自助式勞務眾包平臺，為企業提供各種商業檢查和信息搜集，相比傳統的市場調查方式可以大大節省調查成本，而且有效地保證了調查數據真實性，縮短了調查的周期.App成為該平臺運行的核心，而App中的任務定價又是其核心要素.因此本文主要通過貪婪算法模型，對原來定價進行修正后并制定新的定價方案，為任務發布者以及實行者提供合理的參考依據.

1 數據來源與模型假設

本文做出以下模型的假設：⑴假設會員在執行任務時，選擇任務時是理性的，優先選擇離自己近的，價格高的任務.⑵假設會員的定位是會員自身的位置定位，而不是居住的IP定位.⑶假設會員獲得任務的渠道是一致的，不存在時間上的延遲.

2 任務未完成原因分析

2.1 研究思路

首先將地圖無憂所收集已結束項目的任務位置數據在地圖上可視化，通過觀察地圖上任務完成分布情況，結合會員信息分布情況，然后將任務完成分布情況分成四類，找到聚類中心點[2]，在不同類中將已完成任務與任務標價進行相關性進行分析，進行分區，找出定價規律.最后通過經緯度轉換找出分布情況，通過分析任務完成情況所在位置，結合任務定價和會員屬性，分析得出任務未被完成的原因.

2.2 研究方法

將已結束項目的任務位置信息利用R語言可視化，將完成任務和未完成任務和會員聚集情況[3]同時將任務定位導入到地圖無憂中，分別得到圖1、2.

結合圖1、2進行分析，得到如下現象：大部分會員聚集的地方，任務完成度較高，但是仍存在會員很少但任務卻完成；會員離任務很近，但任務卻未被完成；某一區會員眾多，卻存在任務未被完成的情況.因此可能存在定價問題.針對所挖掘的信息，建立出聚類分析模型，研究定價規律和未完成的原因.

圖1 任務完成情況熱力圖

圖2 任務在地圖上可視化

2.3 結果分析

對任務的位置進行聚類分析，觀察圖2，可以發現任務完成情況存在明顯的分區現象.因此選擇軟件進行K-mean將其分為四類將任務經緯度數據導入MATLAB中進行處理得到四個中心點位置分別為:(23.014861,113.184759）；（22.663103,114.046420）；(23.278157,113.326456)；（22.956052,113.749090）.

利用EXCEL表對全部任務經緯度進行轉換成距離.為進一步求解出任務完成度和會員的關系，利用轉換出的距離本文等分成大小相同的正方形，將數據置于網格化量化得到圖3.

圖3 會員信息網格化

圖例說明格網顏色代表會員人數，紅色越深代表人數越少，越偏向黑色代表人數越多，格網的數字右下角黃色標簽表示該網內會員數，左下角綠色代表完成任務人數，左上角白色標簽代表未完成的任務的人數.根據圖中所反應的信息，雖然會員分布在較多黑格子中，但是任務完成度并不樂觀，白色標簽未完成的任務大部分分布在灰色盒子中.任務未被完成的原因可能由于定價偏低，影響會員積極性.

結合圖1、2、3行比較分析，發現不同區任務完成分布不同，同時不同區域的定價和中心點的距離，存在不同的變化關系.因此必須進行分區計算定價和距離的相關系數，分析兩者之間的相關關系.

令對已完成項目任務數據中各區相關系數分別為：ρ1；ρ2；ρ3；ρ4.

通過分區進行相關性分析，不同區的相關性還是存在明顯差異，這與其經濟發展情況密切相關，由于不同地區經濟發展情況不同，會員對任務定價接受程度不同，可能即使存在任務，也不愿接單.

2.3.1 任務定價規律：針對不同區，任務定價存在差異，從圖中可以看出，部分偏離中心點很遠處，定價比較高.可能是為了鼓勵更多人注冊會員；在會員集中的地方，任務定價偏低；但是由于存在限制單數的情況，因此在集中的區域也會有未完成的任務；由于經濟環境的差異，商家所給出的價格并不能滿足參與者所接受的價格，因此可能存在任務無法完成的情況.

2.3.2 任務未完成的原因:任務與會員距離太遠，成本太高；部分地區會員數太少，不能與任務達到供需平衡；任務所給出的定價，不能滿足參與者的需求；預定任務開始時間的間斷性，使得部分任務無法完成；會員預定任務限額，使會員集中區也可能存在任務無法完成的情況.

3 任務定價方案

3.1 研究思路

對項目設計新的定價方案，分3個步驟，第一步根據會員信息中的每個會員的信譽值估計出他們完成任務的質量；第二步根據那些區域附近已完成任務的定價估計會員完成任務所需的成本和每個會員預定任務的限額，對任務進行定價；第三步根據會員完成任務的質量（對信譽值處理）進行降序排序，采用貪婪算法[4]進行任務分配，再通過類比推理得出定價范圍.

3.2 研究方法

發布者通過自助式勞務眾包平臺發布任務，并進行定價.但影響定價的因素有很多，在這里主要考慮會員本身因素[5]（完成任務的質量、成本、最大完成任務數量）、會員密度、任務密度、區域經濟發展水平.根據已完成項目任務的經度、緯度數據，得出任務分布在4個地級市，具體到區（或者縣級市、縣）共有25個區域.經過EXCEL篩選得到不同區域任務完成度（見表1）.

表1 不同區域任務完成度

佛山市南海區、廣州市南沙區、東莞市東莞市、佛山市高明區、佛山市三水區、廣州市從化市、廣州市增城市、清遠市佛岡縣任務完成情況均達到92%以上，說明這些地區定價結構比較合理，只需考慮其他地區的定價方案即可.

有界貪婪算法[6]:

（1）選取區域內部分會員，取得“任務預算（即某個會員能夠完成的最大任務個數及位置范圍）”Bp=εB，設置t=1（2）在情況下重復以下步驟.（3）給會員分配任務.（4）.（5）結束當前步驟.（6）結束當前循環.（7）對會員按照ci進行升序排序.（8）在最后一輪中，重復以下步驟.（9）判斷剩余“任務預算”BP＜minci.（10）如果成立跳出循環.（11）否則，選擇剩余會員中符合條件的會員.（12）BP=BP-ci.（13）結束當前步驟.（14）結束當前循環.（15）對會員進行完成任務質量估值：多次探索取平均值的方法.（16）根據上一步驟得出的結果，得出函數：μi=f(ci).（17）利用函數得到剩余會員的任務質量估值.（18）算法結束.

通過C++貪婪算法編程，求得區域會員與任務的一種對應關系.

深圳市福田區任務完成度0%，由表2知，該區域的任務標價較低，然而該區域內會員數量較多，因此應合理地提高任務價格.同理也可以分析得出：廣州增城區、南沙區和佛山市三水區的任務定價均較高，但是這些區域任務位置離會員平均距離較遠，因此對定價也有影響.

綜上知，以深圳市福田區、廣州市天河區等17個區（除佛山市南海區、廣州市南沙區、東莞市東莞市、佛山市高明區、佛山市三水區、廣州市從化市、廣州市增城區、清遠市佛岡縣之外），應適當提高定價，在考慮其他地區會員位置與任務位置的關系后，覺得將這些地區的任務定價范圍確定在70～75.

4 基于距離范圍確定的完成度模型

4.1 研究思路

把任務聯合在一起打包發布[7]，對任務點進行篩選后，再對會員的經緯度聚類分析.最后以貪婪算法定價模型為基礎進行擴展得出任務分配及其完成情況的變化，并且分析任務完成率的高低變化情況.

4.2 研究方法

首先篩選出信譽度較高且任務限額大于10的會員，得出符合要求的會員共有252個；接著根據市場的供求關系，并且結合圖1和圖3分析任務與會員的大致位置后，將任務位置通過MATLAB聚類分析得到252個“聯合任務”的位置.

任務發布者往往追求任務能夠全部完成，因此本文將“聯合任務”與會員一一對應，以期望得到任務完成度最大，但現實情況中有些任務離會員較遠，對已完成項目任務的數據進行處理，計算出原始數據中的任務完成情況，通過統計完成任務個數與總任務個數對比得到任務的完成率：

其中q為任務完成情況，Xi表示任務完成的個數，Xn表示為總的任務個數.

對于打包分布情況下數據處理——經緯度轉化為距離，根據歐氏距離公式：

考慮到任務個數和會員個數較多，將兩組數據導入Excel軟件中，選擇出所有中的最短距離.

4.3 結果分析

通過App軟件數據分析可以得到，一般在距離在3000米以內的任務幾乎都被實行，在3000米之外除了現實中一些偶然因素，一般情況下任務都沒有得得到完成.這恰好與圖表中的呈現的會員與任務點集聚分布相似相符.根據所搜集到的數據，統計出任務點與會員點之間的距離在3000米以內的個數為200，因此方案的完成率為P=200/252=79.365%

通過對于打包分布情況下任務完成率與不打包分布的情況下的任務完成率對比可以發現，在對任務進行打包后得到的任務完成率有所提高，減少了由于用戶互相選擇出現了任務無人選擇的情況.

5 分區擬合回歸模型

5.1 研究思路

本文選取已完成任務的定價價格、經度、緯度會員密度、會員信譽度作為指標，進行回歸擬合[8].

5.2 研究方法

將新項目任務數據導入到地圖進行可視化分析，得到圖4.

圖4 任務分布位置圖

可以觀察到待處理數據大部分分布在廣州市，還有零散的點分布在深圳市及附近.因此分區進行處理.由于前面的分析結論，得知雖然深圳市會員密度高，但是會員活躍度不高.由于經濟發展水平不同，導致定價水平存在差異.因此本文首先對廣州市進行回歸擬合分析，然后將深圳市及附近的數據通過類比前面已建立的模型，進行定價.由于并沒有搜集到會員所完成的具體任務，因此將會員信譽度作為虛擬變量引入.

經過幾個函數的擬合優度、模型顯著性進行對比，本文選取擬合優度最好，模型通過顯著性檢驗的數據.通過Stata進行回歸擬合，Y代表任務定價、C代表經度，V代表緯度、M代表會員密度、ξ代表隨機干擾項得到如下模型：

各個t值所對應的p值均小于0.05，拒絕原假設，各變量顯著.同時F(3,125)=13.45，模型顯著.R2=0.875，模型擬合優度較高.

將廣州區已經完成的任務，利用EXCEL將數據帶入回歸方程，通過計算預測值和實際定價的差值，用STATA做出誤差散點圖，如圖5所示.

圖5 誤差散點圖

根據圖5可以看出誤差大部分分布在0-3中，誤差范圍并不大，在實際情況實行中，誤差可能來自會員信譽度，可以根據任務發布點，會員信譽情況引入虛擬變量Di,根據會員信息中的信譽值，將信譽值進行分段：

極差=Max信譽-Min信譽，采用等距分組，將區間分為：

將虛擬變量賦值為0.75；1.5；2.25；3，并且引入回歸函數中，其中bi表示接受任務會員的信譽水平：

經過廣州市已完成任務誤差散點圖分析，證明模型可行性較好，加入有關會員信譽的虛擬變量，回歸函數針對位于廣州市地區的任務做出了較為準確的定價方案.根據新方案中所給的經緯度信息，將所處廣州市的經度、緯度、會員密度一一對應，便可求出所求定價.

5.3 結果分析

已經看到深圳任務完成度在15%以下，但是在地圖上深圳所在地區會員數量并不低.針對此現象，本文將數據利用R語言進行可視化，得到會員與完成任務的疊加圖如圖6，會員與未完成任務疊加圖如圖7所示.

結合圖6針對深圳市寶安區，即圖6中深圳市左下角處，黃色點較小，完成任務的定價處于[65,67]，因此進行定價，同時為了調動會員的積極性，可以對價格進行正方向的微調.同時在深圳市右上方紅色集中區，對比之前會員完成圖注：黃色點代表未完成的會員疊加，紅色點代表完成任務，點越大標價越高，格網代表會員數，紅色人少，黑灰色人多.情況定價，黃色點較大，價格普遍在[76,80]之間.

圖6 任務完成疊加圖

圖7 未完成任務疊加圖

6 結束語

本文的特色是運用R語言強大的視圖功能，結合多種統計軟件，使復雜的問題借助圖形得到較為準確和完整的結果,以深圳市福田區、廣州市天河區等17個區價格作為參考依據，在考慮其他地區會員位置與任務位置的關系后，覺得將這些地區的任務定價范圍確定在70～75.