[alg] omgekeerd logaritmisch steekproefen nemen

[killercow]

Ik ben bezig met een script wat per pagehit allerlei gegevens gaat opslaan, Nu is het natuurlijk vreselijk interesant om alle views op te slaan, maar dat vreet natuurlijk al snel veel te veel ruimte.

Ik had bedacht dat het waarschijnlijk het zo veel waard is om naar gelang de groei van het aantal bezoekers in verhouding steeds minder data op te slaan, (zeg maar een soort van steekproefen), maar ik heb geen idee hoe ik dat het beste (en het liefst een beetje dynamisch) kan bouwen.

Stel dat ik 100 views heb, dan is het interesant om van ongeveer 15 bezoekers alle gegevens te weten. (15%)
Als ik echter 100000 views heb is het natuurlijk niet interesant om daarvan (15%) procent op te slaan. dat zouden immers 15000 records zijn.

Ik dacht dat een omgekeerd logarithmische steekproef veel beter zou zijn, dan heb je de volgende staffel:

code:

views, steekproefen
10 , 1
100, 2
1000, 3
10000, 4

Maar dat is natuurlijk wel weer erg weinig, en niet erg aanpasbaar (per site bijvoorbeeld)

Heeft iemand hier toevallig als eens over nagedacht? ik kan me voorstellen dat een wiskundige hier binnen no time een variabele (x,y) formule bij heeft bedacht waarbij het aantal steekproefen aanpasbaar is.

[WVL_KsZeN]

antwoord : machten

bijvoorbeeld de wortel uit het aantal views.

100 -> 10 records
10000 -> 100 records.

als je 100 records op 10.000 te weinig vind, neem je een iets hogere macht, bijvoorbeeld (views)^0.6 ofzo, dan heb je al 251 records (en bij 100 views 16 records).

wat je dus kunt doen bv is :

bij de eerste view sla je de record op. vervolgens wacht je (1)^.6 view en sla die op (dat is dus direct de volgende
daarna wacht je 2^.6 views en slaat die op (dat is dus view 4).
dan wacht je 4^.6 etc.. etc.. etc..

[ Voor 33% gewijzigd door WVL_KsZeN op 03-11-2004 17:10 ]

[Grijze Vos]

killercow schreef op 03 november 2004 @ 16:59:

code:

views, steekproefen
10 , 1
100, 2
1000, 3
10000, 4

code:

views, steekproefen
10 , 1 *10
100, 2 * 10
1000, 3  * 10
10000, 4 * 10

?

[Orphix]

Je kan het ook time-based doen. Bijvoorbeeld elke 5 seconden een keer wel de gegevens opslaan. Voordeel hiervan is dat je altijd de maximum grootte kan berekenen van de loggegevens. Het kan dan hoogstens kleiner zijn. Nadeel is wel dat de gegevens die je hebt gelijk verspreid zijn over de gehele dag. In piekuren zullen relatief minder hits geregistreerd worden, waardoor een hit in daluren meer meegeteld wordt dan een hit in een piekuur.

[Macros]

Wat Orphix voorstelde wilde ik ook zeggen. Je genereert elke zoveel tijd een token. Die tokens doe je in een bucket. Elke keer als er een pageview is kijk je of er tokens in de bucket zitten. Zo ja dan log je en haal je er 1 token uit. Zo nee dan log je niet.

[Verwijderd]

Als je nou eens opsomt wat je allemaal wil loggen, dan kunnen wij misschien kijken of de opslag efficienter kan. Wanneer je bijvoorbeeld wil weten per pagina hoelang de gemiddelde bezoeker er op rondneust, kan je voor alle bezoekers de tijd loggen en dan een gemiddelde uitrekenen. Je kan ook per pagina een record aanmaken met aantal bekeken momenten, gemiddelde tijd, standaarddeviatie. Nieuwe gemiddeldes en standaarddeviaties uitrekenen is simpel. Zo houd je het aantal records laag, maar sla je wel de benodigde gegevens op...

[analog_]

Waarom niet procentueel ? met een minumum van zeg maar 100 ofzoiets ?
en dan random uit de 100000000 10% halen
Ewald

[Grijze Vos]

Je kunt natuurlijk ook alles loggen en elke dag even de logs van de dag parsen tot iets compacts.

[Verwijderd]

[off topic]
steekproeven.
[/off topic]

[dingstje]

WVL_KsZeN schreef op 03 november 2004 @ 17:04:
antwoord : machten

bijvoorbeeld de wortel uit het aantal views.

100 -> 10 records
10000 -> 100 records.

als je 100 records op 10.000 te weinig vind, neem je een iets hogere macht, bijvoorbeeld (views)^0.6 ofzo, dan heb je al 251 records (en bij 100 views 16 records).

wat je dus kunt doen bv is :

bij de eerste view sla je de record op. vervolgens wacht je (1)^.6 view en sla die op (dat is dus direct de volgende
daarna wacht je 2^.6 views en slaat die op (dat is dus view 4).
dan wacht je 4^.6 etc.. etc.. etc..

Dan kan je geen evolutie afleiden uit je statistieken. Na 100000 hits moet je zodanig lang wachten dat je niet snel op trends inspeelt.

Ik zou gewoon alles loggen en samenvattingen opslaan om de x tijd (per uur, per dag, ...)

[killercow]

dingstje schreef op 03 november 2004 @ 21:22:
[...]


Dan kan je geen evolutie afleiden uit je statistieken. Na 100000 hits moet je zodanig lang wachten dat je niet snel op trends inspeelt.

Ik zou gewoon alles loggen en samenvattingen opslaan om de x tijd (per uur, per dag, ...)

Ik denk dat ik toch voor de machten methode ga, deze compressed m'n hoeveelheid data zonder dat ik er echt waardevolle info verloren gaat.

Als ik ook nog eens iedere 24 uur de count op 0 dump (niet alle sites tegelijk, om de load the spreaden) moet het best gaan, ik gok er op dat ik alsnog vaak genoeg aan de 10K tot 100K kom, en dat ik inderdaad met nog hogere getallen de veranderingen in de stats niet meer kan recorden.

Heel erg bedankt allemaal, kan trouwens best een leuk discussie punt zijn dit, De procentuele versie is zoals ik al schreef in de openings post niet handig omdat het aantal records dat gelogd wordt linear meeloopt met de groei van het aantal kliks. En ik ben van mening dat als je steekproeVen wilt doen op internet verkeer, je steeds minder hebt aan de kleine details, maar dat juist de grote massa gaat tellen.
Aan de andere kant kunnen 2 (per ongeluk) "gekozen" minderheden een enorm vertekend beelt opleveren, stel dat ik van de 10 steekproeven die ik neem voor de 5000 (latere) views die ik krijgt, er twee uitkies met de zelfde zeldzame browser, dan komen die natuurlijk behoorlijk vertekend uit de bus.

[Orphix]

killercow schreef op 04 november 2004 @ 00:12:
Aan de andere kant kunnen 2 (per ongeluk) "gekozen" minderheden een enorm vertekend beelt opleveren, stel dat ik van de 10 steekproeven die ik neem voor de 5000 (latere) views die ik krijgt, er twee uitkies met de zelfde zeldzame browser, dan komen die natuurlijk behoorlijk vertekend uit de bus.

Dat klopt. Maar er is een algemene vuistregel in de statistiek, de zgn 'Wet van de grote getallen', die stelt dat zulke fluctuaties bij grotere aantallen elkaar opheffen en zodoende niet meer significant zijn. Ik vermoed dat als je van elke dag 100 hits registreert, je na een paar dagen al representatieve cijfers hebt.

[T-MOB]

killercow schreef op 04 november 2004 @ 00:12:
[...]


Ik denk dat ik toch voor de machten methode ga, deze compressed m'n hoeveelheid data zonder dat ik er echt waardevolle info verloren gaat.

Als ik ook nog eens iedere 24 uur de count op 0 dump (niet alle sites tegelijk, om de load the spreaden) moet het best gaan, ik gok er op dat ik alsnog vaak genoeg aan de 10K tot 100K kom, en dat ik inderdaad met nog hogere getallen de veranderingen in de stats niet meer kan recorden.

Heel erg bedankt allemaal, kan trouwens best een leuk discussie punt zijn dit, De procentuele versie is zoals ik al schreef in de openings post niet handig omdat het aantal records dat gelogd wordt linear meeloopt met de groei van het aantal kliks. En ik ben van mening dat als je steekproeVen wilt doen op internet verkeer, je steeds minder hebt aan de kleine details, maar dat juist de grote massa gaat tellen.
Aan de andere kant kunnen 2 (per ongeluk) "gekozen" minderheden een enorm vertekend beelt opleveren, stel dat ik van de 10 steekproeven die ik neem voor de 5000 (latere) views die ik krijgt, er twee uitkies met de zelfde zeldzame browser, dan komen die natuurlijk behoorlijk vertekend uit de bus.

Als ik jou was zou ik toch voor een samenvating over een tijdsinterval (per dag ofzo) gaan. Dus gewoon alles loggen en aan het eind van de dag de gegevens aggregeren. Waarom? (omdat het kan!).
Serieus: Met een steekproef raak je redelijk wat informatie kwijt die boeiend is voor een website. Je zult bijvoorbeeld nooit het aantal unieke bezoekers kunnen bepalen. Je zult nooit kunnen bepalen of iemand doorsurft op je site of gelijk weg is na je frontpage gezien te hebben. Kortom met een steekproef kun je eigenlijk alleen wat basale eigenschappen van je gebruikers bepalen (browser, land van herkomst, etc).

Maar zelfs als het om de basale zaken gaat dan bespaar je redelijk grof door een samenvatting per dag te maken. Als je 100 karakteristieken per dag opslaat dan levert aggregeren je een factor n winst op qua disk-ruimte. Waarbij n gelijk is aan het aantal bezoekers/steekproeven. Minus natuurlijk een paar velden met gegevens over de totalen. Het is iig een enorme besparing.

Voeg deze twee samen (en meer mogelijkheden, én minder diskruimte) dan is voor mij de keuze snel gemaakt...

[Verwijderd]

killercow > als ik jou was zou ik ook inderdaad voor de mogelijkheid van T-Mob gaan. Zoals ik ook al eerder heb aangegeven, kan je ook gewoon de belangrijkste gegevens opslaan van de gehele groep; de gemiddeldes en standaarddeviaties.
Als ik T-Mob goed begrijp logt hij per dag iedereen en brengt hij dan alle informatie terug naar de kern om vervolgens de individuele logs te verwijderen.

[killercow]

bwah,

PHP ondersteund geen decimale machten

vreemd lijkt me want zowel c++ als c ondersteunen het gewoon,
Ik heb bijvoorbeeld even de functies pow() van kcalc (wat het wel ondersteund), en die van php opgezocht.:

C++:

/* {{{ proto number pow(number base, number exponent)
   Returns base raised to the power of exponent. Returns integer result when possible */
PHP_FUNCTION(pow)
{
    zval *zbase, *zexp;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z/z/", &zbase, &zexp) == FAILURE) {
        return;
    }

    /* make sure we're dealing with numbers */
    convert_scalar_to_number(zbase TSRMLS_CC);
    convert_scalar_to_number(zexp TSRMLS_CC);

    /* if both base and exponent were longs, we'll try to get a long out */
    if (Z_TYPE_P(zbase) == IS_LONG && Z_TYPE_P(zexp) == IS_LONG && Z_LVAL_P(zexp) >= 0) {
        long l1 = 1, l2 = Z_LVAL_P(zbase), i = Z_LVAL_P(zexp);

        if (i == 0) {
            RETURN_LONG(1L);
        } else if (l2 == 0) {
            RETURN_LONG(0);
        }

        /* calculate pow(long,long) in O(log exp) operations, bail if overflow */
        while (i >= 1) {
            int overflow;
            double dval;

            if (i % 2) {
                --i;
                ZEND_SIGNED_MULTIPLY_LONG(l1,l2,l1,dval,overflow);
                if (overflow) RETURN_DOUBLE(dval * pow(l2,i));
            } else {
                i /= 2;
                ZEND_SIGNED_MULTIPLY_LONG(l2,l2,l2,dval,overflow);
                if (overflow) RETURN_DOUBLE((double)l1 * pow(dval,i));
            }
            if (i == 0) {
                RETURN_LONG(l1);
            }
        }
    }
    convert_to_double(zbase);
    convert_to_double(zexp);

    RETURN_DOUBLE( pow(Z_DVAL_P(zbase),Z_DVAL_P(zexp)) );
}

en die van Kcalc:

C++:

static CALCAMNT ExecPower(CALCAMNT left_op, CALCAMNT right_op)
{
    if (right_op == 0)
        if (left_op == 0) // 0^0 not defined
        {
            _error = true;      
            return 0L;
        }
        else
            return 1L;

    if (left_op < 0 && isoddint(1 / right_op))
        left_op = -1L * POW((-1L * left_op), right_op);
    else
        left_op = POW(left_op, right_op);

    if (errno == EDOM || errno == ERANGE)
    {
        _error = true;
        return 0L;
    }
    else
        return left_op;
}

Heeft iemand enig idee waarom PHP zo moeilijk doet?

[ Voor 3% gewijzigd door killercow op 05-11-2004 13:24 ]

[BestTested!]

Om nog even in te springen op het steekproef gebeuren zelf.
Ik neem aan dat je van plan bent een hoop statistiek op je gegevens los te laten en daaruit een aantal dingen te berekenen.

Je zou dan de grote ook kunnen afhangen van je betrouwbaarheids interval. Stel je wil een 95% betrouwbaarheidsinterval over je verwachtingswaarde. Je kan dan terugrekenen hoe groot je sample moet zijn. Bij weinig hits met een Student-T verdeling, meer dan 30 is een normaal verdeling al voldoende.
(Fouten onder voorbehoud )

Ik weet niet hoe ver je kennis statistiek rijkt, maar dan is dit 'Statistich gezien' de meest nette oplossing.

[T-MOB]

BestTested! schreef op 06 november 2004 @ 12:35:
Om nog even in te springen op het steekproef gebeuren zelf.
Ik neem aan dat je van plan bent een hoop statistiek op je gegevens los te laten en daaruit een aantal dingen te berekenen.

Je zou dan de grote ook kunnen afhangen van je betrouwbaarheids interval. Stel je wil een 95% betrouwbaarheidsinterval over je verwachtingswaarde. Je kan dan terugrekenen hoe groot je sample moet zijn. Bij weinig hits met een Student-T verdeling, meer dan 30 is een normaal verdeling al voldoende.
(Fouten onder voorbehoud )

Ik weet niet hoe ver je kennis statistiek rijkt, maar dan is dit 'Statistich gezien' de meest nette oplossing.

Ik denk dat je hier een aantal zaken vergeet / door de war haalt. Er is geen normale verdeling van welke browser iemand gebruikt... Je kunt hooguit per browser de verwachting dat iemand hem gebruikt beschouwen als een normaal verdeelde kans.
Het totaal aantal waarnemingen dat nodig is is dus voornamelijk afhankelijk van het aantal variabelen dat je wilt onderzoeken en de hoeveelheid variatie die daar in mogelijk is. Per mogelijk "antwoord" zou je moeten streven naar minimaal 5 waarnemingen. Wil je in het geval van browsers dus iets zinnigs zeggen over browsers die door ongeveer 1% van je bezoekers worden gebruikt dan zul je minimaal 500 waarnemingen moeten doen...

In het geval van een website, waar gegevens 'at virtually no cost' beschikbaar zijn zou ik echter de moeiet niet nemen om een steekproefsysteem te maken. Je kunt namelijk vrij gemakkelijk alles loggen.

[BestTested!]

Ik denk dat je hier een aantal zaken vergeet / door de war haalt. Er is geen normale verdeling van welke browser iemand gebruikt... Je kunt hooguit per browser de verwachting dat iemand hem gebruikt beschouwen als een normaal verdeelde kans.

Er is inderdaad geen normaal verdeling van welke browser iemand gebruikt. Maar wel of iemand een browser wel aldan niet gebruikt. Kan kan dan bijvoorbeeld zeggen dat 85% tot 88% van je bezoekers IE gebruiken o.i.d. Dat is beter dan gewoon de kans te berekenen met IE / totaal *100%

Het totaal aantal waarnemingen dat nodig is is dus voornamelijk afhankelijk van het aantal variabelen dat je wilt onderzoeken en de hoeveelheid variatie die daar in mogelijk is. Per mogelijk "antwoord" zou je moeten streven naar minimaal 5 waarnemingen. Wil je in het geval van browsers dus iets zinnigs zeggen over browsers die door ongeveer 1% van je bezoekers worden gebruikt dan zul je minimaal 500 waarnemingen moeten doen...

Het aantal is inderdaad afhankelijk van het aantal variabelen. Maar die 5 is, naar mijn mening, een beetje natte vinger werk. Een 'zinnige uitspraak' is dan ook maar een begrip dat afhangt van de mate van uitsluitsel van toeval.

In het geval van een website, waar gegevens 'at virtually no cost' beschikbaar zijn zou ik echter de moeiet niet nemen om een steekproefsysteem te maken. Je kunt namelijk vrij gemakkelijk alles loggen.

Omdat het hier om steekproefen gaat werk je altijd met een sample. Wil je een uitspraak doen, dan is het wel zo netjes om een betrouwbaarheidsinterval te gebruiken.
En echt zoveel moeite is het niet. Een enkele formule geeft je het antwoord al.
Voorbeeld 1
Voorbeeld 2

[Verwijderd]

Offtopic.

Ik moest laatst een dergelijk formule bedenken voor een produkt-verkopend bedrijf. Het bedrijf wou bij een produktje met een inkoopwaarde van 0,10 eurocent een winst van 500% maken (verkoop: 0,50 eurocent) en bij een produkt met een inkoopwaarde van bijvoorbeeld 120 euro een winst van 120% (verkoop: 144 euro).

De winstmarge moest echter niet statisch omlaag kruipen maar moest eerst drastich dalen nagelang de inkoop hoger werd en moest vervolgens zeer langzaam dalen.
Een grafiek met een curve was het resultaat.

Ik heb de curve verdeeld in 4 statische lijnen, waardoor er met 4 formules gewerkt kan worden.

Indien een inkoop tussen de 0 en 1,00 euro ligt, past men formule 1 toe.
Wanneer de inkoop bijvoorbeeld tussen de 100 en 120+ euro ligt, past men formule 4 toe.

formule 1 (inkoop 0-100 eurocent; voorbeeld):

code:

percentage = -300*inkoop+500;

/offtopic

Edit: Als een slimme kop zin heeft om een verzameling van vier formules, gebasseerd op een niet statisch gecurvde lijn, samen te voegen tot één formule; call me

[ Voor 11% gewijzigd door Verwijderd op 06-11-2004 13:53 ]

[killercow]

heb nu 3 dagen lopen stoeien met die stomme decimale machten, heeft iemand (een wiskunde guru) een andere vergelijkbare oplossing?

(in de hoeveelheid waarmee ik stats moet gaan opslaan gaat het zelf bij *virtualy no cost) toch om vrij grote bedragen)

Houdt er rekening mee dat de formulie niet gewoon alsnog een decimale waarde aan pow() geeft. alvast bedankt, wie weet krijg ik het nog voor elkaar om de source code's van php en kcalc met elkaar te verenigen.

[Verwijderd]

a^b = e^(b log a)
dat is dus niet de 10log maar de e-log (ook wel "ln")

dus ipv pow( $a , 0.6 ) zoiets als exp( 0.6 * log($a) )

[ Voor 14% gewijzigd door Verwijderd op 09-11-2004 18:21 ]

[T-MOB]

BestTested! schreef op 06 november 2004 @ 13:42:
[...]
Er is inderdaad geen normaal verdeling van welke browser iemand gebruikt. Maar wel of iemand een browser wel aldan niet gebruikt. Kan kan dan bijvoorbeeld zeggen dat 85% tot 88% van je bezoekers IE gebruiken o.i.d. Dat is beter dan gewoon de kans te berekenen met IE / totaal *100%

Hier haal je 2 heel verschillende dingen aan... Je eerste zin klopt.... bijna. Voor een binomiale verdeling (wel of niet browser X) geldt bij grote getalen dat een normale verdeling bij benadering te gebruiken is.
Wat je daarna zegt heeft hier niets mee te maken. Het is inderdaad beter om - als je een steekproef neemt - te vermelden hoe betrouwbaar je resultaten zijn. Als je gegevens over de gehele populatie kunt verkijgen zou ik toch gaan voor de laatste methode: gewoon IE / totaal * 100%, met 100% betrouwbaarheid .

[...]
Het aantal is inderdaad afhankelijk van het aantal variabelen. Maar die 5 is, naar mijn mening, een beetje natte vinger werk. Een 'zinnige uitspraak' is dan ook maar een begrip dat afhangt van de mate van uitsluitsel van toeval.

Die 5 is hoe dan ook gebruikelijk in de sociale wetenschap. Een kort en intuïtief antwoord is dat je met minder dan 5 resultaten lastig kunt bepalen in welke lijn van een willekeurige normale verdeling jouw resultaten zich bevinden. Je zult wel iets "harder" bewijs willen zien neem ik aan, bekijken we de bron die je zelf hebt aangehaald dan lezen we (uit voorbeeld 2):

Nu mag deze formule gebruikt worden indien n·p>=5 en n·(1-p)>=5.

Dat komt er op neer dat wil je een zaak (zeg browser) bepalen die 1% voorkomt (p=0.01) Dan zul je een minimale n (=steekproefomvang) moeten hebben van 500 (want 0.01 * 500 = 5). Kortom, je hebt altijd 5 waarnemingen in een categorie nodig om een normale verdeling te kunnen veronderstellen. Dit heeft alles te maken met aannnames over verdelingen, maar google is je vriend mbt details...

/offtopic

@ivy: de formule die je zoekt ziet er ongeveer als volgt uit:

code:

$winstmarge = $A + $B / ($inkoopsprijs * $C)

Ik zou zeggen schrijf een functietje in PHP en experimenteer wat met A, B en C totdat je de juiste benadering hebt gevonden. Als de winstmarge harder moet dalen met de prijs kun je de inkoopsprijs nog kwadrateren...

[ Voor 4% gewijzigd door T-MOB op 10-11-2004 03:30 ]