Formal Concept Analysis with Rust (1) - Introduction

Introduction

不知不觉，从开始使用Rust到现在已经有接近一年了，Rust也渐渐成为了目前用起来感觉最舒服的语言。虽然Rust号称因为有确定性析构，所以不会在内存释放上有效率损失，不过在实际使用中，总是能够感觉到再有大量小内存分配和释放的时候运行效率和内存效率都比C要稍微低一些。这次，让我们用Rust通过实现一套形式概念分析的算法，来看看Rust在全列举程序上的表现到底如何。

Formal Concept Lattice

这次我们将把重心放在实现上，对与Formal Concept的我们只介绍在程序中需要使用的特征，如果打算了解更详细的理论内容，可以参考Lattice Theory的综述性论文，比如：

Wille, Rudolf.

"Restructuring lattice theory: an approach based on hierarchies of concepts."

Ordered sets. Springer Netherlands, 1982. 445-470.

简单来说，对于一组文章\(D={d_1, d_2, \dots, d_n}\)，和一些事先提取出来的文字\(W={w_1, w_2, \dots, w_n}\), 每一篇文章都可以包含若干文字，同时每一个文字可以属于若干篇文章。基于这个关系，我们可以想象：如果文章和文字的集合选取得当，那么我们可以得到一个文章-文字集合\(C=(A,B), A \subseteq D, B \subseteq W\)，其中A中文章的共通文字集合恰好是B，而反之，所有包含B的文章集合又恰好是A。用聚类的语言来说，就是我们根据特征B选取了一个Cluster A。那么，对于所有可能的这种\((A,B)\)的集合，则就是一个根据文字对文章进行的聚类分析。而这里，每一个\(C=(A,B)\)称为一个Formal Concept（形式概念）。

现在让我们来思考两个形式概念之间可能存在的关系，对于两个形式概念\(C_1 = (A_1, B_1)\), \(C_2 = (A_2, B_2)\)，如果\(A_1 \subset A_2\)，也就是说\(A_2\)除了有\(A_1\)的文章之外，还包含了别的文章，那么显然的，\(A_2\)所有文章的共通文字肯定会更少（注意：而不是不会更多，原因是如果\(B_2\)跟\($B_1\)是一样的，那么根据Formal Concept的性质，我们可以知道\(A_1 = A_2\)）。因此，我们可以根据\(A\) 或者 \(B\) 的包含关系来创建一个束，这个束成为Formal Concept Lattic。

当我们有了一个Formal Concept Lattice，就相当于我们把文章进行了分层聚类，最顶层包含了所有的文章和它们共通的文字（文字可能是空集），越下面共通的文字越多而每一个Formal Concept包含的文章越少，直到最下面，我们得到所有共通的文字和包含这些文字的文章的集合。在实际应用中，Formal Concept Lattice可以用来分析话题的关注度，提取抽象概念，以及通过额外的关联（比如文字合集的互信息量）来提取关键信息。不过，在这篇文章里，我们不会设计应用，而是把重心放在构建Formal Concept Lattice本身上。

Building Formal Concept Lattice

假设我们已经有了文章和单词的包含关系，比如像下面的表：

每一行代表了一篇文章-所有单词的对应关系，0代表文章里没有出现这个单词，1则反之。要建立一个Formal Concept Lattice，只需要完成下面两件事：

• 列举出所有可能的Formal Concept
• 对于所有可能的Formal Concept，将它们按照包含关系建立成Lattice。

由于并不是任意的文章集合-单词集合都是Formal Concept，因此我们需要筛选出那些满足性质的组合。比如，在上面这个表中， \((\{doc1, doc2\}, \{word2\})\)并不是一个Formal Concept，原因是虽然word2是doc1和doc2的共通单词，但实际上doc1,doc2和doc3共同包含word2，因此正确的Formal Concept应该是\((\{doc1, doc2, doc3\}, \{word2\})\)。

那么假设我们有了文章集合\(\{doc1, doc2\}\)，那么该如果获得一个Formal Concept？答案很简单，由于Formal Concept是唯一的，因此我们首先寻找\(\{doc1, doc2\}\)的共通单词，这里是\(\{word2\}\)，然后，我们只需要寻找所有包含\(\{word2\}\)的文章即可，在这里，我们可以看到是\(\{doc1, doc2, doc3\}\)，这样，我们就能获得一个Formal Concept。而这个寻找单词-寻找文章的操作，在Formal Concept Analysis里称作闭包（Closure）。很容易想象，有了闭包操作，我们只需要对所有的可能的文章组合取闭包，然后去掉重复，就可以得到所有的Formal Concept了。这就是目前所有Formal Concept Enumeration算法的基本思想。总结起来，算法可以简单归纳成一个简单的深度优先搜索:

Function EnumerateConcept(concept)
    for any document not in concept.concept do
        concept.document = concept.document+ document
        new_concept = closure(concept.document)
        if new_concept is not duplicate do
            add new_concept to concept_list
        end do
        EnumerateConcept(new_concept)
    end do
end func

有了所有的Formal Concept之后，我们可以着手开始建立Lattice了，不过，由于Lattice包含关系的限制，我们并不能想图一样简单的对所有Formal Concept Pair遍历然后创建连接，而是需要先把Formal Concept按照文章数的多少排序，然后按照大小顺序来简历Lattice。如果你对Lattice不熟，那么有可能不明白为什么，没关系，让我们看一个例子：

假设我们已经有三个Formal Concept(只列出的文章集合)： \(C_1 = \{doc1, doc2, doc3\}\), \(C_2 = \{doc1, doc3\}\), \(C_3 = \{doc3\}\), 那么Lattice应该是\(C_1 - C_2 - C_3\)，其中，\(C_1\) 和 \(C_3\)不能直接相连，因为按照顺序关系，其中还有一个\(C_2\)。

看到这里，你可能已经明白了，如果我们遍历所有可能的组合，那么我们并不知道这两个Concept之间是否有别的“中间节点”，但是，由于包含关系的性质（较小的一定无法包含较大的），我们只要按照大小排序，那么对于任何两个Concept，可能的中间节点总是在它们之间 —— 这样我们就判定两个节点是否能直接相连了。更明确一些，实际上，在列举过程中我们可以自然的得到足够的信息，因此并没有必要真的去排序然后遍历，这些我们会在后面的文章里讨论。

Summary

在这篇文章里我们简单介绍的Formal Concept Lattice的性质和相关的算法。在接下来的文章中，我们将会依次实现下面的功能：

• Formal Concept的数据结构
• Formal Concept的列举算法
• Formal Concept Lattice的创建算法
• 基于Formal Concept Lattice的简单数据挖掘

在下一章里，我们将会着手实现最基本的数据结构，在实现中，我们会遇到并解决一些Rust独有的Borrow-checker问题。