DETECTION OF HOMEGENEOUS PRODUCTION BATCHES OF SPACe ELECTRONIC COMPONENTS BASED ON SEPARATION OF A MIXTURE OF SPHERICAL GAUSSIAN DISTRIBUTIONS

Texto integral

Введение. EM-алгоритм (максимизация математического ожидания) успешно применяется для статистических задач, связанных с анализом неполных данных, когда некоторые статистические данные отсутствуют, либо для случаев, когда функция правдоподобия имеет вид, не допускающий удобных методов исследования, но допускающий серьезные упрощения при введении дополнительных «ненаблюдаемых» («скрытых») величин [1]. Именно такая постановка задачи (кластеризация многомерных данных нормального распределения со скрытыми данными) используется нами для решения задач разделения ЭРИ по производственным партиям исходного сырья. пусть плотность распределения на множестве x имеет вид смеси k распределений (предполагаем, что распределения гауссовы): где ρj(х) - функция правдоподобия j-й компоненты смеси; αj - ее априорная вероятность, а функции правдоподобия принадлежат параметрическому семейству распределений φ(x;θ) и отличаются только значениями параметра ρj(х) = φ(x;θ). задача разделения смеси (нечеткой кластеризации) заключается в том, чтобы, имея выборку xn случайных и независимых наблюдений из смеси ρ(х), зная число k и функцию φ, оценить вектор параметров распределения θ = (α1, …, αk, θ1, … θk). искусственно вводится вспомогательный вектор скрытых переменных g, который может быть вычислен, если известны значения вектора параметров θ. em-алгоритм состоит из итерационного повторения двух шагов. на e-шаге вычисляется ожидаемое значение вектора скрытых переменных g по текущему приближению вектора параметров θ. обозначим через ρ(х, θj) = ρ(х)ρ(θj|x) = αjρj(x) плотность вероятности того, что объект x получен из j-й компоненты смеси. обозначим апостериорную вероятность того, что обучающий объект xi получен из j-й компоненты смеси. на m-шаге решается задача максимизации логарифма правдоподобия и находится следующее приближение вектора θ по текущим значениям векторов g и θ. m-шаг сводится к вычислению весов компонент αj и оцениванию параметров θj путем решения k независимых оптимизационных задач. данный алгоритм не позволяет определять количество k компонентов смеси (количество кластеров), поэтому должна решаться серия задач с различным предполагаемым числом кластеров. кроме того, em-алгоритм обладает сильной неустойчивостью по начальным данным [1]. тем не менее, к его преимуществам можно отнести [2] то, что его можно комбинировать с другими алгоритмами обработки данных, также для его использования не требуется выделения метрик. при применении более распространенной модели k-средних к задаче выделения однородных производственных партий электрорадиоизделий (эри) проблема выбора метрики или меры расстояния [3] не имеет однозначного решения. на практике приходится использовать сложные специальные способы нормировки данных [4]. em-алгоритм успешно работает с малыми объемами данных. некоторые дорогие виды электрорадиоизделий, несущие в космических аппаратах наибольшую функциональную нагрузку, поступают партиями от нескольких штук, что делает применение em-алгоритма и алгоритмов на его основе весьма перспективным применительно к нашей задаче. простые эксперименты с реализацией em-алгоритма в среде моделирования r для автоматической группировки партий эри от 50 до 620 штук (рис.1, 2) показывают [5], что данный алгоритм способен эффективно разделять смесь распределений, получая адекватные результаты, соответствующие реальным производственным партиям эри, если для выборки можно выделить несколько (не более 10) информативных признаков. кроме определения принадлежности каждого эри (точки на диаграмме) к кластеру, алгоритм дает таблицу с вероятностными характеристиками принадлежности к кластеру и показывает форму кластера, визуализируя возможные корреляции параметров эри. в то же время, работа алгоритма при использовании многомерных данных, какими являются данные неразрушающих испытаний эри, приводит к «зависанию» алгоритма, требует значительных вычислительных ресурсов, особенно в случаях, если число измерений приближается к числу группируемых объектов (векторов данных). выделение информативных признаков - сложная задача. так, на рис. 2 видно, что по двум признакам очень трудно выделить партии изделий. в то же время, обработка всех 205 признаков позволяет сделать это с весьма высокой точностью. создание модификаций em-алгоритма с повышенной устойчивостью результата откроет новые перспективы в решении задачи автоматической группировки эри по производственным партиям, в частности, при небольшом объеме входных данных. данной проблематике и посвящена настоящая статья. 2 кластера Рис. 1. Срез (показаны 2 параметра из 32) результата автоматической группировки усилителей 140УД25АС1ВК 3 кластера 5 кластеров Рис. 2. Разбиение сборной партии ЭРИ 1526ИЕ5 на 3 и 5 групп Свойства сферических гауссовых распределений. Сферическое гауссово распределение [6] N(µ, s2In) определено на xÎRn с плотностью где - евклидово расстояние. Если X = (X1, ..., Xn) случайно выбраны на распределении N(0, s2In), тогда их координатами будут независимые случайные переменные с одинаковыми распределениями N(0, s2). Каждая координата имеет ожидаемое значение дисперсии s2 такое, что Из теории больших отклонений [7], связанной с тем, что ||X||2 будет плотно сконцентрировано вокруг ns2, следует Таким образом, большая часть плотности вероятности N(0, s2In) укладывается в тонкую оболочку с радиусом от основания [6]. Это не противоречит факту того, что плотность гауссова распределения будет максимальной у центра, когда площадь поверхности на расстоянии r от основания - , увеличивается быстрее, чем уменьшается плотность с расстоянием r [8]. Рассмотрим гауссово распределение N(0, s2In), имеющее радиус . Распределения N(µ1, s12In) и N(µ2, s22In) на Rn будем называть с-разделенными [9], если выполняется условие Смесь гауссовых распределений является с-разделённой, если все распределения в ней попарно с-разделены. Будем считать, что cij определяет разделение между i-м и j-м распределением и c = mini¹j cij. Мы можем обоснованно ожидать, что сложность исследования смеси гауссовых распределений повышается с понижением значения c. При c = 2 (т. е. при 2-разделенной смеси) кластеры в основном не пересекаются. При больших размерностях пространства n это утверждение верно даже для -разделенной смеси. Если c мало, то проекция смеси на любую одну координату будет выглядеть унимодальной (частотная гистограмма имеет единственный пик). Это также может быть верно для проекции на несколько координат. Но для больших n, при совместном рассмотрении всех координат, распределение прекратит выглядеть унимодальным (слово «выглядит» обретает буквальный смысл, например, при использовании MDS-визуализации [10]). Именно это обстоятельство часто обусловливает использование данных большой размерности: там, где объекты практически невозможно разделить по одному или нескольким признакам, использование большой совокупности признаков позволяет добиться результата. Например, в [6] авторы продемонстрировали данное свойство многомерных сферических распределений на 256-мерном наборе дискретных данных, состоящем из рукописных символов, собранных почтовой службой США. Известные подходы к выделению однородных партий изделий. В настоящей статье задача разделения производственных партий электрорадиоизделий (где каждый кластер должен представлять отдельную производственную партию этих изделий, изготовленную из единой партии сырья) сводится к задаче разделения сферических гауссовых распределений. Задача выделения однородных партий электрорадиоизделий возникает, например, при комплектации узлов космических аппаратов. Специализированные тестовые центры проводят от нескольких десятков до нескольких сотен неразрушающих тестов [11; 12] для каждого экземпляра ЭРИ. При этом предполагается, что все экземпляры ЭРИ уже прошли входной контроль по ужесточенным нормам [13-16], т. е. отдельные их параметры могут колебаться лишь в очень узких диапазонах, определенных этими нормами, и отдельные параметры являются неинформативными. В то же время, совокупность большого числа этих параметров позволяет эффективно разделять производственные партии этих изделий. В частности, хорошие результаты достигнуты при решении задачи автоматической группировки ЭРИ с использованием моделей k-средних, k-медиан и k-медоид. Недостатком одноименных алгоритмов, основанных на идее процедуры k-средних, называемой также процедурой Ллойда или ALA-процедурой [17; 18], а также PAM-алгоритма для задачи k-медоид является то, что они относятся к алгоритмам локального поиска (не в строгом смысле), зависящим от выбора начального решения. При этом разработаны детерминированные алгоритмы [19; 20], а также рандомизированные алгоритмы, обеспечивающие, тем не менее, весьма точный и при этом стабильный результат [21-23], что немаловажно во всех процедурах, связанных с космическим производством, все этапы которого требуют весьма строгой регламентации. В частности, хорошие результаты достигаются при применении кластеризации, основанной на расстояниях с прямоугольной метрикой [3]. Преимущество нечеткой кластеризации в виде задачи разделения смеси гауссовых распределений посредством EM-алгоритма заключается в том числе в том, что эта модель, в отличие от модели k-средних и аналогичных, оперирует не абстрактными расстояниями в неком пространстве характеристик различной физической природы, а вероятностными характеристиками возможности отнесения конкретного экземпляра ЭРИ к той или иной группе (кластеру). При этом использование именно сферических гауссовых распределений позволяет в некотором смысле обратить так называемое проклятие размерности [24] в полезное свойство многомерных данных. Использование модели традиционных (не сферических) распределений N(µ, S) с плотностью распределения где ковариационная (иначе - корреляционная) матрица, в случае использования данных очень большой размерности приводит к следующим эффектам. Во-первых, матрица размерности n для каждого гауссова распределения (т. е. для каждого кластера) требует достаточно много памяти и значительных вычислительных ресурсов при пересчете ЕМ-алгоритмом на каждом шаге. Во-вторых, использование данной матрицы предполагает, что для каждой координаты каждое распределение (кластер) имеет собственное значение дисперсии (соответствующий элемент диагонали матрицы при этом плотность j-го распределения тем чувствительнее к изменению координаты, чем меньше дисперсия по этой координате. Таким образом, незначительные колебания какой-либо характеристики, вызванные, например, неточностью измерительных приборов, рассматриваются как значительные при принятии решения об отнесении объекта к тому или иному распределению (кластеру), снижая относительную значимость более информативных признаков. Тот же эффект проявляется и при кластеризации с использованием модели k-средних в сочетании с нормировкой данных по среднеквадратичному отклонению или 0-1-нормировкой [4]. В то же время, использование специального метода нормировки исходных данных, учитывающего именно физическую природу каждой из характеристик ЭРИ [4], а не разброс характеристики в исследуемой партии изделий, позволяет добиться гораздо лучших результатов. Аналогичным образом использование единого значения дисперсии по всем координатам (характеристикам), т. е. использование модели смеси сферических гауссовых распределений в сочетании со способом нормировки, описанным в [4], позволяет добиваться адекватных результатов при использовании данных очень большой размерности, которые являются результатом измерений, производимых в ходе тестирования ЭРИ. Применение EM-алгоритма к задаче выделения однородных партий. EM-алгоритм для разделения смеси сферических распределений может быть описан следующим образом. Дан набор данных S Ì Rn, EM-алгоритм для смеси k нормальных распределений с общей сферической матрицей ковариации стартует с начальными стартовыми значениями параметров µiá0ñ, αiá0ñ, siá0ñ, которые в дальнейшем обновляются в соответствии со следующей двухшаговой процедурой (здесь t - номер итерации). Алгоритм 1. EM-алгоритм. Шаг 1. Пусть ti~N(µiátñ,siátñ2In) является плотностью i-го гауссова распределения: Для каждого вектора исходных данных x Î S и каждого 1 £ i £ k по формуле Байеса [25] вычислим условную вероятность того, что x относится к i-му распределению с учетом текущих параметров: . (1) Шаг 2. Производится адаптация параметров распределений. Пусть N - количество векторов данных: (2) (3) (4) Повторять с шага 1. Условием останова в таком алгоритме является останов приращения целевой функции, в качестве которой принимается логарифмическая функция правдоподобия (5) Мы использовали комбинированное условие останова: t > 100 или Lát+1ñ - Látñ < 0,0001. Отметим, что в случае данных большой размерности (d > 100) плотность отдельных распределений ti(x) может принимать как очень малые значения (ti(x) < 1 · 10-300), так и очень большие значения, что может потребовать применения специальных механизмов при реализации алгоритма. В частности, мы использовали библиотеку decimal [26], применение которой существенно замедляет расчеты, но обеспечивает работу с величинами требуемых порядков. В работах [21-23] предложен подход к повышению точности и стабильности результата решения задач k-медиан, k-медоид, k-средних, основанный на применении жадных агломеративных эвристических процедур в комбинации с различными метаэвристиками и методами локального поиска. Идея жадной агломеративной эвристики основана на последовательном исключении кластеров из решения. Каждый раз удаляются те кластеры, удаление которых дает наименьший прирост целевой функции (данные задачи являются задачами минимизации). В настоящей работе мы предлагаем аналогичные подходы к построению жадных агломеративных эвристических процедур. В данном случае мы имеем дело с задачей максимизации функции (5). Первые два подхода полностью аналогичны подходам, примененным в [21-23]. Алгоритм 2. Жадная агломеративная эвристика, вариант 1. Дано: начальное число гауссовых распределений (кластеров) k, требуемое число кластеров K. 1. Выбрать случайным образом начальное решение с K кластерами, т. е. выбрать случайным образом начальные параметры распределений множества распределений . В качестве начальных значений µiá0ñ выбираются случайные векторы данных, дисперсии siá0ñ рассчитываются по формуле (4). Также устанавливаются равные начальные значения множества весовых коэффициентов распределений 2. Выполнить алгоритм 1, получить новое (улучшенное) решение задачи, представленное множествами D и W. 3. Если K = k, то останов. 4. Для каждого выполнять следующее: 4.1. Получить усеченное множество распределений и множество их весовых коэффициентов Запустить алгоритм 1 с начальными значениями параметров распределений, представленных усеченным множеством D′ и весами W′. При этом алгоритм 1 ограничивается одной итерацией. Для полученного ЕМ-алгоритмом решения рассчитать целевую функцию L согласно (5), сохранить ее значение в переменной L’I’. 4.2. Следующая итерация цикла 4. 5. Найти индекс . 6. Получить усеченные множества Перейти к шагу 3. Кроме того, мы испытали два упрощенных алгоритма. Алгоритм 3. Упрощенная жадная эвристика № 1. Полностью повторяет алгоритм 2, кроме шага 4.2: 4.2. Без запуска EM-алгоритма рассчитать целевую функцию L согласно (5), сохранить ее значение в переменной L′I′. Вычислительные эксперименты показывают, что если задать EM-алгоритму в качестве числа требуемых распределений (кластеров) значение k большее, чем фактическое количество кластеров в выборке, во многих случаях в результате работы алгоритма несколько «лишних» кластеров получают значение весовых коэффициентов wi, близкое к нулю. На этом свойстве основана еще более упрощенная версия алгоритма. Алгоритм 4. Упрощенная жадная эвристика № 1. Частично повторяет алгоритм 2, при этом цикл 4-4.3 исключен, а шаг 5 выполняется в следующей редакции: 5. Найти индекс Как и в работе о применении жадной агломеративной эвристики с алгоритмами k-средних [27], важным является вопрос выбора начального значения числа кластеров. В настоящей работе мы не рассматривали данный вопрос, ограничиваясь пока экспериментами с k = 2K и k = 4K (удвоенное и учетверенное число начальных кластеров). Результаты вычислительных экспериментов. Результаты вычислительных экспериментов приведены для двух наборов данных. Первый набор - искусственно сгенерированный набор данных с m = 200, K = 3, n = 12. Второй набор - данные испытаний [28] электрорадиоизделий 1526ИЕ10 (m = 3987, n = 205), нормированные согласно [4]. Сравнительные результаты работы алгоритмов представлены в табл. 1. Из табл. 1 видно, что жадная эвристика (алгоритмы 2, 3 и 4) имеет преимущество перед использованием алгоритма 1 по точности результата. В то же время под вопросом остается оптимальное начальное количество кластеров k. Перспективным представляется исследование подхода с адаптацией начального количества кластеров, аналогичный подходу с адаптацией начального количества кластеров для решения задач k-средних и p-медианной задачи, описанному в [27]. Таблица 1 Сравнительные усредненные по 30 запускам результаты работы алгоритмов для двух наборов данных Набор данных Алгоритм Усредненное значение целевой функции (5) Среднее время работы, с Сгенерированный набор данных, m = 200, n = 12, K = 3 Алгоритм 1 Алгоритм 2, k = 6 Алгоритм 2, k = 12 Алгоритм 3, k = 6 Алгоритм 3, k = 12 Алгоритм 4, k = 6 Алгоритм 4, k = 12 -7430,39 -7263,48 -7028,99* -7230,06 -7036,80 -7152,64 -7110,28 0,557 3,882 21,472 3,913 23,581 2,932 9,820 Испытания ЭРИ 1526ИЕ10, m = 3987, n = 205, K = 3 Алгоритм 1 Алгоритм 2, k = 6 Алгоритм 2, k = 12 Алгоритм 3, k = 6 Алгоритм 3, k = 12 Алгоритм 4, k = 6 Алгоритм 4, k = 12 613261,510 622559,536* 622559,536* 622559,536* 622559,536* 622559,536* 613506,5485 14,820 113,140 653,113 96,677 667,399 96,677 553,159 Примечание: * - лучший результат. Таблица 2 Фрагмент решения задачи автоматической группировки результатов испытаний ЭРИ 1526ИЕ10, m = 3987, n = 205, K = 3 № вектора данных (№ ЭРИ) Предполагаемый номер кластера Вероятность отнесения к предполагаемому кластеру 225 1 1 226 1 1 227 1 1 … … … 230 2 0,87564 231 1 0,99554 232 1 1 … … … Фрагмент итоговых результатов с указанием оценки вероятности отнесения векторов данных к тому или иному распределению (кластеру) показан в табл. 2. Видно, что в случае многомерных данных вероятности стремятся к 0 или 1, что подтверждает гипотезу о том, что данные являются с-разделенными при малых значениях с. Заключение. Таким образом, вычислительные эксперименты показывают, что применение жадной агломеративной эвристики позволяет получить результаты значительно более высокой точности в сравнении с мультистартом EM-алгоритма из случайных начальных решений. При этом самая простая и самая быстрая модификация алгоритма с жадной эвристикой - алгоритм 4 - не уступает по точности результатов другим модификациям, требующим гораздо более значительного времени счета. Программное обеспечение на основе описанного подхода может быть использовано в реализации задач повышения надежности программно-аппаратных комплексов автоматизированных систем управления в части управления качеством выпускаемой продукции. Сходство ЕМ-алгоритма с алгоритмами для решения задач k-средних, k-медоид и k-медиан, а также сходство соответствующих алгоритмов, реализующих жадную агломеративную эвристику, дает обоснованную надежду на получение в дальнейшем алгоритмов, обеспечивающих еще более высокую точность и стабильность результата.

Sobre autores

V. Orlov

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

D. Stashkov

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

L. Kazakovtsev

Reshetnev Siberian State Aerospace University

Email: levk@bk.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

I. Nasyrov

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

A. Antamoshkin

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

Bibliografia

Arquivos suplementares