Gauss eliminatie met PHP

Datum:30 juni 2007

Inmiddels is wel redelijk goed bekend welke factoren een rol spelen bij de positionering van zoekresultaten in Google. Eén van die factoren is bijvoorbeeld of het keyword wat jij hebt ingevoerd in de titel van een pagina staat. Als dit wel zo is, zal de pagina horen scoren dan wanneer het niet zo is, ceteris paribus. Nu zijn er waarschijnlijk honderden factoren te bedenken die een rol spelen op de Google SERP-positionering, maar met zeg eens 10 van de grootste factoren zou je de SERP-positie ook redelijk moeten kunnen verklaren. Het is uiteraard de vraag hoe je tot een weging van de factoren komt. In een zeer gesimpliceerde versie van ons vraagstuk, hebben we bijvoorbeeld deze vergelijking:

X * factor1 + Y * factor2 + Z * factor3 = SERP_Score

Stelsel van lineaire vergelijkingen

Nu is het zo dat we de waarde van de belangrijkste van deze factoren kunnen weten. Als factor2 bijvoorbeeld gelijk is aan de PageRank van het domein, kunnen we het getal hiertoe invullen. We vervangen dus factor2 door bijvoorbeeld 2 en doen dat ook voor de andere factoren. Zo komen we tot bijvoorbeeld deze vergelijking:

X * 0 + Y * 2 + Z * 1 = 4

Aangezien we uiteraard voor meerdere zoekresultaten de SERP-score en de factoren van verschillende sites kunnen bepalen, komen we bijvoorbeeld tot deze drie vergelijkingen:

1) X * 0 + Y * 2 + Z * 1 = 4
2) X * 1 + Y * 1 + Z * 2 = 6
3) X * 2 + Y * 1 + Z * 1 = 7

Elk van deze drie vergelijkingen geeft informatie over de samenhang tussen dezelfde X, dezelfde Y en dezelfde Z. Omdat deze vergelijkingen als het ware bij elkaar horen en omdat elke vergelijking lineair is (in de zin dat er geen kwadraten in zitten), noemen we deze drie vergelijkingen samen een stelsel van lineaire vergelijkingen. Aangezien we even veel vergelijkingen hebben als variabelen (namelijk: beiden 3), is dit stelsel op te lossen indien er een oplossing is.

Gauss-eliminatie

De manier waarmee we het stelsel gaan oplossen heet de Gauss-eliminatie en is dan ook bedacht door Carl Friedrich Gauss. Het is een methode die elementaire rijoperaties uitvoert op de drie vergelijkingen zoals wij die hebben gegeven. De drie operaties zijn:

twee vergelijkingen verwisselen
Dit is in feite geen handeling. Het komt er op neer dat als ik zeg dat Arie en Bert bakker zijn waar zijn, ik net zo goed had kunnen zeggen dat Bert en Arie bakker zijn. Tja, ontken dat maar eens...
een vergelijking met een scalair c (ongelijk aan 0) vermenigvuldigen
Als ik zeg dat er 24 flesjes bier in een krat gaan, kan ik net zo goed zeggen dat er 48 flesjes in twee kratten gaan. Bijna even simpel als dat ding hierboven.
bij een vergelijking een veelvoud van een andere vergelijking optellen of aftrekken
Deze is íets lastiger, maar niet veel. Stel ik zeg twee dingen: 1) Er gaan 24 flesjes bier in een krat en 2) er gaan 6 flesjes bier in mijn jaszak. Ik kan dan uiteraard zeggen dat er 30 flesjes bier in een krat én mijn jaszak gaan. Immers, er gaan er 24 in een krat en 6 in een jaszak, dus als ik er 30 moet vervoeren moet ik zowel mijn krat als mijn jaszak gebruiken. Als ik echter twee jaszakken en 1 krat heb, kan ik 2 * 6 + 24 = 36 flesjes meenemen.

Laten we als voorbeeld eens proberen bovenstaande drie vergelijkingen op te lossen a.d.h.v. bovengenoemde drie operaties. We beginnen met wat we al hadden:

1) X * 0 + Y * 2 + Z * 1 = 4
2) X * 1 + Y * 1 + Z * 2 = 6
3) X * 2 + Y * 1 + Z * 1 = 7

Als we nu 2 keer de tweede vergelijking van de derde aftrekken, krijgen we dit:

1) X * 0 + Y *  2 + Z *  1 = 4
2) X * 1 + Y *  1 + Z *  2 = 6
3) X * 0 + Y * -1 + Z * -3 = -5

Vervolgens tellen we 0,5 keer de eerste vergelijking bij de derde op om dit te krijgen:

1) X * 0 + Y * 2 + Z *  1   =  4
2) X * 1 + Y * 1 + Z *  2   =  6
3) X * 0 + Y * 0 + Z * -2,5 = -3

We zien nu dat Z * -2,5 = -3, oftewel Z = 6/5. Die Z-waarde vullen we in in vergelijking 1 om te komen tot Y * 2 + 6/5 * 1 = 4, oftewel Y = 7/5. Vervolgens zien we door vergelijking 1 dat X = 11/5.

Opmerking:

Uiteraard gaat dit proces niet zo willekeurig als het nu lijkt. Het is echter niet doel met deze tutorial je helemaal bij te brengen hoe Gauss eliminatie werkt. Als je straks snapt wat je hiermee kan, is mijn doel bereikt.

Werken met matrices

Er is een andere manier om dit stelsel van vergelijkingen als hierboven op te schrijven, namelijk door gebruik te maken van matrices. Het gaat te ver om hier al te diep op in te gaan, maar in het kader van de volledigheid zal ik het stelsel vergelijkingen hierboven in matrix-vorm neerzetten:

    	    +- -+
	    | X |
            | Y |
            | Z |
            +- -+
		   
+-     -+   +- -+
| 0 2 1 |   | 4 |
| 1 1 2 |   | 6 |
| 2 1 1 |   | 7 |
+-     -+   +- -+

Gauss-eliminatie met PHP

Op PHPMath.com vond ik een kleine PHP-class voor Gauss-eliminatie. Er zaten nog wat zaken in waardoor hij niet werkte op PHP 4, maar dat heb ik gecorrigeerd. Hieronder plaats ik de code met een klein beetje commentaar, om nogmaals aan te geven hoe Gauss-eliminatie werkt.

<?php
class GaussianElimination {

    function solve($parameters, $uitkomst) {

        $epsilon = 1e-10;

        // Aantal rijen
        $N  = count($uitkomst);

        // Eliminatie
        for ($p = 0; $p < $N; $p++) {

            // Vind grootste waarde in de kolom
            $max = $p;
            for ($i = $p+1; $i < $N; $i++)
                if (abs($parameters[$i][$p]) > abs($parameters[$max][$p]))
                    $max = $i;
            $temp = $parameters[$p]; $parameters[$p] = $parameters[$max]; $parameters[$max] = $temp;
            $t    = $uitkomst[$p]; $uitkomst[$p] = $uitkomst[$max]; $uitkomst[$max] = $t;

            // Check of de matrix wel kan uitkomen of niet
            if (abs($parameters[$p][$p]) <= $epsilon) die("Matrix is singular or nearly singular");

            // Pivot rijtje gevonden
            for ($i = $p+1; $i < $N; $i++) {
                $parameterslpha = $parameters[$i][$p] / $parameters[$p][$p];
                $uitkomst[$i] -= $parameterslpha * $uitkomst[$p];
                for ($j = $p; $j < $N; $j++)
                    $parameters[$i][$j] -= $parameterslpha * $parameters[$p][$j];
            }
        }

        // Maak de oplossingsvector leeg
        $x = array_fill(0, $N-1, 0);

        // Vervangen
        for ($i = $N - 1; $i >= 0; $i--) {
            $sum = 0.0;
            for ($j = $i + 1; $j < $N; $j++)
                $sum += $parameters[$i][$j] * $x[$j];
            $x[$i] = ($uitkomst[$i] - $sum) / $parameters[$i][$i];
        }

        return $x;

    }

}

// Voorbeeldcode
$variabelen =     array(    array(0, 2, 1),
                           array(1, 1, 2),
                           array(2, 1, 1));

$output = array(4, 6, 9);

$g = new GaussianElimination;

$x = $g->solve($variabelen, $output);

for ($i=0; $i < count($x); $i++) {

    echo $x[$i]."<br />";

}
?>

Aanpassingen/opmerkingen

De concrete situatie waar we over spraken, ging over het regresseren van de SERP posities gebaseerd op een aantal variabelen. Dit zal nooit volkomen uitkomen. Allereerst kan een SERP positie van #1 niet als een 1 gezien worden, maar als beste schatting van de werkelijke waarde. De werkelijke uitkomst van de vergelijking kan ook 69 zijn, terwijl de werkelijke waarde van #2 in de SERP's bijvoorbeeld 71 is, nr# 79 enz. Ook is het zo dat we regresseren op slechts een deel van variabelen die van invloed zijn. Als laatste punt zou ik willen noemen dat er misschien geen lineair verband tussen de SERP positie en de PageRank, maar bijvoorbeeld wel tussen de SERP positie en de PageRank in het kwadraat. Dit gaat echter te ver voor dit artikel.

Netters.nl

Navigatie

Recente bloginzendingen

Actuele vacatures

Gebruikerslogin

Zoeken

Nu online

Actieve forum onderwerpen

Enquête

Wie is nieuw