如何利用奇异值分解简化数据

作者/ Peter Harrington

拥有电气工程学士和硕士学位,他曾经在美国加州和中国的英特尔公司工作7年。Peter拥有5项美国专利,在三种学术期刊上发表过文章。他现在是Zillabyte公司的首席科学家,在加入该公司之前,他曾担任2年的机器学习软件顾问。Peter在业余时间还参加编程竞赛和建造3D打印机。

餐馆可划分为很多类别,比如美式、中式、日式、牛排馆、素食店,等等。你是否想过这些类别够用吗?或许人们喜欢这些的混合类别,或者类似中式素食店那样的子类别。如何才能知道到底有多少类餐馆呢?我们也许可以问问专家?但是倘若某个专家说应该按照调料分类,而另一个专家则认为应该按照配料分类,那该怎么办呢?忘了专家,我们还是从数据着手吧。我们可以对记录用户关于餐馆观点的数据进行处理,并且从中提取出其背后的因素。

这些因素可能会与餐馆的类别、烹饪时所用的某个特定配料,或其他任意对象一致。然后,我们就可以利用这些因素来估计人们对没有去过的餐馆的看法。

提取这些信息的方法称为奇异值分解(Singular Value Decomposition,SVD)。从生物信息学到金融学等在内的很多应用中,SVD都是提取信息的强大工具。

我们将介绍SVD的概念及其能够进行数据约简的原因。然后,我们将会介绍基于Python的SVD实现以及将数据映射到低维空间的过程。再接下来,我们就将学习推荐引擎的概念和它们的实际运行过程。为了提高SVD的精度,我们将会把其应用到推荐系统中去,该推荐系统将会帮助人们寻找到合适的餐馆。最后,我们讲述一个SVD在图像压缩中的应用例子。

SVD的应用

奇异值分解

优点:简化数据,去除噪声,提高算法的结果。

缺点:数据的转换可能难以理解。

适用数据类型:数值型数据。

利用SVD实现,我们能够用小得多的数据集来表示原始数据集。这样做,实际上是去除了噪声和冗余信息。当我们试图节省空间时,去除噪声和冗余信息就是很崇高的目标了,但是在这里我们则是从数据中抽取信息。基于这个视角,我们就可以把SVD看成是从有噪声的数据中抽取相关特征。如果这一点听来奇怪,也不必担心,我们后面会给出若干SVD应用的场景和方法,解释它的威力。

首先,我们会介绍SVD是如何通过隐性语义索引应用于搜索和信息检索领域的。然后,我们再介绍SVD在推荐系统中的应用。

隐性语义索引

SVD的历史已经超过上百个年头,但是最近几十年随着计算机的使用,我们发现了其更多的使用价值。最早的SVD应用之一就是信息检索。我们称利用SVD的方法为隐性语义索引(Latent Semantic Indexing,LSI)或隐性语义分析(Latent Semantic Analysis,LSA)。

在LSI中,一个矩阵是由文档和词语组成的。当我们在该矩阵上应用SVD时,就会构建出多个奇异值。这些奇异值代表了文档中的概念或主题,这一特点可以用于更高效的文档搜索。在词语拼写错误时,只基于词语存在与否的简单搜索方法会遇到问题。简单搜索的另一个问题就是同义词的使用。这就是说,当我们查找一个词时,其同义词所在的文档可能并不会匹配上。如果我们从上千篇相似的文档中抽取出概念,那么同义词就会映射为同一概念。

推荐系统

SVD的另一个应用就是推荐系统。简单版本的推荐系统能够计算项或者人之间的相似度。更先进的方法则先利用SVD从数据中构建一个主题空间,然后再在该空间下计算其相似度。考虑图14-1中给出的矩阵,它是由餐馆的菜和品菜师对这些菜的意见构成的。品菜师可以采用1到5之间的任意一个整数来对菜评级。如果品菜师没有尝过某道菜,则评级为0。

图1 餐馆的菜及其评级的数据。对此矩阵进行SVD处理则可以将数据压缩到若干概念中去。在右边的矩阵当中,标出了一个概念。

我们对上述矩阵进行SVD处理,会得到两个奇异值(读者如果不信可以自己试试)。因此,就会仿佛有两个概念或主题与此数据集相关联。我们看看能否通过观察图中的0来找到这个矩阵的具体概念。观察一下右图的阴影部分,看起来Ed、Peter和Tracy对“烤牛肉”和“手撕猪肉”进行了评级,同时这三人未对其他菜评级。烤牛肉和手撕猪肉都是美式烧烤餐馆才有的菜,其他菜则在日式餐馆才有。

我们可以把奇异值想象成一个新空间。与图14-1中的矩阵给出的五维或者七维不同,我们最终的矩阵只有二维。那么这二维分别是什么呢?它们能告诉我们数据的什么信息?这二维分别对应图中给出的两个组,右图中已经标示出了其中的一个组。我们可以基于每个组的共同特征来命名这二维,比如我们得到的美式BBQ和日式食品这二维。

如何才能将原始数据变换到上述新空间中呢?下面我们将会进一步详细地介绍SVD,届时将会了解到SVD是如何得到UVT两个矩阵的。VT矩阵会将用户映射到BBQ/日式食品空间去。类似地,U矩阵会将餐馆的菜映射到BBQ/日式食品空间去。真实的数据通常不会像图1中的矩阵那样稠密或整齐,这里如此只是为了便于说明问题。

推荐引擎中可能会有噪声数据,比如某个人对某些菜的评级就可能存在噪声,并且推荐系统也可以将数据抽取为这些基本主题。基于这些主题,推荐系统就能取得比原始数据更好的推荐效果。在2006年末,电影公司Netflix曾经举办了一个奖金为100万美元的大赛,这笔奖金会颁给比当时最好系统还要好10%的推荐系统的参赛者。最后的获奖者就使用了SVD。

下面将介绍SVD的一些背景材料,接着给出利用Python的NumPy实现SVD的过程。然后,我们将进一步深入讨论推荐引擎。当对推荐引擎有相当的了解之后,我们就会利用SVD构建一个推荐系统。

SVD是矩阵分解的一种类型,而矩阵分解是将数据矩阵分解为多个独立部分的过程。接下来我们首先介绍矩阵分解。

矩阵分解

在很多情况下,数据中的一小段携带了数据集中的大部分信息,其他信息则要么是噪声,要么就是毫不相关的信息。在线性代数中还有很多矩阵分解技术。矩阵分解可以将原始矩阵表示成新的易于处理的形式,这种新形式是两个或多个矩阵的乘积。我们可以将这种分解过程想象成代数中的因子分解。如何将12分解成两个数的乘积?(1,12)、(2,6)和(3,4)都是合理的答案。

不同的矩阵分解技术具有不同的性质,其中有些更适合于某个应用,有些则更适合于其他应用。最常见的一种矩阵分解技术就是SVD。SVD将原始的数据集矩阵Data分解成三个矩阵UΣVT。如果原始矩阵Data是m行n列,那么UΣVT就分别是m行m列、m行n列和n行n列。为了清晰起见,上述过程可以写成如下一行(下标为矩阵维数):

上述分解中会构建出一个矩阵Σ,该矩阵只有对角元素,其他元素均为0。另一个惯例就是,Σ的对角元素是从大到小排列的。这些对角元素称为奇异值(Singular Value),它们对应了原始数据集矩阵Data的奇异值。使用PCA,我们会得到矩阵的特征值,它们告诉我们数据集中的重要特征。Σ中的奇异值也是如此。奇异值和特征值是有关系的。这里的奇异值就是矩阵Data * DataT特征值的平方根。

前面提到过,矩阵Σ只有从大到小排列的对角元素。在科学和工程中,一直存在这样一个普遍事实:在某个奇异值的数目(r个)之后,其他的奇异值都置为0。这就意味着数据集中仅有r个重要特征,而其余特征则都是噪声或冗余特征。接下来,我们将看到一个可靠的案例。

我们不必担心该如何进行矩阵分解。在NumPy线性代数库中有一个实现SVD的方法。如果读者对SVD的编程实现感兴趣的话,请阅读Numerical Linear Algebra

利用Python实现SVD

如果SVD确实那么好,那么该如何实现它呢?SVD实现了相关的线性代数,但这并不在我们的讨论范围之内。其实,有很多软件包可以实现SVD。NumPy有一个称为linalg的线性代数工具箱。接下来,我们了解一下如何利用该工具箱实现如下矩阵的SVD处理:

要在Python上实现该矩阵的SVD处理,请键入如下命令:

>>> from numpy import *
>>> U,Sigma,VT=linalg.svd([[1, 1],[7, 7]])

接下来就可以在如下多个矩阵上进行尝试:

>>> U
array([[-0.14142136, -0.98994949],
[-0.98994949, 0.14142136]])
>>> Sigma
array([ 10., 0.])
>>> VT
array([[-0.70710678, -0.70710678],
[-0.70710678, 0.70710678]])

我们注意到,矩阵Sigma以行向量array([ 10., 0.])返回,而非如下矩阵:

array([[ 10., 0.],
       [ 0., 0.]]).

由于矩阵除了对角元素其他均为0,因此这种仅返回对角元素的方式能够节省空间,这就是由NumPy的内部机制产生的。我们所要记住的是,一旦看到Sigma就要知道它是一个矩阵。好了,接下来我们将在一个更大的数据集上进行更多的分解。

建立一个新文件svdRec.py并加入如下代码:

def loadExData():
return[[1, 1, 1, 0, 0],
       [2, 2, 2, 0, 0],
       [1, 1, 1, 0, 0],
       [5, 5, 5, 0, 0],
       [1, 1, 0, 2, 2],
       [0, 0, 0, 3, 3],
       [0, 0, 0, 1, 1]]

接下来我们对该矩阵进行SVD分解。在保存好文件svdRec.py之后,我们在Python提示符下输入:

>>> import svdRec
>>> Data=svdRec.loadExData()
>>> U,Sigma,VT=linalg.svd(Data)
>>> Sigma
array([ 9.72140007e+00, 5.29397912e+00, 6.84226362e-01,7.16251492e-16, 4.85169600e-32])

前3个数值比其他的值大了很多(如果你的最后两个值的结果与这里的结果稍有不同,也不必担心。它们太小了,所以在不同机器上产生的结果就可能会稍有不同,但是数量级应该和这里的结果差不多)。于是,我们就可以将最后两个值去掉了。

接下来,我们的原始数据集就可以用如下结果来近似:

图2就是上述近似计算的一个示意图。

图2 SVD的示意图。矩阵Data被分解。浅灰色区域是原始数据,深灰色区域是矩阵近似计算仅需要的数据

我们试图重构原始矩阵。首先构建一个3×3的矩阵Sig3

>>> Sig3=mat([[Sigma[0], 0, 0],[0, Sigma[1], 0], [0, 0, Sigma[2]]])

接下来我们重构原始矩阵的近似矩阵。由于Sig3仅为3x3矩阵,我们只需使用矩阵U的前3列和VT的前3行。在Python中实现这一点,输入命令:

>>> U[:,:3]*Sig3*VT[:3,:]
array([[ 1.,   1.,   1.,   0.,   0.  ],
       [ 2.,   2.,   2.,   -0.,  -0. ],
       [ 1.,   1.,   1.,   -0.,  -0. ],
       [ 5.,   5.,   5.,   0.,    0. ],
       [ 1.,   1.,   -0.,   2.,   2. ],
       [ 0.,   0.,   -0.,   3.,   3. ],
            [ 0.,   0.,   -0.,   1.,   1.  ]])

我们是如何知道仅需保留前3个奇异值的呢?确定要保留的奇异值的数目有很多启发式的策略,其中一个典型的做法就是保留矩阵中90%的能量信息。为了计算总能量信息,我们将所有的奇异值求其平方和。于是可以将奇异值的平方和累加到总值的90%为止。另一个启发式策略就是,当矩阵上有上万的奇异值时,那么就保留前面的2000或3000个。尽管后一种方法不太优雅,但是在实际中更容易实施。之所以说它不够优雅,就是因为在任何数据集上都不能保证前3000个奇异值就能够包含90%的能量信息。但在通常情况下,使用者往往都对数据有足够的了解,从而就能够做出类似的假设了。

现在我们已经通过三个矩阵对原始矩阵进行了近似。我们可以用一个小很多的矩阵来表示一个大矩阵。有很多应用可以通过SVD来提升性能。下面我们将讨论一个比较流行的SVD应用的例子——推荐引擎。

基于协同过滤的推荐引擎

近十年来,推荐引擎对因特网用户而言已经不是什么新鲜事物了。Amazon会根据顾客的购买历史向他们推荐物品,Netflix会向其用户推荐电影,新闻网站会对用户推荐新闻报道,这样的例子还有很多很多。当然,有很多方法可以实现推荐功能,这里我们只使用一种称为协同过滤(collaborative filtering)的方法。协同过滤是通过将用户和其他用户的数据进行对比来实现推荐的。

这里的数据是从概念上组织成了类似图2所给出的矩阵形式。当数据采用这种方式进行组织时,我们就可以比较用户或物品之间的相似度了。这两种做法都会使用我们很快就介绍到的相似度的概念。当知道了两个用户或两个物品之间的相似度,我们就可以利用已有的数据来预测未知的用户喜好。例如,我们试图对某个用户喜欢的电影进行预测,推荐引擎会发现有一部电影该用户还没看过。然后,它就会计算该电影和用户看过的电影之间的相似度,如果其相似度很高,推荐算法就会认为用户喜欢这部电影。

在上述场景下,唯一所需要的数学方法就是相似度的计算,这并不是很难。接下来,我们首先讨论物品之间的相似度计算,然后讨论在基于物品和基于用户的相似度计算之间的折中。最后,我们介绍推荐引擎成功的度量方法。

相似度计算

我们希望拥有一些物品之间相似度的定量方法。那么如何找出这些方法呢?倘若我们面对的是食品销售网站,该如何处理?或许可以根据食品的配料、热量、某个烹调类型的定义或者其他类似的信息进行相似度的计算。现在,假设该网站想把业务拓展到餐具行业,那么会用热量来描述一个叉子吗?问题的关键就在于用于描述食品的属性和描述餐具的属性有所不同。倘若我们使用另外一种比较物品的方法会怎样呢?我们不利用专家所给出的重要属性来描述物品从而计算它们之间的相似度,而是利用用户对它们的意见来计算相似度。这就是协同过滤中所使用的方法。它并不关心物品的描述属性,而是严格地按照许多用户的观点来计算相似度。图3给出了由一些用户及其对前面给出的部分菜肴的评级信息所组成的矩阵。

图3 用于展示相似度计算的简单矩阵

我们计算一下手撕猪肉和烤牛肉之间的相似度。一开始我们使用欧氏距离来计算。手撕猪肉和烤牛肉的欧氏距离为:

而手撕猪肉和鳗鱼饭的欧氏距离为:

在该数据中,由于手撕猪肉和烤牛肉的距离小于手撕猪肉和鳗鱼饭的距离,因此手撕猪肉与烤牛肉比与鳗鱼饭更为相似。我们希望,相似度值在0到1之间变化,并且物品对越相似,它们的相似度值也就越大。我们可以用相似度=1/(1+距离)这样的算式来计算相似度。当距离为0时,相似度为1.0。如果距离真的非常大时,相似度也就趋近于0。

第二种计算距离的方法是皮尔逊相关系数(Pearson correlation)。它度量的是两个向量之间的相似度。该方法相对于欧氏距离的一个优势在于,它对用户评级的量级并不敏感。比如某个狂躁者对所有物品的评分都是5分,而另一个忧郁者对所有物品的评分都是1分,皮尔逊相关系数会认为这两个向量是相等的。在NumPy中,皮尔逊相关系数的计算是由函数corrcoef()进行的,后面我们很快就会用到它了。皮尔逊相关系数的取值范围从-1到+1,我们通过0.5 + 0.5*corrcoef()这个函数计算,并且把其取值范围归一化到0到1之间。

另一个常用的距离计算方法就是余弦相似度(cosine similarity),其计算的是两个向量夹角的余弦值。如果夹角为90度,则相似度为0;如果两个向量的方向相同,则相似度为1.0。同皮尔逊相关系数一样,余弦相似度的取值范围也在-1到+1之间,因此我们也将它归一化到0到1之间。计算余弦相似度值,我们采用的两个向量AB夹角的余弦相似度的定义如下:

其中,||A||、||B||表示向量A、B的2范数,你可以定义向量的任一范数,但是如果不指定范数阶数,则都假设为2范数。向量[4,2,2]的2范数为:

同样,NumPy的线性代数工具箱中提供了范数的计算方法linalg.norm()

接下来我们将上述各种相似度的计算方法写成Python中的函数。打开svdRec.py文件并加入下列代码。

程序清单1 相似度计算

from numpy import *
from numpy import linalg as la

def ecludSim(inA,inB):
    return 1.0/(1.0 + la.norm(inA - inB))

def pearsSim(inA,inB):
    if len(inA) < 3 : return 1.0
    return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1]

def cosSim(inA,inB):
    num = float(inA.T*inB)
    denom = la.norm(inA)*la.norm(inB)
    return 0.5+0.5*(num/denom)

程序中的3个函数就是上面提到的几种相似度的计算方法。为了便于理解,NumPy的线性代数工具箱linalg被作为la导入,函数中假定inAinB都是列向量。perasSim()函数会检查是否存在3个或更多的点。如果不存在,该函数返回1.0,这是因为此时两个向量完全相关。

下面我们对上述函数进行尝试。在保存好文件svdRec.py之后,在Python提示符下输入如下命令:

>>> reload(svdRec)
<module 'svdRec' from 'svdRec.pyc'>
>>> myMat=mat(svdRec.loadExData())
>>> svdRec.ecludSim(myMat[:,0],myMat[:,4])
0.12973190755680383
>>> svdRec.ecludSim(myMat[:,0],myMat[:,0])
1.0

欧氏距离看上去还行,那么接下来试试余弦相似度:

>>> svdRec.cosSim(myMat[:,0],myMat[:,4])
0.5
>>> svdRec.cosSim(myMat[:,0],myMat[:,0])
1.0000000000000002

余弦相似度似乎也行,就再试试皮尔逊相关系数:

>>> svdRec.pearsSim(myMat[:,0],myMat[:,4])
0.20596538173840329>>> svdRec.pearsSim(myMat[:,0],myMat[:,0])
1.0

上面的相似度计算都是假设数据采用了列向量方式进行表示。如果利用上述函数来计算两个行向量的相似度就会遇到问题(我们很容易对上述函数进行修改以计算行向量之间的相似度)。这里采用列向量的表示方法,暗示着我们将利用基于物品的相似度计算方法。后面我们会阐述其中的原因。

基于物品的相似度还是基于用户的相似度?

我们计算了两个餐馆菜肴之间的距离,这称为基于物品(item-based)的相似度。另一种计算用户距离的方法则称为基于用户(user-based)的相似度。回到图3,行与行之间比较的是基于用户的相似度,列与列之间比较的则是基于物品的相似度。到底使用哪一种相似度呢?这取决于用户或物品的数目。基于物品相似度计算的时间会随物品数量的增加而增加,基于用户的相似度计算的时间则会随用户数量的增加而增加。如果我们有一个商店,那么最多会有几千件商品。在撰写本文之际,最大的商店大概有100000件商品。而在Netflix大赛中,则会有480000个用户和17700部电影。如果用户的数目很多,那么我们可能倾向于使用基于物品相似度的计算方法。

对于大部分产品导向的推荐引擎而言,用户的数量往往大于物品的数量,即购买商品的用户数会多于出售的商品种类。

推荐引擎的评价

如何对推荐引擎进行评价呢?此时,我们既没有预测的目标值,也没有用户来调查他们对预测的满意程度。这里我们就可以采用前面多次使用的交叉测试的方法。具体的做法就是,我们将某些已知的评分值去掉,然后对它们进行预测,最后计算预测值和真实值之间的差异。

通常用于推荐引擎评价的指标是称为最小均方根误差(Root Mean Squared Error,RMSE)的指标,它首先计算均方误差的平均值然后取其平方根。如果评级在1星到5星这个范围内,而我们得到的RMSE为1.0,那么就意味着我们的预测值和用户给出的真实评价相差了一个星级。

小结

SVD是一种强大的降维工具,我们可以利用SVD来逼近矩阵并从中提取重要特征。通过保留矩阵80%~90%的能量,就可以得到重要的特征并去掉噪声。SVD已经运用到了多个应用中,其中一个成功的应用案例就是推荐引擎。

推荐引擎将物品推荐给用户,协同过滤则是一种基于用户喜好或行为数据的推荐的实现方法。协同过滤的核心是相似度计算方法,有很多相似度计算方法都可以用于计算物品或用户之间的相似度。通过在低维空间下计算相似度,SVD提高了推荐系引擎的效果。

在大规模数据集上,SVD的计算和推荐可能是一个很困难的工程问题。通过离线方式来进行SVD分解和相似度计算,是一种减少冗余计算和推荐所需时间的办法。

 

《机器学习实战》通过精心编排的实例,切入日常工作任务,摒弃学术化语言,利用高效的可复用Python代码来阐释如何处理统计数据,进行数据分析及可视化。通过各种实例,读者可从中学会机器学习的核心算法,并能将其运用于一些策略性任务中,如分类、预测、推荐。另外,还可用它们来实现一些更高级的功能,如汇总和简化等。本文节选自《机器学习实战》