基于核加權KNN和多目標優化的眾包平臺定價系統設計

彭云聰，任心晴，石浩森

（南京郵電大學，江蘇 南京　210046）

0　引言

當下，眾包模式以其自由、合作、碎片化工作等特點，越來越受到企業的青睞。眾包指公司或機構把過去員工的工作，以自由自愿形式外包給非特定的大眾的一種大型網絡運營模式[1]。它大大提高了經濟效率，更是一種未來的商業模式。

國內對眾包模式的研究主要體現在眾包的概念[2]、參與活動的用戶行為模式[3]和任務定價規律等方面。王桂云等人研究了任務設計、發布方信譽和不同平臺對參與者行為的影響[4]；胡靜思等人則提出了基于雙邊市場理論的眾包平臺定價策略[5]，重點討論了網絡外部性、用戶歸屬、平臺差異化以及平臺技術對定價的影響。而孫信聽等人則采用解決多臂賭博機的方法確定任務定價規則，基于貪婪算法對任務進行分配以達到平臺收益的最大化[6]。

本文參考 2017年高教社杯全國大學生數學建模競賽數據，以“拍照賺錢”眾包平臺為例，基于題目所給出的地理位置信息、用戶情況、歷史訂單詳情等，研究眾包模式下任務的最優定價問題[7]。考慮任務的位置、任務價格和任務難度為影響任務完成情況的因素，建立基于多項式核函數的加權KNN[8]模型和多目標優化模型，最后通過有序樣本聚類法[9]，確定最優任務定價規則。綜上所述，合理構建眾包平臺定價系統，一定程度上對解決該類問題起參考作用。

1　核加權KNN分類預測模型

1.1　指標確立

研究表明一般任務價格和任務完成情況主要取決于任務類型、任務顆粒度和任務難度[10]，因此可以通過上述三個方面定量化的指標，制定合理的價格。如果當前價格與合理價格偏差過大，那么就可能出現無人接單的情況。

圖1　指標關系圖Fig.1　Index relation diagram

本文不考慮打包發布，忽略任務顆粒度的影響，選取任務經度、緯度、附近用戶人數、當前任務價格作為定量指標，任務完成情況作為判別結果。由于數據間存在較大的量綱差異，將數據進行標準化預處理。當前定價方案下，任務完成率約60%。

1.2　傳統的KNN模型

根據樣本數據特點，通過經驗分析，基于KNN的判別模型較為合適。為了對任務完成情況進行判別分析，引入映射

其中xi為樣本， f （Xi）為樣本完成情況的預測值

KNN決策規則為

其中

1.3　核加權KNN分類模型

在構造距離量度過程中只涉及到樣本點之間的點積運算，同時考慮到數據可能低維不可分，所以引入多項式核函數，利用φ()·將數據樣本投射到高維特征空間 F，通過在F中基于準則構造新的分類函數，解決在初始空間線性不可分的問題。

用核函數替代內積運算，核函數為

本文定義多項式核函數為

此時參數d決定了模型的適應性，若選擇不當，會降低預測精度。

定義樣本間距離量度為

根據樣本的距離量度，在訓練樣本中找到每個樣本的k個近鄰樣本，分別計算出相應的權值[12]，通過高斯函數定義權值為

式中d為兩樣本之間的距離量度，ac、為任意常數，決定了權值變化趨勢速度。

最后求出該樣本的k個近鄰樣本的加權平均

將每個測試樣本的加權平均與閾值 t比較，樣本較為均衡情況下閾值一般取0.5，若f≤t，則判定該任務未被完成。核加權KNN分類法對測試樣本的k個近鄰樣本給予不同權重，權重隨著近鄰樣本點和測試樣本之間的距離量度的改變而呈負指數函數改變。

1.4　參數的優化

每個樣本近鄰數k和多項式核函數次數d的確定，是基于核函數的加權KNN模型建立的關鍵。為了提高精度和泛化能力，需要對參數進行優化處理。

參數k對分類器的精度有著重要的影響，利用遍歷法結合交叉驗證對參數 k的不同取值進行測試，以分類精度為標準，當k為4時，預測精度達到較高的水平。

通常情況下，參數d為大于1的整數，但由于實際問題的特殊性，為了使模型精度較高，有較好的魯棒性，假設它為區間[0,5]上的任意一個實數。采用粒子群優化算法[13](PSO)來確定參數 d，其步驟為：

Step1: 初始化粒子群體，包括隨機位置和速度；

Step2: 計算當前情況下的分類器的誤差率，判斷是否更新歷史最佳位置和全局最佳位置；

Step3: 通過公式計算下一次每個粒子的位置，當迭代達到規定次數或誤差率減小不顯著則尋優結束，如果不滿足結束條件，那么返回Step2。

通過迭代搜尋最優值，最后尋得最優 d值為1.93，如圖2。

1.5　模型檢驗

本文選取了核加權 KNN模型，采用交叉驗證法，將其分類預測精度與其他分類器相比，如表1，說明了核加權KNN分類模型的優越性。

圖2　適應度進化曲線Fig.2　Fitness evolution curve

考慮到NFL定理，我們使用多種代表性分類方法采用交叉驗證法對比精度，可以看出對當前問題，本文構建的核加權KNN模型是最適宜的解決方法。

表1　不同分類器的預測精度Tab. 1　Prediction accuracy of different classifiers

2　基于多目標優化的最優定價方案

2.1　多目標規劃模型

任務完成率和每個任務的收益是反映經營模式的經濟效益的重要標準，而任務完成率又與任務價格正相關，所以兩者存在相互制約的關系。

由于每個任務的成本價格未知，并且眾包平臺不一定要每一單利潤大于 0，對于初起步的平臺，任務的完成率及其效應至關重要，所以不能簡單地通過利潤最大化來建立目標函數。因此，根據完成率最大，提升價格最少為目標建立優化模型。

· 任務完成率是指在不同定價方案情況下，完成任務數與總任務數的比值，屬于效益型指標，而新定價方案的完成數通過核加權 KNN分類模型仿真預測得出。根據映射

任務完成率目標函數為

式中n為任務總數

· 新方案的任務總價格與原來總價基礎上的任務加價是一致的，簡便起見，考慮加價情況即可，設每個未完成任務提高價格為 p （ Xi），那么所有任務的加價為

因此，最終優化目標為

2.2　基于貪心法的增益分析求解

對于多目標優化，常采用線性加權和法、分層法等，但是加權和法需要確定各個指標的權值，本文指標量綱差異較大，權重不易確定，缺少理論依據；而帶寬容的分層多目標優化法中寬容程度的確定主觀性太強。因此本文提出了一種基于貪心法的增益分析。

對平臺發展而言，任務完成率目標函數更重要，因此利用價格變動情況下判別函數（）fX的結果，結合貪心法得到每增加 1%的任務完成率下最低的加價金額。如圖 3，可以看出每個任務完成率下的價格增益情況。

2.3　基于有序樣本聚類法最優分割點的選擇

觀察圖 3，較難判斷出最優分割點，使其分為加價合理與加價不合理的兩部分，因此采用有序樣品聚類分析法——將每提升 1%任務完成率所需要加價金額按序排列，記為，從而進行有序樣本最優聚類，其臨界點即為最優分割點。

圖3　任務價格增加量與任務完成率曲線圖Fig.3　Diagram of task price increase and task completion rate

有序樣本依次為 X1, X2,…,Xn，若某一類G包含樣品有，則這一類的直徑為

式中XG為類的均值向量

則分類法的損失函數為

圖4　最優分類點Fig.4　Optimal classification point

2.4　仿真結果

本文通過建立基于核函數的加權 KNN模型，迭代計算出所有情況下的任務價格，預測出相應任務價格下任務完成情況，根據增益梯度，采用有序樣本聚類法找到完成率和相應增加價格的最優分割點，從而發現當增加的價格為400元時，任務完成率達到89%，并且得出各個任務的訂單價格。

3　定價系統設計建議與改進方向

3.1　定價系統設計建議

· 不同類型眾包平臺具體量化而來的指標可能有顯著差異，需要結合工作人員的經驗，找出與任務完成情況有關的指標。建議以最近一段時間此地區的歷史數據作為訓練樣本，確定當前階段的最優定價方案。

· 特征工程是數據挖掘中最重要的一環，它決定了算法的上限，因此結合從業人員經驗對任務各個指標進行選擇、交互等操作可能會提高模型的實用性。

3.2　改進方向

·KNN類算法對于高維或者海量數據進行相似度量，計算時間會非常長，此時可以根據實際情況選擇高性能計算，或者退而求其次采用隨機森林算法、梯度提升樹算法等進行接單判定，也能有較好的效果，同時節約計算成本。

4　結論

本文根據實例，對歷史訂單進行數據挖掘，揭示出隱藏在數據背后的灰色關系，合理地對任務完成情況進行仿真分類預測，同時根據平臺自身發展情況構建多目標優化模型，提出了最優定價方案。綜上所述，合理地構建了拍照賺錢的眾包平臺定價系統，同時易于遷移到各種眾包平臺對各種訂單進行輔助定價。

未來可以進一步結合從業人員經驗對特征處理，進一步提升模型適應性，處理海量數據時可以根據實際情況選擇采用云計算或者更換效果較為接近的隨機森林、梯度提升樹等算法節約計算成本。