Перейти к содержимому
Compvision.ru
mrgloom

kmeans и MNIST dataset

Recommended Posts

image.png

image.png

хотел попробовать k-means для MNIST dataset, попробовал пример из opencv kmeans.cpp, не очень понятно почему иногда кол-во выдаваемых кластеров меньше заявленных 5, которые установлены пользователем, вообщем непонятно что будет если с кол-вом кластеров не угадаешь? тем более что на прикрепленных картинках видно, что один кластер разбивается на 2, каким это параметром задается?(т.е. разбитие кучи на несколько?)

и не понятно как подавать на вход MNIST, в случае точек я так понимаю подаются всего лишь их координаты (x,y), а когда мы имеем дело с изображениями надо взять бинаризовать и развернуть попиксельно в вектор? допустим получим N кластеров(N=10), как потом к каждому кластеру привязать цифру?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

1. kmeans очень критичен к правильности задания количества кластеров, если число кластеров задано не правильно, получаем то что Вы привели.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

kmeans очень критичен к правильности задания количества кластеров, если число кластеров задано не правильно, получаем то что Вы привели.

а как он теоретически должен работать в таких случаях?

т.е. если кол-во кластеров будет больше чем реальное, он уменьшит кол-во кластеров? или просто разобьет цельные кластеры на подкластеры? или это зависит от параметров?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Кластеров в любом случае будет ровно столько, сколько задано, только разбиение будет кривое.

Вот демка "для поиграть": http://www.paused21.net/off/kmeans/bin/

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

ну на второй картинке видно что кластеров не 5, а 4, ну хотя это странно.

так же не очень понятно как они потом визуализируют

mnist_large.jpg

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

хотя опять же не очень понятно, тогда получится разность по метрике всего лишь скаляр,а нам надо координаты (x,y).

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

да и может есть такие уже готовые "визуализаторы"?

ну даже хотя бы не чтобы картинки выводило, а просто точки в 2D, но можно было бы посмотреть характеристики точки.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

не могу прочитать из бинарного файла, заголовок нормально читает, а потом где уже данные идут всё нули выдает.

int reverseInt (int i) 

{

    unsigned char c1, c2, c3, c4;


    c1 = i & 255;

    c2 = (i >> 8) & 255;

    c3 = (i >> 16) & 255;

    c4 = (i >> 24) & 255;


    return ((int)c1 << 24) + ((int)c2 << 16) + ((int)c3 << 8) + c4;

}

void read_mnist(/*string full_path*/)

{

	ifstream file ("C:\MNIST\t10k-images-idx3-ubyte.gz");

	if (file.is_open())

	{

		int magic_number=0;

		int number_of_images=0;

		int n_rows=0;

		int n_cols=0;

		file.read((char*)&magic_number,sizeof(magic_number));

		magic_number= reverseInt(magic_number);

		file.read((char*)&number_of_images,sizeof(number_of_images));

		number_of_images= reverseInt(number_of_images);

		file.read((char*)&n_rows,sizeof(n_rows));

		n_rows= reverseInt(n_rows);

		file.read((char*)&n_cols,sizeof(n_cols));

		n_cols= reverseInt(n_cols);

		for(int i=0;i<10000/*number_of_images*/;++i)

		{

			for(int r=0;r<28/*n_rows*/;++r)

			{

				for(int c=0;c<28/*n_cols*/;++c)

				{

					unsigned char temp=0;  

					file.read((char*)&temp,sizeof(temp));//непонятно постоянно выдает нули

				}

			}

		}

	}

}

TEST SET IMAGE FILE (t10k-images-idx3-ubyte):

[offset] [type] [value] [description]

0000 32 bit integer 0x00000803(2051) magic number

0004 32 bit integer 10000 number of images

0008 32 bit integer 28 number of rows

0012 32 bit integer 28 number of columns

0016 unsigned byte ?? pixel

0017 unsigned byte ?? pixel

........

xxxx unsigned byte ?? pixel

Pixels are organized row-wise. Pixel values are 0 to 255. 0 means background (white), 255 means foreground (black).

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

что то я не понял для чего knearest нужны ответы? или это не тоже самое, что kmeans?

http://opencv.itseez.com/modules/ml/doc/k_nearest_neighbors.html

http://www.aishack.in/2010/10/k-nearest-neighbors-in-opencv/

тут кстати k-nearest

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

kmeans - это алгоритм кластеризации. Точки группируются по кучкам.

k nearest neighbours - это алгоритм поиска k точек, ближайших к заданной.

Используется для задач классификации.

1) Задаем запрос (ставим точку, класс которой хотим узнать)

2) Находим k её ближайших соседей (класс каждого из соседей известен).

3) Считаем соседей какого класса среди этих k штук больше, тот класс и присваиваем нашей новой точке.

Выложил свои лекции по машинному обучению, там это есть. http://www.compvision.ru/forum/index.php?showtopic=864

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Считаем соседей какого класса среди этих k штук больше, тот класс и присваиваем нашей новой точке

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

опять же тогда получается, что можно сначала кластеризовать, а потом применить knearest.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

K-means - это обучение без учителя, то есть он знает сколько кластеров и где, но не знает что это такое (как называется каждый класс).

K-ближайших соседей знает какой класс где расположен (так как это обучение с учителем).

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

ну так можно тупо проставить им номера ,а потом при необходимости уже дать им название.

п.с. интересно есть ли задачи, где не знают ни названия кластеров ни их кол-ва.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

post-701-0-60850500-1336051660_thumb.png

хмм забавно попробовал, получил подозрительные центры кластеров.

выборка была 10к,в качестве вектора признаков подавал тупо пиксели, попробовал поиграть с параметрами вроде все тоже самое.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

попробовал для разного кол-ва элементов в выборке и результат как бы не меняется хоть 100 хоть 10к

вот что выдает для всего 2,3 и т.д. элементов, а начиная с 8 все идет одно и то же.

т.е. такое ощущение, что некоторые кластеры как то не разделяются и получается нечто среднее между ними.

post-701-0-17094700-1336053331_thumb.png

post-701-0-04070700-1336053392_thumb.png

post-701-0-20192400-1336053443_thumb.png

post-701-0-03413900-1336053490_thumb.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Тут проблема с метрикой. Комп же не знает как измерять расстояние между цифрами

Если вывести все точки в ряд, и перевести в двоичный вид, то при сдвиге на 1 точку результат меняется в 2 раза, хотя цифра не поменялась.

Или добавить точку в конце, это вообще перечеркнет все.

Проблема возникает из за того, что ответы (метки классов), чтобы можно было вывести обобщение (как в knn) не даны.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

или попробовать добавлять в вектор признаков уменьшенные\размытые копии того же изображения.

или попробовать вычислить моменты букв, хотя этого наверно мало.

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

Проблема возникает из за того, что ответы (метки классов), чтобы можно было вывести обобщение (как в knn) не даны.

ну а по большому счету какая разница ведь мы все равно используем плохую метрику? или я что то не понимаю.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

что интересно, распределение по кластерам такое на 10к сэмплов

(9994,1,1,1,1,1,1,0,0,0)

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Нужно уменьшить размерность пространства, а то точек жидковато получается на столько то измерений.

Думаю тут PCA самое то будет.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

почему жидковато? 28*28 в векторе признаков на 10к или на 60к сэмплов, тут дело в другом скорее.

и как вообще размерность задачи зависит от кол-ва сэмплов?

но во всяком случае, попробую размыть и уменьшить в 2 раза, но у меня такое ощущение, что это только потеря информации,

хотя еще есть идея сделать пирамиду изображений и всю её пихнуть в вектор может это как то поможет обобщению, но тут проблема наверно в том что кол-во пикселей на маленьких изображениях будет меньше и их вклад будет тоже меньше.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

http://en.wikipedia.org/wiki/Curse_of_dimensionality

http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%BA%D0%BB%D1%8F%D1%82%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8

вот оно как оказывается, но причину я как то все равно не понял, т.е. понял что проблема есть, но не осознал.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

мне надо использовать PCA как используется для лиц, там поиск eigenvectors?

(я пока не очень вникал)

если есть материал то подкиньте.

и тут уже получается, что kmeans уже не причем?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

И эти оси будут лежать в плоскости точек. Затем переводим координаты точек в это пространство.

Таким образом мы уменьшили размерность с которой работаем с 3 до 2.

Далее мы можем применять любые методы классификации/кластеризации. Например с теми же лицами, если применим k-means то нам не обязательно знать кто есть кто, метод просто выдаст нам k групп похожих людей. Если применим KNN - то сможем по заданному образцу найти K похожих на него лиц и так далее.

Вот, как мне кажется, понятное видео:

и

ЗЫ: По поводу "жидковато" я имел ввиду не "проклятье размерности", а то что с ростом размерности пространства, необходимое для формирования модели количество данных сильно растет.

Пример:

Есть 100 точек и отрезок 1 см.

Точки ставите случайно по равномерному распределению.

По поставленным точкам можно достаточно точно восстановить отрезок.

Добавляем одно измерение - теперь у нас квадрат со стороной 1 см. ставим те же 100 точек.

Квадрат восстановим, но уже хуже.

Если продолжить рассуждения для куба, то результат будет плачевный, не говоря уже о многомерных фигурах, вот почему важно уменьшить размерность пространства, найдя главные компоненты.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×