Идея ядерных методов

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

Где окажутся средние точки каждого класса? В точности в одном и том же месте! Хотя и вам, и мне ясно, что все точки внутри круга – крестики, а вне него – кружки, линейный классификатор не в состоянии различить эти классы.

Но что если сначала возвести координаты x и y каждой точки в квадрат? Точка, которая имела координаты (-1, 2), теперь превратится в (1, 4), точка (0,5, 1) – в (0,25, 1) и т. д. Новая диаграмма изображена на рис. 9.8.

Теперь все крестики переместились в угол, а все нолики оказались вне угла. Разделить их прямой линией стало совсем просто, а для классификации новой точки достаточно возвести ее координаты в квадрат и посмотреть, по какую сторону от прямой она окажется.

Рис. 9.7. Один класс окружен другим

 

Рис. 9.8. Перемещение точек в другое пространство

Этот пример показывает, что путем предварительной трансформации точек можно создать новый набор данных, допускающий разделение прямой линией. Однако это специально подобранный пример, для которого трансформация описывается просто; в реальных задачах она оказывается куда сложнее, к тому же производится в пространстве большей размерности. Например, можно взять двумерный набор данных с координатами x и y и трансформировать его в трехмерный по формулам a = x ^ 2, b = x * y, c = y ^ 2. Увеличив размерность задачи, иногда становится проще найти разделяющую два класса поверхность.

Переход к ядру

Хотя для перевода данных в новое пространство можно написать код, подобный приведенному выше, на практике так поступают редко, потому что при работе с реальными наборами данных для поиска разделителя иногда требуется переходить в пространство с сотнями и тысячами измерений, что вряд ли реализуемо. Однако для любого алгоритма, в котором используются скалярные произведения, – в том числе и для линейного классификатора – можно применить метод перехода к ядру (kernel trick).

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

Функция радиального базиса аналогична скалярному произведению в том смысле, что принимает два вектора и возвращает число. Но, в отличие от скалярного произведения, она нелинейна и, следовательно, может использоваться для отображения более сложных пространств. Добавьте функцию rbf в файл advancedclassify.py: def rbf(v1,v2,gamma=20): dv=[v1[i]-v2[i] for i in range(len(v1))] l=veclength(dv) return math.e**(-gamma*l)

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

векторов и вычисление скалярного произведения результата усреднения с вектором A дает тот же результат, что усреднение скалярных произведений вектора A со всеми векторами из того же множества. Поэтому, вместо того чтобы вычислять скалярное произведение классифицируемой точки со средней точкой класса, можно вычислить скалярные произведения или функции радиального базиса для данной точки и всех остальных точек класса, а затем выполнить усреднение. Добавьте функцию nlclassify в файл advancedclassify.py:

def nlclassify(point,rows,offset,gamma=10): sum0=0.0 sum1=0.0 count0=0 count1=0

for row in rows: if row.match==0: sum0+=rbf(point,row.data,gamma) count0+=1 else:

sum1+=rbf(point,row.data,gamma) count1+=1

y=(1.0/count0)*sum0-(1.0/count1)*sum1+offset

if y<0: return 0 else: return 1

def getoffset(rows,gamma=10): l0=[] l1=[]

for row in rows: if row.match==0: l0.append(row.data) else: l1.append(row.data) sum0=sum(sum([rbf(v1,v2,gamma) for v1 in l0]) for v2 in l0) sum1=sum(sum([rbf(v1,v2,gamma) for v1 in l1]) for v2 in l1)

return (1.0/(len(l1)**2))*sum1-(1.0/(len(l0)**2))*sum0 Величина смещения в трансформированном пространстве тоже отличается, и на ее вычисление может уйти заметное время. Поэтому ее следует вычислять для набора данных один раз и передавать при каждом вызове nlclassify:

Попробуйте воспользоваться новым классификатором для набора данных о возрасте и посмотрите, решает ли он обнаруженную ранее проблему:

>>> advancedclassify.nlclassify([30,30],agesonly,offset)

1

>>> advancedclassify.nlclassify([30,25],agesonly,offset)

1

>>> advancedclassify.nlclassify([25,40],agesonly,offset)

0

>>> advancedclassify.nlclassify([48,20],agesonly,offset)

0

Блестяще! После трансформации классификатор сумел понять, что существует полоса пар с близкими возрастами и что по обе стороны от этой полосы составление пары крайне маловероятно. Теперь он распознает, что 48 и 20 не подходят для составления пары. Попробуем еще раз, включив и другие данные:

>>> ssoffset=advancedclassify.getoffset(scaledset) >>> numericalset[0].match 0

>>> advancedclassify.nlclassify(scalef(numericalset[0].data),scaledset, ssoffset)

0

>>> numericalset[1].match 1

>>> advancedclassify.nlclassify(scalef(numericalset[1].data),scaledset, ssoffset)

1

>>> numericalset[2].match

0

>>> advancedclassify.nlclassify(scalef(numericalset[2].data),scaledset, ssoffset)

0

>>> newrow=[28.0,-1,-1,26.0,-1,1,2,0.8] # Мужчина не хочет иметь детей, а женщина хочет

>>> advancedclassify.nlclassify(scalef(newrow),scaledset,ssoffset)

0

>>> newrow=[28.0,-1,1,26.0,-1,1,2,0.8] # Оба хотят иметь детей >>> advancedclassify.nlclassify(scalef(newrow),scaledset,ssoffset)

1

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100