Pythonと系列 (1) discrepancy

はじめに

今まで研究のデータを取るのにほぼC言語のみでプログラムを書いていたが、一念発起（という程高尚なものでもない）してPythonで書いてみようと試みた。Pythonに関しては、まだ勉強中ではあるものの、やはり実際に使うプログラムを書いてみるのが良い勉強になるのだ。

系列とdiscrepancy

Discrepancy(不一致度,くい違い度)というのは系列を評価する際の指標の一つであり、ランダムな要素からなる系列が要素の出現範囲にどれぐらい偏って分布しているのかを示している。一般に真の乱数系列は高いdiscrepancyを持ち、系列の先頭100個といった限られた範囲の要素に関しては、その要素が取りうる出現範囲の中に「疎な部分と密な部分」を併せ持つ。
これに対して、low discrepancyな系列は同じ先頭100個の要素であっても系列の出現範囲内にほぼ均一な間隔で要素が出現する。モンテカルロ法などのシミュレーション分野やロー法といった攻撃方法において用いられる系列は、乱数であることが求められるがそれと同等以上に「領域内から偏りなく要素を抽出する」というlow discrepancyな系列が求められる。

ここでは、非常に簡易なdiscrepancyの数値化として、「有限精度の整数値を持つ系列」に限定し、「系列を要素の大きさ順に並べ替えたときに要素が含まれていない一番大きな間隔の幅」を求めるプログラムを書いてみる。

幾つか調べてみて、numpyにリストの各要素前後間の差分を計算するdiffという関数があるのを見つけた。これを使えば、差分は簡単に計算できる。系列中の最小値と領域の最小値、系列中の最大値と領域の最大値の間隔を算出するため、「系列を要素の大きさ順にソートした後で、領域の最小値と最大値を前後に付け加える」という処理を行う。これで、出現範囲の下半分に偏った系列などを入力した場合でも問題なく計算できる。

discrepancy.py

import numpy as np
def Discrepancy(minvalue, maxvalue, sequence):
    # 並べ替え
    sortedsequence = sorted(sequence)
    # 最小値と最大値でサンドウィッチにする
    sortedsequence.insert(minvalue,0)
    sortedsequence.append(maxvalue)
    # 差分を取る(numpyが必要)
    diffvalues = np.diff(sortedsequence)
    # 差分の最大値＝一番広い間隔
    diffmax = max(diffvalues)
    print('DiffMax : ' + str(diffmax))

if __name__  == '__main__':
    # 実行例
    S1=[4,6,0,1,5]
    S2=[2,8,0,4,6]
    print(S1)
    Discrepancy(0,10,S1)
    print(S2)
    Discrepancy(0,10,S2)

非常に簡単だが、関数の呼び出しは要素の出現範囲最小値(minvalue)と最大値(maxvalue)、そして系列のリスト(sequence)を引数として渡す。最大値、最小値でサンドウィッチにする部分は、多分もう少しまとめて書くような方法があると思うのだが、とりあえず動くのでこれで良しとする。差分を取って、その差分リストの中から最大値を求めれば、それが最初の系列で「一番間隔が開いている部分の長さ」に相当する。

$ python3 discrepancy.py
[4, 6, 0, 1, 5]
DiffMax : 4
[2, 8, 0, 4, 6]
DiffMax : 2

似たような系列にも見えるが、範囲が[0,10)なので7以上の要素が無い上の系列は差分の最大値が大きくなっている。

まとめ

Pythonによる系列の数値解析、まずはdiscprepacy計算のための「一番広い間隔をもつ要素の空白部分」を求めるプログラムを作成してみた。見た目はとても素直で分かりやすい。

次回は一般的な定義によるdiscprepancyの計算を取り上げる。