Иерархическая кластеризация., Немного 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
                            {
                                  // ребро и есть кластер
                            }

[Andrewshkovskii]

Что-то ты нагромоздил кода, хотя просто я использую QtStl в своем проекте, там попроще с векторами и множествами, да и для представления ребер/кластеров я реализовал отдельный класс( просто выкладывать его сюда мало смысла - всеравно без Qt не получиться скомпилировать)
А твой ответ не совсем ясен( честно скажу, в код не вникал).
У него на Срезе 15 обременяются вершины Инская и лянгасово, т.к между ними мин. ребро
на срезе 156 к этому ребру/кластеру добовляется вершина Орехово, т.к она связана с одной из вершин в предыдущем кластере(а именно - Инская) следующим мин. ребром с весом в 156..По тому же принципу и Егоршино на срезе 176 добавляется в тот же кластер, далее Омск на срезе 226, Пермь на срезе 239 (т.к все они имею связи через ребра МОД). На 334 срезе связывается Войновка и Екатеринбург, т.к они имею следующее мин. ребро из не использованных, и ни одна из этим вершин не имеется в предыдущих кластерах, поэтому они стают особняком на этом срезе, а после чего у них соединение на Перьми появляется и они объединяются в кластер..

А твои результаты я не понял. Может я плохо объясняю? Пожалуйста, спроси, что именно не понятно - я постараюсь объяснить более человеческим языком. Если надо, скину свои исходники.

Приведу всетаки полный код, может что яснее странет..
Сначала класс кластер/ребро :
интерфейс :

#ifndef CLUSTER_H
#define CLUSTER_H
#include <QSet>// Qt'вые множества
#include <QString>

class Cluster
{
private :
 int value_;
 QSet<int> items_;
public :
 Cluster();
 Cluster(Cluster & other);//конструктор копироавния
 Cluster(int item1 ,int item2, int nValue);//для ребра конструктор
 Cluster(int item1, int nValue);//для одной вершины
 const int& value()const {return value_; }//возвращает вес кластера/ребра
 void setValue(const int &newValue){value_=newValue;};//устанавливает вес
 QSet<int> &items();//возврашает вершины в кластере/ребре
 void append(Cluster * nClust);//"поглотить" другое ребро/кластер
 QString toString(QStringList * lst);//перевести номера вершин в их строковой эквивалент
};

#endif // CLUSTER_H

Реализация ... :

#include "cluster.h"

Cluster::Cluster()
{
}

Cluster::Cluster(Cluster &other)
{
    items_=other.items();
    value_=other.value();
    centerPos_=other.centerPos();
    isPainted_=other.isPainted();
}

Cluster::Cluster(int item1 , int item2, int nValue)
 {
   value_=nValue;
   items_.insert(item1);
   items_.insert(item2);
 }

Cluster::Cluster(int item1 , int nValue)
 {
   value_=nValue;
   items_.insert(item1);
 }

void Cluster::append(Cluster * nClust)
{
   QSetIterator <int> it (nClust->items());
    while (it.hasNext())//Java-style итератор, очень удобно. Пока есть элементы в контейнере
        items_ << it.next();//забираем их из другого кластера.
}

QSet<int>& Cluster::items()
{
            return items_;
}

QString Cluster::toString(QStringList * lst)
  {
   QString str;
   QStringList * list = lst;
   QSetIterator <int> it (items_);
   str.append("|");
   while(it.hasNext())
       str.append(list->at(it.next())+" ");
   str.append("|");
   return str;
   }

А вот алгоритм кластеризации :

void Model::calculateNewClustersModel(QStandardItemModel * spanningMatrixModel)
{
       clusters.clear();//очищаем вектор срезов. Представляет из себя QVector <QMap < int, QVector <Cluster* > >
        static bool *isNum = new bool;
        int rc = spanningMatrixModel->rowCount();//размер МОД
        int sM[rc][rc];//цисленный массив
        QVector <Cluster *> ribs;//вектор ребер..
        for (int i=0;i<rc;++i)
            for (int j=0;j<rc;++j)
              sM[i][j]=spanningMatrixModel->item(i,j)->text().toInt(isNum,10);
              //перегоняет модель таблицы в численный массив
        for (int i=0;i<rc;++i)
            for (int j=i+1;j<rc;++j)
                if (sM[i][j]!=0)
               ribs.push_back(new Cluster(i,j,sM[i][j]));//собираем ребра
        qSort(ribs.begin(),ribs.end(),cmp);//сортируем их по возрастанию веса.

            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();//поглатить ребро i
                                qDebug() << "appended" <<ribs.at(j)->toString(&vHeaderData) << ribs.at(j)->value();
                                //Вывод информации о том, какой кластер поглатился и кем
                           }
                            else
                            {
                                  qDebug() <<"single" <<ribs.at(i)->toString(&vHeaderData) << ribs.at(i)->value();
                                  //Вывод информации о том, какое ребро является уже кластером                            
}
    for(int i=0;i<ribs.size();++i)
        qDebug() << "2 " <<ribs.at(i)->toString(&vHeaderData) << ribs.at(i)->value() <<
                " SIZE " << ribs.at(i)->items().size();
}

И вот вывод моего кода для "Вагонооборот" при 19 строках :

"|Курган Инская |" 152 SIZE 2
"|Войновка Бердяуш |" 416 SIZE 2
"|Алтайская Орехово |" 428 SIZE 2
"|Пермь Нижний Новгород |" 461 SIZE 2
"|Екатеринбург Челябинск |" 576 SIZE 2
"|Войновка Бердяуш Богданович |" 593 SIZE 3
"|Смычка Агрыз |" 799 SIZE 2
"|Алтайская Орехово Каменск-Уральский |" 1264 SIZE 3
"|Пермь Екатеринбург Нижний Новгород Челябинск |" 1305 SIZE 4
"|Алтайская Орехово Смычка Агрыз Каменск-Уральский |" 1453 SIZE 5
"|Курган Инская Юдино |" 2296 SIZE 3
"|Егоршино Пермь Екатеринбург Нижний Новгород Челябинск |" 2325 SIZE 5
"|Егоршино Пермь Омск Екатеринбург Нижний Новгород Челябинск |" 2328 SIZE 6
"|Курган Войновка Инская Бердяуш Юдино Богданович |" 2732 SIZE 6
"|Курган Алтайская Орехово Войновка Инская Бердяуш Смычка Агрыз Юдино Богданович Каменск-Уральский |" 2876 SIZE 11
"|Лянгасово Егоршино Пермь Омск Екатеринбург Нижний Новгород Челябинск |" 5161 SIZE 7
"|Курган Алтайская Орехово Войновка Инская Бердяуш Смычка Чусовская Агрыз Юдино Богданович Каменск-Уральский |" 5953 SIZE 12
"|Лянгасово Егоршино Орехово Пермь Войновка Инская Омск Екатеринбург Бердяуш Смычка Чусовская Агрыз Нижний Новгород Юдино Челябинск Богданович Каменск-Уральский Курган Алтайская |" 7984 SIZE 19

Что это значит?а вот что : SIZE - размер сформированного кластера, чилос перед SIZE - срез, на котором кластер сформирован, ну и соответственно его состав.
Мой вопрос в том, что можно это как-либо оптимизировать?Допустим, что бы не проходил вершины, которые уже посчитал как еденичный кластер и т.д. Просто для параметра "Количество сортировочных путей" у меня считает не правильно кластера т.к там одинаковые ребра по весу..
Да к тому же , эта оптимизация мне нужная для того, что бы нормально отрисовывать дендрограмму ( как на сайте снизу), т.к я буду использовать "события" Qt(сигналы/слоты) что, кого поглотило и отрисовывать их по-порядку, а не после нахождения...

Сообщение отредактировано: volvo - 30.11.2009 13:28