Алгоритм кластеризации.Data mining. Опции

[Andrewshkovskii]

Суть такова..уже неделю бьюсь с реализацией одного алгоритм, но никак не могу приудмать.. В общем, задача такая
:
Есть матрица остовного дерева


Она собой представляет матрицу смежности графа, где значения в ячейках - вес ребра между двумя вершинами, * - значит ребра для этих вершин нет.
вот так можно представить этот граф
Верщины и вес верщины
"Войновка,Инская" 2732
"Егоршино,Пермь" 4667
"Орехово,Инская" 6588
"Лянгасово,Егоршино" 7489
"Пермь,Войновка" 14946

Ребра, как и кластеры, у меня реализованны следующей структурой
:

Раскрывающийся текст

        struct Cluster
         {
           private :
            int value_;
            QVector <int> items_;
            QPoint centerPos;
            bool isPainted;
           public :
            Cluster();
            Cluster(int item1 ,int item2, int nValue);
            Cluster(int item1, int nValue);
            void setValue(int newValue);
            int value(){ return value_; }
            const QVector<int> & items() {return items_;};
            void setPainted(bool is);
            QString toString(QStringList * lst);
            void append(Cluster nClust);
            bool operator==(Cluster & o){return items_==o.items();};
          };

Раскрывающийся текст

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

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

void Model::Cluster::setValue(int newValue)
{
    value_=newValue;
}

QString Model::Cluster::toString(QStringList * lst)
  {
   QString str;
   QStringList * list = lst;
   int i=0;
   for(;i<items_.size()-1;++i)
          str.append(list->at(items_.at(i))+",");
   str.append(list->at(items_.at(i))+"");
   return str;
   }

void Model::Cluster::append(Cluster nClust)
{
    for(int i=0;i<nClust.items().size();++i)
        items_.push_back(nClust.items().at(i));
}

void Model::Cluster::setPainted(bool is)
{
    isPainted=is;
}

Model::Cluster::Cluster()
{
}

void Model::outClusters()
{
    for(int i=0;i<clusters.size();++i)
    {
        qDebug() << clusters.at(i).first << ":";
       for(int j=0;j<clusters.at(i).second.size();++j)
           qDebug() << clusters[i].second[j].value() << ":" << clusters[i].second[j].toString(&vHeaderData);
    }
}

Суть алгоритма:
Вершины – объекты минимального остовного дерева группируются в кластеры.
Выбираются два объекта, которым соответствует минимальное ребро.
. Далее эти объекты стягиваются в один кластер (класс, таксон, страту) и
процедура повторяется до тех пор, пока на n-1(n-количество верщин, n-1 - ребер) этапе группирования не будет
сформирован один кластер, объединяющий все объекты.
Вот так :
1. шаг
формируется кластер из "Войновка,Инская" со значением 2732
2.
"Егоршино,Пермь" 4667
3.
"Орехово,Инская,Войновка" 6588
4.
"Лянгасово,Егоршино,Пермь" 7489
5.
"Лянгасово,Егоршино,Пермь,Орехово,Инская,Войновка" 14946
подобрая программа лежит вот тут http://el-niko.ru/lab/1/
Все что я смог реализовать, это нахождение ребер..тоесть я пытался как-то додуматься до реализации этого алгоритма, но заходил в тупик.
Вот немного кода :

Раскрывающийся текст

        clusters.clear();// Это вектор пар QVector < QPair <int,QVector<Cluster> > >  clusters;
 //нужен для отображения срезов кластеров, т.е на значении int у нас есть вектор из кластеров , у которох их значение не привышает заданное, т.е
 //в нашем случае, при значении 4667 мы отобразим :
 //"Войновка,Инская"
 //"Егоршино,Пермь" 
 // Лянгасово
 // Орехово
        static bool *isNum = new bool;
        int rc = spanningMatrixModel->rowCount();
        int sM[rc][rc];
        QVector <Cluster> ribs;
        QVector <Cluster> items;
        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);//переводим данные из таблицы в матрицу
              if (sM[i][j]!= 0 )
                  items.push_back(Cluster(i,sM[i][j]));//записывает значения для каждой вершины
             }
        for (int i=0;i<rc;++i)
            for (int j=i+1;j<rc;++j)
                if (sM[i][j]!=0)
                    ribs.push_back(Cluster(i,j,sM[i][j]));//получаем ребра графа

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

Сообщение отредактировал Andrewshkovskii - 19.11.2009, 15:29

[Andrewshkovskii]

Решено.

Прикрепленные файлы

 clusters.zip ( 24,13 килобайт ) Кол-во скачиваний: 9

 

[ViGOur]

Блин, давно еще прочитал твою тему, но забыл спросить (работы много), смотрел ли ты в сторону метода опорных векторов (SVM) и подходят ли они тебе для твоей задачи?

Просто есть уже реализованная либа svm light, потому не нужно реализовывать все эти формулы. К счастью.

От тебя только требуется на начальном этапе самому сделать кластеры (что ты в принципе и сделал), отдать это все для обучения в SVM, который на основе них создаст модели. После чего уже прогнать все вершины через SVM для создания кластеров, на основе моделей созданных ранее.

По моим результатам SVM классифицировал примерно 30-50% не классифицированных мной данных.

p.s. правда с ним немного муторно разбираться...

Сообщение отредактировал ViGOur - 9.12.2009, 17:31

[Andrewshkovskii]

Да я бы не стал так заморачиваться, ибо это была лабораторная работа, просто преподаватель нам плохо объясняет алгоритмы, и из всего потока(70 чел) сдали эту лабу 5 человек..