大数据文本 LINQ XML 中级开发 C#

使用 XML 转储构建类别层级和分类维基百科文章

Ilia Reznik

5.00/5 (25投票s)

2016年6月1日

CPOL

10分钟阅读

43659

332

如何使用 XML 转储对维基百科文章进行分类。

下载项目 - 73.1 KB

引言

维基百科作为数据挖掘的独特来源的价值怎么强调都不为过。其全部文本内容的XML转储允许每位研究者发现隐藏在历史和社会中的事物之间的关系和模式。

这个过程的必要阶段是过滤感兴趣的信息。在最简单的情况下，可以使用关键字搜索。然而，这种方法的可靠性很低，因为它忽略了短语中关键字的含义，并且无法指定紧密描述主题的关键字集合。维基百科有一个组织信息的内在机制。那就是分类。几乎每一页都被要求属于至少一个类别。然而，基于这一事实的分类在实践中并不“易于使用”。

在本文中，我们

使用我们先前工作的代码和结果来构建一个相当复杂的对象，该对象表示维基百科的类别层级结构。
开发一个分类器，用于确定一个页面是否属于某个类别或其任何子类别。
提供一个GUI应用程序，演示类别层级结构的使用并执行适当的分类。

背景

了解维基百科页面的创建及其分类过程是很有益的。需要下载完整的“pages‐articles”XML转储文件。我们使用了enwiki‐20160305‐pages‐articlesmultistream.xml.bz2（2016年春季大约12.7G的存档，包含52.5G的文件）。现在它在其原始位置不可用。类似的较新文件可以从维基百科下载页面维基百科下载页面下载，例如。然后，我们需要我们先前文章“解析维基百科XML转储”中的项目来提取真实数据。

C#代码使用各种集合、一些LINQ和RegEx。

维基百科中的分类

首先，让我们简要回顾一下维基百科的分类方式。

维基百科返回的每个网页都显示了它所属的类别列表。它们列在每页底部的“Categories”框中。例如，“Algorithm”页面属于“Algorithms”、“Mathematical logic”和“Theoretical computer science”类别。

我们称它们为“直接父项”，相应地将该页面视为“直接子项”。存在一些例外。例如，像“Contents”这样的基本类别没有父项。“Articles”类别下存储了实际的文章。目前，即使不包括所谓的“隐藏”类别和特殊用途类别，也有超过一百万个类别。

每个直接父类别通常有自己的直接父项。例如，“Mathematical logic”是“Logic”、“Fields of Mathematics”和“Philosophy of mathematics”的直接子项。这样，父子关系就可能形成长链。

由此方法生成的类别层级结构不是一个简单的树结构，因为每个页面通常至少有几个父项。该结构要复杂得多。理想情况下，它应该是一个有向无环图。简单来说，不应该有循环，也不应该出现子项出现在其自身父项列表中的情况。实际上，存在许多此类循环和双向父子关系。其中一些非常短，另一些则跨越多个层级。维基百科提供了一个工具来揭示它们。示例

此图像中的框是可点击的。箭头表示从父项到子项的关系。

维基百科会随时间而变化，因此某些此类情况可能会消失。但很难想象所有这些都可以被消除。基于类别层级结构开发自动分类器时，应非常小心。

另一个需要考虑的因素是，类别关系中的任何错误可能比常规页面中的错误产生更严重的影响，因为搜索可能会返回大量误报（当错误的类别被定义为子类别时）或漏报（当真正的子类别被遗漏时）。父项的选择几乎完全是维基百科贡献者的责任。稍后将给出几个相关问题的示例。因此，研究人员不应仅依赖于查询层级结构的正式方法。他们必须准备好运用常识，进行足够的统计选择检查，并选择最合理的查询。

幸运的是，情况并不像乍看起来那么糟糕。任何人都可以通过在维基百科搜索框中键入“Category:[SomeCategory]”来选择几个类别，然后遍历父项或子项来确保链的构建是否合理。

研究人员的目标

构建层级结构对象本身并不是目的。实际任务在于提取与研究主题相关的信息。在许多情况下，主题可以用类别来描述。让我们举个例子。

假设我们的研究侧重于维基百科中提到的体育界人物。通过筛选类别列表，我们找到了“Sportspeople”类别。如果按照我们之前描述的方法将页面及其父类别提取出来，那么我们就有一个查找表，如下所示：

名称	出生	逝世	年龄	Count	父类别
Moonlight Graham	1879	1965	86	45	...\|来自北卡罗来纳州费耶特维尔的体育人士\|美国医生\|...\|纽约巨人队（NL）球员\|马里兰大学巴尔的摩分校校友\|...
Lou Thesz	1916	2002	86	198	..\|美国男性职业摔跤手\|匈牙利裔美国人\|职业摔跤名人堂和博物馆\|...
Marc Perrodon	1878	1939	61	9	..\|来自旺多姆的人\|法国男性击剑运动员\|法国奥运击剑运动员\|1908年夏季奥运会的击剑运动员\|...

第一行明确提到了“Sportspeople”这个词在直接父项中。因此，分类似乎非常明显。然而，事实并非如此，因为实际的父项是“Sportspeople from...”，而不是“Sportspeople”。在一般情况下，一个词在整个类别名称中可能具有任何含义。“Sportspeople from Fayetteville, North Carolina”确实是“Sportspeople”的子类别，但拥有共同的词语并不能作为一般情况下父子关系的可靠证据。

第二行和第三行的分类对于人类来说是清晰的，因为我们知道摔跤手和击剑运动员（尤其是在参加奥运会的情况下）是体育界人士。计算机事先并不知道这一点。因此，要进行自动分类，就需要了解感兴趣类别的所有子类别。只有当一个页面所属的子类别正好出现在该页面的直接父类别列表中时，该页面才与主题类别相关。

让我们构建类别层级结构图和一个基于它的分类器。

Hierarchy类

两个字典构成了Hierarchy类的核心。

/// <summary>CategoryData of category by name</summary>
public Dictionary<string, CategoryData> CategoriesByName;

/// <summary>Category name by index</summary>
public Dictionary<int, string> CategoriesByIndex;

第一个字典允许按名称快速访问类别属性，第二个字典按索引检索类别名称。类别属性属于CategoryData类。

/// <summary>A class containing information about category</summary>
public class CategoryData
{
    /// <summary>Immediate parents for the category by index</summary>
    public HashSet<int> Parents = new HashSet<int>();
    /// <summary>Immediate children for the category by index</summary>
    public HashSet<int> Children = new HashSet<int>();

    public int Index;
    public int Level;

    /// <summary>Constructor</summary>
    public CategoryData(int index, int level = -1)
    {
        Index = index;
        Level = level;
    }
}

我们引入Level来衡量一个类别相对于顶级类别的距离。顶级类别可以是任何一个。然而，为了包含维基百科的全部内容，它应该设置为“Contents”或“Articles”。顶级类别的Level定义为零。其所有直接子项的Level为一。它们的子项的Level为二，依此类推。在计算层级之前，我们需要加载所有类别及其直接父项。对于每个类别，它们存储在CategoryData的Parents成员中。使用HashSet<int>是因为成员的顺序无关紧要，并且保证没有重复项。

如果类别A是类别B的直接父项，那么B就是A的直接子项。通过CategoryData的Children成员可以快速访问子项。

Hierarchy类的构造函数读取包含类别名称及其父项名称的制表符分隔文件，并将其加载到这些字典中。该文件可能包含可选的“Level”列。

/// <summary>
/// This constructor loads a tab-delimited file containing categories, 
/// their levels (optional), and immediate parents.
/// </summary>
/// <param name="categoryParentsPath">
/// Path to tab-delimited file with the following columns: 
/// Category  [Level] [Any columns] Parent1|Parent2|...
/// </param>
public Hierarchy(string categoryParentsPath)

如果输入文件包含Levels列，则每个类别的级别将设置为文件中的值。否则，将在该方法结束时相对于“Articles”计算级别（如果存在）。如果不存在，则后续使用

要求调用者执行。

/// <summary>Calculates levels relatively to the specified top category</summary>
/// <param name="topCategory">Name of top category</param>
/// <returns>None</returns>
public void SetLevelsFromTop(string topCategory)

要保存Hierarchy对象（或其子图，在调用SetLevelsFromTop(...)之后），请使用Save(...)。

/// <summary>
/// Saves the hierarchy in the tab-delimited file of format: Category Level Parent1|Parent2...
/// </summary>
/// <param name="path">Path to the output file</param>
/// <returns>None</returns>
public void Save(string path)

保存的较小文件可以在输入时使用，如果只需要子图。

要检索所有父项或子项（不只是直接的），请使用AllRelatives(...)。

/// <summary>Calculates all relatives of category</summary>
/// <param name="index">Index of category</param>
/// <param name="direction">true for children, false for parents</param>
/// <returns>HashSet<int> (Index and Level) </returns>
public HashSet<int> AllRelatives(int index, bool direction)

正确的计算可能相对较长。为了避免GUI“冻结”，此方法通过围绕异步任务的包装器进行装饰，返回其结果。

private async Task<HashSet<int>> AllRelativesTask(int index, bool direction)
{
    return await Task.Run(() => GetAllRelatives(index, direction)).ConfigureAwait(false);
}

private HashSet<int> GetAllRelatives(int index, bool direction)
{
    HashSet<int> result = new HashSet<int>();
    HashSet<int> relatives = new HashSet<int>();
    relatives.Add(index);
    while (relatives.Count > 0)
    {
        result.UnionWith(relatives);
        relatives = ValidRelatives(relatives, direction);
        relatives.ExceptWith(result);
    }
    return result;
}

此方法实现了在给定方向上对图进行非递归遍历。使用HashSet类可以处理打破循环。由于类别的数量有限且result中没有重复项，因此循环是有限的。

ValidRelatives(...)从HashSet<int>类别集合中的所有节点收集可接受的直接亲属。

private HashSet<int> ValidRelatives(HashSet<int> categories, bool direction)
{
    HashSet<int> result = new HashSet<int>();
    foreach (int i in categories)
    {
        HashSet<int> validRelatives = ValidRelatives(i, direction);
        result.UnionWith(validRelatives);
    }
    return result;
}

在考虑以下真实世界中的子父关系示例后，将解释HashSet<int> ValidRelatives(int index, bool direction)的含义。

尽管不能保证维基百科的相关内容不会被更改，但跟踪这条相当典型的链是很好的。只需点击图像中的区域，并在打开网页的底部查看相应的父类别。

“Sports competitions”出现在“Abstraction”甚至“Animal anatomy”的子类别中是完全没有道理的。为了理解为什么会发生这种情况，让我们注意类别的层级。

第一个有疑问的关系是Competition (Level 3) <‐ Difference (4)。第二个是Thought (3) <‐ Mind (5) <‐ Brain (6)。通常，父项应该位于层级结构的上层，并且Level值应低于子项。上面的链显示了对该规则的违反。

为了尽量减少此类无意义结果的风险，我们对父项和子项级别之间的可能关系应用了限制，使用了ParentLevelAllowance属性。

public enum ParentLevelAllowanceType { LowerOnly = 0, SameOrLower = 1, Any = 2 };
private ParentLevelAllowanceType parentLevelAllowance = 
                            ParentLevelAllowanceType.SameOrLower; // Default

并以这种方式计算ValidRelatives。

public HashSet<int> ValidRelatives(int category, bool direction)
{
    int level = Level(category);
    switch (ParentLevelAllowance)
    {
        case (ParentLevelAllowanceType.LowerOnly) :
        {
            return direction ? new HashSet<int>(Children(category).Where(x => Level(x) > level))
                             : new HashSet<int>(Parents(category).Where(x => Level(x) < level));
        }
        case (ParentLevelAllowanceType.SameOrLower) :
        {
            return direction ? new HashSet<int>(Children(category).Where(x => Level(x) >= level))
                             : new HashSet<int>(Parents(category).Where(x => Level(x) <= level));
        }
        default:
        {
            return direction ? new HashSet<int>(Children(category))
                             : new HashSet<int>(Parents(category));
        }
    }
}

LowerOnly和SameOrLower，研究感兴趣的类别。根据我们的经验，SameOrLower是最好的默认设置。LowerOnly通过减少检测的总数来降低误报的数量。

为了说明这个问题，让我们假设一项研究侧重于科学领域的人物。“Science”类别似乎是一个不错的起点。在LowerOnly的情况下，它会产生大约40000个子项的列表。虽然可能存在例外，但我们没有发现任何非科学的子项（根据我们的看法）。同时，很容易发现该列表并不像所需的那样完整。SameOrLower会生成一个更大的集合，其中包含许多我们不想要的东西的虚假子项。

Chain from Science (2) to Prayers by meher baba (5)