Jump to content
Compvision.ru
Sign in to follow this  
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), как потом к каждому кластеру привязать цифру?

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

mnist_large.jpg

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

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

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

Share this post


Link to post
Share on other sites
Считаем соседей какого класса среди этих k штук больше, тот класс и присваиваем нашей новой точке

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

попробовал для разного кол-ва элементов в выборке и результат как бы не меняется хоть 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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

и

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

Пример:

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

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

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

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

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

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×