第14章 利用SVD簡化數(shù)據(jù)

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

利用SVD簡化數(shù)據(jù)首頁

SVD 概述

奇異值分解（SVD, Singular Value Decomposition）:
    提取信息的一種方法炎功，可以把 SVD 看成是從噪聲數(shù)據(jù)中抽取相關(guān)特征。從生物信息學(xué)到金融學(xué)缓溅，SVD 是提取信息的強大工具蛇损。

SVD 場景

信息檢索-隱形語義檢索（Lstent Semantic Indexing, LSI）或 隱形語義分析（Latent Semantic Analysis, LSA）

隱性語義索引：矩陣 = 文檔 + 詞語

• 是最早的 SVD 應(yīng)用之一，我們稱利用 SVD 的方法為隱性語義索引（LSI）或隱性語義分析（LSA）坛怪。

LSA舉例

推薦系統(tǒng)

1. 利用 SVD 從數(shù)據(jù)中構(gòu)建一個主題空間淤齐。
2. 再在該空間下計算其相似度。(從高維-低維空間的轉(zhuǎn)化酝陈，在低維空間來計算相似度床玻，SVD 提升了推薦系統(tǒng)的效率。)

主題空間案例1

• 上圖右邊標(biāo)注的為一組共同特征沉帮，表示美式 BBQ 空間锈死；另一組在上圖右邊未標(biāo)注的為日式食品 空間。

圖像壓縮

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除對角線的0), 幾乎獲得了10倍的壓縮比穆壕。

SVD公式

SVD 原理

SVD 工作原理

矩陣分解

• 矩陣分解是將數(shù)據(jù)矩陣分解為多個獨立部分的過程待牵。
• 矩陣分解可以將原始矩陣表示成新的易于處理的形式，這種新形式是兩個或多個矩陣的乘積喇勋。（類似代數(shù)中的因數(shù)分解）
• 舉例：如何將12分解成兩個數(shù)的乘積缨该？（1，12）川背、（2贰拿，6）熄云、（3，4）都是合理的答案缴允。

SVD 是矩陣分解的一種類型，也是矩陣分解最常見的技術(shù)

• SVD 將原始的數(shù)據(jù)集矩陣 Data 分解成三個矩陣 U练般、∑、V
• 舉例：如果原始矩陣 \(Data_{m*n}\) 是m行n列敞贡，
  • \(U_{m*n}\) 表示m行n列
  • \(∑_{m*k}\) 表示m行k列
  • \(V_{k*n}\) 表示k行n列摄职。

\(Data_{m*n} = U_{m*k} * ∑{k*k} * V{k*n}\)

SVD公式

具體的案例：（大家可以試著推導(dǎo)一下：https://wenku.baidu.com/view/b7641217866fb84ae45c8d17.html ）

SVD公式的測試案例

• 上述分解中會構(gòu)建出一個矩陣∑虑稼，該矩陣只有對角元素势木，其他元素均為0(近似于0)歌懒。另一個慣例就是啦桌，∑的對角元素是從大到小排列的及皂。這些對角元素稱為奇異值。
• 奇異值與特征值(PCA 數(shù)據(jù)中重要特征)是有關(guān)系的板驳。這里的奇異值就是矩陣 \(Data * Data^T\) 特征值的平方根碍拆。
• 普遍的事實：在某個奇異值的數(shù)目(r 個=>奇異值的平方和累加到總值的90%以上)之后若治，其他的奇異值都置為0(近似于0)感混。這意味著數(shù)據(jù)集中僅有 r 個重要特征，而其余特征則都是噪聲或冗余特征婆跑。

SVD 算法特點

優(yōu)點：簡化數(shù)據(jù)，去除噪聲滑进，優(yōu)化算法的結(jié)果
缺點：數(shù)據(jù)的轉(zhuǎn)換可能難以理解
使用的數(shù)據(jù)類型：數(shù)值型數(shù)據(jù)

推薦系統(tǒng)

推薦系統(tǒng) 概述

推薦系統(tǒng)是利用電子商務(wù)網(wǎng)站向客戶提供商品信息和建議募谎，幫助用戶決定應(yīng)該購買什么產(chǎn)品，模擬銷售人員幫助客戶完成購買過程近哟。

推薦系統(tǒng) 場景

1. Amazon 會根據(jù)顧客的購買歷史向他們推薦物品
2. Netflix 會向其用戶推薦電影
3. 新聞網(wǎng)站會對用戶推薦新聞頻道

推薦系統(tǒng) 要點

基于協(xié)同過濾(collaborative filtering) 的推薦引擎

• 利用Python 實現(xiàn) SVD(Numpy 有一個稱為 linalg 的線性代數(shù)工具箱)
• 協(xié)同過濾：是通過將用戶和其他用戶的數(shù)據(jù)進行對比來實現(xiàn)推薦的。
• 當(dāng)知道了兩個用戶或兩個物品之間的相似度疯淫，我們就可以利用已有的數(shù)據(jù)來預(yù)測未知用戶的喜好戳玫。

基于物品的相似度和基于用戶的相似度：物品比較少則選擇物品相似度熙掺，用戶比較少則選擇用戶相似度咕宿±啵【矩陣還是小一點好計算】

• 基于物品的相似度：計算物品之間的距離缆镣。【耗時會隨物品數(shù)量的增加而增加】
• 由于物品A和物品C 相似度(相關(guān)度)很高董瞻，所以給買A的人推薦C。

使用SVD簡化數(shù)據(jù)-基于物品相似度

• 基于用戶的相似度：計算用戶之間的距離挟秤〕椋【耗時會隨用戶數(shù)量的增加而增加】
• 由于用戶A和用戶C 相似度(相關(guān)度)很高，所以A和C是興趣相投的人截珍，對于C買的物品就會推薦給A。

使用SVD簡化數(shù)據(jù)-基于用戶相似度

相似度計算

• inA, inB 對應(yīng)的是 列向量

1. 歐氏距離：指在m維空間中兩個點之間的真實距離云稚，或者向量的自然長度（即改點到原點的距離）。二維或三維中的歐氏距離就是兩點之間的實際距離静陈。
   • 相似度= 1/(1+歐式距離)
   • 相似度= 1.0/(1.0 + la.norm(inA - inB))
   • 物品對越相似诞丽，它們的相似度值就越大。
2. 皮爾遜相關(guān)系數(shù)：度量的是兩個向量之間的相似度僧免。
   • 相似度= 0.5 + 0.5*corrcoef() 【皮爾遜相關(guān)系數(shù)的取值范圍從 -1 到 +1，通過函數(shù)0.5 + 0.5*corrcoef()這個函數(shù)計算懂衩，把值歸一化到0到1之間】
   • 相似度= 0.5 + 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
   • 相對歐氏距離的優(yōu)勢：它對用戶評級的量級并不敏感。
3. 余弦相似度：計算的是兩個向量夾角的余弦值牵敷。
   • 余弦值 = (A·B)/(||A||·||B||) 【余弦值的取值范圍也在-1到+1之間】
   • 相似度= 0.5 + 0.5*余弦值
   • 相似度= 0.5 + 0.5*( float(inA.T*inB) / la.norm(inA)*la.norm(inB))
   • 如果夾角為90度法希，則相似度為0；如果兩個向量的方向相同苫亦，則相似度為1.0怨咪。

推薦系統(tǒng)的評價

• 采用交叉測試的方法润匙。【拆分數(shù)據(jù)為訓(xùn)練集和測試集】
• 推薦引擎評價的指標(biāo)： 最小均方根誤差(Root mean squared error, RMSE)趁桃，也稱標(biāo)準誤差(Standard error)，就是計算均方誤差的平均值然后取其平方根卫病。
  • 如果RMSE=1, 表示相差1個星級典徘；如果RMSE=2.5, 表示相差2.5個星級。

推薦系統(tǒng) 原理

• 推薦系統(tǒng)的工作過程：給定一個用戶逮诲，系統(tǒng)會為此用戶返回N個最好的推薦菜。
• 實現(xiàn)流程大致如下：
  1. 尋找用戶沒有評級的菜肴裆甩，即在用戶-物品矩陣中的0值齐唆。
  2. 在用戶沒有評級的所有物品中嗤栓，對每個物品預(yù)計一個可能的評級分數(shù)箍邮。這就是說：我們認為用戶可能會對物品的打分（這就是相似度計算的初衷）。
  3. 對這些物品的評分從高到低進行排序堪澎，返回前N個物品。

項目案例: 餐館菜肴推薦系統(tǒng)

項目概述

假如一個人在家決定外出吃飯樱蛤，但是他并不知道該到哪兒去吃飯剑鞍，該點什么菜。推薦系統(tǒng)可以幫他做到這兩點攒暇。

開發(fā)流程

收集 并 準備數(shù)據(jù)

項目數(shù)據(jù)導(dǎo)入

def loadExData3():
    # 利用SVD提高推薦效果，菜肴矩陣
    """
    行：代表人
    列：代表菜肴名詞
    值：代表人對菜肴的評分就轧，0表示未評分
    """
    return[[2, 0, 0, 4, 4, 0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
           [0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0],
           [3, 3, 4, 0, 3, 0, 0, 2, 2, 0, 0],
           [5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
           [4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5],
           [0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4],
           [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
           [0, 0, 0, 3, 0, 0, 0, 0, 4, 5, 0],
           [1, 1, 2, 1, 1, 2, 1, 0, 4, 5, 0]]

分析數(shù)據(jù): 這里不做過多的討論(當(dāng)然此處可以對比不同距離之間的差別)

訓(xùn)練算法: 通過調(diào)用 recommend() 函數(shù)進行推薦

recommend() 會調(diào)用 基于物品相似度 或者是 基于SVD，得到推薦的物品評分妒御。

• 1.基于物品相似度

基于物品相似度

歐式距離的計算方式

# 基于物品相似度的推薦引擎
def standEst(dataMat, user, simMeas, item):
    """standEst(計算某用戶未評分物品中，以對該物品和其他物品評分的用戶的物品相似度送讲，然后進行綜合評分)

    Args:
        dataMat         訓(xùn)練數(shù)據(jù)集
        user            用戶編號
        simMeas         相似度計算方法
        item            未評分的物品編號
    Returns:
        ratSimTotal/simTotal     評分（0～5之間的值）
    """
    # 得到數(shù)據(jù)集中的物品數(shù)目
    n = shape(dataMat)[1]
    # 初始化兩個評分值
    simTotal = 0.0
    ratSimTotal = 0.0
    # 遍歷行中的每個物品（對用戶評過分的物品進行遍歷惋啃，并將它與其他物品進行比較）
    for j in range(n):
        userRating = dataMat[user, j]
        # 如果某個物品的評分值為0，則跳過這個物品
        if userRating == 0:
            continue
        # 尋找兩個用戶都評級的物品
        # 變量 overLap 給出的是兩個物品當(dāng)中已經(jīng)被評分的那個元素的索引ID
        # logical_and 計算x1和x2元素的真值边灭。
        overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]
        # 如果相似度為0，則兩著沒有任何重合元素绒瘦，終止本次循環(huán)
        if len(overLap) == 0:
            similarity = 0
        # 如果存在重合的物品，則基于這些重合物重新計算相似度憨降。
        else:
            similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])
        # print 'the %d and %d similarity is : %f'(iten,j,similarity)
        # 相似度會不斷累加，每次計算時還考慮相似度和當(dāng)前用戶評分的乘積
        # similarity  用戶相似度授药，   userRating 用戶評分
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    # 通過除以所有的評分總和垂涯，對上述相似度評分的乘積進行歸一化，使得最后評分在0~5之間耕赘，這些評分用來對預(yù)測值進行排序
    else:
        return ratSimTotal/simTotal

• 2.基于SVD(參考地址：http://www.codeweblog.com/svd-%E7%AC%94%E8%AE%B0/)

基于SVD

# 基于SVD的評分估計
# 在recommend() 中，這個函數(shù)用于替換對standEst()的調(diào)用九火，該函數(shù)對給定用戶給定物品構(gòu)建了一個評分估計值
def svdEst(dataMat, user, simMeas, item):
    """svdEst(計算某用戶未評分物品中，以對該物品和其他物品評分的用戶的物品相似度岔激，然后進行綜合評分)

    Args:
        dataMat         訓(xùn)練數(shù)據(jù)集
        user            用戶編號
        simMeas         相似度計算方法
        item            未評分的物品編號
    Returns:
        ratSimTotal/simTotal     評分（0～5之間的值）
    """
    # 物品數(shù)目
    n = shape(dataMat)[1]
    # 對數(shù)據(jù)集進行SVD分解
    simTotal = 0.0
    ratSimTotal = 0.0
    # 奇異值分解
    # 在SVD分解之后是掰，我們只利用包含了90%能量值的奇異值，這些奇異值會以NumPy數(shù)組的形式得以保存
    U, Sigma, VT = la.svd(dataMat)

    # # 分析 Sigma 的長度取值
    # analyse_data(Sigma, 20)

    # 如果要進行矩陣運算，就必須要用這些奇異值構(gòu)建出一個對角矩陣
    Sig4 = mat(eye(4) * Sigma[: 4])
    # 利用U矩陣將物品轉(zhuǎn)換到低維空間中炫彩，構(gòu)建轉(zhuǎn)換后的物品(物品+4個主要的特征)
    xformedItems = dataMat.T * U[:, :4] * Sig4.I
    # 對于給定的用戶，for循環(huán)在用戶對應(yīng)行的元素上進行遍歷昨忆，
    # 這和standEst()函數(shù)中的for循環(huán)的目的一樣杉允，只不過這里的相似度計算時在低維空間下進行的邑贴。
    for j in range(n):
        userRating = dataMat[user, j]
        if userRating == 0 or j == item:
            continue
        # 相似度的計算方法也會作為一個參數(shù)傳遞給該函數(shù)
        similarity = simMeas(xformedItems[item, :].T, xformedItems[j, :].T)
        # for 循環(huán)中加入了一條print語句叔磷，以便了解相似度計算的進展情況。如果覺得累贅世澜，可以去掉
        print 'the %d and %d similarity is: %f' % (item, j, similarity)
        # 對相似度不斷累加求和
        simTotal += similarity
        # 對相似度及對應(yīng)評分值的乘積求和
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        # 計算估計評分
        return ratSimTotal/simTotal

排序獲取最后的推薦結(jié)果

# recommend()函數(shù)，就是推薦引擎，它默認調(diào)用standEst()函數(shù)案疲，產(chǎn)生了最高的N個推薦結(jié)果。
# 如果不指定N的大小褐啡，則默認值為3备畦。該函數(shù)另外的參數(shù)還包括相似度計算方法和估計方法
def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):
    # 尋找未評級的物品
    # 對給定的用戶建立一個未評分的物品列表
    unratedItems = nonzero(dataMat[user, :].A == 0)[1]
    # 如果不存在未評分物品，那么就退出函數(shù)
    if len(unratedItems) == 0:
        return 'you rated everything'
    # 物品的編號和評分值
    itemScores = []
    # 在未評分物品上進行循環(huán)
    for item in unratedItems:
        estimatedScore = estMethod(dataMat, user, simMeas, item)
        # 尋找前N個未評級物品懂盐，調(diào)用standEst()來產(chǎn)生該物品的預(yù)測得分，該物品的編號和估計值會放在一個元素列表itemScores中
        itemScores.append((item, estimatedScore))
        # 按照估計得分拌喉，對該列表進行排序并返回俐银。列表逆排序尿背，第一個值就是最大值
    return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[: N]

測試 和 項目調(diào)用捶惜，可直接參考我們的代碼

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/14.SVD/svdRecommend.py

要點補充

基于內(nèi)容(content-based)的推薦

1. 通過各種標(biāo)簽來標(biāo)記菜肴
2. 將這些屬性作為相似度計算所需要的數(shù)據(jù)
3. 這就是：基于內(nèi)容的推薦。

構(gòu)建推薦引擎面臨的挑戰(zhàn)

問題

• 1）在大規(guī)模的數(shù)據(jù)集上汽久，SVD分解會降低程序的速度
• 2）存在其他很多規(guī)模擴展性的挑戰(zhàn)性問題鹤竭，比如矩陣的表示方法和計算相似度得分消耗資源回窘。
• 3）如何在缺乏數(shù)據(jù)時給出好的推薦-稱為冷啟動【簡單說：用戶不會喜歡一個無效的物品，而用戶不喜歡的物品又無效】

建議

• 1）在大型系統(tǒng)中啡直，SVD分解(可以在程序調(diào)入時運行一次)每天運行一次或者其頻率更低，并且還要離線運行撮执。
• 2）在實際中，另一個普遍的做法就是離線計算并保存相似度得分抒钱。(物品相似度可能被用戶重復(fù)的調(diào)用)
• 3）冷啟動問題颜凯，解決方案就是將推薦看成是搜索問題谋币，通過各種標(biāo)簽／屬性特征進行基于內(nèi)容的推薦症概。

項目案例: 基于 SVD 的圖像壓縮

收集 并 準備數(shù)據(jù)

將文本數(shù)據(jù)轉(zhuǎn)化為矩陣

# 加載并轉(zhuǎn)換數(shù)據(jù)
def imgLoadData(filename):
    myl = []
    # 打開文本文件，并從文件以數(shù)組方式讀入字符
    for line in open(filename).readlines():
        newRow = []
        for i in range(32):
            newRow.append(int(line[i]))
        myl.append(newRow)
    # 矩陣調(diào)入后诅蝶，就可以在屏幕上輸出該矩陣
    myMat = mat(myl)
    return myMat

分析數(shù)據(jù): 分析 Sigma 的長度個數(shù)

通常保留矩陣 80% ～ 90% 的能量，就可以得到重要的特征并去除噪聲调炬。

def analyse_data(Sigma, loopNum=20):
    """analyse_data(分析 Sigma 的長度取值)

    Args:
        Sigma         Sigma的值
        loopNum       循環(huán)次數(shù)
    """
    # 總方差的集合（總能量值）
    Sig2 = Sigma**2
    SigmaSum = sum(Sig2)
    for i in range(loopNum):
        SigmaI = sum(Sig2[:i+1])
        '''
        根據(jù)自己的業(yè)務(wù)情況舱馅，就行處理，設(shè)置對應(yīng)的 Singma 次數(shù)

        通常保留矩陣 80% ～ 90% 的能量习柠，就可以得到重要的特征并取出噪聲。
        '''
        print '主成分：%s, 方差占比：%s%%' % (format(i+1, '2.0f'), format(SigmaI/SigmaSum*100, '4.2f'))

使用算法: 對比使用 SVD 前后的數(shù)據(jù)差異對比资溃，對于存儲大家可以試著寫寫

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除對角線的0), 幾乎獲得了10倍的壓縮比。

# 打印矩陣
def printMat(inMat, thresh=0.8):
    # 由于矩陣保護了浮點數(shù)宝恶，因此定義淺色和深色，遍歷所有矩陣元素垫毙，當(dāng)元素大于閥值時打印1霹疫，否則打印0
    for i in range(32):
        for k in range(32):
            if float(inMat[i, k]) > thresh:
                print 1,
            else:
                print 0,
        print ''


# 實現(xiàn)圖像壓縮综芥，允許基于任意給定的奇異值數(shù)目來重構(gòu)圖像
def imgCompress(numSV=3, thresh=0.8):
    """imgCompress( )

    Args:
        numSV       Sigma長度   
        thresh      判斷的閾值
    """
    # 構(gòu)建一個列表
    myMat = imgLoadData('input/14.SVD/0_5.txt')

    print "****original matrix****"
    # 對原始圖像進行SVD分解并重構(gòu)圖像e
    printMat(myMat, thresh)

    # 通過Sigma 重新構(gòu)成SigRecom來實現(xiàn)
    # Sigma是一個對角矩陣，因此需要建立一個全0矩陣屠阻，然后將前面的那些奇異值填充到對角線上。
    U, Sigma, VT = la.svd(myMat)
    # SigRecon = mat(zeros((numSV, numSV)))
    # for k in range(numSV):
    #     SigRecon[k, k] = Sigma[k]

    # 分析插入的 Sigma 長度
    analyse_data(Sigma, 20)

    SigRecon = mat(eye(numSV) * Sigma[: numSV])
    reconMat = U[:, :numSV] * SigRecon * VT[:numSV, :]
    print "****reconstructed matrix using %d singular values *****" % numSV
    printMat(reconMat, thresh)

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/14.SVD/svdRecommend.py

• 作者：片刻 1988
• GitHub地址: https://github.com/apachecn/MachineLearning
• 版權(quán)聲明：歡迎轉(zhuǎn)載學(xué)習(xí) => 請標(biāo)注信息來源于 ApacheCN