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

Написал код для визуализации на VCL (Билдер). Вот что получилось:


(если взять чуть более широкую панель, то все будет прекрасно отображаться, здесь масштаб маловат, поэтому одно налезает на другое...)

А теперь, собственно, КАК оно делалось:
1) в класс MyCluster введен еще один member под названием center, который хранит смещение от верха панели (фактически - координату Y кластера. Координата X нам не особенно нужна, есть srez). Ну, а потом, как только нашли очередной минимум:

		outCanvas->Pen->Color = clBlack;
		outCanvas->MoveTo(visLabelWidth + 30 + clusters[ii].sr, clusters[ii].center);
		outCanvas->LineTo(visLabelWidth + 30 + min, clusters[ii].center);
		outCanvas->MoveTo(visLabelWidth + 30 + clusters[jj].sr, clusters[jj].center);
		outCanvas->LineTo(visLabelWidth + 30 + min, clusters[jj].center);
		outCanvas->LineTo(visLabelWidth + 30 + min, clusters[ii].center);

		clusters[ii] += clusters[jj]; // Сливаем кластеры
		clusters[ii].sr = min; // запоминаем, когда произошло слияние
		std::for_each(clusters.begin(), clusters.end(),
			Updator(std::make_pair(jj, ii))); // Обновляем ссылки на старый кластер

		clusters[jj].disabled = true; // jj кластер убран

		// Рисуем центр "Объединенного" кластера
		outCanvas->Pen->Color = clRed;
		int px = visLabelWidth + 30 + min, py = clusters[ii].center;
		outCanvas->Ellipse(px - 2, py - 2, px + 2, py + 2);

		res.push_back(clusters[ii]);
		// Ну и так далее... 

Это отрисует "дерево". А уж на перемещение TrackBar-а вешаем:

void UpdateClusterList(int srez, std::vector<MyCluster>& vec, TMemo* memo)
{
	std::vector<MyCluster>::iterator it;
	memo->Clear();
	for(it = vec.begin(); it != vec.end(); it++)
	{
		if(it->sr >= srez)
		{
			memo->Lines->Add(it->ShowInfo());
			// Показываем нужную информацию, я заменил вывод << методом ShowInfo()
		}
	}

}

void __fastcall TForm1::TrackBar1Change(TObject *Sender)
{
	UpdateClusterList(((TTrackBar *)Sender)->Position, res, memResults);
}

Вот и все, теперь список кластеров будет содержать только те элементы, поле sr которых не меньше текущей позиции ТрэкБара, что и нужно было. Останется только рисовать эту красную линию при движении бегунка, для наглядности...



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