Neo4J로 마코프 체인 시뮬레이션

Question

Markov chain은 특정 확률로 다른 상태로 전환 할 수있는 상태 집합으로 구성됩니다.

마코프 체인은 각 상태에 대한 노드, 각 전환에 대한 관계를 생성 한 다음 적절한 확률로 전환 관계에 주석을 달아 Neo4J에서 쉽게 나타낼 수 있습니다.

하지만 을 시뮬레이션 할 수 있습니다 Neo4J를 사용하여 마르코프 체인을 시뮬레이션 할 수 있습니까? 예를 들어, Neo4J가 특정 상태에서 시작하도록 강요 당하고 확률에 따라 다음 상태와 다음 상태로 전환 할 수 있습니까? Neo4J는이 상태 공간을 통과 한 경로를 출력 할 수 있습니까?

아마도 간단한 예를 들어 이해하기가 쉽습니다. my company's tech blog이라는 텍스트를 기반으로 2 그램의 영어 모델을 만들고 싶다고합시다. 다음을 수행하는 스크립트를 작성합니다.

1. 블로그의 텍스트를 아래로 내립니다.
2. 인접한 모든 문자 쌍을 반복하고 Neo4J에 노드를 만듭니다.
3. 인접한 문자의 3-tuple마다 다시 반복 한 다음 처음 두 글자가 나타내는 노드와 마지막 두 글자가 나타내는 노드 사이에 Neo4J 방향 관계를 만듭니다. 이 관계에있는 카운터를 1로 초기화합니다. 관계가 이미 존재하면 카운터가 증가합니다.
4. 마지막으로, 각 노드를 반복하고, 얼마나 많은 총 송신 전환이 발생했는지 계산 한 다음 특정 노드의 각 관계에 대해 count/totalcount과 같은 새로운 주석을 만듭니다. 이것이 전환 확률입니다.

이제 Neo4J 그래프가 완성되었으므로 2g 모델의 영어로 "문장"을 만들려면 어떻게해야합니까? 결과는 다음과 같습니다.

REPTAGIN의 돌연변이가 자라는 돌연변이가 CRE의 돌연변이입니다.

Answer 1

Neo4j는 사용자가 원하는대로 기능을 제공하지는 않지만 이미 데이터베이스를 올바르게 채우고 있기 때문에 필요한 트래버스는 몇 줄의 코드만으로 이루어집니다.

실험을 약간 수정하여 here으로 다시 만들었습니다. 우선, 텍스트를 통해 단일 패스로 데이터베이스를 채 웁니다 (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()); 
    } 
}