Иерархическая кластеризация., Немного DataMining на С++ Опции

[Andrewshkovskii]

Вершины – объекты
минимального остовного дерева группируются в кластеры.
Выбираются два объекта, которым соответствует минимальное ребро min_jd_j,
где j=1, n-1. Далее эти объекты стягиваются в один кластер (класс, таксон, страту) и
процедура шага 2 повторяется до тех пор, пока на n-1 этапе группирования не будет
сформирован один кластер, объединяющий все объекты. STOP.



На рис. представлена последовательность группировки объектов в
кластеры для заданного на рис.1 примера минимального остовного дерева.
Порядок объединения объектов в кластеры отображён на рёбрах, которые
связывают объединяемые объекты .Таким образом, первыми
объединяются объекты X₄ и Х₅,которые в МОД связывает минимальное ребро d₄
с весом 2. Вторыми объединяются объекты X₂и X₃, связанные ребром d₂
с весом 3 , и так далее, пока на шестом этапе группирования ранее связанные объекты (X₁,X₂,X₃,X₄,X₅,X₆)
не будут объединены с объектом X₇ ребром с весом 7.

И так , перейдем к описанию алгоритма кластеризации на примере :
Ребра МОД :

(ИЗ--ВЕС-->В);
1. Е--2328-->Ом
2. В--2732-->И
3. Е--4667-->П
4. Л--5161-->Ом
5. О--6588-->И
7. П--14946-->В
И образуемые кластера :
(Шаг. №кластера)
1. 1.Е + ОМ значение кластера 2328
2. 1.
2. В + И 2732
3. 1. кластер поглощает вершину П, новый кластер Е+Ом+П 4667
2.
4. 1. поглощает вершину Л, новый кластер Е+Ом+П+Л 5161
2.
5. 1.
2. поглощает вершину О, новый кластер В + И + О 6588
6. 1 поглошает 2 и получается Л+Е+О+П+В+И+Ом 14946

Надеюсь понятно..вот как я понял этот алгоритм вербально :
Цикл от i=0 до n-1
Цикл от j=0 до n-1
Если множество вершин ребра/кластера_i при пересечении с множеством вершин ребра/кластера_j образует не пустое множество
если значение ребра/кластера_j >=значению ребра/кластера_i
ТОГДА образуется кластер соединением множества вершин ребра/кластера_j и множества вершин ребра/кластера_i
ИНАЧЕ наше ребро и есть кластер.

Правильно ли я понял алгоритм?
Вот так его можно описать в коде..

//ribs это объект класса реализующего :
//  QSet<int> - множество вершин ребра/кластера, возвращается путем вызова метода items() 
// свойство value, которое возвращает вес ребра/кластера
//считать, что операции &, &= - пересечение
// += - слияние. 
            for(int i=0;i<ribs.size();++i)
                for(int j=0;j<ribs.size();++j)
                    if (ribs.at(j)!=ribs.at(i))//не сравниваем сами с собой..
                        if ( (!(ribs.at(i)->items() & ribs.at(j)->items()).empty()))
                        //если пересечение не образует пустое множество
                            if (ribs.at(j)->value() >= ribs.at(i)->value())
                            //если значение j ребра/кластера меньше i
                           {
                                ribs.at(j)->items()+=ribs.at(i)->items();//соединяем j и i  ребро/кластера
                           }
                            else
                            {
                                  // ребро и есть кластер
                            }

[volvo]

Шо-то мне не очень понятно, что там твой согруппник сделал... Нет, ну сначала все идет как надо, а потом начинается нечто, не поддающееся объяснению. Смотри, чего я тут наваял (за основу взята твоя же программа для нахождения МОД):

#include <iostream>
#include <vector>
#include <limits>

bool exists(std::vector<int> vec, int value)
{
    std::vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);
    return (it != vec.end()) ? true : false;
}

int main()
{
    const int matrixSize = 8; // 17; // 6;
    const std::string titles[matrixSize] =
    {
        "Lantasovo", "Egorshino", "Orehovo", "Perm",
        "Voynovka", "Inskaya", "Omsk", "Ekaterinburg"
    };

    int dm[matrixSize][matrixSize] =
    {
        {    0,  177,  171, 642,  981,   15, 403, 1315 },
        {  177,    0,  348, 465,  804,  192, 226, 1138 },
        {  171,  348,    0, 813, 1152,  156, 574, 1486 },
        {  642,  465,  813,   0,  339,  657, 239,  673 },
        {  981,  804, 1152, 339,    0,  996, 578,  334 },
        {   15,  192,  156, 657,  996,    0, 418, 1330 },
        {  403,  226,  574, 239,  578,  418,   0,  912 },
        { 1315, 1138, 1486, 673,  334, 1330, 912,    0 }
    }; // матрица смежности графа
    
    int sm[matrixSize][matrixSize];//матрица МОД
    int used[matrixSize];//использованные вершины
    int count=0;
    int min;
    
    for (int i=0; i< matrixSize; ++i)
    {
        used[i]=0;
        for(int j=0;j< matrixSize;++j) sm[i][j]=0;
    }
    
    used[0]=1;
    int idx;
    do
    {
        min=std::numeric_limits<int>::max();
        for(int i=0;i<matrixSize;++i)
        {
            if (used[i]!=0)
            {
                for(int j=0;j<matrixSize;++j)
                    if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j]==0))
                    {
                        min=dm[j][i]; idx = j;
                    }
            }
        }
        
        for(int i=0;i < matrixSize;++i)
            for(int j=0;j<matrixSize;++j)
                if( (dm[j][i]== min) && (used[j]==0) &&(used[i]==1))
                {
                    used[j] =1;
                    sm[j][i]= sm[i][j] = min;
                    count++;
                    i=matrixSize;
                    break;
                }
    }
    while(count < matrixSize-1);

    // Выводим матрицу МОД ...
    for(int i = 0; i < matrixSize; i++)
    {
        for(int j = 0; j < matrixSize; j++)
        {
            std::cout << sm[i][j] << " ";
        }
        std::cout << std::endl;
    }

    std::vector< std::pair<std::string, int> > tree;
    std::vector<int> used_vertex;
    for(int cycle = 0; cycle < matrixSize; cycle++)
    {
        std::pair<int, int> curr;

        min = (cycle) ? std::numeric_limits<int>::max() : 0;
        for(int i = 0; i < matrixSize; i++)
        {
            for(int j = i + 1; j < matrixSize; j++)
            {
                if(sm[i][j] > 0 && sm[i][j] < min && cycle &&
                   (exists(used_vertex, i) || exists(used_vertex, j)))
                {
                    min = sm[i][j]; curr.first = i; curr.second = j;
                }
            }
        }
        
        //
        if(!exists(used_vertex, curr.first))
        {
            used_vertex.push_back(curr.first);
            tree.push_back(std::pair<std::string, int>(titles[curr.first], min));
            sm[curr.first][curr.second] = sm[curr.second][curr.first] = 0;
        }
        else
            if(!exists(used_vertex, curr.second))
            {
                used_vertex.push_back(curr.second);
                tree.push_back(std::pair<std::string, int>(titles[curr.second], min));
                sm[curr.first][curr.second] = sm[curr.second][curr.first] = 0;
            }
    }
    std::vector< std::pair<std::string, int> >::iterator it;
    for(it = tree.begin(); it != tree.end(); it++)
    {
        std::cout << it->first << " : " << it->second << std::endl;
    }

    return 0;
}

(С++ так С++, по-полной)

Данные - оттуда же, из таблицы по ссылке, при "Количество записей = 8". Вот вывод программы (исключая МОД, оно строится правильно):

Lantasovo : 0
Inskaya : 15
Orehovo : 156
Egorshino : 177
Omsk : 226
Perm : 239
Voynovka : 339
Ekaterinburg : 334

Чувствуешь? А у него каким-то необъяснимым образом сначала группируются Войновка с Екатеринбургом, и только потом этот кластер объединяется с остальными. Это откуда такое взялось?