基于核加權(quán)KNN和多目標(biāo)優(yōu)化的眾包平臺定價系統(tǒng)設(shè)計

彭云聰，任心晴，石浩森

（南京郵電大學(xué)，江蘇 南京　210046）

0　引言

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

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

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

1　核加權(quán)KNN分類預(yù)測模型

1.1　指標(biāo)確立

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

圖1　指標(biāo)關(guān)系圖Fig.1　Index relation diagram

本文不考慮打包發(fā)布，忽略任務(wù)顆粒度的影響，選取任務(wù)經(jīng)度、緯度、附近用戶人數(shù)、當(dāng)前任務(wù)價格作為定量指標(biāo)，任務(wù)完成情況作為判別結(jié)果。由于數(shù)據(jù)間存在較大的量綱差異，將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化預(yù)處理。當(dāng)前定價方案下，任務(wù)完成率約60%。

1.2　傳統(tǒng)的KNN模型

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

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

KNN決策規(guī)則為

其中

1.3　核加權(quán)KNN分類模型

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

用核函數(shù)替代內(nèi)積運算，核函數(shù)為

本文定義多項式核函數(shù)為

此時參數(shù)d決定了模型的適應(yīng)性，若選擇不當(dāng)，會降低預(yù)測精度。

定義樣本間距離量度為

根據(jù)樣本的距離量度，在訓(xùn)練樣本中找到每個樣本的k個近鄰樣本，分別計算出相應(yīng)的權(quán)值[12]，通過高斯函數(shù)定義權(quán)值為

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

最后求出該樣本的k個近鄰樣本的加權(quán)平均

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

1.4　參數(shù)的優(yōu)化

每個樣本近鄰數(shù)k和多項式核函數(shù)次數(shù)d的確定，是基于核函數(shù)的加權(quán)KNN模型建立的關(guān)鍵。為了提高精度和泛化能力，需要對參數(shù)進(jìn)行優(yōu)化處理。

參數(shù)k對分類器的精度有著重要的影響，利用遍歷法結(jié)合交叉驗證對參數(shù) k的不同取值進(jìn)行測試，以分類精度為標(biāo)準(zhǔn)，當(dāng)k為4時，預(yù)測精度達(dá)到較高的水平。

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

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

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

Step3: 通過公式計算下一次每個粒子的位置，當(dāng)?shù)_(dá)到規(guī)定次數(shù)或誤差率減小不顯著則尋優(yōu)結(jié)束，如果不滿足結(jié)束條件，那么返回Step2。

通過迭代搜尋最優(yōu)值，最后尋得最優(yōu) d值為1.93，如圖2。

1.5　模型檢驗

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

圖2　適應(yīng)度進(jìn)化曲線Fig.2　Fitness evolution curve

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

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

2　基于多目標(biāo)優(yōu)化的最優(yōu)定價方案

2.1　多目標(biāo)規(guī)劃模型

任務(wù)完成率和每個任務(wù)的收益是反映經(jīng)營模式的經(jīng)濟效益的重要標(biāo)準(zhǔn)，而任務(wù)完成率又與任務(wù)價格正相關(guān)，所以兩者存在相互制約的關(guān)系。

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

· 任務(wù)完成率是指在不同定價方案情況下，完成任務(wù)數(shù)與總?cè)蝿?wù)數(shù)的比值，屬于效益型指標(biāo)，而新定價方案的完成數(shù)通過核加權(quán) KNN分類模型仿真預(yù)測得出。根據(jù)映射

任務(wù)完成率目標(biāo)函數(shù)為

式中n為任務(wù)總數(shù)

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

因此，最終優(yōu)化目標(biāo)為

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

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

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

2.3　基于有序樣本聚類法最優(yōu)分割點的選擇

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

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

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

式中XG為類的均值向量

則分類法的損失函數(shù)為

圖4　最優(yōu)分類點Fig.4　Optimal classification point

2.4　仿真結(jié)果

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

3　定價系統(tǒng)設(shè)計建議與改進(jìn)方向

3.1　定價系統(tǒng)設(shè)計建議

· 不同類型眾包平臺具體量化而來的指標(biāo)可能有顯著差異，需要結(jié)合工作人員的經(jīng)驗，找出與任務(wù)完成情況有關(guān)的指標(biāo)。建議以最近一段時間此地區(qū)的歷史數(shù)據(jù)作為訓(xùn)練樣本，確定當(dāng)前階段的最優(yōu)定價方案。

· 特征工程是數(shù)據(jù)挖掘中最重要的一環(huán)，它決定了算法的上限，因此結(jié)合從業(yè)人員經(jīng)驗對任務(wù)各個指標(biāo)進(jìn)行選擇、交互等操作可能會提高模型的實用性。

3.2　改進(jìn)方向

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

4　結(jié)論

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

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