Однако если в наборе данных есть всего несколько поврежденных записей — скажем, невероятно невероятные измерения — стандартные методы подгонки данных могут выйти из строя. Эта проблема становится гораздо более острой с данными большого размера или данными со многими переменными, которые повсеместно распространены в цифровую эпоху.
С начала 1960-х годов было известно, что существуют алгоритмы для устранения искажений в данных большой размерности, но ни один из алгоритмов, предложенных за последние 50 лет, не применим, когда количество переменных превышает, скажем, 12.Это скоро изменится. Ранее в этом месяце на симпозиуме IEEE по основам компьютерных наук группа исследователей из Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института, Университета Южной Калифорнии и Калифорнийского университета в Сан-Диего представила новый набор алгоритмов, которые могут эффективно подходят распределения вероятностей к многомерным данным.Примечательно, что на той же конференции исследователи из Технологического института Джорджии представили очень похожий алгоритм.
Новаторская работа над «надежной статистикой» или статистическими методами, которые могут допускать искаженные данные, была проделана статистиками, но обе новые статьи созданы группами компьютерных ученых. Это, вероятно, отражает смещение внимания в данной области к вычислительной эффективности методов подгонки моделей.«С точки зрения теоретической информатики гораздо более очевидно, насколько редко проблема может быть эффективно решена», — говорит Анкур Моитра, доцент кафедры математики Rockwell International Career Development Assistant в MIT и один из руководителей MIT. -USC-UCSD проект. «Если вы начнете с какой-то гипотетической вещи -« Боже, как бы мне хотелось это сделать.
Если бы я мог, это было бы надежно »- у вас будут плохие времена, потому что это будет неэффективно. начните с того, что, как вы знаете, вы можете делать эффективно, и выясните, как соединить их вместе, чтобы получить надежность ».Противодействие коррупции
Чтобы понять принцип, лежащий в основе надежной статистики, объясняет Мойтра, рассмотрим нормальное распределение — кривую колокола, или, говоря математическим языком, одномерное распределение Гаусса. Одномерный гауссиан полностью описывается двумя параметрами: средним или средним значением данных и дисперсией, которая является мерой того, насколько быстро данные распространяются вокруг среднего.Если данные в наборе данных — скажем, рост людей в данной популяции — хорошо описываются распределением Гаусса, то среднее значение — это просто среднее арифметическое.
Но предположим, что у вас есть набор данных, состоящий из измерений роста 100 женщин, и хотя большинство из них сгруппированы около 64 дюймов — некоторые немного выше, некоторые немного ниже — одна из них по какой-то причине составляет 1000 дюймов. Если взять среднее арифметическое, средний рост женщины составит 6 футов 4 дюйма, а не 5 футов 4 дюйма.Один из способов избежать такого бессмысленного результата — это оценить среднее значение, не взяв среднее числовое значение данных, а найдя его медианное значение. Это потребует перечисления всех 100 измерений в порядке от наименьшего к наибольшему и взятия 50-го или 51-го.
Таким образом, алгоритм, который использует медианное значение для оценки среднего, является более надежным, что означает, что он менее чувствителен к поврежденным данным, чем алгоритм, использующий среднее значение.Однако медиана — это всего лишь приближение к среднему, и точность приближения быстро снижается с увеличением количества переменных.
Анализ больших данных может потребовать изучения тысяч или даже миллионов переменных; в таких случаях приближение среднего значения к медиане часто приводит к непригодным для использования результатам.Выявление выбросовОдин из способов отсеять поврежденные данные из набора данных большой размерности — взять двумерные поперечные сечения графика данных и посмотреть, похожи ли они на гауссовские распределения. Если они этого не делают, возможно, вы обнаружили группу ложных точек данных, например, ту женщину ростом 80 футов, которую можно просто вырезать.
Проблема в том, что во всех ранее известных алгоритмах, которые использовали этот подход, количество поперечных сечений, необходимых для поиска поврежденных данных, было экспоненциальной функцией количества измерений. Напротив, Мойтра и его соавторы — Гаутам Камат и Джерри Ли, оба аспиранты Массачусетского технологического института в области электротехники и информатики; Илиас Диакониколас и Алистер Стюарт из USC; и Дэниел Кейн из USCD — нашли алгоритм, время работы которого увеличивается с увеличением количества измерений данных с гораздо более разумной скоростью (или, полиномиально, на жаргоне информатики).Их алгоритм основан на двух выводах.
Во-первых, какую метрику использовать при измерении удаленности набора данных от диапазона распределений примерно одинаковой формы. Это позволяет им определить, когда они отсеивают достаточно поврежденных данных, чтобы их можно было подобрать.Другой — как определить области данных, в которых следует начинать создание поперечных сечений. Для этого исследователи полагаются на так называемый эксцесс распределения, который измеряет размер его хвостов или скорость, с которой концентрация данных уменьшается далеко от среднего.
Опять же, есть несколько способов сделать вывод о эксцессе из выборок данных, и выбор правильного является центральным для эффективности алгоритма.Подход исследователей работает с распределениями Гаусса, определенными комбинациями распределений Гаусса, другим распространенным распределением, называемым распределением продукта, и определенными комбинациями распределений продукта.
Хотя они считают, что их подход может быть распространен на другие типы распределений, в текущей работе их основное внимание уделяется применению своих методов к реальным данным.