は、上部紙ソングの「人の移動における予測可能性の限界」のように、予測可能

Question

私は私の占有データセットの予測の上限を計算しようとしている上で結合しました。基本的には、家庭（= 1）で自宅ではなく（= 0）、ソング紙の訪問先（タワー）を表します。

私は、エントロピー1と予測可能性0.5を返すランダムなバイナリシーケンスで自分のコード（https://github.com/gavin-s-smith/MobilityPredictabilityUpperBoundsとから派生したもの）をテストしました。代わりに、返されたエントロピーは0.87であり、予測可能性は0.71です。

はここに私のコードです：

import numpy as np 
from scipy.optimize import fsolve 
from cmath import log 
import math 

def matchfinder(data): 
    data_len = len(data)  
    output = np.zeros(len(data)) 
    output[0] = 1 

    # Using L_{n} definition from 
    #"Nonparametric Entropy Estimation for Stationary Process and Random Fields, with Applications to English Text" 
    # by Kontoyiannis et. al. 
    # $L_{n} = 1 + max \{l :0 \leq l \leq n, X^{l-1}_{0} = X^{-j+l-1}_{-j} \text{ for some } l \leq j \leq n \}$ 

    # for each position, i, in the sub-sequence that occurs before the current position, start_idx 
    # check to see the maximum continuously equal string we can make by simultaneously extending from i and start_idx 

    for start_idx in range(1,data_len): 
     max_subsequence_matched = 0 
     for i in range(0,start_idx): 
      # for(int i = 0; i < start_idx; i++) 
      # { 
      j = 0 

      #increase the length of the substring starting at j and start_idx 
      #while they are the same keeping track of the length 
      while((start_idx+j < data_len) and (i+j < start_idx) and (data[i+j] == data[start_idx+j])): 
       j = j + 1 

      if j > max_subsequence_matched:  
       max_subsequence_matched = j; 

     #L_{n} is obtained by adding 1 to the longest match-length 
     output[start_idx] = max_subsequence_matched + 1;  

    return output 

if __name__ == '__main__': 
    #Read dataset    
    data = np.random.randint(2,size=2000) 

    #Number of distinct locations 
    N = len(np.unique(data)) 

    #True entropy 
    lambdai = matchfinder(data) 
    Etrue = math.pow(sum([ lambdai[i]/math.log(i+1,2) for i in range(1,len(data))]) * (1.0/len(data)),-1) 

    S = Etrue 
    #use Fano's inequality to compute the predictability 
    func = lambda x: (-(x*log(x,2).real+(1-x)*log(1-x,2).real)+(1-x)*log(N-1,2).real) - S 
    ub = fsolve(func, 0.9)[0] 
    print ub 

matchfinder機能は最長一致を探すことによりエントロピーを見つけて（=最短ストリングが以前に見たことがない）、それに1を加算します。次に、Fanoの不等式を使用して予測可能性を計算します。

何が問題なのですか？

ありがとうございます！

Answer 1

エントロピー関数が間違っているようです。紙ソン、C.、ク、Z.、Blumm、N.、&Barabási、A. L.（2010）への参照元 。人間の移動性における予測可能性の限界。 Science、327（5968）、1018-1021。コードで

が、それは次のようになります：あなたが言及した、実際のエントロピーはレンペル - ジブのデータ圧縮に基づくアルゴリズムによって推定される

nは、時系列の長さである

Etrue = math.pow((np.sum(lambdai)/ n),-1)*log(n,2).real 

。

ここでは、指定された数式とは異なる対数を使用しています。しかし、Fanoの不等式の対数の基底は2であるため、エントロピー計算には同じ基底を使用するのが理にかなっているようです。また、ゼロインデックスではなく最初のインデックスから合計を開始した理由はわかりません。

だから今、例えば関数にそれを包む：3つの場所

Distinct locations: 3 
Time series length: 10000 
Maximum entropy: 1.58496 
Real entropy: 1.56567 
Upper bound of predictability: 0.41172 

のLempel-Ziv符号のための2箇所

Distinct locations: 2 
Time series length: 10000 
Maximum entropy: 1.00000 
Real entropy: 1.01441 
Upper bound of predictability: 0.50013 

出力用

def solve(locations, size): 
    data = np.random.randint(locations,size=size) 
    N = len(np.unique(data)) 
    n = float(len(data)) 
    print "Distinct locations: %i" % N 
    print "Time series length: %i" % n 

    #True entropy 
    lambdai = matchfinder(data) 
    #S = math.pow(sum([lambdai[i]/math.log(i + 1, 2) for i in range(1, len(data))]) * (1.0/len(data)), -1) 
    Etrue = math.pow((np.sum(lambdai)/ n),-1)*log(n,2).real 
    S = Etrue 
    print "Maximum entropy: %2.5f" % log(locations,2).real 
    print "Real entropy: %2.5f" % S 

    func = lambda x: (-(x * log(x, 2).real + (1 - x) * log(1 - x, 2).real) + (1 - x) * log(N - 1, 2).real) - S 
    ub = fsolve(func, 0.9)[0] 
    print "Upper bound of predictability: %2.5f" % ub 
    return ub 

出力をcompr nが無限に近づくと、実際のエントロピーに収束します。そのため、2つの場所の場合、最大限よりわずかに高いです。

私はあなたが正しくラムダの定義を解釈した場合にもわかりません。あなたのマッチングアルゴリズム、「最短私は以前dosen'tどの位置から始まる部分文字列の長さは、位置1からI-1に現れる」ので、私たちはさらにサブストリングはもう一意ではありませんいくつかのポイントに着いたときとして定義されます一意の部分文字列が存在しないので、部分文字列の長さより常に1つ長く、長さは0になるはずです。

簡単な例をあげましょう。位置の配列が次のようになっている場合：

[1 0 0 1 0 0] 

次に、最初の3つの位置パターンがもう一度繰り返されていることがわかります。それは、このように、それが0に等しい、第四の場所からshorthestユニークサブが存在しないことを意味ので、出力（ラムダ）は次のようになります。

[1 1 2 0 0 0] 

しかし、そのような場合のために、あなたの関数が返します：

[1 1 2 4 3 2] 

私はあなたがその問題を治療するための機能をマッチング書き直し：

def matchfinder2(data): 
    data_len = len(data) 
    output = np.zeros(len(data)) 
    output[0] = 1 
    for start_idx in range(1,data_len): 
     max_subsequence_matched = 0 
     for i in range(0,start_idx): 
      j = 0 
      end_distance = data_len - start_idx #length left to the end of sequence (including current index) 
      while((start_idx+j < data_len) and (i+j < start_idx) and (data[i+j] == data[start_idx+j])): 
       j = j + 1 
      if j == end_distance: #check if j has reached the end of sequence 
       output[start_idx::] = np.zeros(end_distance) #if yes fill the rest of output with zeros 
       return output #end function 
      elif j > max_subsequence_matched: 
       max_subsequence_matched = j; 
     output[start_idx] = max_subsequence_matched + 1; 
    return output 

違いはもちろんの小さい、Bシーケンスの小さな部分に対してのみ結果が変化します。