RSHandbook筆記P1C1：推薦系統(tǒng)中的數(shù)據(jù)挖掘方法

標(biāo)簽： 推薦系統(tǒng)HandBook筆記

由于簡書不支持latex公式，為了更好的閱讀體驗請移至本文作業(yè)部落的地址，轉(zhuǎn)載請注明筐钟。
推薦系統(tǒng)中的數(shù)據(jù)挖掘方法

介紹

本章主要介紹推薦系統(tǒng)中使用的數(shù)據(jù)挖掘技術(shù)。
典型的數(shù)據(jù)挖掘包含三步：數(shù)據(jù)處理褒脯，數(shù)據(jù)分析和結(jié)果解釋壳繁。

圖1.1

數(shù)據(jù)預(yù)處理

我們把數(shù)據(jù)定義為對象和它們屬性的集合。
本節(jié)主要關(guān)注當(dāng)我們設(shè)計一個推薦系統(tǒng)的時候的遇到的三個重要問題枯饿。首先酝锅，復(fù)習(xí)一下相似度或距離計算方法，然后奢方，討論從大量數(shù)據(jù)中采樣的問題搔扁，最后，討論降維的通用技術(shù)蟋字。

相似度度量方法

1. 歐式距離
   $$ d(x,y)=\sqrt{\mathop{\sum}_{k=1}^n(x_k-y_k)2} $$
   其中稿蹲，$ n $是維（屬性）數(shù)，$ x_k $和$ y_k $是數(shù)據(jù)對象想$x$和$y$的第$ k $個屬性鹊奖。

2. Minkowski距離
   $$ d(x,y)=({\mathop{\sum}_{k=1}^n|x_k-y_k|r)^\frac{1}{r}} $$
   其中r是距離的度苛聘。r值得不同，Minkowski距離有不同的名字：$r=1$:city block(曼哈頓距離)忠聚，$r=2$:歐氏距離焰盗，$r\rightarrow\infty$:supremum距離,這個距離計算數(shù)據(jù)對象的某些維度之間最大不同。

3. Mahalanobis距離
   $$ d(x,y)=\sqrt{(x-y)\sigma^{-1}(x-y)T} $$
   這里咒林，$\sigma$是數(shù)據(jù)的協(xié)方差矩陣熬拒。

4. 余弦相似度
   $$ cos(x,y)=\frac{x\cdot y}{|x||y|} $$

5. 皮爾遜相關(guān)系數(shù)
   $$ Pearson(x,y)=\frac{\sum(x,y)}{\sigma_x\times\sigma_y} $$

RS中使用的較多的是余弦相似度和皮爾遜相似度，Spertus等人做實驗發(fā)現(xiàn)余弦相似度效果最好垫竞。而Lathia等人實驗結(jié)果顯示RS的預(yù)測準(zhǔn)確度與相似度方法的選擇關(guān)系不大澎粟。

另外蛀序，當(dāng)項目僅包含二元屬性時，有幾個特殊的相似度度量方法活烙。首選計算四個值：$M01$,$M10$,$M11$,$M00$=$x$為0徐裸，$y$為1的屬性數(shù)量，以此類推啸盏。我們可以計算1.簡單搭配系數(shù) $ SMC=\frac{number\ of\ matches}{number\ of\ attributes}=\frac{M11+M00}{M01+M10+M11+M00} $重贺；2.Jaccard系數(shù)$JC=\frac{M11}{M01+M10+M11}$。以及Jaccard的一種變化（Tanimoto）：$ d=\frac{x\cdot y}{|x|^2+|x|2-x\cdot y} $回懦。

采樣

采樣（Sampling）是DM中從大數(shù)據(jù)集中選擇相關(guān)數(shù)據(jù)子集的一種主要技術(shù)玫荣。Sampling還可以用來創(chuàng)建訓(xùn)練集和測試集癌蓖。訓(xùn)練集用來學(xué)習(xí)參數(shù)和算法的配置虽画。測試集用來評估模型和訓(xùn)練階段得到的配置數(shù)據(jù)來確保未觀測到的數(shù)據(jù)在模型上也表現(xiàn)得很好箱吕。

采樣的關(guān)鍵問題是得到的子集是否具有代表性。最簡單的采樣技術(shù)就是隨機采樣舟茶，等概率的抽取數(shù)據(jù)谭期。此外，還有其他的隨機方法吧凉。比如隧出，在分層（stratified）采樣中，吧數(shù)據(jù)根據(jù)特定的特征劃分成幾個部分阀捅，然后在幾個部分上獨立隨機采樣鸳劳。

現(xiàn)在比較通用的方法是使用標(biāo)準(zhǔn)不放回隨機抽樣，80/20劃分訓(xùn)練集和測試集也搓。

為避免劃分數(shù)據(jù)集的采樣導(dǎo)致過度專一化（over-specialization），訓(xùn)練過程應(yīng)該重復(fù)多次涵紊。不同的訓(xùn)練集/測試集用來重復(fù)訓(xùn)練/測試K次傍妒。最終，取K次試驗的平均成果摸柄。這個過程就是交叉驗證機制颤练。有幾個交叉驗證技術(shù)：1.重復(fù)隨機采樣，把標(biāo)準(zhǔn)隨機采樣重復(fù)K次驱负。2.n-fold交叉驗證嗦玖，數(shù)據(jù)集被分成n個folds，一個fold用來測試模型跃脊，其余n-1個用來訓(xùn)練模型宇挫。然后交叉驗證過程被重復(fù)n次，每次使用不同的子樣本作為驗證集酪术。3.leave-one-out（LOO）方法器瘪，它可以被視為n-Fold的極端情況翠储，它把每個樣本單獨做為驗證集。

降維

稀疏性和維數(shù)災(zāi)難的問題常常出現(xiàn)在RS中橡疼。因此援所，降維技術(shù)非常有必要的。RS中最常用的兩個降維技術(shù)是：1.主成分分析（PCA）欣除，2.奇異值分解（SVD）住拭。

PCA

PCA是一種經(jīng)典的發(fā)現(xiàn)高維數(shù)據(jù)中的模式的統(tǒng)計方法。

第一成分的方差的量是大于第二成分方差的量的历帚。我們可以通過忽略掉那些在方差上貢獻較小的成分來達到降維的目的滔岳。

圖2顯示了二維高斯聯(lián)合分布點云的PCA分析。在數(shù)據(jù)聚集之后抹缕，主成分被計算為$u_1$和$u_2$澈蟆。注意新坐標(biāo)的長度是他們特征向量中包含的能量。由圖2的例子卓研，第一個成分$u_1$包含了83.5%的能量趴俘，這意味著移除成分$u_2$僅僅損失16.5%的信息。一般而言奏赘，選擇$m^{'}$個成分寥闪，使之能量累積超過特定的閾值，一般為90%磨淌。

f2.2.jpg

SVD

奇異值分解是一種強力的降維技術(shù)疲憋。SVD降維的關(guān)鍵問題是找到一個低維特征空間，它能代表一些語義概念信息（在LSA中是一種基礎(chǔ)方法）梁只。

SVD算法的核心依賴于如下理論：

給出一個矩陣$A$,總能分解成$A=U\lambda V^T$缚柳。給一個$n\times m$的矩陣$A$（n個項目，m個特征）搪锣，我們能獲得一個$n\times r$的矩陣$U$（n個項目秋忙，r個概念），和一個$r\times r$的對角陣$\lambda$（概念的強度）构舟，以及一個$m\times r$的矩陣$V$（m個特征灰追，r個概念）。

f2.3.jpg

把r個特征值降序排列狗超，取前k個弹澎，這樣就得到了rank-k的A矩陣的近似矩陣$A_k=U_k\lambda_kV_k^T$。

SVD有兩個使用方式努咐，第一種是利用SVD尋找用戶-產(chǎn)品之間的潛在關(guān)系苦蒿，從而預(yù)測評分。第二種是利用SVD的產(chǎn)生的低維空間提高近鄰方法的精度渗稍。

SVD的優(yōu)點是當(dāng)新加入的數(shù)據(jù)時刽肠，不需要重新計算模型溃肪。SVD方法在Netflix大賽中取得了巨大的成功。

順帶一提音五，還有很多MF的方法惫撰，如非負矩陣分解（NMF）等。這些方法和SVD十分相似躺涝。

去噪

原始數(shù)據(jù)中可能有一些不同的噪聲厨钻，比如丟失的值或無用的數(shù)據(jù)等。因此坚嗜，降噪是去除數(shù)據(jù)中不良影響夯膀，最大化數(shù)據(jù)信息量的重要過程。

在RS中苍蔬，主要區(qū)分兩類噪聲：natural和malicious（惡意的）诱建。

malicious噪聲能夠影響RS的輸出。而natural噪聲對RS的表現(xiàn)的影響可以忽略不計碟绑。

分類

一個分類器是將特征空間映射到標(biāo)簽空間中俺猿，舉一個餐館的例子，根據(jù)描述餐館的一系列特征格仲，它們可以被分為（good押袍，bad）兩類。

有兩種分類：1.有監(jiān)督的凯肋，即標(biāo)簽或類目是已知的谊惭。2.無監(jiān)督的，即標(biāo)簽或類目是未知的侮东。

最近鄰

第一種是基于實例的分類器圈盔，通常也叫做最近鄰分類器（kNN）。如果要給一個點分類悄雅，kNN分類器從訓(xùn)練數(shù)據(jù)中尋找它的k個最近的點驱敲，然后依賴最近的這些點給予標(biāo)記。

給出一個需要分類的點$q$煤伟，和一個訓(xùn)練集$ X={{x_1,l_1}\dots{x_n}} $，$x_j$是第j個元素木缝，$l_j$是它的標(biāo)簽便锨，然后尋找到一個k最近鄰的子集$ Y={{y_1,l_1}\dots{y_n}} $,其中$Y\in X$而且$\sum_1^kd(q,y_k)$是最小的。Y中包含了X中與$q$最接近的k個點我碟。然后放案，$q$可以標(biāo)記為$l=f({l_1\dots l_k})$。

f2.4.jpg

可能現(xiàn)在kNN最大的挑戰(zhàn)就是$k$的選擇矫俺。如果$k$太小吱殉，那么分類器就會對噪聲點十分敏感掸冤，反之，如果$k$太大友雳，鄰域內(nèi)就會包含太多其他類的點稿湿。

kNN在RS中被廣泛使用，在CF中押赊，尋找相似的用戶或項目饺藤。而且它還具有惰性學(xué)習(xí)的優(yōu)點，維護模型的成本低流礁。

決策樹

決策樹是以樹結(jié)構(gòu)組織目標(biāo)屬性或類的分類器涕俗。決策樹包含兩類節(jié)點a）決策節(jié)點，決定目標(biāo)屬性屬于那一顆子樹神帅，b）葉子節(jié)點再姑，顯示目標(biāo)屬性的值

通常的一些決策樹：Hunts Algorithm，CART找御，ID3元镀，C4.5，SLIQ萎坷，SPRINT凹联。其中Hunt Algorithm是最早也是最容易理解的。

決策樹的劃分策略可以根據(jù)最大化信息增益得到：
$$ \Delta_i=I(parent)-\mathop{\sum}\limits_{j=1}^{k_i}\frac{N(v_j)I(v_j)}{N} $$

其中哆档，$k_i$是屬性$i$的值蔽挠，$N$是觀察的到的數(shù)量，$v_j$是根據(jù)屬性$i$值的第$j$個劃分瓜浸。除此之外澳淑，還有一種度量方法是Gini指數(shù)。

決策樹迭停止條件是所有觀測值都屬于同一類插佛。但在實踐中杠巡，我們需要對龐大的決策樹進行剪枝操作，簡化決策樹的復(fù)雜度雇寇。

使用決策樹構(gòu)建分類器的主要優(yōu)點是消耗低氢拥，對未知實例分類的速度快。

決策樹可能會用于基于模型的RS方法中锨侯。一種可能性是使用內(nèi)容特征去建立一個決策樹嫩海，它將所有與用戶偏好有關(guān)的變量都建模。另外囚痴，決策樹還可以作為RS的一部分叁怪，比如它可以過濾一部分用戶。

基于規(guī)則的分類器

基于規(guī)則的分類器使用“if...then...”規(guī)則的集合來分類數(shù)據(jù)深滚。規(guī)則的前提或是條件是屬性連詞的表達式奕谭。規(guī)則的結(jié)論是一個正或者負的分類涣觉。

如果對象的屬性滿足規(guī)則的條件，我們可以說規(guī)則Ｒ覆蓋對象ｘ血柳。我們定義規(guī)則的覆蓋性為滿足前提的部分記錄官册。另一方面，我們定義準(zhǔn)確性為既滿足前提又滿足結(jié)論的部分記錄混驰。如果規(guī)則彼此之間是獨立的攀隔，我們說分類器包含互斥的規(guī)則（mutually exclusive rules）。最后栖榨，如果屬性值得所有可能組合都被覆蓋的話昆汹，即，一個記錄至少被一個規(guī)則覆蓋婴栽，我們認為分類器具有詳盡規(guī)則（exhausitive rules）满粗。

為了建立一個基于規(guī)則的分類器，我們可以用從數(shù)據(jù)中直接抽取規(guī)則的直接方法愚争。這種方法的例子是RIPPER映皆，或CN2。另一方面轰枝，使用間接的方法從其它分類模型中抽取規(guī)則很常見捅彻，例如：決策樹模型或是神經(jīng)模型。

基于規(guī)則分類器的優(yōu)點是它們表示很明確鞍陨，因為它們是符號化的并且可以在沒有任何轉(zhuǎn)化的情況下操作數(shù)據(jù)的屬性步淹。

但是，與決策樹方法類似诚撵，建立一個完整基于規(guī)則的推薦模型是很難的缭裆。事實上，這種方法在推薦的環(huán)境中不是很流行寿烟，因為得到一個基于規(guī)則的系統(tǒng)意味著我們要么具有一些決策過程中的顯式的先驗知識澈驼，要么我們從另一個模型中提取規(guī)則，例如決策樹筛武。但是基于規(guī)則的系統(tǒng)通過注入一些領(lǐng)域知識或者是商業(yè)規(guī)則來提高推薦系統(tǒng)的性能缝其。

貝葉斯分類器

貝葉斯分類器是解決分類問題的一個概率框架。它基于條件概率和貝葉斯理論徘六。貝葉斯學(xué)派使用概率來代表從數(shù)據(jù)中學(xué)習(xí)到的關(guān)系的不確定性内边。先驗代表了我們的期望值，或者真正關(guān)系可能是什么的先驗知識硕噩。特別地假残，給定數(shù)據(jù)后缭贡，模型的概率（后驗概率）是與似然值乘以先驗概率的乘積成比例的炉擅。似然值部分包含了數(shù)據(jù)的影響辉懒，而先驗概率則表明觀測數(shù)據(jù)之前模型的可信度。

貝葉斯分類器把每個屬性和類標(biāo)簽都看做隨機變量谍失。給定一個具有$N$個屬性（$A_1,A_2,\dots,A_N$）的記錄眶俩，目標(biāo)預(yù)測類$C_k$，方法是在給定數(shù)據(jù)$P(C_k|A_1,A_2,\dots,A_N)$,找到能夠最大化該類后驗概率的$C_k$的值快鱼。應(yīng)用貝葉斯理論颠印，$P(C_k|A_1,A_2,\dots,A_N)\propto P(A_1,A_2,\dots,A_N|C_k)P(C_k)$。

一個特殊但是最常用的分類器是樸素貝葉斯分類器抹竹。它假設(shè)屬性的概率是相互獨立的：$P(A_1,A_2,\dots,A_N|C_k)=P(A_1|C_k)P(A_2|C_k)\dots P(A_N|C_k)$线罕。

樸素貝葉斯的主要好處是，受孤立噪音點和不相關(guān)的屬性的影響小窃判，并且在概率估算期間可以通過忽略實例來處理缺失值钞楼。但是，獨立性假設(shè)對一些相互關(guān)聯(lián)的屬性來說可能不成立袄琳。在這種情況下询件，通常的方法是使用所謂的貝葉斯信念網(wǎng)絡(luò)（BBN）（或是簡稱貝葉斯網(wǎng)絡(luò)）。BBN使用非循環(huán)圖表示屬性之間的依賴性唆樊，并使用概率表表示結(jié)點與直接父親之間的聯(lián)系宛琅。和樸素貝葉斯分類器方法類似，BBN可以很好地處理不完整的數(shù)據(jù)逗旁，對于模型的過擬合有相當(dāng)?shù)慕研浴?/p>

貝葉斯分類器在基于模型的推薦系統(tǒng)中特別受歡迎嘿辟。它們經(jīng)常被用來為基于內(nèi)容的推薦生成模型。當(dāng)然痢艺，它們也被用于協(xié)同環(huán)境中仓洼。

人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)（ANN）由一組內(nèi)連接點和帶權(quán)鏈接組成，其想法來自于生物大腦的結(jié)構(gòu)堤舒。ANN中的節(jié)點被稱為神經(jīng)元色建，類似于生物神經(jīng)。這些簡單的功能單元組成網(wǎng)絡(luò)舌缤，網(wǎng)絡(luò)在用有效數(shù)據(jù)訓(xùn)練之后能夠?qū)W習(xí)分類問題箕戳。

f2.5.jpg

ANN的最簡單模型是感知器模型，如圖5所示国撵。如果我們把激活函數(shù)$\phi$特指為簡單的閾值函數(shù)陵吸，則輸出就是根據(jù)每條鏈接的權(quán)重將輸入值累加，然后和某個閾值$\theta_K$相比較介牙。輸出函數(shù)為：
[
y_k=\left{
\begin{array}{ll}
1,\ & if \sum x_iw_{ki}\geq\theta_k \
0,\ & if \sum x_iw_{ki}<\theta_k
\end{array}
\right.
]

感知模型是具有簡單和有效學(xué)習(xí)算法的線性聚類器壮虫。但是，除了使用在感知模型中的閾值函數(shù)之外，還有幾種其它對于激活函數(shù)通用的選擇囚似，比如：多層感知機剩拢，正切雙曲，或者是階梯函數(shù)饶唤。

ANN可以有許多的層徐伐。在ANN中的層被分成三種類型：輸入，隱藏募狂，輸出办素。輸入層的單元響應(yīng)進入網(wǎng)絡(luò)的數(shù)據(jù)。隱藏層接受從輸入單元中的帶權(quán)輸出祸穷。輸出層響應(yīng)隱藏層中的帶權(quán)輸出并且產(chǎn)生最終的網(wǎng)絡(luò)輸出性穿。

ANN最主要的優(yōu)點是（取決于激活函數(shù)）能做非線性的分類任務(wù)，并且由于并行屬性雷滚，它們高效甚至能夠在部分網(wǎng)絡(luò)受損的情況下操作季二。主要的缺點是，它很難對于給定的問題給出理想的網(wǎng)絡(luò)拓撲揭措，并且一旦拓撲被決定它的表現(xiàn)水平就會位于分類錯誤率的下限胯舷。

ANN能夠以類似于貝葉斯網(wǎng)絡(luò)的方法被用來構(gòu)建基于模型的推薦系統(tǒng)。但是绊含，沒有令人信服的研究表明ANN是否會有性能的提升桑嘶。

支持向量機

支持向量機分類的目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)的線性超平面（決策邊界），以邊界最大化的方式分離數(shù)據(jù)躬充。例如逃顶，如果我們在二維平面上看兩類分離的問題，像圖6闡述的那樣充甚，很容易觀察到分成兩個類有許多種可能的邊界線以政。每一個邊界線都有一個相關(guān)的邊緣。SVM后面的理論支持是伴找，如果我們選擇邊緣最大化的那一個盈蛮，我們將來對未知的物品分類出錯的可能性就越小。

f2.6.jpg

兩類之間的一個線性劃分是通過函數(shù)$w\cdot x+b=0$來實現(xiàn)的技矮。我們定義能夠劃分物品類+1或是-1的函數(shù)抖誉，只要這些物品是被來自類劃分函數(shù)的某個最小距離分開的。相應(yīng)的函數(shù)為：
$$
f(x)=\left{
\begin{array}{ll}
1,\ & if\ w\cdot x+b\geq 1\
-1,\ & if\ w\cdot x+b\leq -1
\end{array}
\right.
$$

$$ Margin=\frac{2}{|w|^2} $$

根據(jù)SVM的主要原理衰倦，我們想要最大化兩個類之間的邊緣（Margin）袒炉。事實上這等價于在給定$f(x)$的條件下，最小化倒數(shù)$L(w)=\frac{|w|^2}{2}$樊零。

如果物品不是線性分離的我磁，我們可以通過引入一個松弛變量來把SVM轉(zhuǎn)變?yōu)檐涍吘壏诸惼鳌Ｔ谶@種情況下，新的$f(x)$和$L(w)$函數(shù)定義如下：
$$ L(w)=\frac{|w|^{2}{2}+C\mathop{\sum}\limits_{i=1}}N\varepsilon$$

$$
f(x)=\left{
\begin{array}{ll}
1,\ & if\ w\cdot x+b\geq 1-\varepsilon\
-1,\ & if\ w\cdot x+b\leq -1+\varepsilon
\end{array}
\right.
$$

另一方面夺艰，如果決策邊界是非線性的叛溢，我們需要轉(zhuǎn)換數(shù)據(jù)到高維的空間。這個轉(zhuǎn)換的完成得益于名為核技巧的數(shù)學(xué)變換劲适。最基本的想法是通過核函數(shù)取代在公式2.8中的點積。對于核函數(shù)有許多不同的可行的選擇厢蒜，比如：多項式或者是多層感知器霞势。但是最常用的核函數(shù)是徑向基函數(shù)族（RBF）(高斯核)。

支持向量機最近已經(jīng)在許多的環(huán)境中獲得較好的性能和效率斑鸦。在推薦系統(tǒng)里愕贡，SVM最近也顯示出了顯著效果。

分類器的集成

使用分類器集成背后的最基本的思想是,從訓(xùn)練數(shù)據(jù)構(gòu)造一系列的分類器,并通過聚集預(yù)測值來預(yù)測類標(biāo)簽巷屿。只要我們能假設(shè)這些分類器都是獨立的固以，分類器集成就有效。在這種情況下嘱巾，我們可以確定分類器產(chǎn)生的最糟糕的結(jié)果與在集成中的最壞分類是一樣的憨琳。因此，結(jié)合具有相似的分類錯誤的獨立分類器將只會提升結(jié)果旬昭。

為了產(chǎn)生集成篙螟，有幾種可能的方法。最常用的兩個技術(shù)是Bagging和Boosting问拘。在Bagging方法中遍略，我們采用帶替換的抽樣，在每一個自舉樣本（bootstrap sample）上建立分類骤坐。每個樣本被選擇的概率為$(1-\frac{1}{N})^N$绪杏，注意如果$N$足夠大，它收斂至$1-\frac{1}{e}\approx 0.623$纽绍。在Boosting 方法中蕾久，我們通過更加關(guān)注之前錯誤分類的記錄，使用迭代過程自適應(yīng)地改變訓(xùn)練數(shù)據(jù)的分布拌夏。一開始腔彰，所有的記錄都被分配相同的權(quán)值。但是辖佣，不像Bagging 方法霹抛，在每一輪的提升中權(quán)值是可以變化的：被錯誤分類的記錄權(quán)值將會增加，同時正確分配的記錄的權(quán)值將會降低卷谈。Boosting 方法的例子是AdaBoost 算法杯拐。

分類器集成使用的例子在推薦領(lǐng)域里面非常的實用。事實上，任何一個混合技術(shù)都可以理解成以一種方式集成或另外幾個分類器的集成端逼。實驗結(jié)果顯示朗兵，集成器能產(chǎn)生比其它任何孤立的分類器更好的結(jié)果。

評估分類器

推薦系統(tǒng)中被接受最常用的指標(biāo)是預(yù)測興趣（評分）和測量值的均方差（MAE）或均方根誤差（RMSE）顶滩。這些指標(biāo)在計算精度時對推薦系統(tǒng)的目標(biāo)沒有任何假設(shè)余掖。但是，正如McNee et al.指出的那樣礁鲁，除了精確度之外還有許多指標(biāo)來決定物品是否要被推薦盐欺。

下一步是考慮的是，“現(xiàn)實”中推薦系統(tǒng)的目的是產(chǎn)生一個topN推薦列表仅醇，以及依賴于能多好地分辨出值得推薦的物品來評估這個推薦系統(tǒng)冗美。如果把推薦看作分類問題，就可以使用評估分類器的著名指標(biāo)析二，諸如：準(zhǔn)確度和召回率粉洼。

為了評估一個模型，我們一般考慮以下的指標(biāo)：真正（TP）：分到類A且真的屬于類A的實例數(shù)量叶摄；真負（TN）：沒有分到類A且真的不屬于類A的實例數(shù)量属韧；假正（FP）：分到類A但不屬于類A的實例數(shù)量；假負（FN）：沒有分到類A但屬于類A的實例數(shù)量蛤吓。

最常用來衡量模型性能是定義正確分類的（屬于或不屬于給定的類）實例和總的實例數(shù)量之間的比率：精確度=$(TP+TN)/(TP+TN+FP+FN)$但是挫剑，精確度在許多的例子中有誤導(dǎo)。想象一個帶有99900個類A的樣本和100個類B的樣本的兩類分類問題柱衔。如果分類器簡單地預(yù)測一切屬于類A樊破，計算精度可能是99.9%，但是模型性能值得懷疑唆铐，因為它從沒有發(fā)現(xiàn)類B中的樣本哲戚。改進這種估值的一種方法是定義代價矩陣，定義將類B的樣本分給類A的代價艾岂。

模型性能的其它常用指標(biāo)顺少，特別是在信息檢索中，是準(zhǔn)確率和召回率王浴。準(zhǔn)確率脆炎，定義為$P = TP/(TP+FP)$，是一種在分樣本到類A中犯多少錯誤的指標(biāo)氓辣。另一方面秒裕，召回率，$R = TP/(TP+FN)$钞啸，衡量沒有留下本應(yīng)該劃分到類中的樣本的程度几蜻。$F_1$指標(biāo)綜合了這兩個指標(biāo)：$F_1=\frac{2RP}{R+P}=\frac{2TP}{2TP+FN+FP}$喇潘。

有時我們會比較幾個相互競爭的模型，而不是單獨評估它們的性能梭稚。為此颖低，我們使用在1950年代開發(fā)的用來分析噪音信號的技術(shù)：接受特征曲線（ROC）。ROC曲線描述了正確擊中和假警告之間的特征弧烤。每一個分類的性能用曲線上的點表示（見圖7）忱屑。

f2.7.jpg

聚類分析

聚類，也被稱作為無監(jiān)督的學(xué)習(xí)暇昂，分配物品到一個組中使得在同一組中的物品比不同組中的物品更加類似：目的是發(fā)現(xiàn)存在數(shù)據(jù)中的自然（或者說是有意義）的組莺戒。相似度是由距離衡量來決定，諸如在2.1中敘述的话浇。聚類算法的目標(biāo)是在最小化群內(nèi)距離的同時最大化群間距離。

聚類算法有兩個主要的類別：分層和劃分闹究。劃分聚類算法把數(shù)據(jù)劃分成非重合的聚類幔崖，使得每一個數(shù)據(jù)項確切在一個聚類中。分層聚類算法在已知聚類上繼續(xù)聚合物品渣淤，生成聚類的嵌套集合赏寇，組成一個層級樹。

許多聚類算法試圖最小化一個函數(shù)來衡量聚類的質(zhì)量价认。這樣的質(zhì)量函數(shù)一般被稱為目標(biāo)函數(shù)嗅定，因此聚類可以看作最優(yōu)化的問題：理想聚類算法考慮所有可能數(shù)據(jù)劃分，并且輸出最小化質(zhì)量函數(shù)的劃分用踩。但相應(yīng)的最優(yōu)化問題是NP困難問題渠退，因此許多算法采用啟發(fā)式方法（例如：k-means算法中局部最優(yōu)化過程最可能結(jié)束于局部最小）脐彩。

k-Means

k-Means聚類是一種分塊方法碎乃。函數(shù)劃分$N$個物品的數(shù)據(jù)集到$k$個不相關(guān)的子集$S_j$，其中包含$N_j$個項目惠奸，以便于它們按照給定的距離指標(biāo)盡可能的靠近梅誓。在分塊中每一個聚類通過它的$N_j$個成員和它的中心點$\lambda_j$來定義。每一個聚類的中心點是聚類中所有其它物品到它的距離之和最小的那個點佛南。因此梗掰，我們能把k-means定義為一個最小化$E=\sum_1^k\sum_{n\in S_j}d(x_n,\lambda_j)$的一個迭代過程，$x_n$是代表第$n$個項目的向量嗅回，$\lambda_j$是$S_j$的中心點及穗，$d$是距離函數(shù)。

算法一開始會隨機選擇k個中心點绵载。所有物品都會被分配到它們最靠近的中心節(jié)點的類中敦冬。由于聚類新添加或是移出物品，新聚類的中心節(jié)點需要更新拔第，聚類的成員關(guān)系也需要更新尤误。這個操作會持續(xù)下去，直到再沒有物品改變它們的聚類成員關(guān)系倔幼。算法的第一次迭代的時候，大部分的聚類的最終位置就會發(fā)生，因此缓窜，跳出迭代的條件一般改變成“直到相對少的點改變聚類”來提高效率。

基礎(chǔ)的k-means是極其簡單和有效的算法谍咆。但是禾锤，它有幾個缺陷：（1）為了選擇合適的k值，假定有先驗的數(shù)據(jù)知識（2）最終的聚類對于初始的中心點非常敏感摹察。（3）它會產(chǎn)生空聚類恩掷。k-means也有幾個關(guān)于數(shù)據(jù)的缺陷：當(dāng)聚類是不同的大小，密度供嚎，非球狀形狀時黄娘，就會有問題，并且當(dāng)數(shù)據(jù)包含異常值時它也會有問題克滴。

改進的k-Means

基于密度的聚類算法逼争。諸如：DBSCAN通過建立密度定義作為在一定范圍內(nèi)的點的數(shù)量。例如：DBSCAN定義了三種點：核心點是在給定距離內(nèi)擁有超過一定數(shù)量鄰居的點劝赔；邊界點沒有超過指定數(shù)量的鄰居但屬于核心點鄰居誓焦；噪音點是既不是核心點也不是邊界點。算法迭代移除掉噪音數(shù)據(jù)并且在剩下的點上進行聚類着帽。

消息傳遞聚類算法杂伟。它是最近基于圖聚類方法的系列之一。消息傳遞算法沒有一開始就將節(jié)點的初始子集作為中心點仍翰，然后逐漸調(diào)適稿壁，而是一開始就將所有節(jié)點都看作中心點，一般稱為標(biāo)本歉备。在算法執(zhí)行時傅是，這些點，現(xiàn)在已經(jīng)是網(wǎng)絡(luò)中的節(jié)點了蕾羊，會交換消息直到聚類逐漸出現(xiàn)喧笔。相似傳播是這種系列算法的代表，通過定義節(jié)點之間的兩種信息來起作用：“責(zé)任”龟再，反映了在考慮到其它潛在標(biāo)本的情況下书闸，接收點有多適合作為發(fā)送點的標(biāo)本；“可用性”利凑，從候選標(biāo)本發(fā)送到節(jié)點浆劲，它反映了在考慮到其它選擇相同標(biāo)本的節(jié)點支持的情況下嫌术，這個節(jié)點選擇候選標(biāo)本作為其標(biāo)本的合適程度。

分層聚類牌借。它按照層級樹（樹枝形結(jié)構(gòu)聯(lián)系圖）的結(jié)構(gòu)產(chǎn)生一系列嵌套聚類度气。傳統(tǒng)的分層算法使用一個相似度或者是距離矩陣來合并或者是分裂一個聚類。有兩種主要方法來分層聚類膨报。在聚集分層聚類中磷籍，我們以點作為個體聚類，并且每一個步合并最近的聚類對现柠，直到只有一個（或是k個聚類）聚類剩下院领。分裂分層聚類從一個包含所有物品的聚類開始，并且每一個分裂每一聚類够吩，直到每一聚類包含一個點（或是有K個聚類）比然。

就我們所知，諸如前面提到k-means的替代方法沒有應(yīng)用在推薦系統(tǒng)中周循。k-means算法的簡單和效率優(yōu)于它的替代算法强法。

關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘關(guān)注于規(guī)則的發(fā)現(xiàn)，其它能夠根據(jù)事務(wù)中出現(xiàn)其它物品來預(yù)測出現(xiàn)某個物品鱼鼓。兩個物品被發(fā)現(xiàn)相關(guān)只意味著共同出現(xiàn)拟烫，但是沒有因果關(guān)系该编。

我們定義物品集為一個或多個物品的集合（例如（牛奶迄本，啤酒，尿布））课竣。k-物品集是包含k個物品的集合嘉赎。給定物品的頻繁度被稱之為支持量（比如：（牛奶，啤酒于樟，尿布）=131）公条。并且物品集的支持度是包含它的事務(wù)的比例(例如：（牛奶，啤酒迂曲，尿布）=0.12)靶橱。頻繁物品集是支持度
大于或等于最小支持度閾值的物品集。關(guān)聯(lián)規(guī)則是公式$X\Rightarrow Y$公式的表達式路捧，其中X和Y是物品集（例如：牛奶关霸，尿布$\Rightarrow$啤酒）。

給定一組事務(wù)集合$T$杰扫，關(guān)聯(lián)規(guī)則挖掘的目標(biāo)是發(fā)現(xiàn)具有支持度$\geq$最小支持度閾值以及置信度$\geq$最小置信度閾值的所有規(guī)則队寇。由于暴力計算開銷巨大，我們采用兩步方法：(1)產(chǎn)生了所有支持度$\geq$ 最小支持度的物品集（頻繁項集生成）章姓。(2)從每一頻繁物品集中產(chǎn)生高置信規(guī)則（規(guī)則產(chǎn)生）佳遣。

有幾個技術(shù)來優(yōu)化頻繁物品集的產(chǎn)生识埋。在一個廣泛的意義上，它們可以被分成這些：嘗試最小化候選集數(shù)量（M）零渐，降低事務(wù)量（N）窒舟，降低比較量數(shù)量（NM）。但是最常用的方法是使用先驗規(guī)
則來降低候選數(shù)量相恃。這個原則表明如果物品集是頻繁的辜纲，那么所有的子集也是頻繁的。支持度的衡量標(biāo)準(zhǔn)已經(jīng)驗證了這一點拦耐，因為一個物品集的支持度永遠不會超過它子集的支持度耕腾。Apriori算法是這個規(guī)則實際的實現(xiàn)。

給定一個頻繁集L杀糯，產(chǎn)生規(guī)則時的目的是發(fā)現(xiàn)所有滿足最小的置信度需求的非空子集扫俺。如果$|L|=k$，那么有$2k2$條候選關(guān)聯(lián)規(guī)則固翰。因此狼纬，在生成頻繁物品集時，需要找到高效的方法來生成規(guī)則骂际。對于Apriori算法疗琉，我們能通過合并規(guī)則結(jié)果中共用相同前綴的兩個規(guī)則來產(chǎn)生候選規(guī)則。

關(guān)聯(lián)規(guī)則在發(fā)現(xiàn)模式和推動個性化市場營銷方面的顯著效果聞名已久了歉铝。但是盈简，盡管這些方法和推薦系統(tǒng)的目標(biāo)之間有明顯的關(guān)聯(lián)，但是它們還是沒有成為主流太示。主要原因是這種方法類似于基于物品的CF但缺少靈活性柠贤，因為它需要事務(wù)這個明確的概念--事件共同出現(xiàn)在某個給定的會話中。

總結(jié)

本章介紹了在設(shè)計推薦系統(tǒng)中可能用到的主要的數(shù)據(jù)挖掘方法和技術(shù)类缤。我們也總結(jié)了在文獻中提到的用法臼勉，提供了如何以及在哪用到它們一些粗略指導(dǎo)。