Проблема классификации

[Dan B-Yallay]

Задача поставлена следующим образом:

Eсть набор признаков $p_1, ... , p_n$ и два "шаблона" $a, \ b$, соответствующиe двум классам (в идеале не пересекающимся). Берём некоторый элемент, измеряем у него указанные признаки и сравниваем с шаблоном $a$ - получаем набор $n$ чисел, которые характеризуют "соответствие" шаблону. Сравниваем эти же признаки с шаблоном $b$ и получаем набор других чисел. Таким образом, элементу соответствует вектор размерности $2n$. Далее, имеются группы $A, B$, под которые и были созданы шаблоны, то есть подразумевается, что показатели элементов из группы $A$ "хорошо подходят" под шаблон $a$ и "плохо" под шаблон $b$. Для элементов из группы $B$ ситуация зеркальная. В связи с неизбежными статвыбросами, ошибками измерения и пр., некоторый процент групп $A, \ B$ перекрываeтся и поэтому разделить на 100% эти группы не получится. Тем не менее хочется найти такой критерий (гиперповерхность?), чтобы минимизировать ошибки как первого, так и второго рода. Или хотя бы одного из этих родов. Kоличество элементов в каждой группе одинаково и порядка за сотни тысяч.

Самостоятельные попытки решения:

Википедия делится знаниями о Задача классификации но к сожалению, указанныe методы либо предполагают нормальность раcпределения, идентичность вариации или даже явную возможность разделить классы какой-то плоскостью. Не думаю, что исследуемые данные обладают указанными свойствами. Хуже того, есть некоторая корреляция или зависимость одних признаков от других.

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

Буду благодарен за идеи и ссылки на какие-либо подходы к решению.

(Example)

В качестве примера рассмотрим задачу классификации спортсменов: штангистов и легкоатлетов.
Признаки:
1) вес, kg;
2) объём руки, cm;
3) жим лёжа, kg
4) пробег в день, km;
5) дистанция 800 м на время, min;

Соответственно, шаблон $a = (90, \ 51, \ 180,\ 1.5,\ 8)^T$ и шаблон $b = (65,\ 25,\ 45,\ 35,\ 3)^T$. Для человека с массой $M$ кг "соответствие шаблонy" можно выразить выразить многими способами, например в виде абсолютной $(M - 90)$ или относительниой разницы $(M-90)/90$ (чем меньше, тем лучше) либо $\min \{M,90\}$ (чем больше тем лучше). И так же по остальным признакам.

[Sdy]

Dan B-Yallay,
Думаю, что зря лезу, так как на данный момент мои знания в области ML ограничиваются тремя просмотренными лекциями из видеокурса, но почему вы просто не используете логистическую регрессию? Тут же явная задача бинарной классификации.

[Pavia]

Алгоритм k-means для N-мерного пространства с применением бустинга.

[Dan B-Yallay]

Sdy в сообщении #1399083 писал(а):

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

Дело в том, что MашинЛёрнинг для меня вообще неизведанная территория, но глубоко изучать её в мои планы не входит. Я потому и открыл тему, чтобы мне подсказали, с какого края и какими инструментами копать то, что мне нужно. Дальше уже постараюсь сам. И таки да: логистическая регрессия - это похоже на то, что мне нужно, по крайней мере на первый взгляд. Спасибо.

Pavia в сообщении #1399087 писал(а):

Алгоритм k-means для N-мерного пространства с применением бустинга.

Спасибо за подсказку. Если я не ошибаюсь, этот алгоритм применяется для кластеризации, то есть "наилучшего" разбиения на группы. У меня же задача другая (смежная): группы уже имеются и надо найти "наилучшую" границy их разделения.

[Pavia]

Dan B-Yallay в сообщении #1399151 писал(а):

Если я не ошибаюсь, этот алгоритм применяется для кластеризации, то есть "наилучшего" разбиения на группы. У меня же задача другая (смежная): группы уже имеются и надо найти "наилучшую" границy их разделения.

Под это требование попадает любой параметрический классификатор. К-средних это полу-параметрический метод. Т.е он может применятся как для параметризованных задач так и не параметризованных.
А что он будет оптимизировать определяет целевая функция(ядро). В данном случае её можно сделать логической функцией определив сколько точек попали в свой класс или колличество ошибок 1 и 2 рода.

[Dan B-Yallay]

Dan B-Yallay в сообщении #1399151 писал(а):

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

На второй взгляд выяснилось, что для данной задачи эта регрессия мало отличается от линейной, где функция задаётся как линейная комбинация признаков (регрессоров) $f(\mathbf x) = \mathbf b^T \mathbf x = b_0+ b_1x_1 + b_2 x_2 + ... + b_n x_n$.
А это уже пройденный этап и oн дал хорошiй результат (ошибка около 1%), но хотелось бы знать/показать, что это минимально возможно, причём не только среди обобщённо-линейный методов а вообще.

На самом деле непонятно, почему бы функции, в которую аргументы входят каким-нибудь более замысловатым сложным образом не оказаться более эффективным "разделителем", например:

$$f(\mathbf x) = \beta_0 + \beta_1 x_1 \cdot \cos ( x_4) + \beta_2\dfrac {\sqrt{x_2}}{ \log{x_3}} + ...+ \int\limits_{\beta_n}^{x_n}e^t t^3 \ dt $$

Возвращаюсь пока к уже упомянутому квадратичному классификаторy.

$$ f(\mathbf x) = {\displaystyle \mathbf {x^{T}Ax} +\mathbf {b^{T}x} +c}$$

Кроме того есть направление, которое заинтересовало:

Adjusted least squares fitting of algebraic hypersurfaces
Robust Hypersurface Fitting Based on Random Sampling Approximations

[Pavia]

Dan B-Yallay в сообщении #1399201 писал(а):

На самом деле непонятно, почему бы функции, в которую аргументы входят каким-нибудь более замысловатым сложным образом не оказаться более эффективным "разделителем", например:

$$f(\mathbf x) = \beta_0 + \beta_1 x_1 \cdot \cos ( x_4) + \beta_2\dfrac {\sqrt{x_2}}{ \log{x_3}} + ...+ \int\limits_{\beta_n}^{x_n}e^t t^3 \ dt $$

В смыысле? Рассмотрите аналогичную задачу для $n=2$ вы увидите что более сложная функция будет давать лучшие результаты.
Единственное почему плохо может работать, быть менее эффективным, так это только если ваши шаблоны изначально линейные.
А это так и есть по построению.

Цитата:

Берём некоторый элемент, измеряем у него указанные признаки и сравниваем с шаблоном $a$ - получаем набор $n$ чисел, которые характеризуют "соответствие" шаблону.

[Andrey_Kireew]

Dan B-Yallay если стоит задача непосредственно оптимизировать чувствительность и специфичность, то в качестве функционала можно использовать Somer's D. В английской вики можно про него почитать. Этот показатель связан с площадью ROC кривой так, что оптимизируя его можно напрямую повысить чувствительность/ специфичность. Соотношение между ними, потом, корректируется выбором порога.

-- 14.06.2019, 20:40 --

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

-- 14.06.2019, 20:48 --

Ну вот например вероятностный классификатор:

$$ cl=sgn[e^{-(\bold x-\bold \mu_1)^TC^{-1}_1(\bold x-\bold \mu_1)}-e^{-(\bold x-\bold \mu_2)^TC^{-1}_2(\bold x-\bold \mu_2)}]$$

если cl положительный, значит наблюдение ближе к шаблону 1, иначе - к шаблону 2.
В такой постановке как у Вас он сможет разделить все наблюдения.

[Dan B-Yallay]

Pavia в сообщении #1399275 писал(а):

Рассмотрите аналогичную задачу для $n=2$ вы увидите что более сложная функция будет давать лучшие результаты.
Единственное почему плохо может работать, быть менее эффективным, так это только если ваши шаблоны изначально линейные.
А это так и есть по построению.

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

Andrey_Kireew
Cпасибо за информацию, буду гуглить и викить.

[Andrey_Kireew]

Dan B-Yallay поясните, зачем нужны шаблоны? Известно ведь, что элементы подвыборки А принадлежат одному классу, а элементы подвыборки B другому. Для решения задачи классификации этого достаточно.
Или шаблоны a и b - это дополнительно ужесточение? Т.е. их классификатор должен классифицировать верно обязательно, а все остальные наблюдения выборки по возможности.

[Iam]

На задачу можно посмотреть как на задачу различения двух гипотез $a,b$ по наблюдениям $ h \in R^n , h=(h_1,…,h_n), h_i $- признаки. В такой постановке должны быть заданы априорные вероятности $P(a),P(b)$ гипотез $ a,b $ и условные распределения (здесь плотности) $ w(h \mid a), w(h \mid b). $Тогда $ R^n $ разбивается оптимально (с т. з. минимизации вероятности ошибки) на области $D(a),D(b)$ принятия гипотез $ a,b $условием
$ z \in D(a) \Leftarrow \Rightarrow w(h \mid a)P(a) \ge w(h \mid b)P(b). $
Когда мы говорим о шаблонах, имеем в виду, что имеются соответствующие шаблонам наборы признаков $h_a,h_b $, использование которых позволяет упростить модель и задачу. Так, условие симметричности модели для гипотез $a,b$ в ряде случаев дает возможность записать $w(h \mid b)=w(-h \mid h_a ) $ (не в примере), а понятие «похожести» или «близости» - свести задачу к различению гипотез по искаженным наблюдениям $ h_x, x \in \{a,b\}, $и представлению условных распределений в виде
$ w(h \mid h_x )=w_Z (z), z=\rho (h, h_x) , \rho (\cdot,\cdot) $ - некоторая метрика в $ R^n $.
Если как то удалось подобрать метрику, для которой $ w_Z (z) $ - монотонно убывающая функция, то все ОК - к этому чаще всего сводятся задачи такого типа, в том числе при гауссовских возмущениях. С другой стороны, если изначально не задать распределения $ w(h \mid a),w(h \mid b) $ (или их подходящие классы), то для любого выбранного разбиения $ {D(a),D(b)} $можно придумать такие условия, при которых различение будет весьма плохим.
Конечно, это все тривиальные рассуждения, но они могут прояснить вопрос о том, чтобы «знать/показать, что это минимально возможно, причём не только среди обобщённо-линейных методов, а вообще». Становится ясно, что для получения полезной оценки гарантированной достоверности в задаче из примера желательно задать класс распределений, прежде всего, учитывающий их монотонность по каждому параметру. Кроме того, нужно исключить «одноступенчатые» зависимости, при наличии которых также хорошей границы не получить.

[Dan B-Yallay]

Andrey_Kireew в сообщении #1399295 писал(а):

поясните, зачем нужны шаблоны?

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

Попробую объяснить на таком притянутом за уши примере. Допустим мне нужно разделить животный мир планеты на "хищников" и "жертв". При этом заранее имеется понятие-шаблон хищника: бинокулярное зрение, острые зубы, хороший нюх, умеет кооперироваться и так далее. Шаблон жертвы: это травоядное с круговым зрением, тупыми перемалывающими зубами, хорошим слухом, быстро бегающее и тп.

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

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

-- Пт июн 14, 2019 12:03:33 --

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

[Andrey_Kireew]

Dan B-Yallay в сообщении #1399300 писал(а):

кажется, формализовал задачу как надо

ну, если Вам надо именно так - то это дело "хозяйское" ....

Тем не менее, хотелось бы заметить. Учитывая Ваши же предыдущие объяснения, польза от этого шаблона вызывает большое сомнение. Но тут не совсем понятно его происхождение. Если это достоверные данные, основанные на результатах стат обработки больших массивов информации, многолетних наблюдений, не вызывающие сомнений у специалистов предметной области, либо это следствия каких то логических закономерностей - дело одно. Если же они формируются больше интуитивно, на основе каких то субъективных соображений, и рассматриваются лишь как вспомогательное средство решения задачи - дело совсем другое. В последнем случае введение этих шаблонов ничем не оправдано. Более того, эти шаблоны навязывают модели определённую структуру, возможно для Вас не самую лучшую.
Вы наверное уже успели заметить, что в логистической регрессии просто нет места для шаблона. Нужно ли его туда "запихивать" искусственно?

Dan B-Yallay в сообщении #1399300 писал(а):

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

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

[Dan B-Yallay]

Andrey_Kireew в сообщении #1399313 писал(а):

Если это достоверные данные

Именно так.

Andrey_Kireew в сообщении #1399313 писал(а):

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

Об этом в курсе, спасибо. ))