<b>3.11 商品推薦模型</b>
鑒于商品推薦模型在網際網路和電子商務領域已經成為一個獨立的分析應用領域，并且正在飛速發展并且得到了廣泛應用。是以除本節以外，其他章節将不再對商品推薦模型做任何分析和探讨，至于本節，相對于其他的分析類型來說，會花費更多的筆墨和篇幅。希望能給讀者提供足夠的原理和案例。
<b>3.11.1 商品推薦介紹</b>
電子商務推薦系統主要通過統計和資料挖掘技術，并根據使用者在電子商務網站的行為，主動為使用者提供推薦服務，進而來提高網站體驗的。根據不同的商業需求，電子商務推薦系統需要滿足不同的推薦粒度，主要以商品推薦為主，但是還有一些其他粒度推薦。譬如query推薦、商品類目推薦、商品标簽推薦、店鋪推薦等。目前，常用的商品推薦模型主要分為規則模型、協同過濾和基于内容的推薦模型。不同的推薦模型有不同的推薦算法，譬如對于規則模型，常用的算法有apriori等；而協同過濾中則涉及k最近鄰居算法、因子模型等。沒有放之四海而皆準的算法，在不同的電子商務産品中，在不同的電子商務業務場景中，需要的算法也是不一樣的。實際上，由于每種算法各有優缺點，是以往往需要混合多種算法，取長補短，進而提高算法的精準性。
<b>3.11.2 關聯規則</b>
1. apriori算法
電子商務中常用的一種資料挖掘方法就是從使用者交易資料集中尋找商品之間的關聯規則。關聯規則中常用的一種算法是apriori算法。該算法主要包含兩個步驟：首先找出資料集中所有的頻繁項集，這些項集出現的頻繁性要大于或等于最小支援度；然後根據頻繁項集産生強關聯規則，這些規則必須滿足最小支援度和最小置信度。
上面提到了最小支援度和最小置信度，事實上，在關聯規則中用于度量規則品質的兩個主要名額即為支援度和置信度。那麼，什麼是支援度和置信度呢？接下來進行講解。
給定關聯規則x=>y，即根據x推出y。形式化定義為：
支援度（x=>y）=
置信度（x=>y）=
假設d表示交易資料集；k為項集，即包含k個項的集合；lk表示滿足最小支援度的k項集；ck表示候選k項集。apriori算法的參考文獻描述如下。
在該算法中，候選集的計算過程如下所示。
l1={滿足最小支援度的1項集}
for (k=2; lk-1 ≠; k++)
ck=candicate_gen(
lk-1 )//計算候選項集
for
all transactions t∈d do
ct=subset(ck,t)//候選集是否包含在t中
for all candicates c∈ct do
c.count++
end
lk={c∈ck | c.count大于等于最小支援度}
合并所有的lk，得到頻繁項集
首先進行連接配接運算如下：
insert into ck
select p.item1, p.item2, p.itemk-1,…,
q.itemk
from lk-1 p, lk-1 q
where p.item1=q.item1 and … and
p.itemk-2=q.itemk-2 and p.itemk-1<q.itemk-1;
然後根據頻繁項集定理（即頻繁項集的子集必定是頻繁項集）進行剪枝，過濾掉非頻繁項集，過程如下所示：
forall itemset c∈ck
forall (k-1) 子集 s of c do
if
(s∈lk-1 ) then
delete
c from ck
從上述算法中可以看出，該算法存在一些困難點，譬如需要頻繁掃描交易資料集，這樣如果面臨海量資料集，就難以滿足實際應用需求；對于大型資料集，計算候選集算法的效率較低，這也是一個難以克服的問題。目前已經有一些優化的方法用于處理這些問題，譬如fp-growth算法。在實際應用中，随着資料的不斷增長，可能還需要通過分布式計算來提高算法性能，譬如機器學習算法包mahout中實作了的并行版本fp-growth算法。
2. apriori算法執行個體
假設給定如下電子商務網站的使用者交易資料集，其中，定義最小支援度為2/9，即支援度計數為2，最小置信度為70%，現在要計算該資料集的關聯規則，如表3-1所示。
表3-1 使用者交易資料集
交易辨別 購買商品清單
2001 i1,i2,i5
2002 i2,i4
2003 i2,i3
2004 i1,i2,i4
2005 i1,i3
2006 i2,i3
2007 i1,i3
2008 i1,i2,i3,i5
2009 i1,i2,i3
計算步驟如下所示。
步驟1，根據apriori算法計算頻繁項集。
1）計算頻繁1項集。掃描交易資料集，統計每種商品出現的次數，選取大于或等于最小支援度的商品，得到了候選項集，如表3-2所示。
表3-2 頻繁1項集
商品集 包含該商品集的記錄數
i1 6
i2 7
i3 6
i4 2
i5 2
2）根據頻繁1項集，計算頻繁2項集。首先将頻繁1項集和頻繁1項集進行連接配接運算，得到2項集，如下所示：
商品集 商品集
i1 i1,i2
i2 i1,i3
i3 i1,i4
i4 i1,i5
i5 i2,i3
i2,i4
i2,i5
i3,i4
i3,i5
i4,i5
掃描使用者交易資料集，計算包含每個候選2項集的記錄數，如表3-3所示。
表3-3 候選2項集
i1,i2 4
i1,i3 4
i1,i4 1
i1,i5 2
i2,i3 4
i2,i4 2
i2,i5 2
i3,i4 0
i3,i5 1
i4,i5 0
根據最小支援度，得到頻繁2項集，如表3-4所示。
表3-4 頻繁2項集
3）根據頻繁2項集，計算頻繁3項集。首先将頻繁2項集進行連接配接，得到{{i1,
i2, i3}, {i1, i2, i5}, {i1, i3, i5}, {i2, i3, i4}, {i2, i3, i5}, {i2, i4, i5}}，然後根據頻繁項集定理進行剪枝，即頻繁項集的非空子集必須是頻繁的，{i1, i2, i3}的2項子集為{i1,i2}，{i1,i3}，{i2,i3}，都在頻繁2項集中，則保留；
{i1, i2, i5}的2項子集為{i1,i2}，{i1,i5}，{i2,i5}，都在頻繁2項集中，則保留；
{i1, i3, i5}的2項子集為{i1,i3}，{i1,i5}，{i3,i5}，由于{i3,i5}不是頻繁2項集，移除該候選集；
{i2, i3, i4}的2項子集為{i2,i3}，{i2,i4}，{i3,i4}，由于{i3,i4}不是頻繁2項集，移除該候選集；
{i2, i3, i5}的2項子集為{i2,i3}，{i2,i5}，{i3,i5}，由于{i3,i5}不是頻繁2項集，移除該候選集；
{i2, i4, i5}的2項子集為{i2,i4}，{i2,i5}，{i4,i5}，由于{i4,i5}不是頻繁2項集，移除該候選集。通過剪枝，得到候選集{{i1, i2, i3}, {i1, i2, i5}}，掃描交易資料庫，計算包含候選3項集的記錄數，得到表3-5。
表3-5 頻繁3項集
i1,
i2, i3 2
i2, i5 2
4）根據頻繁3項集，計算頻繁4項集。重複上述的思路，得到{i1,i2,i3,i5}，根據頻繁項集定理，它的子集{ i2,i3,i5}為非頻繁項集，是以移除該候選集。進而，頻繁4項集為空，至此，計算頻繁項集的步驟結束。
步驟2，根據頻繁項集，計算關聯規則。
這裡以頻繁3項集{i1, i2, i5}為例，計算關聯規則。{i1, i2, i5}的非空子集為{i1,i2}、{i1,i5}、{i2,i5}、{i1}、{i2}和{i5}。
規則1，{i1,i2}=>{i5}, 置信度為{i1, i2, i5}的支援度除以{i1,i2}的支援度，即2/4=50%，因其小于最小置信度，是以删除該規則。
同理，最後可以得到{i1,i5}=>{i2}，{i2,i5}=>{i1}和{i5}=>{i1,i2}為3條強關聯規則。
然而，在實際應用apriori算法時，需要根據不同的粒度，譬如類目、商品等，結合不同的次元（浏覽行為，購買行為等）進行考慮，進而建構符合業務需求的關聯規則模型。在電子商務應用中，關聯規則算法适用于交叉銷售的場景。譬如，有人要出行（飛往北京），根據計算出的關聯規則（如：機票=>酒店）來考慮，那麼，可以根據使用者購買的機票，為使用者推薦合适的北京酒店；再比如，在情人節，根據關聯規則，将巧克力和玫瑰花進行捆綁銷售等。
另外，關聯規則還可以用來開發個性化電子商務推薦系統的top n推薦。首先，根據使用者的交易資料，計算使用者在特定時序内購買過的商品；然後，根據關聯規則算法，計算滿足最小支援度和最小置信度的商品關聯規則；再根據使用者已經購買的商品和商品關聯規則模型，預測使用者感興趣的商品，同時過濾掉使用者已經購買過的商品，對于其他的商品，則按照置信度進行排序，進而為使用者産生商品推薦。
<b>3.11.3 協同過濾算法</b>
協同過濾是迄今為止最成功的推薦系統技術，被應用在很多成功的推薦系統中。電子商務推薦系統可根據其他使用者的評論資訊，采用協同過濾技術給目标使用者推薦商品。協同過濾算法主要分為基于啟發式和基于模型式兩種。其中，基于啟發式的協同過濾算法，又可以分為基于使用者的協同過濾算法和基于項目的協同過濾算法。啟發式協同過濾算法主要包含3個步驟：1）收集使用者偏好資訊；2）尋找相似的商品或者使用者；3）産生推薦。
“巧婦難為無米之炊”，協同過濾的輸入資料集主要是使用者評論資料集或者行為資料集。這些資料集主要又分為顯性資料和隐性資料兩種類型。其中，顯性資料主要是使用者打分資料，譬如使用者對商品的打分，如圖3-4所示。
圖3-4 某電商網站使用者對某商品的評分結果
但是，顯性資料存在一定的問題，譬如使用者很少參與評論，進而造成顯性打分資料較為稀疏；使用者可能存在欺詐嫌疑或者僅給定了部分資訊；使用者一旦評分，就不會去更新使用者評分分值等。
而隐性資料主要是指使用者點選行為、購買行為和搜尋行為等，這些資料隐性地揭示了使用者對商品的喜好，如圖3-5所示。
隐性資料也存在一定的問題，譬如如何識别使用者是為自己購買商品，還是作為禮物贈送給朋友等。
圖3-5 某使用者最近在某電商網站的浏覽商品記錄（左側的3本書）
1. 基于使用者的協同過濾
基于使用者（user-based）的協同過濾算法首先要根據使用者曆史行為資訊，尋找與新使用者相似的其他使用者；同時，根據這些相似使用者對其他項的評價資訊預測目前新使用者可能喜歡的項。給定使用者評分資料矩陣r，基于使用者的協同過濾算法需要定義相似度函數s:u×u→r，以計算使用者之間的相似度，然後根據評分資料和相似矩陣計算推薦結果。
在協同過濾中，一個重要的環節就是如何選擇合适的相似度計算方法，常用的兩種相似度計算方法包括皮爾遜相關系數和餘弦相似度等。皮爾遜相關系數的計算公式如下所示：
其中，i表示項，例如商品；iu表示使用者u評價的項集；iv表示使用者v評價的項集；ru,i表示使用者u對項i的評分；rv,i表示使用者v對項i的評分；表示使用者u的平均評分；表示使用者v的平均評分。
另外，餘弦相似度的計算公式如下所示：
另一個重要的環節就是計算使用者u對未評分商品的預測分值。首先根據上一步中的相似度計算，尋找使用者u的鄰居集n∈u, 其中n表示鄰居集，u表示使用者集。然後，結合使用者評分資料集，預測使用者u對項i的評分，計算公式如下所示：
其中，s(u, u')表示使用者u和使用者u'的相似度。
假設有如下電子商務評分資料集，預測使用者c對商品4的評分，見表3-6。
表3-6 電商網站使用者評分資料集
使用者 商品1 商品2 商品3 商品4
使用者a 4 ? 3 5
使用者b ? 5 4 ?
使用者c 5 4 2 ?
使用者d 2 4 ? 3
使用者e 3 4 5 ?
表中? 表示評分未知。根據基于使用者的協同過濾算法步驟，計算使用者c對商品4的評分，其步驟如下所示。
（1）尋找使用者c的鄰居
從資料集中可以發現，隻有使用者a和使用者d對商品4評過分，是以候選鄰居隻有2個，分别為使用者a和使用者d。使用者a的平均評分為4，使用者c的平均評分為3.667，使用者d的平均評分為3。根據皮爾遜相關系數公式來看，使用者c和使用者a的相似度為：
同理，s(c, d) =-0.515。
（2）預測使用者c對商品4的評分
根據上述評分預測公式，計算使用者c對商品4的評分，如下所示：
依此類推，可以計算出其他未知的評分。
2. 基于項目的協同過濾
基于項目（item-based）的協同過濾算法是常見的另一種算法。與user-based協同過濾算法不一樣的是，item-based 協同過濾算法計算item之間的相似度，進而預測使用者評分。也就是說該算法可以預先計算item之間的相似度，這樣就可提高性能。item-based協同過濾算法是通過使用者評分資料和計算的item相似度矩陣，進而對目标item進行預測的。
和user-based協同過濾算法類似，需要先計算item之間的相似度。并且，計算相似度的方法也可以采用皮爾遜關系系數或者餘弦相似度，這裡給出一種電子商務系統常用的相似度計算方法，即基于條件機率計算item之間的相似度，計算公式如下所示：
其中，s(i, j)表示項i和j之間的相似度；freq(ij)表示i和j共同出現的頻率；freq(i)表示i出現的頻率；freq(j)表示j出現的頻率；表示阻力因子，主要用于平衡控制流行和熱門的item，譬如電子商務中的熱銷商品等。
接下來，根據上述計算的item之間的相似度矩陣，結合使用者的評分，預測未知評分。預測公式如下所示：
其中，pu, i表示使用者u對項i的預測評分；s表示和項i相似的項集；s(i, j)表示項i和j之間的相似度；ru, j表示使用者u對項j的評分。
3. item-based協同過濾執行個體
在電子商務推薦系統中，商品相似度計算有着很重要的作用。它既可用于一些特定推薦場景，譬如直接根據目前的商品，為使用者推薦相似度最高的top n商品。同時，它還可以應用于個性化推薦，進而為使用者推薦商品。電子商務網站收集了大量的使用者日志，譬如使用者點選日志等。
基于item-based協同過濾算法，筆者提出了一種增量式商品相似度的計算解決方案。該算法計算流程如圖3-6所示。
圖3-6 增量式商品相似度計算流程圖
其中，商品關系i表示第i天的商品關系資料集。
具體計算步驟如下。
1）擷取當天使用者點選行為資料，過濾掉一些噪聲資料，譬如商品資訊缺失等。進而得到使用者會話sessionid、商品id（商品辨別）、浏覽時間等資訊，如表3-7所示。
由于a4的浏覽時間和a1、a2、a3相差較大，是以将其過濾掉，這裡定義為1800秒，如表3-8所示。
表3-7 使用者點選行為日志表
使用者會話id 浏覽商品的時間
item pairs
100 a1,
20:12 a1, a2 a1, a3
a2,
20:13 a2,a1 a2, a3
a3,
20:15 a3,a1 a3, a2
a4,
23:30
表3-8 過濾後的使用者點選行為日志表
浏覽商品的時間 item pairs
a1, 20:12 a1, a2 a1, a3
a2, 20:13 a2,a1 a2, a3
a3, 20:15 a3,a1 a3, a2
2）首先，計算任意兩種商品之間的共同點選次數。然後，根據基于條件機率的商品相似度計算方法來計算商品的相似度。商品相似度公式如下。
s(i, j)
其中，s(i, j)表示項i和j之間的相似度；freq(ij)表示i和j共同出現的頻率；freq(i)表示i出現的頻率；freq(j)表示j出現的頻率。
3）合并前一天計算的商品相似度資料，進行投票判斷，選擇相似度較大的作為新的商品相似度，進而實作增量式商品相似度計算。
3.11.4 商品推薦模型總結
對于商品推薦模型，除了上述介紹的基于關聯規則和基于協同過濾的算法外，還有其他一些常用的算法，譬如基于内容的算法，即根據商品标題、類目和屬性等資訊，計算商品之間的關系，然後結合使用者行為特征，為使用者提供商品推薦。商品推薦模型面臨着許多重要問題，譬如特征提取問題，即如何從商品标題、類目和屬性中提取商品的重要特征、新使用者問題，即如何解決使用者行為較少，提升推薦品質、新商品問題，即如何處理長尾商品問題，讓更多的商品有推薦展現的機會、稀疏性問題，即對于龐大的使用者和商品資料，使用者評分資料往往會顯得非常稀疏等。面對這些問題，在實際應用中，需要根據業務場景，充分利用各種算法的優點，進而設計出混合推薦算法，以便提升推薦品質。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)