Какие алгоритмы наиболее толерантны к пропускам в данных?

[Alex7]

Друзья, всем привет!

Общая проблема:
Есть разряженный набор данных с двумя классами. Наблюдения у экземпляров класса могут могут прилично отличаться. Например, в одном экземпляре известны параметры: х1, х3, х4, х5; в другом экземпляре известны: х1, х2, х6 и т. д. При этом оба примера принадлежат одному классу.

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

Подскажите, какие алгоритмы наиболее толерантны к пропускам в данных на этапе обучения?

[Andrey_Kireew]

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

[Mihaylo]

Большинство алгоритмов работают с гладкими-линейными зависимостями, таких очень много.

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

С такими данными непросто работать. Это надо понимать. Это значит, что алгоритмов может и не быть, они просто сложны для современного datascience.

Alex7 в сообщении #1413889 писал(а):

Например, в одном экземпляре известны параметры: х1, х3, х4, х5; в другом экземпляре известны: х1, х2, х6 и т. д. При этом оба примера принадлежат одному классу.

В данном примере трудно написать алгоритм, который классифицирует примеры правильно. Ну сами посудите.

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

[ozheredov]

Alex7 в сообщении #1413889 писал(а):

Например, в одном экземпляре известны параметры: х1, х3, х4, х5; в другом экземпляре известны: х1, х2, х6 и т. д. При этом оба примера принадлежат одному классу.

Смотрите random forest

[Pavia]

Andrey_Kireew

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

Большинство алгоритмов, в своём. исходном виде, попросту непригодны, не говоря уже о толерантности.

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

Так что к пропускам непригодны разве, что самые примитивные.

Alex7
У вас нет конкретики в вопросе. Вам подойдут любой алгоритм: деревья решений(random forest), машина опорных векторов(SVM), нейронные сети(ANN и CNN), линейный классификатор, c-mean и k-mean, скользящего среднего(mean shift), самоорганизующаяся карта Кохонена и тд.

Судя по всему лучше вам обратить внимание на то, как работают с текстами.

[Andrey_Kireew]

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

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

Так что к пропускам непригодны разве, что самые примитивные

Что же Вы тогда советуете ТС

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

Вам подойдут любой алгоритм: деревья решений(random forest), машина опорных векторов(SVM), нейронные сети(ANN и CNN), линейный классификатор, c-mean и k-mean, скользящего среднего(mean shift), самоорганизующаяся карта Кохонена и тд.

по Вашему все эти алгоритмы устойчивы к шумам и способны работать с пропусками данных, без введения каких либо видоизменений?

-- 06.09.2019, 22:30 --

Alex7 в сообщении #1413889 писал(а):

Например, в одном экземпляре известны параметры: х1, х3, х4, х5; в другом экземпляре известны: х1, х2, х6 и т. д.

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

[mserg]

Что-то я не совсем понимаю, в чем затруднение...

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

Если переменная числовая, то можно завести дополнительную пседвобулеву переменную - она принимает значение 1 если значение исходной переменной пропущено; и 0, если значение исходной переменной заполнено. Пропуски нужно заполнить, например, константой - нулем, средним и т.п.

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

[Andrey_Kireew]

mserg в сообщении #1413965 писал(а):

Пропуски нужно заполнить, например, константой - нулем, средним и т.п.

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

[Pavia]

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

по Вашему все эти алгоритмы устойчивы к шумам и способны работать с пропусками данных, без введения каких либо видоизменений?

Именно так.

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

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

Опять Вы ошибаетесь.

[Andrey_Kireew]

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

Andrey_Kireew в сообщении #1413949

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

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

[mserg]

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

mserg в сообщении #1413965 писал(а):

Пропуски нужно заполнить, например, константой - нулем, средним и т.п.

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

А как Вы думаете, зачем добавляется псевдобулева переменная для каждой переменной с пропусками? Для примера, в "линейном случае" константы заполнения подберутся алгоритмом с помощью этих доп. переменных. Это легко показать. Нюансы, конечно, могут возникнуть, но их обсуждение уведет от сути.

[Andrey_Kireew]

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

mserg в сообщении #1413965 писал(а):

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

это распространённое заблуждение - отождествлять неопределённость с нулём или ещё чем то конкретным.
Представьте сами для конкретики, пусть один из признаков - это вес человека. Для одного из наблюдений вес неизвестен. Поставим ноль, и к чему это приведёт в итоге? Да, в этом случае можно поставить dummy variable или сразу - наиболее вероятное значение веса. Это отчасти решит проблему. Ну а если распределение заполняемого признака туповершинное, или бимодальное? Например выборка состоит из мужчин с весом 90$\pm$15 кг и женщин с весов 60$\pm$15 кг. Какой константой заполнить пропуски? маловероятным значением 75? Можно конечно, но лучше заполнять зависящими от пола значениями. Это существенно повысит качество классификатора.

[ozheredov]

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

ИМХО здесь нужен некий комитет решающих правил, каждое из которых ориентируется на свой (случайный) набор переменных и будет просто затыкаться, когда лично у него этот набор неполон. Как раз концепция random forest

[Andrey_Kireew]

ozheredov в сообщении #1413981 писал(а):

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

Это не так. Всегда можно построить прогноз пропущенного значения по оставшимся признакам, причём на основании всей выборки. Пропуски в остальных признаках можно сначала принять равными их безусловным модам. Так пройтись несколько раз по всем признакам, и получится неплохая интерполяция.
С той же целью можно использовать нелинейное шкалирование. О нём можно почитать здесь [Краскэл Дж. Б. Взаимосвязь между многомерным шкалированием и кластер-анализом]. Насколько я помню, там прямо утверждается, что метод позволяет восстановить до 30% пропусков. Но лично, я с этим дела не имел, так что как оно на самом деле - не знаю.

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

[Mihaylo]

Мы просто не знаем, чем вызваны пропуски. "Гадать по фото" можно бесконечно.