之前，我写了一篇关于如何构建一个'喜欢这个的人也喜欢……'特性文章，用来展示相似音乐家名单。我的目标是为了显示用信息检索技术来很好的计算相关艺术家列表是多么的简单。例如，在The Beatles上使用BM25距离表明，最相似的艺术家是John Lennon和Paul McCartney。

我没有涉及的一个有趣的技术是，在计算相关艺术家之前，使用矩阵分解的方法来减少数据的维度。这种分析可以生成使用我原来的博文中的技术没法找到的匹配。

本文一步步指导如何使用几个不同的矩阵分解算法来计算相关的艺术家。代码使用Python编写的，使用Pandas和SciPy来进行计算，使用D3.js来交互式可视化结果。

作为这篇文章的一不分，我还开源了一个隐式交替最小二乘的高性能Python版本矩阵分解算法。这里大部分的代码可以在该项目的样例目录下找到。

加载数据

在本文中，我使用与我第一篇文章相同的Last.fm数据集。使用Pandas，你只需要几行代码，就可以把它加载到一个稀疏矩阵中：

# read in triples of user/artist/playcount from the input dataset
data = pandas.read_table("usersha1-artmbid-artname-plays.tsv", 
                         usecols=[0, 2, 3], 
                         names=['user', 'artist', 'plays'])

# map each artist and user to a unique numeric value
data['user'] = data['user'].astype("category")
data['artist'] = data['artist'].astype("category")

# create a sparse matrix of all the artist/user/play triples
plays = coo_matrix((data['plays'].astype(float), 
                   (data['artist'].cat.codes, 
                    data['user'].cat.codes)))

这里返回的矩阵具有300,000个艺术家和360,000个用户，以及约一千七百万项。每项表示用户播放该艺术家音乐的次数，以及在2008年，使用Last.fm API收集到的数据。

矩阵分解

通常用于此问题的一个技术是将用户-艺术家-播放矩阵投射到一个低秩逼近，然后计算该空间的距离。

想法是获得原始的播放次数矩阵，然后将其减小到两个更小的矩阵，这两个更小的矩阵相乘得到的结果近似于原始矩阵：

Artist/User/Play CountsArtist FactorsUser Factors=×

与将每个艺术家表示为所有的360,000个可能的用户的播放次数的一个稀疏向量相反，在分解矩阵后，每个艺术家将会由一个50维的密集矢量所表示。

通过减少像这样的数据维度，我们实际上是将输入矩阵压缩到两个小得多的矩阵。这种压缩迫使输入数据的泛化，而这种泛化会使得更好的理解数据。

潜在语义分析

因式分解输入矩阵的一个简单方法是计算在一个适当的加权矩阵上的奇异值分解 (1)：

artist_factors, _, user_factors = scipy.sparse.linalg.svds(bm25_weight(plays), 50)

SVD（奇异值分解）是那些令人惊讶的有用技术之一，可以被用于像主成分分析或者多维标度。我刚想包含一个关于它如何工作的概述，但最近Jeremy Kun写了一篇SVD的优秀概述，而我不会尝试超越他。对于这篇文章的目的，我们只需要知道，SVD生成输入矩阵的一个低秩逼近，而我们可以使用那个低秩逼近表示。

这样使用SVD被称为潜在语义分析 (LSA)。其真正包含的是，通过该分解空间中的余弦距离来获得最相关的艺术家，这可以这样做：

class TopRelated(object):
    def __init__(self, artist_factors):
        # fully normalize artist_factors, so can compare with only the dot product
        norms = numpy.linalg.norm(artist_factors, axis=-1)
        self.factors = artist_factors / norms[:, numpy.newaxis]

    def get_related(self, artistid, N=10):
        scores = self.factors.dot(self.factors[artistid])
        best = numpy.argpartition(scores, -N)[-N:]
        return sorted((best, scores[best]), key=lambda x: -x[1])

在分解矩阵后，输入数据中的潜在隐藏结构会暴露出来，潜在语义分析因此得名 —— 这可以被认为是揭示输入数据的语义。

例如，'Arcade Fire'和'The Arcade Fire'在我所使用的数据集中并无相同的听众：它由Last.fm的历史所生成，而人们要么使用他们音乐库中的一个标签，要么使用另一个。

这意味着，所有的比较艺术家的直接方法都认为，这两个乐队是完全不一样的。然而，这些标签都指向一个相同的乐队 —— LSA试图获取的事实是，他们的排名彼此最为相似：

LSA

LSA
隐ALS

类似的“拱廊之火”由LSA：

艺术家	LSA
在拱廊之火	0.988
该逗人	0.985
救护车有限公司	0.984
全国	0.981
拍拍手说好啊	0.977
更多 ...

TheArcadeFireTheDearsArcade Fire

你还可以看到，"Guns N Roses"与"Guns N' Roses"和"Nick Cave and the Bad Seeds"与"Nick Cave the Bad Seeds"也具有相同的效果。随意输入其他艺术家，但请记住，这个数据集是2008年的，所以，这里并没有更晚点的艺术家。（Ele注：这里无法重现效果，请到原文进行尝试）

虽然LSA成功的一般化了我们的数据的某些方面，但是这里的结果并不完美。例如，看看Bob Dylan的结果。

要做得更好，并仍保持一般化的能力，我们需要想出一个更好的模型。

隐式交替最小二乘

推荐系统经常使用矩阵分解模型来为用户生成个性化推荐。已发现这些模型在推荐东西上工作良好，并且可以容易的重复用于计算相关艺术家。

在推荐系统中使用的许多MF模型都假定明确的数据，其中，用户使用一些，例如五星评定，来对他们喜欢或不喜欢的东西进行评定。他们通常将确实的数据看成未知，然后使用SGD最小化重构错误。

虽然，这里的数据是隐式的 —— 我们可以假设，一个用户听一个艺术家的歌表示他喜欢这首歌，但我们并没有相应的信号可以表明一个用户不喜欢一个艺术家。与显式数据相比，隐式数据通常更加丰满和易于收集 —— 但即使一个用户给了5星评定，但绝大部分的评级将只是积极的，所以无论如何，你都需要考虑隐性行为。

这意味着，我们不能只是将缺失的数据当成未知，取而代之，我们必须将一个不听某个艺术家的音乐的用户当成该用户可能不喜欢那个艺术家的信号。

这表示了在学习因式分解时的几个挑战。

第一个挑战是有效地进行这种分解：通过将未知当成负数，原生实现将会遍历输入矩阵中的每一项。由于这里的维度大约是360K x 300K —— 相对于只有1千七百万个非零项，总共有超过一千亿的项要考虑。

第二个问题是，我们不能肯定，一个用户不听某个艺术家的歌就真的表示他不喜欢它。可能还有其他原因使得他不听这个艺术家的歌，特别是考虑到，在数据集中，对于每一个用户，我们只有前50个播放次数最多的艺术家。

用于隐式反馈数据集的协同过滤论文以一种优雅的方式，考虑到了这两种挑战。

要处理我们对我们的负数数据不自信的情况，这个方法使用二分偏好上的不同置信水平来学习一个因式分解的矩阵表示：看不见的项被当做具有一个低的置信值的负数，而看得见的项则被当做具有较高的置信值的正数。

那么，我们的目标是通过最小化平方误差函数的置信加权和，来学习用户因子X_u和艺术家因子Y_i：

loss=∑u∑iCui(Pui−XuYi)2+λ(∥Xu∥2+∥Yi∥2)

Cui<script type="math/tex" id="MathJax-Element-2">C_{ui}</script> 是我们所具有的用户喜欢该艺术家的置信度，Pui是一个二进制值，它表示该用户是否听这个艺术家的歌，而λ是一个基本的L2正则化矩阵，用来减少过度拟合。

要最小化用户因子，我们固定项的因子常量不变，然后使用损失函数的导数来直接计算X_u：

Xu=(YTCuY+λI)−1(YTCUPu)

项因子以一种相似的方式计算，而整个值是通过来回交替进行最小化，直到其收敛（因此，‘交叉最小二乘法’由此得名）。

这个论文的巧妙之处在于，它如何对所有数据进行学习，但只需要对那些非零项进行处理。由于Pu 是稀疏的(负值偏好有一个0值)， YTCuPu 可以容易进行技术。要计算 YTCuY，他们指出，它等价于YTY+YT(Cu−I)Y。通过设置负值项的置信度为1，(Cu−I)是稀疏的，并且YTY 可以对所有用户进行预运算。

将这整个算法放到Python中，你会得到像这样的代码：

def alternating_least_squares(Cui, factors, regularization, iterations=20):
    users, items = Cui.shape

    X = np.random.rand(users, factors) * 0.01
    Y = np.random.rand(items, factors) * 0.01

    Ciu = Cui.T.tocsr()
    for iteration in range(iterations):
        least_squares(Cui, X, Y, regularization)
        least_squares(Ciu, Y, X, regularization)

    return X, Y

def least_squares(Cui, X, Y, regularization):
    users, factors = X.shape
    YtY = Y.T.dot(Y)

    for u in range(users):
        # accumulate YtCuY + regularization * I in A
        A = YtY + regularization * np.eye(factors)

        # accumulate YtCuPu in b
        b = np.zeros(factors)

        for i, confidence in nonzeros(Cui, u):
            factor = Y[i]
            A += (confidence - 1) * np.outer(factor, factor)
            b += confidence * factor

        # Xu = (YtCuY + regularization * I)^-1 (YtCuPu)
        X[u] = np.linalg.solve(A, b)

要调用它，对于置信矩阵，我是用了与我们在LSA中使用的相同的权重，然后以相同的方式计算相关艺术家：

artist_factors, user_factors = alternating_least_squares(bm25_weight(plays), 50)

This method leads to significantly better results than just using LSA. Take a look at a 与只使用LSA相比，这个方法可以获得一个明显更好的结果。以 Bob Dylan为例，看看一个slopegraph：

LSA

LSA
隐ALS
交叠
杰卡德
落合
余弦
平滑余弦
TFIDF
BM25

隐ALS

LSA
隐ALS
交叠
杰卡德
落合
余弦
平滑余弦
TFIDF
BM25

鲍勃·迪伦
LSA与隐ALS

Neil Young - #1#1 - Neil YoungLoudon Wainwright Iii - #2#44 - Loudon Wainwright IiiElvis Costello & The Imposters - #3#881 - Elvis Costello & The ImpostersTim Keller - #4#230 - Tim KellerThe Umbrellas Of Cherbourg - #5#231 - The Umbrellas Of CherbourgMuy Cansado - #6#134 - Muy CansadoElvis Costello - #7#25 - Elvis CostelloBob Dylan And The Band - #19#2 - Bob Dylan And The BandDonovan - #50#4 - DonovanThe Band - #90#3 - The BandVan Morrison - #114#6 - Van MorrisonThe Kinks - #151#5 - The KinksBuffalo Springfield - #219#7 - Buffalo Springfield

这里，LSA返回的不相干结果被挤出了列表的头部，并且被相干结果所取代。

隐性ALS的好处是，它仍然成功地一般化了输入。举个例子，无论是Guns N' Roses还是Nick Cave And The Bad Seeds，都仍然得到了它们的同类，只是没有由LSA返回的一些边际结果。

性能

在计算像这样的相关艺术家的过程中，有一些性能挑战。

我在上面贴出来的隐式ALS代码并不是非常快。由于每个用户因子可以彼此独立被计算，因此该算法是令人尴尬地并行的，并且非常适合多线程 —— 这是纯Python代码不擅长的。

为了克服这个问题，我发布了一个快的Python版本，该版本使用Cython和OpenMP来并行化计算。在这个任务中，比Quora刚在他们的QMF库上发布的多线程C++版本，当前会快1.8倍。

通过并行计算，该库可以在一个c4.8xlarge EC2实例上，大约40s内分解Last.fm数据集 (50个因子，15次迭代)。

问题是，一旦分解结束，使用这些因子来计算所有最相关的艺术家要花费大约一个小时。要做到准确的近邻计算则需要O(N²)，因为我们需要将艺术家两两对比。

使用近似近邻搜索是有可能更快的。annoy包使用一个随机的超平面分割方法来建立搜索树森林，从而有效地计算最近的邻居。

annoy包带有Python绑定。要使用余弦距离来生成近似最近邻居，使用这些绑定是非常简单的：

class ApproximateTopRelated(object):
    def __init__(self, artist_factors, treecount=20):
        index = annoy.AnnoyIndex(artist_factors.shape[1], 'angular')
        for i, row in enumerate(artist_factors):
            index.add_item(i, row)
        index.build(treecount)
        self.index = index

    def get_related(self, artistid, N=10):
        neighbours = self.index.get_nns_by_item(artistid, N)
        return sorted(((other, 1 - self.index.get_distance(artistid, other))
                      for other in neighbours), key=lambda x: -x[1])

使用这种方法的结果大致相同，并将计算所有艺术家的时间从一小时减少到大约30s，这还包含了在首位建立索引的时间。

如果你有兴趣了解更多，Erik Bernhardsson有一系列关于annoy如何工作的不错的博文。

总结

矩阵分解方法，例如隐式ALS通常用于生成个性化结果，但也有一些上升空间来将这些模型用于生成相关艺术家列表的更简单的任务。

事实上，Spotify使用了一个名为逻辑矩阵分解(Logistic Matrix Factorization)的矩阵分解技术来生成相关艺术家列表。这个方法与隐式ALS想法类似：它是在二分偏好数据上的一个置信加权因子，但它使用了一个逻辑损失，而不是最小平方损失。该论文用一些例子说明了在哪些地方，逻辑矩阵分解在计算相似艺术家时会比隐式ALS好(2)。

还有许多其他矩阵分解方法可以用来代替在这里讲到的方法。例如，贝叶斯个性化排名(Bayesian Personalized Ranking)，和协同少即是多过滤(Collaborative Less-is-More Filtering) 都试图学习用来为每个用户优化艺术家排名的因式分解表示。

这些模型的真正力量在于，为每个用户生成个性化推荐，对此，我希望在以后的博文中可以深入探讨。

Footnote 1

像LSA这样的技术，在进行矩阵分解之前，通常使用TFIDF来加权输入矩阵。然而，根据之前的博文，我们知道，BM25加权在计算艺术家之间的相似性时会得到一些好的结果。因此，在这里，我使用它来代替。见我的隐式库中的样例应用中的代码，看看如何有效地做这件事。

Footnote 2

这里，隐式ALS的结果比那些在Logistic Matrix Factorization paper上报道的好得多 (除了Mumford Sons，在Last.fm数据集发布之后，他变得流行起来)。这主要是因为我如何加权信心矩阵 —— 通过使用一个简单的线性加权，我也获得了棒棒的结果。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

使用矩阵分解找到相似歌曲.md

使用矩阵分解找到相似歌曲.md

加载数据

矩阵分解

潜在语义分析

类似的“拱廊之火”由LSA：

隐式交替最小二乘

鲍勃·迪伦
LSA与隐ALS

性能

总结

Footnote 1

Footnote 2

Files

使用矩阵分解找到相似歌曲.md

Latest commit

History

使用矩阵分解找到相似歌曲.md

File metadata and controls

加载数据

矩阵分解

潜在语义分析

类似的“拱廊之火”由LSA：

隐式交替最小二乘

鲍勃·迪伦 LSA与隐ALS

性能

总结

Footnote 1

Footnote 2

鲍勃·迪伦
LSA与隐ALS