Задача классификации электронной компонентной базы

Полный текст

Введение. Качество электронной компонентной базы, применяемой при сборке различных электронных узлов, зачастую оставляет желать лучшего. Электронная компонентная база, выпускаемая производителями в США, подразделяется на классы качества (Commercial/Industry, Military, Space) [1; 2]. Проблема повышения качества отечественного производства электронных изделий высокого качества в последнее время становится наиболее актуальной [3-5]. От класса к классу (более высокому) стоимость изделий увеличивается на порядок. Независимо от класса продукции при изготовлении практически любой электронной схемы желательно использовать в ней электрорадиоизделия с близкими эксплуатационными характеристиками, что с наибольшей вероятностью достигается при использовании электрорадиоизделий, изготовленных в одной производственной партии. В идеале вся партия, например микросхем, должна быть выпущена в одних и тех же условиях из одной и той же партии сырья. В то же время поставщики полупроводниковых и других приборов не всегда могут гарантировать однородность партии приборов. Особенно это актуально при использовании изделий импортного производства, доля которых близка к 100 % [5]. В этом случае едва ли не единственным доступным способом повысить качество элементной базы и, как следствие, всей системы является проведение комплексных испытаний поставляемых партий. Одним из направлений повышения качества элементной базы является проверка партий отечественной продукции на однородность и выделение групп элементов с идентичными характеристиками из сборных (предположительно) партий импортного происхождения. Метод классификации с использованием генетического алгоритма. Результатом испытаний, проводимых заводом-изготовителем или испытательным центром, является набор параметров каждого элемента. Результат каждого из видов испытаний является числовой характеристикой (чаще всего, напряжение или ток в той или иной цепи в тех или иных условиях). Сделать вывод об однородности либо разнородности партии изделий по условиям производства следует на основе анализа этих характеристик. Хотя к диапазону каждой из этих характеристик применяются жесткие требования, незначительные на первый взгляд колебания сразу нескольких характеристик позволяют сделать вывод о том, что части партии произведены в разных условиях. Задача k-средних на сегодняшний день является наиболее распространенной моделью кластерного анализа [6]. В свою очередь, кластерный анализ -универсальный инструмент классификации и стати стической обработки данных [7; 8]. Задачу k-средних можно отнести к задачам непрерывной теории размещения [9]. В действительности задача сводится к нахождению k точек (центров, центроидов) в d-мерном пространстве характеристик (здесь d - число измерений характеристик) таких, чтобы сумма расстояний от каждого из векторов данных до ближайшего к нему из k центров достигала минимума. В пространстве характеристик используется, как правило, квадратичная евклидова метрика, поскольку в данном случае нахождение центра каждого из кластеров является элементарной задачей, выполняемой за один шаг, и вычислительная сложность алгоритма падает по сравнению с алгоритмом с евклидовой метрикой, при которой вычисление центра (медианы) [10] - итеративный процесс [11; 12]. Векторами данных при этом являются наборы характеристик, в нашем случае -данные результатов испытаний каждого из изделий, выраженные в виде набора числовых характеристик различной (в общем случае) размерности. Задача является задачей глобального поиска [13]. Для решения данных задач используется ALA-алгоритм (Alternating Location-Allocation - изменяющееся размещение-распределение) [13]. Данный алгоритм является процедурой локального поиска, начинается с указания некоторого начального решения -начального множества центров, в качестве которого используется подмножество из k точек-векторов данных, и состоит в поочередном нахождении множеств векторов данных для каждого из центров, для которых данный центр является ближайшим, и нахождения нового центра для каждого из этих множеств. В случае задачи k-средних в качестве нового центра выбирается медиана множества, в случае p-медианной задачи новый центр является решением задачи Вебера [10], для чего используется итеративная процедура Вайсфельда [11] или более совершенные ее модификации [12]. Вследствие этого требуется гораздо больше вычислительных ресурсов. В общем случае непрерывную задачу k-средних можно сформулировать следующим образом: N argmin V min LIX.,Ai ), (1) X,, ..., XpeRfT1 M1^ V - ’ где {Al, ..., An} - множество известных точек - векторов данных в d-мерном пространстве; X1, ..., Xp - искомые точки (центры кластеров); L( ) - некоторая функция (метрика) расстояния. В случае евклидовой метрики L ( X-, A ) = d=1 (xjk - aik ) мы имеем p-медианную задачу. Здесь x- = (/... -) у/ = 1,p, д. = (^... aik) 56 Математика, механика, информатика У1 = 1, N . В случае квадратичной евклидовой метрики L ( Xj, Ai ) = £ £( xjk - aik )2 при wi= Wi = lN мы имеем задачу k-средних. Алгоритм 1. ALA-алгоритм. Дано: начальные центры Xi, ...,X* є{, ...,An} . 1. Для каждого вектора данных At є A1, ..., AN найти ближайший центр Ct= arg min L ( Ai. ,X ). j=1,k ' ' Сформировать k множеств (кластеров) векторов данных, для которых каждый из k центров является ближайшим: N^ = {i є {і, N} | Ct = j} . 2. Для каждого кластера Nc‘ust, j = 1, k рассчитать его центр Xj. 3. Если на шаге 2 значение хотя бы одного из центров поменялось, то перейти к шагу 1. 4. Иначе останов. В случае задачи k-средних такой алгоритм называется стандартной процедурой k-средних (р-средних). Для задачи k-средних нахождение нового центра кластера - весьма простая задача: x,k= £ aik/\C^\Vk = ЇД ієСсІШІ j Здесь |cc4“'| - мощность множества. В случае евклидовой метрики центр кластера является решением задачи Вебера [10], его приближенное значение может быть получено с использованием итеративной процедуры Вайсфелда [11; 12]. Для снижения вычислительных затрат на шаге 2 пересчитываются центры лишь тех кластеров, состав которых изменился на шаге 1. Результат описанного алгоритма зависит от выбора начальных значений центров. Известная процедура k-means++ [14] имеет преимущество перед хаотическим выбором начальных центров, гарантируя точность результата 0(log(p)). Тем не менее такая точность может быть неприемлема для многих практически важных задач. В этом случае используются различные техники рекомбинации множеств начальных центров. Существует множество подходов к оптимизации работы ALA-алгоритма, например сэмплинг [14] (решение задачи на случайным образом выбранной части данных и использование результата в качестве начального решения при решении полной задачи), различные потоковые алгоритмы для работы с большими объемами данных [15] и др. Зависимость результатов ALA-алгоритма, как и любой процедуры локального поиска, от заданных начальных значений является серьезной проблемой также и с точки зрения воспроизводимости результатов работы алгоритма классификации: при разных запусках алгоритма, в зависимости от выбора начальных значений центров кластеров, одни и те же векторы данных могут относиться к различным кластерам (в терминологии классификации элементной базы -относиться к различным партиям) либо к одному и тому же кластеру (к одной производственной партии). Таким образом, требуется разработка алгоритма кластерного анализа, дающего стабильный результат. Иными словами, требуется повышение точности используемого оптимизационного алгоритма. Превосходные результаты могут быть получены для задач кластерного анализа и классификации с использованием метода Information Bottleneck Clustering -метода «бутылочного горлышка» при кластеризации [16]. Работа данного алгоритма начинается с рассмотрения каждого из векторов данных как отдельного кластера. Затем из системы один за другим удаляются «лишние» кластеры, пока не останется требуемое количество. Каждый раз удаляется кластер, удаление которого дает наименьший прирост суммарного квадратичного расстояния от векторов данных до ближайшего из центров кластеров. Такие алгоритмы чрезвычайно медленные [16]. Некий компромисс представляют собой генетические алгоритмы с жадной эвристикой [17], изначально разработанные для решения /»-медианной задачи на сети, в редакции, предложенной в работе [18], могут быть применены для решения непрерывных задач. Идею подхода можно изложить следующим образом [9]. Алгоритм 2. Генетический алгоритм с жадной эвристикой для/-медианной задачи. Дано: Размер популяции NP. 1. Сформировать (случайным образом или с использованием процедуры k-means++) NP различных начальных решений х1, ..., XN с ft N}, |xi| = P ^i = = 1, N- множеств индексов векторов данных мощности P, используемых в качестве исходных решений ALA-алгоритма. Для каждого из начальных решений оценить значение целевой функции Ffltness ( x), которое здесь и далее вычисляется алгоритмом 3, сохранить значения данной функции в переменных ... fNk. 2. Если достигнуты условия останова, то останов. Решением является начальное решение х * , которому i соответствует наименьшее значение fi. Для нахождения окончательного решения запускается ALA-алгоритм (алгоритм 1). 3. Выбрать случайным образом два индекса k1, k2 є {1, N}, k1 Ф k2 . 4. Получить промежуточное решение X с = X k1 u X k2 . 5. Если |хc > p , то перейти к шагу 7. 6. Вычислить j* = argminFeine,,(xc \ {j}). Исключить jєXc v ' j* из Xc : Xc = Xc \{j*}- Перейти к шагу 5. 7. Если 3i є {1, N }: хt = Xc, то перейти к шагу 2. 8. Выбрать индекс k3 є {1, Np }. Выбираются случайным образом два индекса k4, k5 є{1, N}, если f4 > f5 , то k3 =k4, иначе k3 = k5 . 57 Вестник СибГАУ. 2014. N 4(56) 9. Заменить х*3 и соответствующее значение цеЛевой функдии: X i3 = X с , fh = F fitness (х с ). ПеРейти к шагу 2. Определение значения целевой функции осуществляется при помощи алгоритма 3ю Алгоритм 3. Вычисление целевой функции F ( x ) fitness \r^/ ' Дано: начальное решение x . 1. Запустить алгоритм 1 с начальным множеством центров {Ai \i є x}, получить множество центров {*1, ..., Xp}. 2. Возвратить значение Ffiness (X) = = VN w min L(Xt,A). Шаг 4 алгоритма 2 порождает промежуточное решение - множество мощности до 2p, из которого последовательно исключаются (шаг 6) элементы до достижения мощности p. При этом на каждой такой итерации требуется количество вычислений функции Ffintess, соответствующее текущей мощности множества - промежуточного решения. В настоящей работе предлагается уменьшить количество центров в промежуточном решении, порождаемом на шаге 4. Одной из идей, применяемых для улучшения результата локального поиска, достигнутого ALA-алгоритмом, является замена части центров в решении на случайным образом выбранные векторы данных [18]. В нашем случае добавляем к начальному решению некоторое число элементов другого начального решения, а затем последовательно исключаем центры из начального решения, пока не останется p центров. Количество добавляемых центров выбирается случайным образом. Таким образом, шаг 4 алгоритма 2 приобретает следующий вид: 4.1. С помощью генератора случайных чисел выбрать целое r є {1, p}. 4.2. Из множества x* выбрать случайным обра- * зом подмножество X k мощности r. 4.3. Получить промежуточное решение Xс = X*3 U х*2 . Результаты. В зависимости от класса электронного компонента и от конечного узла, в монтаже которого будет использован данный элемент, применяется различное количество тестов. Так, например, для микросхемы 1526ЛЕ5 были сняты показания 55 измерений, различающихся и размерностью, и измеряемой физической величиной. Разработанные алгоритмы кластеризации были применены для классификации партий радиоэлектронных изделий по производственным партиям, различающимся условиями производства и, следовательно, характеристиками, измеряемыми при проведении неразрушающих испытаний. Кроме того, данные алгоритмы были применены и для определения количества партий в тестируемом множестве изделий. Пространство результатов измерений нормируется [19]. Для визуализации результатов измерений и производимой с помощью разработанных алгоритмов классификации тестируемых радиоэлектронных изделий был применен метод MDS (Multi-Dimensional Scaling -многомерное масштабирование [16; 20]) и собственно средства визуализации ELKI [21] и GNUPlot. Данные программные разработки распространяются по лицензии GNU GPL с открытым исходным кодом, что делает их удобными для интеграции в сложные прикладные разработки. Были использованы 10 сборных партий различных ЭРИ (диоды, стабилитроны, полевые транзисторы, микросхемы), каждая из которых содержала от одной до семи производственных партий, различающихся условиями изготовления. Объемы сборных партий -от 60 до 1250 единиц продукции. Алгоритмы классификации были запущены для каждой из партий 10 раз с различными значениями параметра k (предполагаемое число кластеров-партий ЭРИ) от 1 до 10. Результаты разбиения сборной партии микросхемы 1526ЛЕ2 на предполагаемые производственные партии для k от 1 до 4 показаны на рисунке. Результаты разбиения показаны в условном двумерном пространстве (результат процедуры MDS). Визуально для микросхемы 1526ЛЕ5 можно различить 3 кластера, что соответствует фактически присутствовавшим в сборной партии (всего 825 единиц) экземплярам трех производственных партий. Результатом работы алгоритмов кластеризации является собственно соответствие номеров единиц продукции в сборной партии и номеров предполагаемых производственных партий, а также суммарный разброс параметров результатов измерений в нормированном пространстве, являющийся целевой функцией алгоритмов. Зависимость данного суммарного разброса от количества предполагаемых производственных партий (т. е. от количества кластеров k) сведены в табл. 1. Из табл. 1 видно, что для изделия 1526ЛЕ5 значение целевой функции в первой партии изделий (825 единиц изделий) резко падает с ростом k до значения k = 4 (четыре производственных партии). Для второй партии (1132 изделия) такое поведение целевой функции не характерно вследствие того, что данная партия составлена из изделий лишь одной производственной партии. Все результаты получены за время, не превышающее 5 с (данное время было задано как условие останова алгоритма). Для сравнения: обработка данных той же первой партии изделия 1526ЛЕ5 из 825 единиц методом Information Bottleneck Clustering потребовала более 15 мин времени на машине с процессором Intel Xeon с тактовой частотой 2 ГГц при сравнимых по точности результатах. В табл. 2 приведены сравнительные результаты различных методов, примененных для классификации первой партии изделий. Новый алгоритм дает стабильные результаты (минимальный разброс значений) при высокой скорости выполнения расчета. 58 Математика, механика, информатика Таблица 1 Зависимость значения целевой функции (суммарного расстояния до центров кластеров) от числа предполагаемых производственных партий к изделия 1526ЛЕ5 к Партия 1 (сборная) Партия 2 (однородная) Ffitness ( X ) В % от предыдущего значения Ffitness ( X ) В % от предыдущего значения 1 84359 - 32984 - 2 53968 63,9 % 29355 89 % 3 37985 70,4 % 27110 92,3 % 4 27329 71,9 % 25320 93,4 % 5 21098 77,2 % 23927 94,5 % 6 19865 94,2 % 22754 95,1 % 7 18952 95,4 % 21821 95,9 % 8 18091 95,5 % 21035 96,4 % 9 17357 95,9 % 20425 97,1 % 10 17021 98,1 % 20078 98,3 % 1 1 1 1 1 1 + 1 1 1 1 1 У 1 1 с t 1 1 1 1 кластер(партия) 20 2 кластера (партии) • ’<д.: < * * + -р ** *1+ * * * -t + * • * it* t * * , io . _ + ^ М +л+ І ’ Г-С4* і*, , x ‘ * t t’ ■*** t/ , і ?*"***' * * “ - * ■ . ; л% * ■ * .#++ C*. ./Лм' ,ti * . , - * С * * * *-■>“*, 5 + * * ** ■ f . rv< Vv*“*T*> ■ 0 + + Л + T * * x * 1 . ** & * . ' •• . -10 .♦ Щ, < -і-1-j-1-1-1-1-1-1- -30 -1-L-1-J.-1-L-L-L-L- Щ -15 -и -S 0 5 10 15 20 20 15 10 -5 0 5 10 15 И) ill. -і-г-и-і-г . 3 кластера(партии) 30 г p p і I- Т"-^-1- г г 4 кластера(партии) j* K * * к - V, - • . ■ . ■ ч*5 < ‘ «« "у * ** ■ . + 51 ' V * + *< * _ * х А- + я 10 0 * « □ ■ : t.ü-42*v *-+н|=„0° - ■ : >, '* "V" *= ' + ’ І*А_ ' . ° DTtJ О о * А о -10 * ^ - ■ .■'“j * H * J % - к - -20 ■20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20 Разбиение сборной партии микросхемы 1526ЛЕ5 на 1-4 кластера, представляющих предполагаемые производственные партии 59 Вестник СибГАУ. 2014. N 4(56) Таблица 2 Сравнение результатов различных методов для первой партии изделия 1526ЛЕ5 при к = 4 Алгоритм Число запусков Время на 1 запуск, с Среднее значение F ( х ) fitness уА/ Точность в сравнении с наилучшим известным значением Лучшее значение F ( X ) fitness Наихудшее значение F (x ) fitness \r^/ Pазброс значений, % Information Bottleneck 1 972 27318,1 99,996 % 27317,1 27317,1 k-means++ 30 5 27398,4 99,7 % 27316,9 27416,9 0,37 % Новый алгоритм 30 5 27320,1 99,98 % 27316,9 27321,1 0,015 % Заключение. Задача классификации поступающих партий электрорадиоизделий по производственным партиям с различными условиями производства на основе данных неразрушающих тестов может быть сведена к задаче кластерного анализа. Применение предложенного в настоящей работе генетического алгоритма с особой эвристикой позволяет решать подобные задачи, получая стабильный результат. Библиографические ссылки

Об авторах

Лев Александрович Казаковцев

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: levk@bk.ru
кандидат технических наук, доцент, доцент кафедры информационных экономических систем

Виктор Иванович Орлов

ОАО «ИТЦ - НПО ПМ», г. Железногорск

директор

Алена Александровна Ступина

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: saa55@rambler.ru
доктор технических наук, профессор, профессор кафедры системного анализа и исследования операций

Игорь Сергеевич Масич

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: i-masich@yandex.ru
кандидат физико-математических наук, доцент, доцент кафедры системного анализа и исследования операций

Список литературы

Дополнительные файлы