Простая линейная классификация

Этот классификатор будет совсем простым, но послужит неплохой основой для дальнейшей работы. Он ищет среднее по всем данным в каждом классе и строит точку, представляющую центр этого класса. Новые точки классифицируются по близости к имеющимся центрам. Нам потребуется функция, которая вычисляет среднюю точку класса. В данном случае есть всего два класса, соответствующие 0 и 1. Добавьте функцию lineartrain в файл advancedclassify.py: def lineartrain(rows): averages={} counts={}

for row in rows:

#      Получить класс данной точки cl=row.match

averages.setdefault(cl,[0.0]*(len(row.data))) counts.setdefault(cl,0)

#      Добавить точку к средним for i in range(len(row.data)):

averages[cl][i]+=float(row.data[i])

#      Подсчитываем количество точек в каждом классе counts[cl]+=1

# Делим суммы на счетчики и получаем средние for cl,avg in averages.items( ): for i in range(len(avg)): avg[i]/=counts[cl]

return averages

Выполните эту функцию в интерактивном сеансе и получите средние: >>> reload(advancedclassify)

<module ‘advancedclassify’ from ‘advancedclassify.pyc’> >>> avgs=advancedclassify.lineartrain(agesonly)

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

Рис. 9.4. Линейный классификатор по средним точкам

Крестиками представлены средние точки, вычисленные функцией lineartrain. Линия, разделяющая данные, проходит посредине между двумя крестиками. Это означает, что все точки слева от линии ближе к средней точке класса «не пара», в точки справа от линии – к средней точке класса «пара». Если вы получаете новую пару возрастов и хотите понять, будут ли эти люди составлять пару, то можете нанести соответствующую точку на диаграмму и посмотреть, к какому среднему она окажется ближе.

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

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

Рис. 9.5. Примеры векторов

Скалярное произведение двух векторов – это число, получающееся в результате суммирования попарных произведений координат векторов. Создайте в файле advancedclassify.py новую функцию dotproduct:

def dotproduct(v1,v2):

return sum([v1[i]*v2[i] for i in range(len(v1))]) По-другому скалярное произведение можно вычислить путем умножения длин двух векторов на косинус угла между ними. Самое важное здесь то, что косинус отрицателен, если угол больше 90°, а следовательно, и скалярное произведение в этом случае отрицательно. Чтобы понять, как этим можно воспользоваться, взгляните на рис. 9.6.

Рис. 9.6. Использование скалярных произведений для вычисления расстояния

На этой диаграмме вы видите две средние точки для классов «пара» {M0) и «не пара» {Mj), а также точку C посредине между ними. Есть и еще две точки, Xj и X2, которые надлежит классифицировать. Показан вектор, соединяющий M0 с Mj, а также векторы, соединяющие Xj и X2 с C.

На этом рисунке X^ расположена ближе к M0, поэтому классифицируется как «пара». Обратите внимание, что угол между векторами Xj ^ C и M0 ^ Mj составляет 45°, то есть меньше 90°, а следовательно, скалярное произведение X^ ^ C и M0 ^ M^ положительно.

С другой стороны, угол между X2 ^ C и M0 ^ Mj больше 90°, так как векторы направлены в разные стороны. Поэтому их скалярное произведение отрицательно.

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

Точка C лежит посредине между M0 и M^, то есть С = {M0 + M^) / 2, поэтому формула для определения класса выглядит так:

Класс = sign{{X – {M0 + M^) / 2) . {M0 – M^)) Раскрыв скобки, получаем:

Класс = sign{X.M0 – X.Mj + {M0.M0 – Mj.Mj) / 2) По этой формуле мы и будем определять класс. Добавьте в файл advancedclassify.py функцию dpclassify:

def dpclassify(point,avgs):

b=(dotproduct(avgs[1],avgs[1])-dotproduct(avgs[0],avgs[0]))/2 y=dotproduct(point,avgs[0])-dotproduct(point,avgs[1])+b if y>0: return 0 else: return 1

Теперь воспользуемся построенным классификатором в интерактивном сеансе и посмотрим, что получится: >>> reload(advancedclassify)

<module ‘advancedclassify’ from ‘advancedclassify.py’> >>> advancedclassify.dpclassify([30,30],avgs)

1

>>> advancedclassify.dpclassify([30,25],avgs)

1

>>> advancedclassify.dpclassify([25,40],avgs)

0

>>> advancedclassify.dpclassify([48,20],avgs)

1

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

возрастов 48 и 20 не должно было бы дать пару, но поскольку линия только одна и точка находится справа от нее, то функция решает, что это пара. В разделе «Идея ядерных методов» ниже вы увидите, как можно усовершенствовать этот метод, чтобы он умел выполнять и нелинейную классификацию.

Вы можете следить за любыми ответами на эту запись через 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