Как найти среднее расстояний между объектами и центроидом отнесенных к кластеру 0
Мне необходимо найти среднее расстояний между объектами, отнесенными к кластеру 0, и центроидом этого кластера. В результате кластеризации получились следующие значения: Так же есть массив расстояний от данных до всех центроидов:
array([[ 5.23450093, 16.31035799, 9.08639092], [ 4.83735465, 8.48691804, 7.31864058], [ 9.33809402, 3.21886799, 5.15388203], [13.6821051 , 3.32080981, 8.09706737], [15.64608577, 8.8897569 , 15.47780669], [ 0.63245553, 12.00115735, 6.56220237], [ 4.5607017 , 15.3306157 , 8.09706737], [ 5.83095189, 11.57703666, 10.68000468], [ 7.37563557, 5.13430727, 3.81608438], [15.42076522, 3.70060055, 10.25 ], [ 7.82304289, 10.10088005, 2.01556444], [ 7.72010363, 7.304869 , 1.03077641], [ 8.54400375, 4.90181372, 7.84617741], [ 7.33484833, 10.90998523, 2.65753645], [15.26433752, 5.54025671, 9.03119593]]) Отслеживать
задан 2 дек 2021 в 11:13
11 3 3 бронзовых знака
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
У вас уже есть матрица расстояний до кластерных центроидов — дальше простая работа с матрицами.
- выбираем из матрицы расстояний только строки, принадлежащие кластеру 0
- считаем среднее значение (функция/метод mean ) в получившейся на предыдущем шаге матрице в первом столбце (столбец с индексом 0 ). Я исхожу из того, что расстояния до кластера 0 находятся в первом столбце матрицы расстояний.
Отслеживать
ответ дан 2 дек 2021 в 11:19
MaxU — stand with Ukraine MaxU — stand with Ukraine
149k 12 12 золотых знаков 59 59 серебряных знаков 132 132 бронзовых знака
Спасибо большое!
2 дек 2021 в 12:00
- python
- машинное-обучение
- кластеризация
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.1.3.2953
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Кластерный анализ
При помощи данной процедуры Вы можете провести многомерную классификацию объектов(документов), то есть классификацию объектов одновременно по нескольким переменным.
Содержание:
- Основные определения
- Запуск процедуры
- Страница Результат
- Интегральная оценка результатов кластеризации — выбор оптимального числа кластеров
- Страница Одномерная проекция
- Страница Двухмерная проекция
- Страница Качество разделения
- Страница Обратное решение
- Сохранение результатов классификации
- Дополнительно
Основные определения
- Под кластером понимается группа объектов, которые расположены в многомерном пространстве переменных максимально близко друг к другу и при этом максимально удалены от объектов из других групп.
- Центр кластера – наиболее типичный представитель данного кластера (его геометрический центр). По характеристикам центра кластера можно судить обо всем кластере.
- Кластерное решение — один из множества способов разделения объектов по кластерам. Качество кластерного решения зависит от числа кластеров, удачного выбора стартовых точек, количества итераций и метода агломерации.
- Метод агломерации . Существует много методов разделения объектов на кластеры. В настоящее время в программе реализована только одна процедура «К — средние» , представляющая собой наиболее быстрый алгоритм кластерного анализа. В общих словах, алгоритм заключается в следующем:
- В многомерном пространстве в качестве начальных центров кластеров выбираются случайные объекты (или объекты, наиболее удаленные друг от друга).
- Каждый объект относится к тому кластеру, к центру которого он ближе всего.
- Когда все объекты отнесены к тому или иному кластеру их центры пересчитываются: рассчитывается геометрический центр кластера.
- Снова повторяются этапы 2 и 3: каждый объект относится к тому или иному кластеру и центры кластеров снова пересчитываются, этот процесс называется «итерация» (приближение).
- Процесс повторяется, пока изменения в центрах кластеров не станут равны 0 (достигнуто оптимальное решение) или не будет превышено допустимое число итераций.
Содержание
Запуск процедуры
Для запуска процедуры заполните раздел «Параметры»:
- Выбранные переменные — выберите (перетащите из Структуры) переменные, которые будут участвовать в кластерном анализе. Рекомендуется использовать
количественные(псевдоколичественные) либо бинарные переменные. Данный метод достаточно хорошо работает и с 
номинальными переменными, представленными в виде совокупнсоти бинарных значений. Для этого разверните в структуре нужныю переменную, отметьтье (используя Shift или Ctlrl) нужные значения и перетащите их в «Выбранные переменные». - Стандартизация переменных: если Вы используете переменные, замеренные в различных единицах измерения (например, «возраст» в годах и «доход» в рублях, тогда доход окажет на результат анализа гораздо большее влияние, чем возраст, просто потому что поскольку имеет более длинную шкалу), то, имеет смысл привести все переменные к единой единице измерения: одно стандартное отклонение. Стандартизация оказывает влияние только при использовании Евклидового расстояния
, поскольку другие методы не требуют стандартизации.
- Не стандартизовать — программа не производит стандартизации при расчете расстояний.
- Z-очки — программа производит стандартизацию переменных (рассчитывает на сколько стандартных отклонений индивидуальное значение отклоняется от среднего по совокупности. Эффективно при использовании нормально распределенных и бинарных переменных.
- Перевести в интервал от 0 до 1 — программа переводит все переменные в стандартный интервал, таким образом, что минимальное значение соответствует 0, а максимальное — 1.
- Другие способы предварительной стандартизации доступны в процедуре «Преобразование/Стандартизация».
- Число кластеров: укажите, на сколько кластеров (групп) программа должна разделить совокупность. Обычно начинают анализ с 2х кластеров и постепенно повышают число кластеров до определения оптимального решения.
- Точность (зн. после запятой): точность расчетов в промежуточных и итоговых таблицах.
- Максимальное число итераций: количество повторных перерасчетов кластеров. Если у Вас очень много документов, то возможно потребуется уменьшить число итерациий, чтобы расчеты произволились быстрее (при небольшой потере точности).
- Отображать вес переменных — если отметить эту опцию, то рядом с переменной в таблице будет показан ее вес относительно способности дифференцировать (различать) кластеры. Чем выше вес (от 0 до 1) тем сильнее различаются кластеры по данной переменной.
- Подсвечивать различия (% от в целом) — подсвечивать наиболее отличающиеся от ситуации «в целом»(последний столбец) конечные центры кластеров.
- Зеленым цветом выделяются значения центров кластеров, которые значительно меньше среднего по совокупности,
- Красным — те, которые значительно больше среднего по совокупности.
- Вы можете указать % отличия от «В целом» (чем больше — тем более явные различия будут выделены цветом.
- Способ определения расстояния: здесь можно выбрать метод определения расстояния между объектами.
- Евклидово расстояние: между парой объектов рассчитывается геометрическое расстояние – чем дальше геометрически расположены объекты друг от друга, тем больше Евклидово расстояние. Евклидово расстояние применимо как количественных ли псевдо-количественных, так и для бинарных переменных,
- Коэффициент Пирсона: между парой объектов рассчитывается коэффициент Пирсона. Чем больше коэффициент Пирсона, тем теснее объекты коррелируют друг с другом. (Для определения расстояния программа использует выражение 1-Коэффициент Пирсона). Коэффициент Пирсона применим только для количественных или псевдо-количественных переменных.
- Коэффициент Жаккара— специально разработан для бинарных переменных (совокупности бинарных значений). При использовании смешанного набора переменных (бинарных и количественных) не рекомендуется.
- Евклидово расстояние
После того как Вы указали требуемые переменные и параметры, нажмите кнопку [Пересчитать] . Содержание
Страница Результат
Содержит основную информацию о результатах кластерного анализа в ряде таблиц.
Таблица «Характеристики / конечные центры кластеров» содержит информацию о параметрах каждого кластера. Предпочтительны компактные кластеры, то есть те, у которых небольшое среднее и небольшое максимальное расстояние до центра. Так же стоит обратить внимание и на объем кластеров (сколько объектов входит в состав каждого кластера).
- Строка » Силуэтная мера связности и разделения кластеров [-1..+1]» — см.ниже Интегральная оценка результатов.
- Среднее расстояние между центрами кластеров — см.ниже Интегральная оценка результатов.
- Строка «Объем кластера » — количество объектов, включенных в состав данного кластера.
- Строка «Среднее расстояние до центра » — среднее расстояние от каждого кластера до центра кластера.
- Строка «Минимальное расстояние до центра» — расстояние от центра кластера до ближайшего объекта — члена кластера.
- Строка «Максимальное расстояние до центра» — расстояние от центра кластера до самого дальнего объекта — члена кластера.
- Далее идет список переменных, каждой из которых в соответствующем столбце указан центр каждого кластера. Конечные центры кластеров представляют собой основу анализа полученного кластерного решения. Для каждой переменной (строки) указано ее среднее значение в том или ином кластере (столбцы с номерами), для бинарных переменных указана доля объектов с данным значением среди всех объектов данного кластера. Так, если в столбце кластера К1 в строке «Мужской» указана «1», значит все объекты этого кластера — мужчины. Напротив, «0» означает, что в данном кластере нет мужчин, а «0,5» означает, что половина кластера — мужчины. Каждый кластер стоит проинтерпретировать, исходя из значений переменной.
- Столбец «В целом» содержит суммарную (объем кластера) и средние значения по каждой характеристике и переменной.
Таблица «Конечные центры кластеров» содержит основну для анализа кластерного решения – таблицу конечных центров кластеров. Для каждой переменной (строки) указано ее значение в том или ином кластере (столбцы с номерами), для бинарных переменных указана доля объектов с данным значением среди всех объектов данного кластера. Так, если в столбце кластера К1 в строке «Мужской» указана «1», значит все объекты этого кластера — мужчины. Напротив, «0» означает, что в данном кластере нет мужчин. Каждый кластер стоит проинтерпретировать, исходя из значений переменной.
В скобках для каждой переменной подсчитана важность ее участия в разделении кластеров. Чем выше значение в собках — тем важнее обратить внимание на эту переменную.
Таблица «Расстояния между кластерами». Расстояния между кластерами по определению должны быть максимальны. Например, Вы выбираете, остановиться на решении с 3 или с 4 кластерами. Если по таблице расстояний для решения с 4 кластерами Вы видите что два кластера не сильно отличаются друг от друга, то решение с тремя достаточно удаленными друг от друга кластерами будет оптимальнее. 
Совет: для того, чтобы работать с кластерами было более удобно — дайте названия каждому кластеру. Для этого достаточно щелкнуть по заголовкам столбцов в любой таблице и ввести название кластера.
Интегральная оценка результатов кластеризации — выбор оптимального числа кластеров
- 1 означала бы, что все наблюдения расположены точно в центрах их кластеров.
- −1 означало бы, что все наблюдения расположены в центрах некоторых других кластеров.
- 0 означает, что наблюдения расположены в среднем на равных расстояниях от центра их кластера и центра ближайшего кластера.
- Плохое качество разделения: от -1 до 0,2
- Среднее качество разделения: от 0,2 до 0,5
- Хорошее качество разделения: от 0,5 до 1.
Подробнее см. L. Kaufman, P. Rousseeuw Finding Groups in Data: An Introduction To Cluster Analysis. Вместе с тем, при выборе кластерного решения из 2х, 3х 4х и т.д. числа кластеров, стоит учитывать не только числовые, но и содержательные характеристики кластеров (таблица Конечные центры кластеров) — насколько Вам понятно содержание кластеров и насколько, найденные программой кластеры соответствуют реальной картине.
Страница Одномерная проекция
На данной странице вы можете посмотреть по каждой переменной, насколько заметна ее роль в выделении кластеров. Выберите любую переменную или значение в списке «Выбранные переменные» (в параметрах процедуры) и Вы увидите графическое распределение по данной переменной с указанием доли каждого кластера. Если переменная представлена несколькими бинарными значениями, то диаграмма для каждого из них будет одинакова, поскольку это диаграмма в целом по всей переменной. Если переменная заметно влияет на результат кластеризации, то доли кластеров будут смещены к определенным полюсам или значениям этой переменной.
Например, если мужчины и женщины представляют сбой разные кластеры (К1 и К2) то на диаграмме, в столбике «Мужчины» будет сильно преобладать доля кластера К1, а в столбике «Женщины» — доля кластера К2. Если пол не существенно влияет на результаты кластеризации, то мужчины и женщины будут с примерно равной вероятностью попадать в разные кластеры и доля К1 и К2 будет примерно одинакова в столбиках «Мужчины» и «Женщины».
Если, речь идет о количественной переменной, допустим, «Возраст (в годах)», то при ее существенной роли в кластеризации, можно будет заметить преобладание К1 среди молодых, а К2 — среди пожилых возрастов.
Содержание
Страница Двухмерная проекция
Здесь Вы можете графически оценить результаты кластеризации, если наберетесь терпения :). Двухмерная проекция здесь отражает расстояния между всеми объектами, участвующими в кластерном анализе, таким образом, вы сможете графически, на одной картинке, оценить насколько удачно программа распределила объекты по кластерам. К сожалению, стоит учитывать nhb момента:
- Двухмерная проекция является всего лишь проекцией матрицы расстояний между каждой парой объектов на двухмерную плоскость и отображает эти расстояния с определенным искажением, стрессом, который нарастает, в зависимости от числа объектов.
- Чтобы уменьшить данное искажение, программе требуется достаточно долгая вычислительная работа (итерации).
- Поскольку размер исходной анализируемой матрицы зависит от квадрата числа документов (нужна матрица расстояний между каждой парой документов), то при большом числе документов(несколько тысяч) процедура может быть недоступной всвязи с недостатком оперативной памяти. В этом случае кнопка [
Запуск процедуры] будет неактивной.
При переходе на страницу Вы увидите рекомендуемое программой число итераций, расчитанное в зависимости от числа анализируемых объектов (число кластеров не играет роли — анализируются расстояния между объектами). Вы можете уменьшить число итераций, чтобы ускорить процесс получения двухмерной проекции или, наоборот, увеличить число итераций, чтобы уменьшить искажение (хотя значительное увеличение числа итераций лишь немного уменьшает искажения — с каждой итерацией искажения становятся меньше). В любом случае, после [Запуска процедуры] вы можете остановить процесс итераций, нажав справа внизу кнопку [ 
Stop] . Но имейте ввиду, что программа остановится не сразу, а по завершению текущей итерации, что может занять определенное время. В результате, вы получите диаграмму, на которой будут изображены все объекты, участвующие в кластеризации, причем цвет и форма будут показывать, к какому из кластеров они относятся. Используйте кнопку 
над диаграммой, чтобы определить размер точек и наличие подписей. 
Например, по приведенной ниже картинке можно судить о том, что программа достаточно четко распределила объекты по 5 кластерам, хотя некоторые отдельные объекты попадают в поле соседних кластеров. Вместе с тем, трудно сказать в чем причина такого неудачного распределения отдельных объектов — в неудачной кластеризации или в искажении, возникшем при формировании проекции. Так же, обратите внимание на синий (самый большой) кластер. Графически видно, что он напрашивается быть разделенным на два кластера. 
Содержание
Страница Качество разделения
С помощью этой страницы Вы можете выбрать оптимальное число кластеров на основе значения Силуэтной меры.
- В начале заполните параметры — выберите переменные и назначьте особенности вычислений расстояний.
- Затем Укажите диапазон — минимальное и макасимальное количество кластеров, которые Вы желаете рассмотреть.
- Нажмите [Запуск процедуры].
Программа построит График изменения Силуэтной меры и рассчитает Таблицу основных показателей кластеров .
- С помощью графика Вы можете выбрать самое высокое значение Силуэтной меры на выбранном диапазоне кластерных решений.
- Если Вас интересует объем (число объектов) каждого кластера в диапазоне кластерных решений — перейдите на вкладку Объем кластеров .
- Вы можете остановить выполнение процедуры нажав [STOP] в правом нижнем углу окна программы.
Содержание
Страница Обратное решение
- В начале заполните параметры — выберите переменные и назначьте особенности вычислений расстояний.
- Затем укажите переменную — разделяющую объекты на группы (кластеры).
- Нажмите [Запуск процедуры].
Сохранение результатов классификации
В том случае. когда представленное кластерное решение вас устраивает, вы можете сохранить результат классификации, используя кнопки слева внизу окна.
- Кнопка [
Принадлежность к кластеру] создает новую переменную в которой каждому объекту ставится в соответствие номер кластера, к которому он принадлежит. - Кнопка [Расстояние до центра кластера] создает новую переменную, в которой каждому объекту ставится в соответствие расстояние до центра кластера, к которому он принадлежит. Чем больше расстояние до центра кластера, тем менее типичным членом является данный объект в кластере.
Совет: для того, чтобы работать с кластерами было более удобно — дайте названия каждому кластеру. Для этого достаточно щелкнуть по заголовкам столбцов в любой таблице и ввести название кластера.
Дополнительно
- Если выбрана сегментирующая переменная, то справа внизу окна присутствует переключатель групп для анализа. Например, если таковой выбрана переменная Пол, то с его помощью вы можете быстро посмотреть таблицу для всего массива, для мужчин, для женщин. Более сложную сегментацию вы можете настроить в меню программы с помощью кнопки [Подмассив].
- Вы можете копировать содержимое любой страницы в буфер обмена с помощью кнопки [Копировать] в меню программы.
Содержание
Вычислить диапазон расстояний до числа соседних объектов (Пространственная статистика)
Возвращает минимальные, максимальные и средние расстояния до указанного N-го ближайшего соседа (N – входной параметр) для набора объектов. По мере работы инструмента производится запись сообщений.
Иллюстрация
Использование
- Для данного набора объектов инструмент возвращает минимальные, максимальные и средние расстояния до указанного числа соседних объектов ( N ). Пример: если указать значение 8 для параметра Соседи , инструмент создаст список расстояний от каждого объекта до его восьми ближайших соседей, затем на основе этого списка производится расчет минимального, максимального и среднего расстояний.
- Максимальное значение – это расстояние, в пределах которого каждый из объектов имеет хотя бы N соседних объектов.
- Минимальное значение – это расстояние, в пределах которого хотя бы один из объектов имеет N соседних объектов.
- Среднее значение – это среднее расстояние, в пределах которого объекты имеют N соседних объектов.
Внимание:
Следует обязательно производить проецирование ваших данных, если область исследования превышает 30 градусов. Хордовые расстояния не обеспечивают точных оценок геодезических расстояний, превышающих 30 градусов.
Параметры
Входные объекты
Класс или слой пространственных объектов, применяемый для расчета статистики по расстояниям.
Число соседей
Число соседних объектов (N), принимаемых во внимание для каждого объекта. Это число должно быть целым, оно должно находиться в пределах от единицы до полного количества объектов в классе. Составляется список расстояний от каждого объекта до его N-х соседних объектов, затем в окно результатов выводится максимальное, минимальное и среднее расстояние.
Метод расстояний
Определяет, как рассчитываются расстояния от одного объекта до соседнего объекта.
- Евклидово — Расстояние по прямой линии между двумя точками (как ворона летает)
Производные выходные данные
Минимальное расстояние до N соседей.
Среднее расстоянии до N соседей.
Максимальное расстояние до N соседей.
arcpy.stats.CalculateDistanceBand(Input_Features, Neighbors, Distance_Method)
Input_Features
Класс или слой пространственных объектов, применяемый для расчета статистики по расстояниям.
Число соседних объектов (N), принимаемых во внимание для каждого объекта. Это число должно быть целым, оно должно находиться в пределах от единицы до полного количества объектов в классе. Составляется список расстояний от каждого объекта до его N-х соседних объектов, затем в окно результатов выводится максимальное, минимальное и среднее расстояние.
Distance_Method
Определяет, как рассчитываются расстояния от одного объекта до соседнего объекта.
- EUCLIDEAN_DISTANCE — Расстояние по прямой линии между двумя точками (как ворона летает)
Производные выходные данные
Минимальное расстояние до N соседей.
Среднее расстоянии до N соседей.
Максимальное расстояние до N соседей.
Пример кода
CalculateDistanceBand, пример 1 (окно Python)
Окно скрипта Python и демонстрация выполнения функции CalculateDistanceBand .
import arcpy arcpy.env.workspace = "c:/data" mindist, avgdist, maxdist = arcpy.stats.CalculateDistanceBand("Blocks", 10, "EUCLIDEAN_DISTANCE")CalculateDistanceBand, пример 2 (автономный скрипт)
Следующий автономный Python скрипт демонстрирует, как использовать функцию CalculateDistanceBand .
# import module import arcpy # Set geoprocessing workspace environment arcpy.env.workspace = "c:/data" # Set variables infc = "Blocks" field = "POP2000" outfc = "PopHotSpots" neighbors = 10 # Run the CalculateDistanceBand tool to get a distance for use with the Hot Spot # tool from the tool result object mindist, avgdist, maxdist = arcpy.stats.CalculateDistanceBand(infc, neighbors, "EUCLIDEAN_DISTANCE") # Run the Hot Spot Analysis tool, using the maxdist output from the Calculate # Distance Band tool as an input arcpy.stats.HotSpots(infc, field, outfc, "Fixed Distance Band", "EUCLIDEAN_DISTANCE", "None", maxdist)Параметры среды
Особые случаи
До начала анализа геометрия пространственных объектов проецируется в Выходную систему координат. Во всех математических вычислениях учитывается пространственная привязка Выходной системы координат. Если выходная система координат выражена в градусах, минутах и секундах, то геодезические расстояния рассчитываются с помощью хордовых расстояний.
Информация о лицензиях
- Basic: Да
- Standard: Да
- Advanced: Да
Связанные разделы
- Обзор группы инструментов Утилиты
- Поиск инструмента геообработки
- Анализ горячих точек
- Анализ кластеров и выбросов (Anselin Локальный индекс Морана I)
- Пространственная автокорреляция (Глобальный индекс Морана I)
- Кластеризация с высокими/низкими значениями (Глобальный индекс Getis-Ord G)
ИСПОЛЬЗОВАНИЕ КРИТЕРИЯ СРЕДНЕГО РАССТОЯНИЯ ДЛЯ ВЫЯВЛЕНИЯ НОВИЗНЫ В ДАННЫХ Текст научной статьи по специальности «Математика»
В статье рассмотрены особенности выявления новизны в данных, а также общие методы ее выявления. Поскольку отсутствие шума в обучающей информации является определяющим фактором для построения на ней качественных классификаторов в машинном обучении с учителем, то рассмотрен такой практически важный частный случай поиска новизны , когда она определяется в отдельных классах обучающих данных после того, как в этих данных устранены все выбросы . Для большей определенности при поиске новизны предложена ее геометрическая интерпретация в пространстве значений признаков объектов в виде изображающей объект класса точки, находящейся снаружи минимальной гиперокружности, описанной вокруг остальных изображающих точек объектов класса.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Крашенинников А.М.
КОРРЕКЦИЯ ОБУЧАЮЩИХ ВЫБОРОК С УЧЕТОМ ПОГРЕШНОСТЕЙ ИЗМЕРЕНИЯ ХАРАКТЕРИСТИК ОБЪЕКТОВ ПРИ ПОСТРОЕНИИ КЛАССИФИКАТОРОВ ПО МЕТОДОЛОГИИ ОБУЧЕНИЯ С УЧИТЕЛЕМ
Препроцессорная обработка множеств прецедентов для построения решающих функций в задачах классификации
Оценка точности определения координат объекта в рабочей зоне стереодальномера
Разбиение на классы методом альтернативной коллективной адаптации
Кластерный анализ данных и выбор объектов-эталонов в задачах распознавания с учителем
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.USING THE MEAN DISTANCE CRITERION TO IDENTIFY NOVELTY IN THE DATA
The article discusses the features of identifying novelty in data, as well as general methods for identifying it. Since the absence of noise in the training information is a determining factor for building high-quality classifiers on it in supervised machine learning, such a practically important special case of the search for novelty is considered, when it is determined in separate classes of training data after all outliers have been eliminated in these data. For greater definiteness, when searching for novelty, its geometric interpretation in the space of object feature values.
Текст научной работы на тему «ИСПОЛЬЗОВАНИЕ КРИТЕРИЯ СРЕДНЕГО РАССТОЯНИЯ ДЛЯ ВЫЯВЛЕНИЯ НОВИЗНЫ В ДАННЫХ»
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
Использование критерия среднего расстояния для выявления новизны в данных
А.М. Крашенинников Московский государственный университет пищевых производств, Москва
Аннотация: В статье рассмотрены особенности выявления новизны в данных, а также общие методы ее выявления. Поскольку отсутствие шума в обучающей информации является определяющим фактором для построения на ней качественных классификаторов в машинном обучении с учителем, то рассмотрен такой практически важный частный случай поиска новизны, когда она определяется в отдельных классах обучающих данных после того, как в этих данных устранены все выбросы. Для большей определенности при поиске новизны предложена ее геометрическая интерпретация в пространстве значений признаков объектов в виде изображающей объект класса точки, находящейся снаружи минимальной гиперокружности, описанной вокруг остальных изображающих точек объектов класса. Степень удаленности (уровень новизны) р точки относительно всех остальных выражена через радиус и центр данной гиперокружности. С целью качественной оценки уровня новизны объектов класса рассмотрены три ее градации: ближняя, средняя и дальняя. Поскольку прямое использование геометрической интерпретации при поиске новизны требует большого числа вычислений, то для практических расчетов предложен непараметрический критерий статистического характера F, названный критерием средних расстояний. Зависимость статистического критерия F от геометрической характеристики новизны p определена на специальных множествах точек — n-мерных кубах в пространстве с метрикой «манхеттенское расстояние». При анализе данной модели определена верхняя оценка значений F(p) для дополнительных точек, находящихся внутри куба (при 0 < p < 1), и найден вид критерия для внешних по отношению к кубу точек (p >1). По данным зависимостям найдены более общие формулы зависимости F(p) для классов произвольного вида с параметрами . Из данных формул получены значения критерия F для ближней, средней и дальней новизны. При локальном удалении новизны в классах обучающих данных рассмотрены однократный и итерационный подходы. В первом случае новизна заданного уровня определяется и удаляется из класса А только один раз. Во втором случае — итерационным образом, до получения кластера. Разработана общая структура программного обеспечения, реализующего оба метода, и алгоритмы функций.
Ключевые слова: обучающие данные, классификатор, выбросы, новизна, обнаружение новизны, геометрический подход, статистический критерий.
Для идентификации объектов в системах искусственного интеллекта их задают при помощи значений существенных свойств, которые представляют в виде вектора < х >= . Это дает возможность взаимнооднозначно сопоставить каждому объекту с соответствующим ему вектором характеристик a = изображающую точку a в n-мерном
пространстве значений характеристик и. Для того, чтобы системы искусственного интеллекта могли применять к распознанным объектам соответствующие им методы анализа и воздействия, рассматриваемые объекты подразделяют на отдельные классы = .
Задачу распознавания, заключающуюся в отнесении некоторого нового объекта, заданного вектором своих свойств а = к некоторому известному классу Ai из совокупности , называют классификацией, а специальный алгоритм ц, применяемый для ее решения, называют классификатором или решающей функцией. Классификатор обеспечивает отображение объекта со свойствами а = на совокупность классов : ц : ( а) ^ .
В случае технологии обучения с учителем классификаторы строятся по обучающей выборке, которая состоит из примеров — объектов с заданными свойствами а , для которых уже указаны соответствующие им классы и5: ТЕ = < ге? >= < ( а5, и5)>.
Для построения классификаторов применяются: нейронные сети, методы геометрические с использованием метрик в пространстве значений признаков, статистические подходы, методы регрессионного анализа (линейный, логистический, полиномиальный, метод опорных векторов, деревья решений, случайный лес, ридж-регрессия, лассо-регрессия), метод kближайших соседей.
Для построенного классификатора ц качество оценивается долей правильно отображенных на множествах классов новых предъявленных объектов. С этой целью обычно применяется специальный контрольный набор примеров, называемый тестовыми данными.
Общее качество классификатора при обучении с учителем в основном определяется применяемыми при его построении обучающими данными. Основным требованием к ним является следующее: примеры из одного
класса должны образовывать в пространстве признаков кластер, т.е. плотно сгруппированную совокупность точек, которая расположена отдельно от других таких же совокупностей точек, задающих объекты других классов. Данное требование называется гипотезой компактности [1]. По ней образы классов в пространстве признаков U должны составлять кластеры. Выполнение гипотезы компактности гарантирует хорошую отделимость их в пространстве U при помощи специальных гиперповерхностей.
В обучающих данных отклонения от гипотезы компактности (шум) обычно возникают из-за целого ряда ошибок, возникающих при их формировании [2]. Нарушение шумом условия компактности классов в обучающих данных ухудшает условия для построения классификатора, а также его качество — способность правильно классифицировать новые предъявляемые объекты. В частности, те нейросети, которые были построены на зашумленных данных, при последующей классификации новых объектов повторяют те же ошибки, которые содержались в их обучающих данных [3,4].
Основную долю шума в обучающих данных составляют выбросы и новизна. Выбросами называют такие примеры, для которых по тем или иным причинам неправильно заданы их классы, т.е. свойства объекта не характерны для того класса, к которому он причислен. Новизной называют примеры из обучающей выборки, у которых изображающие точки в пространстве U находятся далеко от кластеров всех классов.
Удаление выбросов и новизны при коррекции данных в общем случае может выполняться и одновременно и по отдельности. Для обучающих данных с точки сокращения объема вычислений оптимальный способ коррекции заключается в удалении всех выбросов и последующем удалении новизны.
Методы, применяемые для идентификации новизны, сходны с методами классификации и определения выбросов. Основные группы методов следующие.
1. Генерирование правил. Данные методы генерируют правила, по которым для объекта подтверждается нормальное поведение объекта либо его отклонение от нормы, при котором он является новизной [5,6,7].
2. Нейронные сети и их разновидности (многослойные персептроны; самоорганизующиеся карты (SOM); сети, основанные на привыкании; нейронные деревья; автоассоциативные сети; сети теории адаптивного резонанса (ART); сети радиальных базисных функций (RBF); сети Хопфилда; колебательные сети; байесовские сети). Сеть предварительно обучают на обычных объектах. Новизну определяют по реакции на них нейронной сети [8,9,10].
3. Статистический подход (параметрический и непараметрический), основанный на применении статистических критериев [9-13].
4. Машины опорных векторов (SVM) Подход предполагает, что обычные (нормальные) точки находятся в области с высокой их плотностью, их можно окружить сферой малого радиуса [8]. Отличающиеся данные лежат в областях с низкой плотностью [14,15].
5. Подходы на основе метода ближайшего соседа. По нему предполагается, что нормальные точки имеют близких соседей, а отличающиеся от них расположены удаленно от других точек. Точка считается новизной, если ее расстояние до k ближайших соседей превышает заданное пороговое значение, или на основании расчета фактора локального выброса (LOF) [16,17].
Исследование новизны в данных, как объектов, существенно отличающихся от уже известных, представляет собой самостоятельную
ценность в биологии, экологии, медицине, социологии, информатике и других областях науки и практики [18-20].
Исходный класс обучающей выборки с исправленными выбросами после выявления и последующего удаления в нем новизны представляет собой кластер. Данный случай является одним из возможных вариантов задачи выделения кластеров в наборах данных. Поэтому общие методы выявления новизны во многом сходны с методами кластерного анализа [2123].
Поскольку в основе геометрических методов определения новизны в пространстве ^ как и у геометрических методов классификации [24-26], лежит пространственная интерпретация объектов, то они имеют наглядный геометрический смысл, позволяющий применять для оценки новизны соответствующие аналогии.
Геометрический подход к интерпретации уровней новизны рассмотрен в п.1. На основе идей метода опорных векторов предложена численная интерпретация понятий отсутствия новизны, а также близкой, средней и дальней новизны. Для практического определения новизны заданного уровня предложен статистический критерий, который позволяет существенно упростить методику определения новизны по сравнению с чисто геометрическими методами.
Связь введенных геометрической и статистической характеристик новизны найдена в п.2 с использованием модели в виде и-мерных кубов. На основе данной модели выполнен переход к общей формульной зависимости для произвольных классов, а также к пороговым значениям уровня новизны.
Для практического определения новизны в п.3 предложены два подхода — однократное удаление и итерационное. Дана структуризация необходимого программного обеспечения и алгоритм, реализующий однократное удаление.
В п.4. введено понятие кластера c фиксированным предельным уровнем близости точек. Рассмотрены кластеры первого, второго и третьего типов, соответствующие уровням близкой, средней и дальней новизны. Предложен алгоритм для определения данных кластеров в классах обучающей выборки. Даны оценки сложности алгоритмов одноразового и итеративного выделения новизны.
1. Численная оценка новизны в классах обучающей выборки
Рассмотрим обучающую выбору ТЕ, состоящую из примеров, в которой на первом этапе коррекции уже удалены или скорректированы все выбросы. Поскольку в обучающих выборках плотность объектов в разных классах примерно одинакова, то в этом случае новизна будет локализована в отдельных классах обучающих примеров = . Поэтому в дальнейшем будем рассматривать только данный локальный вариант определения новизны, которая содержится в фиксированном классе.
В основу численной оценки степени удаленности выделенных объектов от всех остальных объектов класса предложено принять геометрическую интерпретацию, близкую к методу опорных векторов. Представим множество изображающих точек класса А в виде представляет собой кластер, а точка N существенно удалена от точек из . Интегрально положение точек кластера в пространстве U можно задать при помощи описанной вокруг них гиперсферы минимального радиуса R, а также центра гиперсферы — некоторой точки Сеь При этом близость точки N ко всем оставшимся точкам из множества точек А можно оценить при помощи расстояния р( Ы, Со1) от нее до центра кластера Сеь
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
В качестве относительной меры удаленной точки N ко всем оставшимся точкам класса А предложено выбрать отношение, которое назовем уровнем близости точки N ко всем оставшимся точкам класса А:
Для качественной оценки наличия новизны и степени удаленности точки а по отношению к кластеру предложены следующие градации новизны.
1. Отсутствие новизны (точка N лежит внутри кластера Сс\ или незначительно выходит за его пределы):
2. Ближняя новизна. Назовем ближней новизной такие точки N, для которых индекс р( N ) изменяется в пределах от 1,5 до 2:
3. Средняя новизна. р( N ) изменяется в пределах:
4. Дальняя новизна:
Таким образом, пороговыми значениями для качественной оценки уровня близости р( N ) выбраны следующие три ее значения: р = 1,5; 2 и 2,5. Выбор конкретного значения уровня близости р определяется спецификой конкретной предметной области.
Очевидно, что для каждой проверяемой точки N построение описанной гиперсферы вокруг оставшихся точек класса с определением ее радиуса Я и
центра Сс1 требует значительного числа вычислений. Для существенного их сокращения т унификации для каждого объекта а класса А/ относительный уровень близости р( а(р), А/ \ a)ГR предложено косвенно оценивать при помощи отношения следующих статистических характеристик рассматриваемой точки а и всего класса А/.
1) р( а (р)) = Хр( а (р), а»)Шс1 — частное среднее выборочное значение расстояния от выделенного объекта а(р) до всех ЫС1 объектов а класса А/ (в том числе — до самого объекта а),
2) р = Хр( а’, а)/ЫС12 — общее среднее выборочное расстояний между всеми парами объектов < а„ а">класса А/.
Для упрощения расчетов в общем среднем выборочном значении р учитываются, как пары значений <р( аг, а"); р( а", а*)>, так и значения
С использованием данной замены вместо геометрической характеристики близости р( а ) точки класса а ко всем оставшимся предложено рассмотреть статистический критерий Б( а(р), А/ ) оценки положения объекта а(р) относительно всего анализируемого класса А/. Б( а (р),А/) = р( ас(р)) / р. (3)
Величина Ос(р), А/ ) названа критерием средних расстояний. Данный критерий по принципу действия сходен с критерием метода к ближайших соседей [27,28] с той разницей, что в нем суммируются расстояния не до части (к), а до всех объектов рассматриваемого класса.
Таким образом, использование геометрической характеристики (уровня) новизны позволяет дать четкую ее пространственную интерпретацию и, в частности, обоснованно выбирать пороговые значения при ее поиске. В то же время, применение статистического критерия Б позволяет существенно упростить поиск новизны в вычислительном плане.
Очевидно, существует монотонная зависимость критерия Б( ах(р), Лу) от уровня близости р( а ). Для обоснованного применения критерия требуется определить вид этой зависимости Б( а(р), Лу) от р( а ), т.е. связать между собой рассмотренные геометрическую и статическую оценку новизны. При этом, в частности, возникает вопрос, какие значения критерия Б соответствуют пороговым значениям р = 1,5; 2,0; 2,5 для произвольных классов, имеющих параметры ? Для определения зависимости Б от р используем специальную модель.
2. Определение связи между геометрическим уровнем новизны р и статистическим критерием F средних расстояний
В качестве модели гиперсферы в и-мерном пространстве, равномерно
заполненной точками, принят и-мерный куб. В пространстве и введена метрика «манхеттенское расстояние». Связь значений критерия средних расстояний Р и геометрического уровня близости точек р рассмотрена на этой геометрической модели.
2.1. Куб Сид. Суммы расстояний между его точками
Рассмотрим в и — мерном пространстве значений характеристик объектов И (0x^2. хи) и-мерный куб Сид, имеющий следующую структуру.
По каждой оси куба, начиная от начальной О, равномерно с шагом 1 расположено д точек. Начальная точка куба имеет координаты (0,0. 0). В метрике р «Манхэттенское расстояние» куб Сид является аналогом гипершара — кластера, равномерно заполненного точками. Общее число V точек в кубе равно ди. Начальная точка куба имеет координаты (0,0. 0). Радиус куба R равен и(д -1)/2. Его центр С^ имеет координаты ((д -1)/2, (д -1)/2, .,(д -1)/2).
С учетом величины радиуса куба Я = и(д-1)/2 в качестве реперной точки anov(p), соответствующей выбранному значению р( некоторой точки а принята точка с координатами: аиоу(р) =( — ри(д-1)/2,0. 0). Величина Ар = — ри(д-1)/2 задает сдвиг точек аиоу(р) относительно
начальной точки О по оси с1. Пороговым значениям р = 1,5; 2 и 2,5 соответствуют точки с координатами: а_(1.5) =(-Ль0. 0) = (-п(ц-1)/4,0. .,0), аиД2.0) =(-Л2,0. 0) = (-п(ц-1)/2,0. .,0),
Для примера на рис.1 в системе координат Ос1Х2 показан куб С 3 для случая п = 2, ц = 3. В нем число точек: У= 32 = 9. Радиус Я = п(ц -1)/2 = 2. Центр Сс1 имеет координаты (1, 1). Координаты реперных точек апоу1= апо^(1.5), an0v2= апД2.0), anOVз= anOV(2.5) будут следующие: апом1 = (-п(ц-1)/4; 0) = (-1; 0), а^^ (-п(ц-1)/2; 0) = (-2; 0), ~апоУ3(-3п(ц-1)14; 0)
^гюм 3 2 апохЛ О 2
2 — — — Рис. 1. Куб С 3 (п = 2, ц = 3) с реперными точками апоу1, апоу2, апоу3
Для выбранных реперных точек апоу1, anov2, апоу3 в рассмотренной модели в точности выполняются геометрические требуемые соотношения: р ( anovl, Сс1)/Я = 1,5; р ( anov2, Сй)/Я = 2; р ( anovз, С^/Я = 2,5.
Определим связь между геометрической характеристикой (уровнем новизны р) и статистическим критерием средних расстояний F.
В множестве точек А/ =, моделирующем класс, содержащий кластер (Спц) и возможную новизну ( апоу(р)), общее число элементов: ИС1 = У+1= цп+1.
Сумма всех расстояний между точками в кубе Спц равна: р( Спц) Мс1 2 = Ц( Спц)р( ~а\ ~а») = пц2п-1(ц2-1)/3.
Также важной характеристикой модели является сумма всех расстояний от начальной точки О = (0,0. 0) до всех точек кластера Сид: Р( О )Ncl = 2р( О, ~аи) = иди(д-1)/2. В множестве точек Лу = с точки зрения анализа удаленности дополнительной точки аи0у(р) ко всему кубу Сид возможны две принципиально отличные возможности.
2.2. Анализ внутренних точек кластера
Соответственно, для значения критерия у внутренней точки выполняется следующее неравенство:
Величина критерия для дополнительной точки, совпадающей с точкой О, на множестве точек Лу= равна: Б( О, Лу) = [иди(д- 1)/2]/[2иди(д-1)/2 + ид2и-1(д2-1)/3] = 1/[2 + (2/3) ди-1(д+1)] .
Учитывая, что общее число элементов в множестве : Ncl = V+1= ди +1, формула для предельного значения критерия для внутренних дополнительных точек у произвольных классов с параметрами принимает вид: Б( О, Л) = 1,5/[^ + (Ncl -1)(и-1)/и + 2].
Таким образом, в качестве критерия попадания дополнительной точки во внутреннюю часть кластера для произвольного класса с параметрами можно принять значение:
При Б( аиоу(р), Лу) > ¥и(и, ад) точка аиоу(р) является внешней (р > 1). Такая точка может быть новизной в классе с параметрами.
2.3. Анализ дополнительных точек, внешних по отношению к кластеру. У внешних точек аиоу(р) при Б( anov(p), Лу ) > ¥и(и, ад) уровень близости к центру кластера р > 1.
Поскольку из всех внутренних точек наиболее удаленной от центра куба является внутренняя точка О, то в качестве реперной точки аиоу(р), соответствующей значению р принимаем точку с координатами: аит,(р) = (-Лр,0. 0) = ( — ри(д-1)/2,0. 0).
Для перехода от суммы расстояний Хр( О, аи) (для начальной точки О) к расстояниям Хр( аит(р), аи) (для внешней реперной точки аиоу(р)) в рассматриваемой метрике необходимо к каждому из ди расстояний р( О, аи) в сумме Хр( О, аи) прибавить величину Др = ри(д-1)/2. При этом:
2р( ату(р), аи) = !р( О, аи) + ди Др = иди(д-1)/2+ риди(д-1)/4 = иди(д-1)(2+р)/4
С учетом данной суммы сумма всех расстояний между всеми парами объектов < ау, аи>множества равна:
!р( ау, аи) = 2(Сид)р( ау, аи)+2£р( аиМ, аи) = ид2и-1(д2-1)/3 + иди(д-1)(2+р)/2= иди(д-1)[ди-1(д+1)/3+(2+р) /2].
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Подстановка сумм в формулу (3) дает для класса выражение критерия Б( апт(р), А/) средних расстояний через для внешней дополнительной точки апоу(р) через величину уровня удаленности р для данной точки:
б( а^, А/ ) = Нс1 -цр( ас, а-)/ ад av, а-) = ис1 -р+р)^/^-
В частности, для примера на рис.1 значения критерия Б для пороговых значений р = 1,5; 2,0; 2,5 будут следующими:
Отметим, что полученная формула справедлива только для внешних по отношению к кубу Спц точек, для которых Я>1. Для внутренних точек апоу(р) куба (Я<1) не выполняется предложенный переход от р( О ) к р( апоу(р)). Поэтому для них полученная формула не верна.
Учитывая, что общее число элементов в множестве : ИС1 = У+1= цп +1, формула Б( anov(p), А/ ) для произвольных классов с параметрами дает следующее выражение для теоретического значения критерия для заданного уровня близости р:
В частности, для пороговых значений уровня новизны р = 1,5; 2,0; 2,5 формулы принимают следующий вид:
Бс (1,5) = Б( атг(1,5), А/) = Ыс1 /[2 + (8/21) (Ыс1 -1+ (Ыс1 -1)(п-1)/п)]; Бс (2,0) = Б( агт(2,0), А/) = Ыс1 /[2 + (1/3) (Ис1 -1+ N -1)(п-1)/п)]; Б, (2,5) = Б( а«^), А/) = Ыс1 /[2 + (8/27) (Ыс1 -1+ (Ыс1 -1)(п-1)/п)].
3. Два подхода к обнаружению новизны. Вспомогательные функции для анализа новизны. Алгоритм CUR_NOVELTY однократного определения
новизны в заданном классе
Рассмотрим общую задачу определения и удаления новизны из класса А, содержащего Ncl объектов, при заданном пороговом значении уровня новизны р. В общем случае поиск новизны можно производить при числе объектов Ncl, не меньшем 3, поскольку иначе понятие новизны теряет смысл.
Исходя из специфики решаемой задачи удаления новизны в обособленных классах обучающих данных, возможны два основных подхода к обнаружению и удалению новизны: 1) однократный (слабый) и 2) итерационный (сильный).
При первом упрощенном (слабом) подходе новизна заданного уровня определяется и удаляется из класса А только один раз.
Однако, также, как и при устранении выбросов, удаление из класса А новизны уровня р (некоторого объекта < а< >) может порождать в сокращенном множестве А\ < ау >другую новизну уровня р. Данная ситуация при удалении новизны может повторяться неоднократно. Поэтому гарантированное удаление новизны заданного уровня может обеспечить только итерационный (сильный) способ ее удаления. Рассмотрим программную реализацию обоих методов.
Входными данными задачи, в которой рассмотрены свойства NI объектов некоторого класса обучающей выборки в и -мерном пространстве значений признаков и, является массив OB[n][Ncl], содержащий численные характеристики свойств объектов.
Для сокращения объема вычислений и упрощения программной структуры основных алгоритмов использованы следующие вспомогательные функции.
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
3.1. Функция МЛШ_ВЛТЛ_СЛЬСрасчета основных данных, необходимых для определения новизны
При определении новизны в заданном классе А[№1] наряду с массивом ОВ[п][№1], в качестве основных данных рассмотрим также:
1) матрицу DIST[Nc1][Nc1] расстояний между объектами в А,
2) вектор SИM[Nc1] сумм SИM[i] (!р( аг, аи), аи е А) расстояний от выбранного объекта \ (0 < \ < №1-1) до всех остальных объектов в А.
Поскольку расчет матрицы DIST является самым трудоемким при определении новизны, то предложено только один раз вычислять эти данные по массиву ОВ[п][№1], а потом корректировать их, не повторяя численных расчетов. При значительных величинах п и №1 такой подход существенно сокращает общий объем вычислений.
Предложено использовать полную матрицу расстояний, поскольку применение именно ее максимально ускоряет все последующие расчеты.
Вектор SИM[Nc1] удобен в качестве вспомогательного при коррекции данных.
Начальный расчет матрицы DIST[Nc1][Nc1] и вектора SИM[Nc1] по массиву ОВ[п][№1] производится функцией MAIN_DATA_CALC. Входные данные функции МЛ1М_ВЛТЛ_СЛЬС:
1) п — размерность пространства И характеристик оьбъектов,
2) №1 — число объектов в совокупности М,
3) ОВ[п][№1] — массив векторов значений характеристик для объектов из совокупности М,
4) ЯО(ОВ1,ОВ2,п) — функция расчета расстояния между объектами ОВ1,ОВ2 в заданной метрике пространства И.
Выходные данные функции МЛ1М_ВЛТЛ_СЛЬС:
2) вектор SИM[Nc1].
Для сокращения расчетов используется симметричность матрицы DIST.
Алгоритм функции следующий.
for i = 0 to Ncl-1 //Проход по всем компонентам вектора SUM и строкам
матрицы расстояния DIST
SUM[i] = 0; // Инициализация очередной компоненты вектора SUM for j = 0 to i-1 do SUM[i] += DIST^i^/суммирование уже вычисленных известных значений расстояний
DIST[i][i] = 0; // Задание значения диагональному элементу матрицы DIST.
for j = i+1 to Ncl-1 // Проход по всем еще не определенным компонентам
текущей строки матрицы DIST
DIST[i][j] = RO (OB[i], OB[j], n); //расчет очередного нового расстояния DIST[j][i] = DIST[i][j]; //формирование симметричного элемента матрицы SUM[i] + = DIST[i][j]; //наращивание компоненты SUM[i]
>//завершение прохода по компонентам вектора SUM и строкам матрицы
3.2. Функция NOVELTY_DETECTION определения новизны в множестве объектов
Однократное определение новизны по заданному уровню р заключается в выявлении всех точек класса, для которых значение критерия средних расстояний превышает пороговую величину. Основные данные для точек класса (матрица DIST[Ncl][Ncl] и вектор SUM[Ncl]) при этом считаются уже определенными ранее.
Определение массива NumNov[NNov] объектов, отнесенных к новизне заданного уровня производится функцией NOVELTY_DETECTION. Входные данные функции NOVELTY DETECTION:
1) n — размерность пространства U характеристик объектов,
2) Ncl — число объектов в классе,
3) вектор SUM[Ncl] сумм SUM[i] расстояний от выбранного объекта i до всех остальных объектов,
4)р — уровень проверяемой новизны.
Выходные данные функции NOVELTY_DETECTION:
1) NNov — число найденных объектов, отнесенных к новизне заданного типа,
2) NumNov[NNov] — массив номеров объектов, отнесенных к новизне.
Псевдокод функции NOVELTY_DETECTION имеет вид.
NNov = 0; // инициализация числа объектов, являющихся новизной SUMW = 0; // инициализация суммы всех расстояний между объектами класса
F = Ncl / (2 + (4/3) *(Ncl-1+pow ((Ncl -1), (и-1) /и) /(2+p)); // расчет критерия F по р,п и Ncl
for i = 0 to Ncl-1 SUMW += SUM[i]; //вычисление SUMW for i = 0 to Ncl-1 if(Ncl*SUM[i]/SUMW>=F) //определение новизны и ее фиксация
3.3. Функция CORRECTION_NOVELTY_DATA коррекции данных по объектам класса с учетом удаления новизны
Определение новизны при помощи функции NOVELTY_DETECTION не изменяет данных исследуемого класса. Функция CORRECTION_NOVELTY_DATA моделирует удаление новизны из класса за счет выполнения следующих действий:
1) удаление информации о новизне из всех основных данных по объектам класса.
2) формирование полных данных по новизне.
Входные данные функции CORRECTIONNOVELTYDATA
1) n — размерность пространства U характеристик оьбъектов,
2) Ncl — число объектов в классе,
3) OB[n][Ncl] — массив векторов значений характеристик для объектов класса,
4) DIST[Ncl][Ncl] — матрица расстояний между объектами в классе,
5) SUM[Ncl] — вектор сумм расстояний от выбранного объекта до всех остальных объектов класса,
6) NNov — число найденных объектов, отнесенных к новизне заданного уровня,
7) NumNov[NNov] — массив номеров объектов, отнесенных к новизне заданного уровня.
Выходные данные функции CORRECTION_NOVELTY_DATA:
1) измененное число NclR объектов в классе,
2) скорректированный массив OBR[n][NclR] векторов значений характеристик для объектов класса,
3) скорректированный вектор SUMR сумм расстояний от объекта класса до остальных,
4) скорректированная матрица DISTR расстояний между оставшимися объектами
5) массив OBNov[n][NNov] векторов значений характеристик для объектов, являющихся новизной.
Псевдокод функции CORRECTION_NOVELTY_DATA имеет
for i = 0 to NNov -1 SUM[NumNov [i]]:=-1;//1 .разметка сумм расстояний
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
for i = 0 to NNov-1 for j:=0 to Ncl-1 OBNov[i][j]:=OB[NumNov[i]][j];//2.формирование данных по объектам новизны
for i = 0 to Ncl-1 if(SUM[i] != -1) //3. проход по сохраняющимся строкам матрицы DIST
for j = 0 to Ncl-1 if(SUM[j] = = -1) //коррекция сохраняющихся элементов SUM, разметка DIST
< SUM[i] - = DIST[i][j]; DIST[i][j] = -1; >for i = 0 to Ncl-1 if(SUM[i] != -1) //4. Уплотнение остающихся строк матрицы DIST
NclR = Ncl — NNov; // 5. коррекция Ncl
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
3.4. Алгоритм CUR_NOVELTYоднократного определения текущей новизны в заданном классе
Функция реализует однократное определение новизны заданного уровня р в некотором классе А.
Применение вспомогательных функций дает возможность представить алгоритм CUR_NOVELTY, решающий данную задачу, в довольно простой форме.
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
1) n — размерность пространства U характеристик оьбъектов,
2) Ncl — число объектов в совокупности М,
3) OB[n][Ncl] — массив векторов значений характеристик для объектов из совокупности М,
4) RO(OB1,OB2,n) — функция рассчета расстояния между объектами OB1,OB2 в заданной метрике пространства U.
5)р — уровень проверяемой новизны.
1) NNov — число найденных объектов, отнесенных к новизне заданного уровня,
2) NumNov[NNov] — массив номеров объектов, отнесенных к новизне заданного уровня,
3) NclR — скорректированное число объектов в классе
4) OBR — скорректированный массив векторов значений характеристик объектов в кластере,
5) OBNov — массив векторов значений характеристик объектов, отнесенных к новизне.
1) матрица DIST[Ncl][Ncl] расстояний между объектами класса,
2) вектор SUM[Ncl] сумм расстояний от выбранного объекта до всех остальных объектов класса.
Алгоритм CUR_NOVELTY включает три этапа.
1. Расчет матрицы DIST[Ncl][Ncl] и вектора SUM[Ncl] по массиву OB[n][Ncl] при помощи функции MAIN_DATA_CALC.
2. Определение новизны уровня р в классе объектов А по матрице DIST и вектору SUM при помощи функции NOVELTY_DETECTION, которая выдает искомые число найденных объектов, отнесенных к новизне
заданного уровня КЫ^ и массив номеров соответствующих объектов NumNov[NNov].
3. Если новизна уровня р и выше в классе А есть (NNov>1), то коррекция данных при помощи функции СОККЕСТЮЫ_БАТА.
Пример 1. Рассмотрим однократное выделение новизны при помощи функции СиЯ_ЫОУБЬТУ. п = 2, Ис1 = 4. Изображающие точки объектов класса показаны на рис.2. Допустимый уровень новизны р = 1.5.
Рис.2. Точки, задающие объекты класса в примере 1
Функция СиЯ_ЫОУБЬТУ дает следующие результаты:
1) предельное значение критерия: Е11т = Б(п = 2, Ыс1 = 4, р = 1.5) =1.052;
2) суммы расстояний от заданной точки класса до всех остальных: БиМ[1] = 5.650; БиМ[2] = 4.414; БЦЩЗ] = 4.236; БиМ[4] = 3.828;
3) сумма всех расстояний между точками внутри класса: SUMW =18.129;
4) значения критерия для объектов класса:
Так как уровень нозизны превышает допустимый у объекта 1, но он является новизной е уровнtv новизны, превышающим р = 1.5. Все остальные точки класса не являются новизной.
4. Итерационное выделение новизны. Определение кластеров в классах.
В результате применения алгоритма СЦЯ_КОУЕЬТУ к некоторому классу А при уровне новизны р после удаления новизны < а,>уровня р среди множества оставшихся точек А\ < а,>может снова появиться новизна того же уровня. Такая же новизна может возникнуть и после повторного применения алгоритма СЦЯ_КОУЕЬТУ и т.д. Итерационное удаление новизны будет продолжаться до тех пор, пока:
1) не будет получено подмножество, не содержащее новизны уровня р (кластер) или же
2) класс А не будет исчерпан — в нем останется менее 3 точек.
Рассматриваемые классы Л,, выделенные из обучающей выборки ТЕ, представляют собой уже предварительно группированные совокупности точек. Поэтому для них введенное понятие уровня новизны р и статистический критерий Б позволяют дать строгое определение кластера с заданной степенью р близости точек.
Кластером с предельным уровнем р близости точек для класса Л, назовем такое его подмножество Л,(р) с Л, его точек, для которого критерий Б относительной удаленности объектов не превышает порогового значения Б(р). Для всех точек ау подмножестваЛ,(р) выполняется условие: Б( ~аУ, Л) < Бсг (р) = Ус//[2+(4/3)(Ус/ -1+ N -1)(и-1)/и)/(2+р)].
Введенное понятие имеет смысл только для классов — предварительно сгруппированных подмножеств объектов, выделенных из их общей совокупности. В ином случае данное понятие не определено.
В общем случае число точек п(Л,(р)) в кластере Лг(р) может изменяться от 2 до всего числа точек Л, (когда Л,(р) = Л,). Случае п(Л1<р)) 3 назовем вырожденным кластером, поскольку при одной и двух точках это понятие не определено.
Введенные уровни новизны позволяют также обоснованно ввести соответствующую им оценку плотности расположения объектов внутри кластеров.
1. Кластер первого типа — кластер с высокой равномерностью расположения объектов — это такой кластер, в котором нет близкой новизны, т.е. для всех его точек ау выполняется условие: Б( ау, Лг) < Бсг (1,5).
2. Кластер второго типа — кластер с средней равномерностью расположения объектов — это такой кластер, в котором, возможно, есть близкая новизна, но нет средней и дальней, т.е. для всех его точек ау выполняется условие: Б( ау, Л) < Бсг (2,0).
3. Кластер третьего типа — кластер с низкой равномерностью расположения объектов — это такой кластер, в котором, возможно, есть близкая и средняя новизна, но нет дальней новизны, т.е. для всех его точек ау выполняется условие: Б( ау, Л) < Бсг (2,5).
Очевидно, выделение кластера уровня р задает более высокие требования на искомое множество точек по сравнению с однократным удалением новизны такого же уровня р.
Однако применение функций МАГЫ_БАТА_САЪС,
ЫОУЕЬТУ_БЕТЕСТЮЫ и СОККЕСТЮЫ_ЫОУЕЬТУ_БАТА дает возможность построить алгоритм ЬЕУЕЬ_СЬ^ТЕК для выделения кластера заданного уровня р, имеющий довольно простую структуру. Входные данные:
1) п — размерность пространства и характеристик объектов,
2) Ыс1 — число объектов класса,
3) ОВ[п][Ыс1] — массив векторов значений характеристик для объектов класса,
4) ЯО(ОВ1,ОВ2,п) — функция расчета расстояния между объектами ОВ1,ОВ2 класса в заданной метрике пространства и,
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
5)р — уровень проверяемой новизны. Выходные данные:
1) Ncluster — число точек в выделенном кластере уровня р,
2) OBC[n][ Ncluster] — массив векторов значений характеристик для объектов выделенного кластера уровня р.
1) матрица DIST[Ncl][Ncl] расстояний между объектами класса,
2) вектор SUM[Ncl] сумм расстояний от выбранного объекта i до всех остальных объектов класса,
3) массив текущей новизны Nov[NNov].
Алгоритм LEVEL_CLUSTER для выделения кластера с заданным
предельным уровнем р близости точек.
MAIN_DATA_CALC (n, Ncl, OB, RO, DIST, SUM); // 1. Расчет матрицы DIST[Ncl][Ncl] и вектора SUM[Ncl]
Nnov =1; // 2. Инициализация текущего количества новизны
while ((Nnov>0)&&(Ncl>2)) //3. Цикл while Условие выполнения итераций
NOVELTY_DETECTION (n, Ncl,OB, р, DIST, SUM, NNov, NumNov);
CORRECTION_DATA(n,Ncl,SUM,DIST,NNov,Nov,NclR,SUMR,DISTR,OBR, OBRNov);//найдена новизна
Ncl = Ncl1; SUM = SUM1; DIST = DIST1; OB=OBR; >//завершение цикла while ((Nnov>0)&&(Ncl>2)) Ncluster = Ncl; OBC=OB;
М Инженерный вестник Дона, №11 (2021) ivdon.ru/ru/magazine/arcliive/nl 1у2021/7279
>//завершение алгоритма LEVEL_CLUSTER
Пример 2. Рассмотрим итерационное выделение новизны при помощи функции LEVEL_CLUSTER. п = 2, ИС1 = 5. Изображающие точки объектов класса показаны на рис.3. Допустимый уровень новизны р = 3.5.
Рис.3. Точки, задающие объекты класса в примере 2 Итерация 1. Функция LEVEL_CLUSTER дает следующие результаты:
1) предельное значение критерия: Flim = F(n = 2, №1 = 5, р = 3.5) =1.447;
2) суммы расстояний от заданной точки класса до всех остальных:
SUM[1] = 11.479; SUM[2] = 7.434; SUM[3] = 7.064; SUM[4] = 7.479; SUM[4] = 13.670;
3) сумма всех расстояний между точками внутри класса SUMW = 47.126;
4) значения критерия для объектов класса:
Уровень новизны у объекта 5 превышает допустимый, он является новизной и удаляется из класса. Итерация 2: 1) Fl1m = F(n = 2, №1 = 4, р = 3.5) =1.176;
2) SUM[1] = 5.236; SUM[2] = 3.414; SUM[3] = 4.0; SUM[4] = 4.650;
Уровень новизны превышает допустимый у объекта 1, он является новизной и удаляется из класса.
Итерация 3: 1) = Б(п = 2, Ш = 3, р = 3.5) =1.0609;
2) БиМ[1] = 2.414; БиМ[2] = 2.000; БиМ[3] = 2.414;
Новизна уровня выше р = 3.5 отсутствует. Следовательно, кластер с предельным уровнем новизны р = 3.5 в исходном классе существует и его составляют точки .
Рассмотренные алгоритмы СиЯ_КОУЕЬТУ (однократное определение текущей новизны заданного уровня р) и ЬЕУЕЬ_СЬи8ТЕЯ (определения кластера уровня р) задают слабый и сильный виды удаления новизны из классов обучающей выборки.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Выбор метода устранения новизны определяется общими требованиями к обучающей выборке и классификатору, который строится по ней.
Длину входа задачи определения новизны определяет массив ОВ[п][Кс1], в котором заданы векторы значений характеристик для объектов из анализируемого класса. Длина массива пропорциональна п-Кс1.
Максимальную сложность из вспомогательных функций, определяющих сложность обоих алгоритмов, имеет функция МАЩ_ОАТА_САЪС, в которой производится расчет матрицы расстояний Б18Т[Кс1][Кс1] и вектор сумм расстояний БиМ[Кс1].
При расчете одного расстояния между объектами, например, в евклидовой метрике, затрачивается 1) п вычитаний, 2) п возведений в квадрат, 3) (п-1) сложений и 4) 1 извлечение квадратного корня. Во всей функции МАЩ_БАТА_САЪС такие расстояния вычисляются ровно N (К -1)/2 раз.
Порядок трех основных операций совпадает и равен п. Поэтому
сложность функции МА!К_БАТА_САЬС равна 0(п-№). Так как (п-№1)
В статье рассмотрена актуальная частная задача определения и удаления новизны в классах обучающих данных, используемых при построении классификаторов при обучении с учителем. От эффективности ее решения во многом зависит качество классификаторов, получаемых на таких выборках.
Предложена геометрическая интерпретация новизны. На ее основе введено общее понятие уровня новизны и три ее качественные градации. Это дает возможность придать новизне объекта четкий пространственный смысл и оценить допустимые для нее пределы в конкретных решаемых задачах. Однако из-за сложности вычисления уровня новизны для практических расчетов предложено использовать связанный с ней статистический критерий средних расстояний. При помощи критерия можно косвенно оценивать уровень близости объектов ко всем объектам класса на основании довольно простых вычислений.
Использование уровня новизны позволило дать четкую геометрическую интерпретацию новизны и в частности, обоснованно выбирать пороговые значения при ее поиске. Применение статистического критерия Б позволяет существенно упростить поиск новизны. Зависимость Б(р), найденная на «-мерных кубах, позволила связать геометрическую оценку новизны с ее статистической оценкой.
Найдена верхняя оценка критерия Б(р) для дополнительных точек, попадающих внутрь основного кластера класса, а также величина критерия для внешних точек кластера. Получена формула для значений критерия на внешних точках произвольных классов с параметрами [п, ЫС1 >, а также
формулы для пороговых значений критерия F при трех введенных градациях новизны, которым соответствуют значения уровня p=1.5; 2.0;2.5.
Рассмотрен обычный алгоритм однократного обнаружения и удаления новизны, который выявляет только текущую новизну заданного уровня, но не гарантирующий ее отсутствие в получаемом сокращенном классе.
С использованием геометрической аналогии введено понятие кластера c предельным уровнем р близости точек, гарантирующих отсутствие в итоговом множестве объектов новизны данного уровня. Также дано определение кластеров первого, второго и третьего типов, соответствующих отсутствию в них близкой, средней и дальней новизны.
Для определения кластера с заданным предельным уровнем р близости точек, требуется применять итерационный (сильный) метод удаления новизны соответствующего уровня из класса. Рассмотрен алгоритм, реализующий данный метод полного удаления новизны заданного уровня.
Показано, что оба алгоритма имеют сложность выше линейной по длине входа задачи, но меньше квадратичной.
Предложенные алгоритмы обнаружения и удаления новизны в классах обучающих данных вместе с алгоритмами удаления выбросов обеспечивают эффективное удаление шумов в этих данных. Применение таких исправленных обучающих данных обеспечивает построение на них качественных классификаторов.
1. Mottl V., Seredin O., Krasotkina O. Compactness Hypothesis, Potential Functions, and Rectifying Linear Space in Machine Learning. URL: link.springer.com/chapter/10.1007/978-3-319-99492-5_3.
2. Santoyo Sergio. A Brief Overview of Outlier Detection Techniques. What are outliers and how to deal with them? 2017. URL:
3. Chen D., Jain R. A robust backpropagation learning algorithm for function approximation. IEEE Trans Neural Netw 5(3). 1994. pp. 467-479.
4. Liano K. Robust error measure for supervised neural network learning with outliers. IEEE Trans Neural Netw 7(1). 1996. pp. 246- 250.
5. J. S. Anstey, D. K. Peters and C. Dawson. Discovering Novelty in Time Series Data, Proc. Newfoundland Electrical and Computer Engineering Conference, IEEE, Newfoundland and Labrador Section, November 2005. URL: researchgate.net/publication/250381613_Discovering_Novelty_in_Time_Series_D ata
6. Chandola V., Banerjee A., Kumar V. Outlier Detection: A Survey, Univ. of Minnesota TR 07-017, August 2007. URL: researchgate.net/publication/242403027_0utlier_Detection_A_Survey
7. Miljkovic D. Review of Novelty Detection Methods. Hrvatska elektroprivreda. Conference MIPRO proceedings of the 33rd International Convention At Opatija, Croatia. May 2010. URL: researchgate.net/publication/261424710_Review_of_novelty_detection_methods.
8. S. Marsland. Novety Detection in Learning Systems, Robotics and Autonomous Systems, 51(2-3). 2005. pp. 191-206.
9. Martinez D. Neural tree density estimation for novelty detection. IEEE Transactions on Neural Networks, Volume: 9 Issue: 2. 1998. pp. 330-338.
10. Lee H., Hwang B., Cho S. Analysis of Novelty Detection Properties of Autoassociative MLP. Journal of the Korean Institute of Industrial Engineering.
researchgate.net/publication/263358725_Analysis_of_Novelty_Detection_Properti es of Autoassociative MLP
11. Rowland B., Maida A. S. Spatiotemporal Novelty Detection Using Resonance Networks. Proceedings of the 17th Annual Florida AI Research Society Conference. May 2004. pp. 676-681.
12. Tanaka T., Weitzenfeld A. Adaptive Resonance Theory in Neural Simulation Language. The MIT Press. 2002. pp. 157-169.
13. Oliveira A.L.I., Neto F.B.L., Meira S.R.L. Combining MLP and RBF Neural Networks for Novelty Detection in Short Time Series. Proc. of MICAI. 2004.URL:researchgate.net/publication/296580021_Combining_MLP_and_RBF_ neural_networks_for_novelty_detection_in_short_time_series,
14. Markou M., Singh S. Novelty detection: A review — Part 2: Neural network based approaches. Signal Processing 83(12). pp. 2499-2521.
15. Scholkopf B., Williamson R., Smolax A., Shawe-Taylory J., Platt J. Support Vector Method for Novelty Detection. Advances in Neural Information Processing Systems 12. URL: proceedings.neurips.cc/paper/1999/file/8725fb777f25776ffa9076e44fcfd776-Paper.pdf
16. Banerjee A., Chandola V., Kumar V., Lazarevic A. Anomaly Detection: A Tutorial, Proc. of SIAM Data Mining Conference. April 2008. 60 p.
17. Hautamaki V. Outlier Detection Using k-Nearest Neighbour Graph, 17th International Conference on Pattern Recognition Vol. 3, Cambridge. 2004. pp.80-84.
18. Miljkovic D. Novelty Detection In Machine Vibration Data Based On Cluster Intraset Distance. Proc. CTS, MIPRO. 2008. pp. 59-66.
19. Hallgrimsson, B., Jamniczky, H. A., Young, N. M. The generation of variation and the developmental basis for evolutionary novelty. Journal of Experimental Zoology Part B: Molecular and Developmental Evolution. 2012. pp. 501-517.
20. Hughes, A. L. The evolution of functionally novel proteins after gene duplication. Proceedings of the Royal Society of London B: Biological Sciences. 1994. pp.119-124.
21. Kailing K., Kriegel H-P., Kröger P. Density-Connected Subspace Clustering for High-Dimensional Data. In: Proc. SIAM Int. Conf. on Data Mining (SDM’04), pp. 246-257.
22. Agrawal R., Gehrke J., Gunopulos D., Raghavan P. Automatic Subspace Clustering of High Dimensional Data. Data Mining and Knowledge Discovery. 2005, pp. 5-33.
23. Kriegel H-P., Kröger P., Zimek A. Subspace clustering. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 2012. pp. 351364.
24. Wolfson, H.J., Rigoutsos, I. Geometric Hashing: An Overview. IEEE Computational Science and Engineering, 1997. pp.10-21.
25. Mian A.S., Bennamoun M., Owens R. Three-dimensional modelbased object recognition and segmentation in cluttered scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, Oct. 2006, pp. 1584-601.
26. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction (PDF) (Second ed.), New York 2008. pp.129-135.
27. Hall P., Park B.U., Samworth R.J. Choice of neighbor order in nearest-neighbor classification. 2008. 36p.
28. Bremner D., Demaine E., Erickson J., Iacono J., Langerman S., Morin P., Toussaint G.T. Output-sensitive algorithms for computing nearest-neighbor decision boundaries. Discrete and Computational Geometry. 2005. p. 593-604.