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

发布于 2024-09-17 00:16:46 字数 11717 浏览 49 评论 0

之前，我写了一篇关于如何构建一个喜欢这个的人也喜欢……特性文章，用来展示相似音乐家名单。我的目标是为了显示用信息检索技术来很好的计算相关艺术家列表是多么的简单。例如，在 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 收集到的数据。

矩阵分解

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

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

与将每个艺术家表示为所有的 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 试图获取的事实是，他们的排名彼此最为相似：

注：原文这个图是可以交互的。

你还可以看到，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 = \sum_u \sum_i { C_{ui}(P_{ui} - X_uY_i)^2} + \lambda (\|X_u\|^2 + \|Y_i\|^2)
$$

$C_{ui}$ 是我们所具有的用户喜欢该艺术家的置信度，$P_{ui}$ 是一个二进制值，它表示该用户是否听这个艺术家的歌，而 $\lambda$ 是一个基本的 L2 正则化矩阵，用来减少过度拟合。

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

$$
X_u = (Y^TC_{u}Y + \lambda I)^{-1}(Y^TC_UP_u)
$$

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

这个论文的巧妙之处在于，它如何对所有数据进行学习，但只需要对那些非零项进行处理。由于 $P_u$ 是稀疏的（负值偏好有一个 0 值)， $Y^TC_uP_u$ 可以容易进行技术。要计算 $Y^TC_{u}$，他们指出，它等价于 $Y^TY + Y^T(C_u-I)Y$。通过设置负值项的置信度为 1，$(C_u - I)$ 是稀疏的，并且 $Y^TY$ 可以对所有用户进行预运算。

将这整个算法放到 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 返回的不相干结果被挤出了列表的头部，并且被相干结果所取代。

隐性 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 数据集发布之后，他变得流行起来)。这主要是因为我如何加权信心矩阵 —— 通过使用一个简单的线性加权，我也获得了棒棒的结果。

分享到QQ

分享到微博