1

Java を使用してリザーバー サンプリング アルゴリズムを実装しようとしています。サイズが不明な N 個のデータ ストリーム (シンク ノードに到着するセンサーからの読み取り値) があります。簡単にするために、未知のサイズのストリームが 1 つあると仮定します。

したがって、リザーバー サンプリング アルゴリズムの 1 つが示唆するのは、サイズのリザーバーを作成することです。5 としましょう。取得した最初の 5 つの測定値をリザーバーに保存します。Ok。より多くの読み取り値を取得すると、読み取り値ごとに 0 から読み取り番号までの乱数が生成され、その乱数がリザーバー サイズよりも小さい場合は、読み取り値がリザーバー [randomNumber] に格納されます。

たとえば、reservoirSize = 5 で、10 回目の測定値を取得したとします。0 から 10 までの乱数を生成し、その数が 5 より小さい場合は、乱数が指す場所に読み取り値を保存します。乱数が 3 であるとしましょう。したがって、読み取り番号 10 をリザーバー [3] に保存します。 

public void sample (Vector pool, double Measurement, int streamIndex) {

    if (streamIndex < ReservoirSize){
        pool.addElement(Double.toString(Measurement));
    }
    else if ((randomIndex=(int)ranNum.nextInt((streamIndex+1)))<ReservoirSize) {
        pool.setElementAt(Double.toString(Measurement), randomIndex);
    }    
}

このコードの問題は、streamIndex が十分に大きくなると (たとえば 4.000 を超える)、読み取り値をほとんどサンプリングしないことです。5 より小さい 0 から 4000 までの乱数を生成する確率は、5 より小さい 0 から 100 までの乱数を生成する確率よりも大幅に小さいため、これは理にかなっています。

また、Vitters の論文から AlgorthmR を実装し、ここで説明する別の方法を実装しました:
Gregable ReservoirSampling

しかし、すべての実装には同じ問題があります。ストリームが大きくなるほど、サンプリング周波数は小さくなります。したがって、0.5 秒のサンプリング レートの場合、サンプリングを開始してから 1 時間後 (つまり、約 7000 の読み取り値がシンク ノードに転送されたことを意味します)、測定量の変化は、さらに 30 分ほど検出されません。変更がリザーバーから破棄されることを示します。

アルゴリズムの実装

    public RSAlgorithmR() {
        this.currentPool = null;
        this.randomStoreatIndex = 0;
        this.randomIndex = 0;
        this.ranNum = new Random();
    }

    public void sample (LLNode cNode, double Measurement) {

    int streamIndex = cNode.getStreamIndex();
    int storeatIndex =cNode.getStoreatIndex();


    if (streamIndex < ReservoirSize) {
        cNode.data.addElement(Double.toString(Measurement));

        if (streamIndex == ( ReservoirSize - 1) ) {
            randomStoreatIndex = (int)ranNum.nextInt(ReservoirSize);
            cNode.setStoreatIndex((int)randomStoreatIndex);                
        }
    }
    else {
        if (storeatIndex == streamIndex) {
            randomIndex=(int)ranNum.nextInt(ReservoirSize);
            cNode.data.setElementAt(Double.toString(Measurement), randomIndex); 

            randomStoreatIndex = (int)ranNum.nextInt(streamIndex - ReservoirSize) + ReservoirSize;
            cNode.setStoreatIndex(randomStoreatIndex);

            System.out.println("Index:: "+streamIndex);
            System.out.println("randomIndex:: " + randomIndex);  
        }               
    }
    cNode.setStreamIndex(); 
};

グレガブル実装

    public ReservoirSampler() {

        this.currentPool = null;
        this.randomIndex = 0;
        this.ranProp = new Random();
        this.ranInd = new Random();
    }

    public void sample (LLNode currentSpot, double humidityRead, 
        double temperatureRead, int streamIndex) {

    double acceptancePropability = (double)ReservoirSize/streamIndex;

    if (streamIndex < ReservoirSize){
        currentSpot.humidityData.addElement(Double.toString(humidityRead));
        currentSpot.temperatureData.addElement(Double.toString(temperatureRead));
    }
    else {

        ranProp.setSeed(System.currentTimeMillis());
        randomPropability=(double)ranProp.nextDouble();


        if ( randomPropability < acceptancePropability){
            ranInd.setSeed(System.currentTimeMillis());
            randomIndex=(int)ranInd.nextInt((ReservoirSize));
            currentSpot.humidityData.setElementAt(Double.toString(humidityRead),randomIndex);
            currentSpot.temperatureData.setElementAt(Double.toString(temperatureRead),randomIndex);

        }
    }                 
}

それはアルゴリズムの通常の動作ですか、それともここで何か不足していますか? それが通常の動作である場合、それをより「正確に」機能させる方法はありますか?

4

1 に答える 1