[PHP]Rand index bereken

[4Real]

Ik ben op het moment bezig met een cluster analyse en wil zien wat het verschil is bij het toepassen van verschillende similarity algoritmes t.o.v. de cluster resultaten. Om te zien wat de verschillen zijn heb ik zeven natuurlijke clusters gedefinieerd (bv, 10 instanties van voertuigen, 10 instanties van dierren etc). Dus ik weet wat de correcte clusters zijn nu wil ik alleen kijken of ik met een script kan berekenen of de clusters overeenkomen met wat ik voor ogen heb. Om dit te berekenen maak ik gebruik van de Rand Index, zodat ik een cijfer heb om te te kunnen vergelijken. Mede gebruik ik deze methode om de true positive (TP), false positive (FP), true negative (TN) & false negative (FN) te berekenen. De method Rand Index geeft echter een andere naam aan deze namen, dus hier de vertaalslag:

code:

TP = A
TN = B
FN = C
FP = D

Om te testen of mijn function overeenkomst met de werkelijkheid heb ik eerste gekeken naar een voorbeeld en deze precies overgenomen om te kijken of ik dezelfde resultaten krijg. Het voorbeeld is hier te vinden: http://www.otlet-institut...s.html#toc-Subsection-4.1

In dit voorbeeld maak ik gebruik van een class lijst en een cluster lijst. De class lijst bevat de clusters zoals ze horen te zijn en de cluster lijst bevat de clusters als die uit een cluster algoritme kan komen. Als eerste de class lijst:

1. o1 o2 o3
2. o4 o5 o6
3. o7 o8 o9

En als clusterlijst gebruik ik:

1. o1 o2
2. o3 o4 o5 o6
3. o7 o8
4. o9

Dan nu de code die ik gebruik, als eerste de RandIndex class. Deze heeft één statische functie de de classlijst en clusterlijst krijgt en gaat dan alles berekenen.

PHP:

class RandIndex
{
    public static function Calculate($classList, $clusterList)
    {
        // first get one dimensional list with all object
        $objectList = array();
        foreach ($clusterList as $cluster)
        {
            foreach ($cluster as $object)
            {
                $objectList[] = $object;
            }
        }
        
        // define true and false positive and negative list (will contain object pairs)
        $tpList = array();
        $tnList = array();
        $fnList = array();
        $fpList = array();
        
        //
        for ( (int) $i = 0; $i < count($objectList); $i++ )
        {
            for ( (int) $j = $i + 1; $j < count($objectList); $j++ )
            {
                // get two objects that create a pair
                $k1 = $objectList[$i];
                $k2 = $objectList[$j];
                
                // find the class index to which the objects belong
                $classIndexK1 = self::__FindIndex($classList, $k1);
                $classIndexK2 = self::__FindIndex($classList, $k2);
                
                // find the cluster index to which the objects belong
                $clusterIndexK1 = self::__FindIndex($clusterList, $k1);
                $clusterIndexK2 = self::__FindIndex($clusterList, $k2);
                
                //echo "<hr>";
                //echo $k1 . "," . $k2 . "<br>";
                //echo "Class: " . $classIndexK1 . "," . $classIndexK2 . "<br>";
                //echo "Cluster: " . $clusterIndexK1 . "," . $clusterIndexK2 . "<br>";
                //var_dump(( $classIndexK1 != $classIndexK2 && $clusterIndexK1 == $clusterIndexK2 && $classIndexK1 != $clusterIndexK1 ));
                    
                if ( $classIndexK1 == $classIndexK2 && $clusterIndexK1 == $clusterIndexK2 )
                {
                    // a, pairs are in the same set in X and in the same set in Y
                    $tpList[] = sprintf("(%s,%s)", $k1, $k2);
                }
                else if ( $classIndexK1 != $classIndexK2 && $clusterIndexK1 != $clusterIndexK2 )
                {
                    // b, pairs are in different sets in X and in different sets in Y
                    $tnList[] = sprintf("(%s,%s)", $k1, $k2);
                }
                else if ( $classIndexK1 == $classIndexK2 && $clusterIndexK1 != $clusterIndexK2 )
                {
                    // c, pairs are in the same set in X and in different sets in Y
                    $fnList[] = sprintf("(%s,%s)", $k1, $k2);
                }
                else if ( $classIndexK1 != $classIndexK2 && $clusterIndexK1 == $clusterIndexK2 )
                {
                    // d, are in different sets in X and in the same set in Y
                    $fpList[] = sprintf("(%s,%s)", $k1, $k2);
                }
            }
        }
        
        // calculate the rand index: formula is: (a+b)/(a+b+c+d)
        $index = (count($tpList) + count($tnList)) / (count($tpList) + count($tnList) + count($fnList) + count($fpList));
        
        // return everything, TP, FP, FN, TN and RandIndex
        return array(
            'tp' => count($tpList), // a
            'tn' => count($tnList), // b
            'fn' => count($fnList), // c
            'fp' => count($fpList), // d
            'index' => $index,
        );
    }

    private static function __FindIndex($haystack, $needle)
    {
        for ( (int) $i = 0; $i < count($haystack); $i++ )
        {
            if ( in_array($needle, $haystack[$i]) === true )
            {
                return $i;
            }
        }
        
        // not found
        throw new Exception("Object kan niet gevonden worden in de haystack (waar haystack, classList of clusterList kan zijn).");
    }
}

En dan de class en cluster lijst.

PHP:

$classList = array(
    array('o1', 'o2', 'o3'),
    array('o4', 'o5', 'o6'),
    array('o7', 'o8', 'o9'),
);

$clusterList = array(
    array('o1', 'o2'),
    array('o3', 'o4', 'o5', 'o6'),
    array('o7', 'o8'),
    array('o9'),
);

Om de output te tonen gebruik ik de volgende drie regels:

PHP:

$res = RandIndex::Calculate($classList, $clusterList);
echo "<pre>";
print_r($res);

Als ik het voorbeeld van de pagina één-op-één overneem dan krijg ik de het volgende resultaat: 0.8056, dus 0.81. Precies zelfde als in het voorbeeld.

Vanaf dit punt ga ik er mee spelen om te kijken of mijn verwachtingspatroon overeenkomt met wat ik uit de functie krijg. Als eerste een simpele:

PHP:

$clusterList = $classList;

De output van de clustering is identiek aan dat van wat ik vooraf wil hebben, dus de output zou 1 moeten zijn en dit zie ik ook terug.

Dan het volgende:

PHP:

$clusterList = array(
    array('o1', 'o2', 'o3', 'o4'),
    array('o5', 'o6'),
    array('o7', 'o8', 'o9'),
);

Verwacht: TP: 7; TN: 24; FN: 2; FP; 3. En dit krijg ik ook precies uit het programma, maar wanneer ik nu o5 achter o4 plaats dan komt er een verschil in verwacht en uitkomst. Dus:

PHP:

$clusterList = array(
    array('o1', 'o2', 'o3', 'o4', 'o5'),
    array('o6'),
    array('o7', 'o8', 'o9'),
);

Verwacht: TP: 6; TN: 21; FN: 2: FP; 3, want:

code:

TP+FP = (5 ncr 2) + (1 ncr 2) + (3 ncr 2) = 10 + 0 + 3 = 13. 
Waar TP = (3 ncr 2) + (1 ncr 2) + (3 ncr 2) = 3 + 0 + 3 = 6. 
Dus FP = (TP+FP) - TP = 13 - 6 = 7.

En het programma geeft mij het volgende resultaat: TP: 7; TN: 21; FN: 2: FP; 6. Één TP is verkeerd berekend dit had een FP moeten zijn. Als je de echo's aanzet in de functie dan worden de resultaten wel getoond en waar het misgaat is het paartje (o4,o5). Deze de class index is #1 en cluster index is 0 voorbeide. Dus de conditie voor een true positive (the number of pairs of elements in S that are in the same set in X and in the same set in Y) gaat wel op, maar eigenlijk hebben we het over andere clusters.

Ik zie even niet wat ik moet gaan aanpassen. Ik kan de volgende conditie nog toevoegen aan de TP if-statement:

PHP:

$classIndexK1 == $clusterIndexK1

Dan haalt hij de TP dit teveel wordt berekent er wel uit, maar de FP statement zal hem nog keihard negeren.

Tevens zit ik kan ik de extra FP niet vinden. De TP zijn namelijk de volgende paartjes:

code:

{(o1,o2),(o1,o3),(o2,o3),(o7,o8),(o7,o9),(o8,o9)}.

Als ik dit bij de FP doe dan kom ik op de volgende paartjes:

code:

{(o1,o4),(o1,o5),(o2,o4),(o2,o5),(o3,o4),(o5,o6)}

Ik mis er eentje, maar ik weet niet welke wat ik zoek er nog één waarde de volgende conditie opgegaat: decision assigns two dissimilar objects to the same cluster.

Disclaimer:
_{Ik weet dat er nog een kleine bug inzit als het gaat om dezelfde index nummering. Toevallig is het in deze situatie goed, maar hoe weet de functie dat cluster #1 gelijk is aan class #1? Dat probleem heb ik herkend en heb een idee om dat op te lossen. Voor nu geef ik goede input aan het programma dus hoef ik mij daar nu geen zorgen om te maken.}

[pedorus]

Volgens mij bereken je handmatig TP fout met 6. Dat lijkt mij gewoon 3(o1-o3 goed)+3(o7-o9 goed)+1(o4-o5 goed)=7?

[Pinobigbird]

Dus de conditie voor een true positive (the number of pairs of elements in S that are in the same set in X and in the same set in Y) gaat wel op, maar eigenlijk hebben we het over andere clusters.

Je definieert een TP als een set samen in een cluster zit, zowel bij X als Y. Je opmerking dat het over andere clusters gaat is niet relevant.

Als je het anders definieert, waarbij ze dus wel in hetzelfde cluster moeten zitten, dan dien je inderdaad de conditie toe toe voegen bij TP:

PHP:

$classIndexK1 == $clusterIndexK1

Daarbij:

Als ik dit bij de FP doe dan kom ik op de volgende paartjes:

code:

{(o1,o4),(o1,o5),(o2,o4),(o2,o5),(o3,o4),(o5,o6)}

Hier mis je de set (o4,o5) als je je andere definitie aanhoudt waarbij dit geen TP maar FP zou zijn. Je dient dan dus ook je definitie en daarmee je conditie voor FP aan te passen. Het simpelste zou zijn om de conditie in de laatste else geheel weg te laten ;-)

Disclaimer:
Ik weet dat er nog een kleine bug inzit als het gaat om dezelfde index nummering. Toevallig is het in deze situatie goed, maar hoe weet de functie dat cluster #1 gelijk is aan class #1? Dat probleem heb ik herkend en heb een idee om dat op te lossen. Voor nu geef ik goede input aan het programma dus hoef ik mij daar nu geen zorgen om te maken.

Je hoeft hier dus in principe geen rekening mee te houden volgens de originele definitie; er is dus geen aanpassing nodig.

[4Real]

Pinobigbird schreef op vrijdag 07 maart 2014 @ 21:09:
[...]

Je definieert een TP als een set samen in een cluster zit, zowel bij X als Y. Je opmerking dat het over andere clusters gaat is niet relevant.

Als je het anders definieert, waarbij ze dus wel in hetzelfde cluster moeten zitten, dan dien je inderdaad de conditie toe toe voegen bij TP:

PHP:

$classIndexK1 == $clusterIndexK1

Daarbij:

[...]

Hier mis je de set (o4,o5) als je je andere definitie aanhoudt waarbij dit geen TP maar FP zou zijn. Je dient dan dus ook je definitie en daarmee je conditie voor FP aan te passen. Het simpelste zou zijn om de conditie in de laatste else geheel weg te laten ;-)



[...]

Je hoeft hier dus in principe geen rekening mee te houden volgens de originele definitie; er is dus geen aanpassing nodig.

Na het even te laten bezinken klopt het inderdaard set(o4,o5) voldoen aan de conditie van TP. Want ze zitten in de zelfde class en in tevens in de zelfde cluster, echter weet ik dat ze eigenlijk bij cluster2 horen. Kan ik hieruit concluderen dat de RandIndex methode sommige TP verkeerd kan interpreteren?

Eerst had ik in de disclaimer nog een opmerking opgenomen over het ordenen van clusters t.o.v. de classes en dit hoeft inderdaad niet aangezien hij per set kijkt wat de definitie is van het paartje is. Is de methodiek dan niet te verbeteren wanneer ik de classes en clusters tegen erlkaar aan zet en dan ga vergelijken met de extra if-statement condities op te nemen? Class / cluster paar maken kan gedaan worden door te kijken wat de overlap is t.o.v. tussen de twee. Het paar met de grootste overlap is de best aannemelijke class/cluster paar.

[pedorus]

Als je de berekening zou veranderen, dan heb je in ieder geval geen rand index meer. Normaal gesproken maakt de volgorde van de clusters niet uit, en dat is maar goed ook, omdat ze meestal niet dezelfde betekenis hebben in een vergelijking tussen clusteringen. Alleen als de clusters wel een betekenis hebben (zoals geschatte leeftijdscategorieën ofzo), dan zou het zinnig zijn om de berekening anders te doen.

[Pinobigbird]

De vraag is dan, wat is de Rand-index van de volgende situatie:

Ideal Clustering	Computed Clustering
{o1,o2,o3} ∈ t1	c1 = {o4,o5,o6}
{o4,o5,o6} ∈ t2	c2 = {o1,o2,o3}

Is dat 0 of 1? Lijkt me dat dat 1 is en je dus geen aanpassing in je algoritme hoeft te doen.

[4Real]

pedorus schreef op zaterdag 08 maart 2014 @ 17:10:
Als je de berekening zou veranderen, dan heb je in ieder geval geen rand index meer. Normaal gesproken maakt de volgorde van de clusters niet uit, en dat is maar goed ook, omdat ze meestal niet dezelfde betekenis hebben in een vergelijking tussen clusteringen. Alleen als de clusters wel een betekenis hebben (zoals geschatte leeftijdscategorieën ofzo), dan zou het zinnig zijn om de berekening anders te doen.

In mijn onderzoek ben ik bezig met het clusteren van woorden. De woorden die een cluster hebben zullen ook een gedeelde context hebben dus op die manier hebben ze wel een betekenis, echter zit ik nog te denken of het daadwerkelijk zo erg is of dat de meting opzich zelf voldoende is. Op het moment gebruik ik namelijk de Rand Index om zes verschillende similarity algoritmes met elkaar te vergelijken.