使用非负矩阵分解进行文档聚类

• 下载源代码 - 18.8 KB
• 下载演示 - 624 KB

引言

这个WPF应用程序在AAAI 2014（一个人工智能会议）的已接受论文列表中查找聚类。它显示每个聚类中的关键词，并允许您根据在聚类中的成员关系对结果列表进行排序。

非负矩阵分解 (NNMF) 是一种相对简单的技术，它使用矩阵分解在某个单矩阵中创建预定数量的聚类。

NNMF聚类可以应用于任何均匀正矩阵，但在本应用中，它被应用于从文档列表及其元数据创建的文档/词项矩阵。

背景

向量空间模型技术已在信息检索和索引编制中使用了数十年。

如果我们有一个文档集合，我们可以计算每个文档中的单词数量，并将结果存储在一个二维数组（或矩阵）中，如下所示

这被称为文档/词项矩阵，简单地列出文档和它们包含的词项的计数。上述文档/词项矩阵也可以被归一化，以便每个值落在0和1之间。

从这个矩阵中，我们可以将每一行视为一个一维数组（或向量），并通过使用两个向量的内积来计算它与同一矩阵中任何其他向量的相似性。在信息检索中，有一种经典的使用这种技术的方式，即从查询构建一个向量，然后计算每个文档与查询的点积，从而产生一个按与查询的相关性排序的文档的有序列表。

NNMF超越了单行比较，并尝试从文档/词项矩阵中找到两个矩阵（特征和权重），将它们相乘可以重建该矩阵。这些特征和权重不能包含负值，因此被称为非负部分。

特征矩阵包含每一特征的行和每一词项的列，其值表示该词项属于该特征的程度。

权重矩阵包含每一文档的行和每一特征的列，其值表示每一文档属于该特征的程度。

线性代数

该应用程序使用开源的 Bright Wire 机器学习库来创建和归一化词项文档矩阵，并将该矩阵转换为NNMF类使用的密集向量。

使用应用程序

示例应用程序会立即下载文档数据集并对链接进行聚类。单击聚类会按其在该聚类中的相关性对文档列表进行排序。单击每个文档会在 Google 上搜索该文档。

Using the Code

该数据集从UCI 机器学习存储库下载。然后将 CSV 解析为数据表，提取并归一化特征，然后从稀疏特征集中创建密集向量。

创建一个查找表，将密集向量与其创建的AAAIDocument关联起来。

// download the document list
var docList = new List<AAAIDocument>();
using (var client = new WebClient()) {
    var data = client.DownloadData(uri);

    // parse the file CSV
    var dataTable = new StreamReader(new MemoryStream(data)).ParseCSV(',');
                
    // create strongly typed documents from the data table
    dataTable.ForEach(row => docList.Add(new AAAIDocument {
        Abstract = row.GetField<string>(5),
        Keyword = row.GetField<string>(3).Split(KEYWORD_SPLIT, StringSplitOptions.RemoveEmptyEntries).Select(str => str.ToLower()).ToArray(),
        Topic = row.GetField<string>(4).Split(TOPIC_SPLIT, StringSplitOptions.RemoveEmptyEntries),
        Group = row.GetField<string>(2).Split(TOPIC_SPLIT, StringSplitOptions.RemoveEmptyEntries),
        Title = row.GetField<string>(0)
    }));
}
 
// create a document lookup table
var docTable = docList.ToDictionary(d => d.Title, d => d);
 
// extract features from the document's metadata
var stringTable = new StringTableBuilder();
var classificationSet = new SparseVectorClassificationSet {
    Classification = docList.Select(d => d.AsClassification(stringTable)).ToArray()
};
 
// normalise the document/term associations
var encodings = classificationSet.Vectorise(true);
 
// convert the sparse feature vectors into dense vectors
var documentClusterList = new List<DocumentCluster>();
using (var lap = Provider.CreateLinearAlgebra()) {
    var lookupTable = encodings
        .Select(d => Tuple.Create(d, lap.Create(d.Data).AsIndexable()))
        .ToDictionary(d => d.Item2, d => docTable[d.Item1.Classification])
    ;
    var vectorList = lookupTable.Select(d => d.Key).ToList();

然后这些密集向量被NNMF聚类。

public IReadOnlyList<IReadOnlyList<IIndexableVector>> Cluster(
  int numIterations,
  Action<float> callback, 
  float errorThreshold = 0.001f
) {
    for (int i = 0; i < numIterations; i++) {
        using (var wh = _weights.Multiply(_features)) {
            var cost = _DifferenceCost(_dataMatrix, wh);
            callback(cost);
            if (cost <= errorThreshold)
                break;
 
            using (var wT = _weights.Transpose())
            using (var hn = wT.Multiply(_dataMatrix))
            using (var wTw = wT.Multiply(_weights))
            using (var hd = wTw.Multiply(_features))
            using (var fhn = _features.PointwiseMultiply(hn)) {
                _features.Dispose();
                _features = fhn.PointwiseDivide(hd);
            }
 
            using (var fT = _features.Transpose())
            using (var wn = _dataMatrix.Multiply(fT))
            using (var wf = _weights.Multiply(_features))
            using (var wd = wf.Multiply(fT))
            using (var wwn = _weights.PointwiseMultiply(wn)) {
                _weights.Dispose();
                _weights = wwn.PointwiseDivide(wd);
            }
        }
    }
 
    // weights gives cluster membership
    return _weights.AsIndexable().Rows
        .Select((c, i) => Tuple.Create(i, c.MaximumIndex()))
        .GroupBy(d => d.Item2)
        .Select(g => g.Select(d => _data[d.Item1]).ToArray())
        .ToList()
    ;
}

此函数迭代numIterations次，每次都试图通过稍微改进矩阵分解来提高其相对于_DifferenceCost函数的分数。

由于初始值是完全随机的，因此每次运行聚类算法时，它都会找到略有不同的聚类。但是，文档集往往保持相对固定 - 即，相同的文档往往会在运行之间一起出现。

差异成本只是找到分解矩阵和原始矩阵之间的距离

float _DifferenceCost(IMatrix m1, IMatrix m2)
{
    return m1.AsIndexable().Rows
        .Zip(m2.AsIndexable().Rows, (r1, r2) => _costFunction.Compute(r1, r2))
        .Average()
    ;

结论

词项/文档矩阵的 NNMF 可以产生一些有趣的结果。找到每个聚类中最强相关的词项集，并拥有每个文档和聚类之间的成员关系程度可能是有用的。

历史

• 2009年3月22日：第一个版本。
• 2009年5月18日：错误修复，服务定义更新。
• 2017年2月21日：重大修订和应用程序迁移到 .net 4.6.1。