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

[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

[Andrewshkovskii]

Привет!:)спасибо за огромную помощь..но я пошел немного другим путем.
Я так же ввел для каждого кластера его центр.
Но вот соотношения значения ползунка и самого кластера на дендрограмме я пока не могу придумать как соотнести.
Да и потом, почему-то криво рисует.Точнее теряет центр нек. кластеров.
Вот как я сделал:

QPointF Model::drawClamp(const QPointF &from, const QPointF &to)//рисуем скобу
{
  QPointF ptr;
//!! space - шаг, тестовый.
  qreal x1,y1,x2,y2;
  if (from.x() > to.x())
  {
      x2 = from.x()+3;
      y2 = from.y();
      x1 = to.x()+3;
      y1 = to.y();
  }
   else
  {
        x1 = from.x()+3;
        y1 = from.y();
        x2 = to.x()+3;
        y2 = to.y();
   }
  visualResultModel->addLine(x1,y1,x2+space,y1);
  ptr.setY((visualResultModel->addLine(x2+space,y1,x2+space,y2))->line().length()/2);//середина вертик. линии ?
  visualResultModel->addLine(x2+space,y2,x2,y2);
  ptr.setX(x2+space);
  qDebug() << ptr;
  visualResultModel->addEllipse(ptr.x(),ptr.y(),2,2,QPen(),*(new QBrush(Qt::black,Qt::SolidPattern)));
  space+=5;
  return ptr;
}

и в коде вот так :

            
clusters[ii] += clusters[jj];
clusters[ii].setPos(drawClamp(clusters[ii].pos(),clusters[jj].pos()));

setPos, соответственно, устанавливает центр.
и для 5 значений получается такая белиберда:

[volvo]

Блин, у меня оказывается на скрине не было видно самой дендрограммы. Поправил... Теперь видно... Твой код завтра посмотрю, может чего и придумается...

[Andrewshkovskii]

Ну я проект скину перед сном, если надо, посмотришь прям с возможностью компилирования.а пока сижу сам думаю..вроде чет наклевывается.
И я пока не настраивал ползунок, и не вывожу текущие кластера, сначала решил разобраться с дендрограммой...
Нашел, вроде ошибку математическую с вычислением центра линии.

 visualResultModel->addLine(x1,y1,x2+space,y1);
  visualResultModel->addLine(x2+space,y1,x2+space,y2);

  visualResultModel->addLine(x2+space,y2,x2,y2);
  ptr.setX(x2+space);
  ptr.setY((y1+y2)/2);//y координата центра вертикальной линии.

Чертит, но не понятно:)
Есть проблема, когда линия одного кластера накладывается на другой..предвижу, что придется искать пересечения новой линии кластера с другой, и отодвигать кого-то...Ох уж это..
Проект вот тут
http://webfile.ru/4122061
Ну кластера считаются в методе Model::calculateNewClustresModel, там же и рисуются (я выше рассказывал где ).


Сообщение отредактировано: Andrewshkovskii - 30.11.2009 2:23

[Гость]

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

[-Volvo-]

надо как-то зафиксировать количество тиков

Что значит "как нибудь"? Устанавливаешь QSlider-у minimum в первый найденный алгоритмом минимум, maximum - в последний найденный минимум, тогда (maximum - minimum + 1) даст тебе количество тиков. Ширина контрола тебе тоже известна. Делишь одно на другое - получаешь pixels per tick.

[Andrewshkovskii]

Там надо минимум в 0 устанавливать, таково требование гуев от преподователя.
А если делать так, как ты говоришь, что количество тикой это max-min +1, т.е max+1 (если минимум в 0) то при некоторых варианта (когда максимум 20000 или 49000) то будет ужас, а не слайдер...

[volvo]

В таком случае у тебя нет другого варианта, кроме как считать, что Слайдер - это проценты, minimum = 0, maximum = 100, ширину слайдера ты знаешь, вычислить, какая ширина в пикселях у одного тика - не составит труда...

Но (опять это самое но, в самый неподходящий момент, да?) Допустим, у тебя последний срез - 40000, тогда 1 тик - это 400 единиц. И что будешь делать, если у тебя за один-единственный щелчок по СпинЭдиту пролетит десяток разветвлений дендрограммы? Ну, тут уж выбирать, либо делать так, как я написал чуть выше, в 26 посте, и до посинения щелкать на СпинЭдит, пока доберешься до очередной развилки графика, либо считать процентами и пропускать некоторые из развилок...

Есть еще один вариант:

но он мне не совсем нравится (Показать/Скрыть)

Сделать все-таки НЕ проценты в Слайдере, а при щелчке на кнопку вверх/вниз у СпинЭдита "пробегать" вперед/назад до следующего/предыдущего разветвления (имея список всех кластеров - это сделать элементарно)

[Andrewshkovskii]

Была такая мысль у меня о фиксации каждого кластера , и потом, при щелчке по спин. эдиту проходить только определенные значения(то есть диапазон значений у спинЭдита будет диапазон срезов дендрограммы, и без конкретного шага, а при щелчке вверх - к след. разветвления, вниз - к предыдущему..) Я вот выбираю меж двух зол..

[Andrewshkovskii]

Перечитал методичку..в общем-то можно и вовсе без слайдера сделать. Т.е. можно остановиться на варианте с спинЭдитом. Только вот как учитывать значения, ведь они без определенного шага идут, в разнобой.
т.е это либо писать алгоритм "перешагивания" , либо наследоваться от слайдера и переопределять метод инкрименции/декрименции значений.

[Andrewshkovskii]

В общем вот что вышло у меня. осталась одна проблема : расстояния, на которых строятся след. кластера, получаются не "настоящими".
Т.е. расстояния "скоб" должны быть связаны с значением кластера, а не фиксированной координатой. Сейчас получается так, что при переход к одному кластеру нормаль идет, а на следующем может линия отброситься назад, хотя кластер посчитан правильно, а все из-за фиксированного значения space и немного не правильного алгоритма построения...А вот как связать - пока не придумал.. Есть мысли какие-нибудь по этому поводу? :/



Алгоритм...

QPointF Model::drawClamp(const QPointF &from, const QPointF &to, long int cut)
{
  QPointF ptr;
  qreal x1,y1,x2,y2;
  if (from.x() > to.x())
  {
      x2 = from.x()+3;
      y2 = from.y();
      x1 = to.x()+3;
      y1 = to.y();
  }
   else
  {
        x1 = from.x()+3;
        y1 = from.y();
        x2 = to.x()+3;
        y2 = to.y();
   }
  visualResultModel->addLine(x1,y1,x2+space,y1); // нарисовать горз. линию
  visualResultModel->addLine(x2+space,y1,x2+space,y2); // вертикальную
  visualResultModel->addLine(x2+space,y2,x2,y2); // гориз. линию
  ptr.setX(x2+space); // запоминаем позицию центра
  ptr.setY((y1+y2)/2);
  visualResultModel->addEllipse(ptr.x(),ptr.y()-2,3,3,QPen(Qt::red),
    *(new QBrush(Qt::red,Qt::SolidPattern))); // рисуем кружочек...
  space+=3.6; // инкремент расстояния
  /* вот тут то и косяк, если образуется новый кластер (из 2х вершни),
  то он будет левее предыдущих кластеров.. */
  return ptr;
}

[Andrewshkovskii]

С этой проблема ещё связано с отрисовкой кластеров для последней закладки (где 2 среза всего 1 и 2)..Т.е. надо как-то в зависимости от длины среза рассчитывать расстояние и рисовать, что бы правдиво было..

Сообщение отредактировано: Andrewshkovskii - 1.12.2009 18:06

[Andrewshkovskii]

		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);

Вот тут, ты отрисовываешь кластер?Я просто не понимаю, зачем MoveTo, да и у линии почему-то всего 2 координаты..

[Andrewshkovskii]

procedure LineTo(X, Y: Integer); Проводит линию текущим пером из текущей точки в (X,Y).
procedure MoveTo(X, Y: Integer); Перемещает текущее положение пера (свойство PenPos) в точку (X,Y).

Понятно..

[volvo]

А расскажи мне (ты свою модель лучше знаешь, чем мне копаться) - почему у тебя visualResultModel->width() изменяется? Ладно бы, изменялась только при переключениях закладок, так нет же:

QPointF Model::drawClamp(const QPointF &from, const QPointF &to, long int cut)
{
  QPointF ptr;
  qreal x1,y1,x2,y2;
  if (from.x() > to.x())
  {
      x2 = from.x()+3;
      y2 = from.y();
      x1 = to.x()+3;
      y1 = to.y();
  }
   else
  {
        x1 = from.x()+3;
        y1 = from.y();
        x2 = to.x()+3;
        y2 = to.y();
   }

   // Для пробы взял 374, как ширину поля, в которое все будет выводиться, начиная с 50-ти
   int curr_x = (374.0 / visualResultModel->width() * cut) + 50;
   qDebug() << "width = " << visualResultModel->width();

  visualResultModel->addLine(x1,y1,curr_x,y1);
  visualResultModel->addLine(x2,y2,curr_x,y2);
  visualResultModel->addLine(curr_x,y1,curr_x, y2);

  ptr.setX(curr_x);
  ptr.setY((y1+y2)/2);
  visualResultModel->addEllipse(ptr.x(),ptr.y()-2,3,3,QPen(Qt::red),*(new QBrush(Qt::red,Qt::SolidPattern)));
  return ptr;
}

// также был добавлен вывод
            values.push_back(qMakePair(min,clusters[ii].pos().x()));
            qDebug() << "min = " << min << ", pos = " << clusters[ii].pos().x();

Результат:

width =  114.25 
min =  15 , pos =  99 
width =  114.25 
min =  16 , pos =  102 
width =  114.25 
min =  17 , pos =  105 
width =  114.25 
min =  51 , pos =  216 
width =  220 
min =  82 , pos =  189 
width =  220 
min =  88 , pos =  199 
width =  220 
min =  89 , pos =  201 
width =  220 
min =  92 , pos =  206 
width =  220 
min =  92 , pos =  206 
width =  220 
min =  94 , pos =  209 
width =  220 
min =  114 , pos =  243 
width =  247 
min =  122 , pos =  234 
width =  247 
min =  134 , pos =  252 
width =  256 
min =  156 , pos =  277 
width =  281 
min =  222 , pos =  345 
width =  349 
min =  288 , pos =  358 
width =  362 
min =  331 , pos =  391 
width =  395 
min =  424 , pos =  451 

с какого перепуга ширина изменилась с width = 114.25 на width = 220 где-то между срезом-94 и срезом-114? Почему ты сразу (как только получаешь максимальный срез) не устанавливаешь ширину поля отрисовки - скажем, через sceneRect - в максимальное значение, или чуть больше, чтоб оставалось место справа? Список ребер есть, достаточно при их инициализации (там, где addEdge) найти максимум, и максимально возможный срез тебе уже известен.

Вот если это сделать, то можно будет использовать тот код, который я привел (возможно - с небольшими недоработками).

[Andrewshkovskii]

Изменяется она потому, что она при первичной отрисовки списка вершин устанавливается в зависимости от длины отображаемого текста, т.е она изначально, при создании не ресайзитсья нормально( правда я даже не понял как её нормально ресайзить, постоянно появлялись скроллбары..в общем я испытывал муки, пол недели потратил на то, что бы разобраться с соотношением координат view и сцены..так и толком не понял).
А далее, когда начинает рисоваться дендрограмма то она автоматически ресайзится под "длины("вроде) новых айтемов..вот так я это поведение понимаю.
Ты предлагаешь устанавливать ширину поля для отрисовки в преобразованную каким-то образом размера макс. ребра?

Сообщение отредактировано: Andrewshkovskii - 1.12.2009 22:52

[volvo]

Угу... Именно:

        // Это у тебя было ...
        clustersCuts.insert(prevCut,(QVector<MyCluster>::fromStdVector(clusters))); // создаем 0 срез

        int biggest_edge = numeric_limits<int>::min();
        for(int i = 0; i < matrixSize; i++)
            for(int j = 0; j < matrixSize; j++)
                if(sm[i][j] > 0) {
                    clusters[i].addEdge(make_pair(j, sm[i][j]));//создаем ребра
                    biggest_edge = (sm[i][j] > biggest_edge) ? sm[i][j] : biggest_edge; // Добавляем
                }

        // А вот теперь попробуем поправить ширину поля вывода...
        QRectF sR = visualResultModel->sceneRect();
        sR.setWidth(biggest_edge);
        visualResultModel->setSceneRect(sR);

        // Ну, дальше все остается без изменений...

А в методе drawClamp:

QPointF Model::drawClamp(const QPointF &from, const QPointF &to, long int cut)
{
  QPointF ptr;
  qreal x1,y1,x2,y2;
  if (from.x() > to.x())
  {
      x2 = from.x()+3;
      y2 = from.y();
      x1 = to.x()+3;
      y1 = to.y();
  }
   else
  {
        x1 = from.x()+3;
        y1 = from.y();
        x2 = to.x()+3;
        y2 = to.y();
   }

   // Оставляем 120 единиц для отрисовки названий городов.
   // Можно там, где собственно выводятся названия запоминать максимальную ширину,
   // можно здесь - примерно...
   int starting = 120;

   int curr_x = ((visualResultModel->width() - starting - 40) / visualResultModel->width() * cut) + starting;
  visualResultModel->addLine(x1,y1,curr_x,y1);
  visualResultModel->addLine(x2,y2,curr_x,y2);
  visualResultModel->addLine(curr_x,y1,curr_x, y2);

  ptr.setX(curr_x);
  ptr.setY((y1+y2)/2);
  visualResultModel->addEllipse(ptr.x(),ptr.y()-2,3,3,QPen(Qt::red),*(new QBrush(Qt::red,Qt::SolidPattern)));
  return ptr;
}

Вот чего получается:


Сколько не щелкал "вперед/назад" - ни разу не было сбоя, куда говоришь, туда и перескакивает, к следующему кластеру - только вперед, к предыдущему - только назад.

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

[Andrewshkovskii]

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

Добавлено через 13 мин.
Ну..я не знаю, какая у тебя версия qt, но когда я расширяю сцену, то у меня при больших значениях я вообще практически ничего не вижу..вот так вот :

Значит, надо брать какой-то процент, либо делить на сотые части значение biggest_edge..

Добавлено через 8 мин.
Ох..с вот с последней закладкой вообще цирк )

Исправил путем умножения cut и biggest_edge на 150 при условии, что они меньше 10..

Добавлено через 15 мин.
нашел значения, при которых "уплывает" дендрограмма

7984
14946
24266
28933
2080
1080
920
873
607

буд думать как из резать, калечить, убивать..

[volvo]

Ох..с вот с последней закладкой вообще цирк

Ну, это вообще не проблема...

Делаем в drawClamp() вот так:

   int starting = 120;
   // int curr_x = ((visualResultModel->width() - starting - 40) / visualResultModel->width() * cut) + starting;
   int curr_x = ((visualResultModel->width() - starting - 40) / (qreal)biggest_edge * cut) + starting;


// Model::calculateNewClustersModel тоже чуть-чуть по другому
        // А вот теперь попробуем изменить ширину поля вывода... Прописываем ЖЕСТКО: 400
        QRectF sR = visualResultModel->sceneRect();
        sR.setWidth(400);
        visualResultModel->setSceneRect(sR);

, а описание biggest_edge переносим в класс Model, а не локально в этом методе. Тогда все закладки отображаются как положено. Я просто последнюю вообще не видел, она скрытная какая-то

я не знаю, какая у тебя версия qt

У меня 4.5.2, через QTCreator. Странно, значит я что-то не замечаю. Надо будет еще посмотреть потом, сейчас я уже мало что соображаю...

[Andrewshkovskii]

хм..действительно..
Над не забыть только biggest_edge обнулять при переходе на другую МОД(Закладку, или меняя кол-во записей)
В принципе осталось пофиксить 2 пункта :
1. Из-за того, что в последней закладке много одинаковых значений срезов текстовое отображение кластеров тупит
(я в принципе придумал решение в виде того, что при каждом новом срезе к его значению будет плюсоваться i, которая в свою очередь изменяется на 1 в основном цикле кластеризации)
2. ну и из-за этого же криво отображаются кластеры для той же закладки.
происходит это вот так :

Ну есть мысль, что если изменять значение среза как-то по другому, для этой закладки, то удастся избавиться от этого.

Ну и небольшой шрих, что бы при уменьшении количества вершин, они заполняли сцену вертикально-равномерно, а не только с левого верхнего угла ..