Hierarhiline klasterdamine

Hierarhiline klasterdamine on väga lihtne meetod, mida ei kasutata Wiki järgi. Tundub, et O(n^2) ei ole kerge saavutada selliselt. Saadav dendrogram on küll ihaldatav, aga see ei ole kuidagi balanced search tree moodi. Plus pool on see, et mõõtmelisus ei ole takistuseks.

Bottom-up O(n^3) meetod näeb selline välja.

Otsetee järgmise koodijupi juurde, mis arvutab puu isomorfismi link.


using System;
using System.Collections.Generic;
using System.Linq;

namespace Simple_clustering
{
    public class Simple_clustering
    {
        public Simple_clustering(List<DNode> nodes)
        {
            clusters = nodes.Count;
            for (int i = 0; i < nodes.Count; i++)
            {
                nodes[i].ID = i;
                tovisit_clusters.Add(i, i);
                d.Add(i, nodes[i]);
                maxid++;
            }
        }
        public Dictionary<int, DNode> d = new Dictionary<int, DNode>();
        Dictionary<int, int> tovisit_clusters = new Dictionary<int, int>();
        int clusters = 0;
        int maxid = 0;

        double[] Sum(int id1, int id2)
        {
            double[] arr = new double[d[id1].centroid.Count()];
            for (int i = 0; i < d[id1].centroid.Length; i++)
            {
                arr[i] = (d[id1].centroid[i] + d[id2].centroid[i]) / 2;
            }
            return arr;
        }
        
        public void Cluster()
        {
            while (d.Count > 2)
            {
                int tovisit = tovisit_clusters.Count;
                for (int i = 0; i < tovisit; i++)
                {
                    int id = tovisit_clusters.ElementAt(i).Value;
                    if (!d.ContainsKey(id))
                        continue;
                    DNode d1 = d[id];
                    DNode d2 = null;
                    double mindist = double.MaxValue;
                    int minID = -1;
                    double temp  = 0;
                    for (int j = 0; j < d.Count; j++)
                    {
                        d2 = d.ElementAt(j).Value;
                        if (d1.ID != d2.ID)
                        {
                            if ((temp =Distance(d1, d2)) < mindist)
                            {
                                minID = d2.ID;
                                mindist = temp;
                            }
                        }
                    }
                    d2 = d[minID];
                    DNode newnode = new DNode();
                    newnode.ID = maxid++;
                    newnode.centroid = Sum(d1.ID, d2.ID);
                    newnode.successors.Add(d1);
                    newnode.successors.Add(d2);
                    d.Remove(d1.ID);
                    d.Remove(d2.ID);
                    d.Add(newnode.ID, newnode);
                }
                tovisit_clusters.Clear();
                for (int i = 0; i < d.Count; i++)
                {
                    tovisit_clusters.Add(d.ElementAt(i).Value.ID, d.ElementAt(i).Value.ID);
                }
            }
        }
        double Distance(DNode v1, DNode v2)
        {
            double sum = 0;
            for (int i = 0; i < v1.centroid.Length; i++)
            {
                sum += Math.Pow(v1.centroid[i] - v2.centroid[i],2);
            }
            return Math.Sqrt(sum);
        }
    }
    public class DNode
    {
        public List<DNode> successors = new List<DNode>();
        public int ID = -1;
        public double[] centroid;
    }
}


Antud koodis on vastus d-s peale pikka töötlemist.

Kuidas ei kasutata HC-d jääb tegelikult arusaamatuks, ilmselt siis mingil puhtal kujul HC-d ei kasutata.
Kiiruselt parem HC variant kui eelmine on top-down HC, kus k-means jagab esialgu andmed kaheks. Saadud klastrid jagab k-Means uuesti kaheks jne. Saadud kahendpuu aitab leida progressiivselt lähedasemaid lähendeid.
Kuidas sellist algoritmi liigitada? See on statistiline, samas hierarhiline, k-NN omadusi pole enam, centroide kasutab. Hübriid.

Järelikult on tegemist nii teoreetiliselt kui praktiliselt huvitava puuga. Otsustasin ka siis teoreetilis-müstilise analüüsi teha nendele puudele, mis paratamatult kuuli kokku jooksutas.

Oletame, et on kaks või rohkem HC puud. Igale puule arvutatakse sertifikaat, nagu isomorfsete puude leidmise algoritmis, mis kasutab “sertifikaate”. Sertifikaadi mõte on, et kui cert(tree1) = cert(tree2), siis puud on isomorfsed. Sellise erinevusega, et sertifikaadi leidmise algoritmis(bottom-up) hoitakse sertifikaadid alles kõigi alampuude juures. Edasi leitakse kõigi HC puude vahel pikim sertifikaat, mis on neil kõigil ühine. Siit ka kokkujooks.

1)Kas seda on võimalik teha?
Tundub jah.
2) Millega see võrdne oleks?
Ma ei tea, tundub tuttav. Suurima isomorfse klastriga dendrogramis? Pole aimugi.
3)Kas HC haavatavus järjekorra suhtes mõjutaks tulemust?
Ma arvan küll.
4)Miks seda otsida?
Sest see on muster ja invariantne. Lisaks tahan leida eigendendrogrami, kuhu kõik sinised puud tulevad..

UPDATE:
Lisan veel koodi.

Graafi(puu) isomorfismide leidmine on n log n kiiruse kandis keskmiselt ja igasuguse strukruuri uurimiseks kasutatav. Calc cert funktsioon on veidralt Tree klassi küljes, aga see kood on välja tiritud, sorry! Et kaks puud oleks isomorfsed, siis peavad nende “sertifikaadid samad olema”. Lisaks võib seda algoritmi kasutada Tree Similarity arvutamiseks. Selleks tuleb pikim ühine alampuu leida, mis on samuti kiire(sorteerimine põhimõtteliselt). Lisan veel, et selles algoritmis need dictionarid hoiavad juba kõiki alampuid, neid ei pea eraldi leidma.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Hierarchical
{

    public class Tree
    {
        public int data = 0;
        public int level = 0;
        public List<Tree> successors = new List<Tree>();
        public Tree predecessor;

        public void AttachSubtree(Tree tree)
        {
            tree.level = this.level + 1;
            tree.predecessor = this;
            this.successors.Add(tree);
        }
        public void RemoveSubtree(Tree tree)
        {
            successors.Remove(tree);
        }
        public string CalcCertificate(Tree tree)
        {
            Queue<Tree> q = new Queue<Tree>();
            Dictionary<int, List<Tree>> dictionary = new Dictionary<int, List<Tree>>();//levels
            Dictionary<Tree, List<string>> certificates = new Dictionary<Tree, List<string>>();
            int max_level = 0;
            q.Enqueue(tree);
            while (q.Count > 0)
            {
                Tree t = q.Dequeue();
                certificates.Add(t, new List<string>());
                certificates[t].Add("01");
                if (dictionary.ContainsKey(t.level))
                    dictionary[t.level].Add(t);
                else
                {
                    if (max_level < t.level)
                        max_level = t.level;
                    dictionary.Add(t.level, new List<Tree>());
                    dictionary[t.level].Add(t);
                }
                for (int i = 0; i < t.successors.Count; i++)
                {
                    q.Enqueue(t.successors[i]);
                }
            }

            while (max_level != 0)
            {
                for (int i = 0; i < dictionary[max_level - 1].Count(); i++)
                {
                    Tree t = dictionary[max_level - 1][i];
                    if (certificates[t].Count == 1 && certificates[t][0] == "01")
                    {
                        certificates[t].Clear();
                    }
                    for (int j = 0; j < t.successors.Count(); j++)
                    {
                        certificates[t].AddRange(certificates[t.successors[j]]);
                    }
                    certificates[t].Sort();
                    string new_cert = "0";
                    for (int j = 0; j < certificates[t].Count(); j++)
                    {
                        new_cert += certificates[t][j];
                    }
                    new_cert += "1";
                    certificates[t].Clear();
                    certificates[t].Add(new_cert);
                }
                
                max_level--;
            }
            return certificates[tree][0];
        }

    }
}

marvin_comic.png

Advertisements