10

马尔可夫链由一组状态组成，这些状态可以以一定的概率转换到其他状态。

通过为每个状态创建一个节点、为每个转换创建一个关系，然后用适当的概率注释转换关系，可以在 Neo4J 中轻松地表示马尔可夫链。

但是，你能用 Neo4J模拟马尔可夫链吗？例如，是否可以强制 Neo4J 从某个状态开始，然后根据概率转换到下一个状态和下一个状态？Neo4J 能否返回并打印出它通过此状态空间的路径？

也许通过一个简单的例子更容易理解。假设我想根据我公司技术博客的文本制作一个 2 克的英语模型。我启动了一个执行以下操作的脚本：

  1. 它拉下博客的文本。
  2. 它遍历每对相邻的字母并在 Neo4J 中创建一个节点。
  3. 它再次遍历每个相邻字母的 3 元组，然后在前两个字母表示的节点和后两个字母表示的节点之间创建 Neo4J 定向关系。它将这个关系上的计数器初始化为 1。如果关系已经存在，那么计数器就会递增。
  4. 最后，它遍历每个节点，计算总共发生了多少次传出转换，然后在等于 的特定节点的每个关系上创建一个新注释count/totalcount。这就是转移概率。

现在 Neo4J 图表已经完成，我如何让它从我的 2-gram 英语模型中创建一个“句子”？以下是输出的样子：

在没有 IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME 的 REPTAGIN 演示是 CRE 的 REGOACTIONA。

4

1 回答 1

6

Neo4j 没有提供您要求的开箱即用功能，但由于您已经正确填充数据库，因此您需要的遍历只是几行代码。

我在这里重新创建了您的实验，并进行了一些修改。首先，我用单遍文本（步骤 2 和 3）填充数据库，但这是次要的。更重要的是，我只存储每个关系上的出现次数和节点上的总数（步骤 4），因为我认为不需要预先计算概率。

您要求的代码如下所示：

/**
 * A component that creates a random sentence by a random walk on a Markov Chain stored in Neo4j, produced by
 * {@link NGramDatabasePopulator}.
 */
public class RandomSentenceCreator {

    private final Random random = new Random(System.currentTimeMillis());

    /**
     * Create a random sentence from the underlying n-gram model. Starts at a random node an follows random outgoing
     * relationships of type {@link Constants#REL} with a probability proportional to that transition occurrence in the
     * text that was processed to form the model. This happens until the desired length is achieved. In case a node with
     * no outgoing relationships it reached, the walk is re-started from a random node.
     *
     * @param database storing the n-gram model.
     * @param length   desired number of characters in the random sentence.
     * @return random sentence.
     */
    public String createRandomSentence(GraphDatabaseService database, int length) {
        Node startNode = randomNode(database);
        return walk(startNode, length, 0);
    }

    private String walk(Node startNode, int maxLength, int currentLength) {
        if (currentLength >= maxLength) {
            return (String) startNode.getProperty(NAME);
        }

        int totalRelationships = (int) startNode.getProperty(TOTAL, 0);
        if (totalRelationships == 0) {
            //terminal node, restart from random
            return walk(randomNode(startNode.getGraphDatabase()), maxLength, currentLength);
        }

        int choice = random.nextInt(totalRelationships) + 1;
        int total = 0;
        Iterator<Relationship> relationshipIterator = startNode.getRelationships(OUTGOING, REL).iterator();

        Relationship toFollow = null;
        while (total < choice && relationshipIterator.hasNext()) {
            toFollow = relationshipIterator.next();
            total += (int) toFollow.getProperty(PROBABILITY);
        }

        Node nextNode;
        if (toFollow == null) {
            //no relationship to follow => stay on the same node and try again
            nextNode = startNode;
        } else {
            nextNode = toFollow.getEndNode();
        }

        return ((String) nextNode.getProperty(NAME)).substring(0, 1) + walk(nextNode, maxLength, currentLength + 1);
    }

    private Node randomNode(GraphDatabaseService database) {
        return random(GlobalGraphOperations.at(database).getAllNodes());
    }
}
于 2013-07-05T11:30:59.350 回答