Implementacja niestandardowego algorytmu aglomeracyjnego od podstaw

Question

Wiem o aglomeracyjnych algorytmach grupowania, sposobie, w jaki rozpoczyna się każdy punkt danych jako indywidualne skupienie, a następnie łączy punkty, tworząc klastry.

Teraz mam przestrzeń wymiarową i kilka punktów danych, które mają wartości w każdym z tych wymiarów. Chcę klastra dwóch punktów/klastry oparte na zasadach biznesowych, takich jak:

• Klastra dwa punkty C1 i C2, jeśli odległość między klastrami w całym wymiarze 1 jest < T1, a odległość w poprzek wymiaru 2 < T2 .. i odległość w całym wymiarze n < Tn.
• Jeśli reguła całej wymiarze 1 jest spełniony i reguła całej wymiarze 2 jest spełniony, wówczas klastra je nie dbając o innych wymiarach ...

.... i podobne zasady niestandardowe.

Ponadto mam własny sposób definiowania i mierzenia odległości między dowolnymi dwoma klastrami w dowolnym wymiarze. Wymiar może zawierać tylko ciągi znaków i chcę zdefiniować własną metrykę odległości. W innym wymiarze może zawierać nazwy lokalizacji, a odległość między dwoma punktami wzdłuż tego wymiaru to odległość geograficzna między nazwaną lokalizacją i tak dalej w przypadku innych wymiarów.

Czy istnieje framework/oprogramowanie, które pozwala wdrażać ten sposób definiowania niestandardowych metryk odległości, a następnie wdrażać aglomeracyjne tworzenie klastrów? Oczywiście klastrowanie aglomeracyjne zatrzymuje się, gdy reguły biznesowe nie są spełnione w dowolnym momencie, a na końcu tworzą się klastry w przestrzeni n-wymiarowej.

Dzięki Abhishek S

Answer 1

można zrobić go z Weka.

Użytkownik musiałby wprowadzić Distance Function i przekazać go do Hierarchical Clusterer przy użyciu metody setDistanceFunction(DistanceFunction distanceFunction).

innych dostępnych clusterers w Weka to: Pajęczyna, EM FarthestFirst, FilteredClusterer, MakeDensityBasedClusterer, RandomizableClusterer, RandomizableDensityBasedClusterer, RandomizableSingleClustererEnhancer, SimpleKMeans, SingleClustererEnhancer.

Przykładem funkcji odległości, z klasy NormalizableDistance:

/** Index in ranges for MIN. */ 
    public static final int R_MIN = 0; 

    /** Index in ranges for MAX. */ 

    public static final int R_MAX = 1; 

    /** Index in ranges for WIDTH. */ 
    public static final int R_WIDTH = 2; 

    /** the instances used internally. */ 
    protected Instances m_Data = null; 

    /** True if normalization is turned off (default false).*/ 
    protected boolean m_DontNormalize = false; 

    /** The range of the attributes. */ 
    protected double[][] m_Ranges; 

    /** The range of attributes to use for calculating the distance. */ 
    protected Range m_AttributeIndices = new Range("first-last"); 

    /** The boolean flags, whether an attribute will be used or not. */ 
    protected boolean[] m_ActiveIndices; 

    /** Whether all the necessary preparations have been done. */ 
    protected boolean m_Validated; 


public double distance(Instance first, Instance second, double cutOffValue, PerformanceStats stats) { 
    double distance = 0; 
    int firstI, secondI; 
    int firstNumValues = first.numValues(); 
    int secondNumValues = second.numValues(); 
    int numAttributes = m_Data.numAttributes(); 
    int classIndex = m_Data.classIndex(); 

    validate(); 

    for (int p1 = 0, p2 = 0; p1 < firstNumValues || p2 < secondNumValues;) { 
     if (p1 >= firstNumValues) 
     firstI = numAttributes; 
     else 
     firstI = first.index(p1); 

     if (p2 >= secondNumValues) 
     secondI = numAttributes; 
     else 
     secondI = second.index(p2); 

     if (firstI == classIndex) { 
     p1++; 
     continue; 
     } 
     if ((firstI < numAttributes) && !m_ActiveIndices[firstI]) { 
     p1++; 
     continue; 
     } 

     if (secondI == classIndex) { 
     p2++; 
     continue; 
     } 
     if ((secondI < numAttributes) && !m_ActiveIndices[secondI]) { 
     p2++; 
     continue; 
     } 

     double diff; 

     if (firstI == secondI) { 
     diff = difference(firstI, 
        first.valueSparse(p1), 
        second.valueSparse(p2)); 
     p1++; 
     p2++; 
     } 
     else if (firstI > secondI) { 
     diff = difference(secondI, 
        0, second.valueSparse(p2)); 
     p2++; 
     } 
     else { 
     diff = difference(firstI, 
        first.valueSparse(p1), 0); 
     p1++; 
     } 
     if (stats != null) 
     stats.incrCoordCount(); 

     distance = updateDistance(distance, diff); 
     if (distance > cutOffValue) 
     return Double.POSITIVE_INFINITY; 
    } 

    return distance; 
    } 

pokazuje, że można traktować oddzielnie różne wymiary (które nazywane są atrybutami w Weka). Możesz więc zdefiniować inną odległość dla każdego wymiaru/atrybutu.

Informacje o regułach biznesowych, aby uniknąć grupowania razem niektórych wystąpień. Myślę, że możesz utworzyć funkcję odległości, która zwraca Double.positiveInfinity, gdy reguły biznesowe nie są spełnione.

Answer 2

ELKI to inna opcja. Ma znacznie więcej algorytmów grupowania niż Weka (co jest bardzo przydatne przy klasyfikacji). Mają nawet samouczek Wiki, wyjaśniający, jak zaimplementować niestandardowe funkcje odległości (które następnie powinieneś być w stanie używać w hierarchicznym grupowaniu): distance function tutorial.

Zauważ, że „reguł biznesowych” nie jest bardzo częstym sposobem na określenie funkcji odległości ...