SILHOUETTE CRITERION FOR AUTOMATIC GROUPING ALGORITHM OF SPACESHIP ELECTRONIC COMPONENTS

全文:

Введение. Одним из основных путей повышения надежности сложных технических систем является комплектация их электронных узлов компонентами наивысшего качества. Также в случае однородности характеристик однотипных компонентов электронного узла достигается высокий уровень согласованности работы, что влечет за собой повышение надежности узла и системы в целом. Для высокой степени однородности характеристик компонентов узла необходимо отбирать для комплектации компоненты, произведенные в рамках одной производственной партии из одной партии сырья [1]. К примеру, в список требований к критически важным узлам может быть включено условие комплектации спецпартиями электронной компонентной базы с повышенными требованиями к составляющим, в том числе к однородности характеристик [2; 3]. Производители электронных компонентов в США и странах Европейского союза выпускают специальный класс продукции для космической отрасли (Space), отличный от военного (Military) класса [4; 5]. В России же специализированные производства электронной компонентной базы (ЭКБ) - электрорадиоизделий (ЭРИ) для космической отрасли - отсутствуют, поэтому ЭРИ общего военного (неспециализированного) применения [2; 3] категорий качества «ВП» и «ОС» («ОСМ») должны подвергаться демонстрации возможности использования в аппаратуре космических аппаратов (КА). ЭКБ иностранного производства, которая находит все более широкое распространение в аппаратуре КА, также должна подвергаться квалификации по условиям применения и уровню качества, поскольку в настоящее время не существует никаких документов о гармонизации систем качества отечественной и импортной ЭКБ. Поэтому демонстрация возможности использования ЭРИ в аппаратуре КА в течение длительного времени (на основе разработки принципов и правил) включает разработку методологии обеспечения качества и работоспособности ЭКБ при воздействии факторов космического пространства. Для исключения попадания в бортовую аппаратуру КА с длительными сроками службы потенциально ненадежных ЭРИ в последние годы внедряется новый принцип комплектования аппаратуры через специализированные испытательные технические центры [6; 7] с проведением операций сплошного входного контроля ЭРИ, дополнительных отбраковочных испытаний (ДОИ), диагностического неразрушающего контроля (ДНК) с применением выборочного разрушающего физического анализа (РФА). Задачей ДОИ и ДНК ЭРИ является, по существу, индивидуальная отбраковка элементов, имеющих скрытые дефекты изготовления. РФА проводится с целью определения соответствия образцов ЭРИ требованиям конструкции и технологического процесса изготовления и выявления нарушений этих требований. Таким образом, все проводимые над ЭРИ испытания можно разделить на две группы: 1) сплошные испытания для всей партии элементов - ДОИ, ДНК; 2) выборочные испытания для нескольких элементов из партии - РФА. Многие из эксплуатируемых до 2000 г. КА, разработанных и изготовленных АО «Информационные спутниковые системы» имени академика М. Ф. Решетнева», в первые дни, месяцы эксплуатации имели замечания по качеству функционирования: сбои, перерывы в связи, отказы, значительная часть которых по результатам анализа возникала из-за отказов ЭРИ. И только на эксплуатируемом с 18 апреля 2000 г. КА Sesat не выявлено существенных замечаний к ЭРИ в течение более 15 лет эксплуатации. Одной из главных причин, по мнению многих специалистов, является то, что впервые в практике все 100 % ЭРИ, комплектующих бортовую аппаратуру КА Sesat, прошли ДОИ, ДНК и РФА [7]. Аналогичные результаты, а именно, отсутствие или существенное снижение количества замечаний к работе ЭРИ, прошедших данный набор испытаний (ДОИ+ДНК+РФА) [8; 9], позволяют сделать вывод о состоятельности подхода к испытаниям, в состав которого входят именно эти три основных компонента. Важное значение имеет разработка методов прогнозирования и обеспечения работоспособности ЭРИ при неблагоприятных внешних воздействиях. Одно из центральных мест при этом занимают методы обеспечения устойчивости к тепловым и радиационным нагрузкам [10-12]. Вопросы обеспечения радиационной стойкости (РС) БА изложены в литературе, например в [13-16], но она в основном посвящена применению ЭРИ в предположении, что стойкость любого ЭРИ из производственной партии известна и одинакова. На самом деле РС ЭРИ внутри производственной партии различна и зависит от содержащихся в каждом ЭРИ внутренних дефектов (дислокации, неконтролируемые примеси, другие точечные дефекты) [17]. Собственно выявление наиболее существенных из таких дефектов в партиях изделий является целью проведения РФА. При этом распространять результаты проведенного РФА на всю поступившую партию изделий необходимо с большой осторожностью. Для этого нужно, как минимум, быть уверенными в том, что мы имеем дело действительно с единой партией ЭРИ, изготовленной из единой партии сырья. Поэтому выявление истинных производственных партий из предположительно сборных партий ЭРИ является одним из важнейших мероприятий при проведении испытаний. Для выявления однородных партий используются алгоритмы кластеризации, некоторые подходы к этой проблеме рассмотрены в [1; 18; 19]. Одной из основных задач при этом является определение предполагаемого количества партий. Задача определения числа групп. Задача автоматической группировки (разбиение на кластеры) требует задания числа групп (кластеров) k, значение которого априори неизвестно. Автоматическое определение числа групп является одной из труднейших задач в классификации данных. Большинство методов автоматического определения числа групп сводятся к проблеме выбора модели. Алгоритмы классификации запускаются при различном числе групп, наилучшее значение выбирается на основании определенного критерия, по которому оценивается эффективность группировки - компактность и взаимная удаленность выявленных групп в нормированном пространстве. В литературе по автоматической группировке и кластерному анализу упоминаются следующие критерии: индекс Дэвиса-Боулдина (DBI) [20], индекс Калински-Харабаша [21], индекс Кржановски-Лая [22], критерий Хартигана [23], GAP-критерий [24], информационный критерий Байеса (BIC) [25], информационный критерий Акаике (AIC) [26], критерий силуэта [27; 28]. Критерий Хартигана: в котором N - число объектов; WK и WK+1 - минимальные значения критерия суммарного разброса параметров при разбиениях на K и K+1 кластеров. Согласно правилу Хартигана, надо последовательно разбивать множество на все большее число кластеров K до тех пор, пока HK не станет меньше 10, именно это K и надо брать в качестве оценки числа кластеров. Информационный критерий Акаике (AIC): где l - значение логарифмической функции правдоподобия построенной модели; k - количество использованных (оцененных) параметров. Наилучшей считается модель с наименьшим значением критерия. Байесовский информационный критерий (Bayesian information criterion, BIC, иногда - Schwarz Criterion) - критерий выбора модели из класса параметризованных моделей, зависящих от разного числа параметров, используемый также в задачах автоматической группировки данных. Для оценивания модели обычно используется метод нахождения максимума функции правдоподобия, значение которого можно увеличить добавлением дополнительных параметров. Однако это может вызвать переобучение. Байесовский критерий устраняет проблему переобучения, штрафуя увеличение числа параметров модели (в случае автоматической группировки - штрафуя увеличение числа групп). Тесно связан с критерием Акаике, но в случае байесовского критерия увеличение параметров штрафуется строже. С помощью критерия BIC можно оценить наиболее подходящее число групп K при автоматической группировке объектов. Формула BIC имеет следующий вид: где lj(δ) - логарифм максимального значения функции правдоподобия для данных δ в соответствии с j-й моделью; pj - число параметров в модели Mj; pj = (D + 1) × × K; D обозначает размерность вектора входных данных. Следует выбирать модель с наибольшим значением этого критерия, и таким образом можно выбрать число кластеров. Критерий «силуэт» изначально был создан как средство интерпретации и подтверждения результатов автоматической группировки данных. Предположим, что данные были разгруппированы на k групп (кластеров). Для каждого экземпляра i определим a(i) - среднее расстояние от экземпляра i до других экземпляров того же кластера. Величина a(i) показывает, насколько правомерно объект i отнесен к данному кластеру (чем меньше значение, тем более обоснованно отнесение этого объекта группе). Будем определять среднее расстояние от объекта i до кластера c как среднее расстояние от i до объектов c. Определим b(i) как наименьшее среднее расстояние от объекта i до любого другого кластера, к которому этот объект не относится. Кластер с наименьшим средним расстоянием будем называть соседним кластером к i. Определим силуэт следующим образом: . Иначе можно записать: Отсюда следует, что . Для того, чтобы s(i) было близко к 1, требуется a(i) << b(i). То есть s(i), близкое к единице, означает, что объект правильно классифицирован. Если же значение s(i) близко к -1, то это означает, что правильнее было бы отнести этот объект к соседнему кластеру. Если s(i) около нуля, то это означает, что объект находится на границе двух кластеров (рис. 1). Среднее s(i) по всем объектам кластера является мерой того, насколько плотной является соответствующая группа, и того, насколько правильно проведена группировка в целом. Если при группировке было выбрано слишком малое или слишком большое число групп, то этот критерий будет принимать низкое значение. Таким образом, этот критерий можно использовать для выбора числа групп. Значения различных критериев применительно к сборной партии интегральных схем космического применения приведены в табл. 1. Критерий силуэта пригоден к использованию только при условии наличия 2 или более кластеров в исследуемых данных. Следует провести оценку распределений частот и плотностей числовых характеристик на наличие многомодальности, что укажет на возможность разделения исходной выборки на группы, сходные по характеристикам объектов [29]. Недостатком оригинального критерия является то, что его использование требует значительных вычислительных ресурсов. Поэтому вместо него иногда имеет смысл использовать ускоренный критерий, который вычисляется намного быстрее, но по качеству практически не уступает оригинальному критерию. При вычислении ускоренного критерия определим a(i) как расстояние от объекта i до центра кластера, к которому он относится. В свою очередь, b(i) определяется как расстояние, наименьшее до центров групп, к которым данный объект не принадлежит, т. е. расстояние до центра соседнего кластера. Результаты вычислительных экспериментов, проведенные с партиями изделий, состав которых априори известен, показали, что наиболее информативным является критерий силуэта и его ускоренная оценка (табл. 1). Остальные критерии фактически являются свертками двух критериев: собственно целевой функции и количества групп k. Определение количества групп (партий) изделий предлагается проводить в соответствии с максимальным значением критерия силуэта. Рис. 1. Значения силуэта для элементов кластеров (разбиение на 2 кластера) на примере задачи разбиения множества интегральных схем по предполагаемым производственным партиям. Экземпляры со значением s(i) < 0,20 помечены знаком «?» (нечетко классифицированные) Таблица 1 Значения целевой функции и критериев оценки эффективности разбиения на группы в зависимости от их числа для изделия 1526ЛЕ5 k Целевая функция Критерий Хартигана Критерий силуэта ускоренный Критерий силуэта Критерий BIC Критерий AIC 1 84359 220,4895 - - 334844 5302219 2 53968 206,9374 0,53918 0,41129 316973 3189458 3 37985 54,3987 0,57784 0,45594 295186 1730708 4 27329 46,9809 0,53645 0,38642 291719 1549824 5 21098 35,9868 0,48232 0,34088 287171 1347527 6 19865 23,0933 0,44891 0,31559 282926 1182413 7 18952 22,6444 0,43588 0,29702 281246 1113269 8 18091 20,4564 0,42419 0,28621 279008 1032668 9 17357 15,0933 0,39457 0,25063 277946 988834 10 17021 13,4691 0,38525 0,23961 276951 968357 Проблема отсева «выбросов». Кроме надежного определения принадлежности каждого из векторов данных к тому или иному кластеру, критерием которого может служить силуэт каждого из векторов данных, требуется также определить, входит ли тот или иной вектор данных в какой-либо из кластеров или же он является отдельным, далеко отстоящим от всех кластерных структур вектором (так называемым выбросом - outlier). Наличие «выбросов» - отдельно стоящих элементов вне кластеров - может быть вызвано различными причинами, например, ошибкой при проведении измерений каких-либо из параметров или же фактическим значительным отклонением этих параметров от значений, типичных для остальной части партии, у конкретного экземпляра ЭРИ вследствие брака или вследствие попадания единичных экземпляров из другой партии. Такие «выбросы» в любом случае являются аномалией в рамках партии ЭРИ, и данные экземпляры не должны отбираться, например, для проведения разрушающего физического анализа. Также на них не могут быть распространены результаты РФА, выполненного на каких-либо из «типичных» экземпляров партии. В настоящее время в литературе нет единого подхода к определению «выбросов», соответственно, нет и единой методологи. Тем не менее, логично считать «выбросом» точку (вектор данных), которая отстоит на значительном расстоянии от других точек. Значительным будем считать расстояние, которое в q раз превосходит среднее внутрикластерное расстояние. Для данной цели введем следующий критерий для каждого из векторов данных A1, …, AN: где Ci - кластер (множество векторов данных), которому принадлежит i-й вектор данных; |Ci| - его мощность (количество векторов данных в нем). Здесь для измерения расстояния используется та метрика или мера расстояния, которая используется и при решении задачи k-средних. В числителе дроби - среднее расстояние от i-го вектора данных до других векторов «своего» кластера, в знаменателе - среднее внутрикластерное расстояние по всей партии ЭРИ. Таким образом, например, для «отсева» (т. е. для причисления их к «выбросам») тех векторов данных, для которых расстояние до других векторов «своего» кластера в q раз превышает среднее внутрикластерное расстояние, требуется проверить условие Koutlier > q. В нашем реализованном программном приложении используется модифицированный критерий и, соответственно, иное пороговое значение: , . Так, если требуется отсечь в качестве «выбросов» векторы данных, для которых среднее внутрикластерное расстояние превышено в два раза, следует установить значение Именно это значение мы использовали в наших экспериментах. Таким образом, «выбросы» определяются проверкой условия . а б Рис. 2. Сборная партия ИС 140УД17АВК, разбиение на группы: а - многомерное шкалирование; б - критерий силуэта Таблица 2 Результаты разбиения экзаменационных выборок интегральных схем Показатель ИС 140УД25АС1ВК ИС 140УД17АВК Партия № 1 30 26 Партия № 2 26 24 Всего 56 50 По результатам работы алгоритма классификации Партия № 1 27 26 Партия № 2 26 24 Неклассифицированные 3 (8,9 %) 0 (0 %) Ошибочные 0 0 С целью проверки работоспособности метода автоматической группировки электрорадиоизделий по производственным партиям мы исследовали партии интегральных схем, заведомо составленные из двух или трех различных производственных партий. Для визуального представления многомерных данных использовалось многомерное шкалирование [30]. На диаграмме многомерного шкалирования (рис. 2) цифрами обозначены номера предполагаемых производственных партий, «Х» и «?» - неклассифицированные элементы. На графике критерия силуэта показана зависимость значения критерия от предполагаемого числа производственных партий. На рис. 2 показано разбиение сборной партии операционных усилителей на две предполагаемые производственные партии, а также значения критерия силуэта для различных вариантов разбиения на разное число партий. Видно, что максимальное значение критерия силуэта четко указывает на число производственных партий, равное двум. Отметим, что разбиение всех элементов, кроме помеченных как ненадежно классифицированные, совпадает с их реальной принадлежностью к той или иной производственной партии. К ненадежно классифицированным отнесены элементы, лежащие за пределами какого-либо из кластеров. При этом наиболее важным вопросом остается адекватность классификации. Были проведены эксперименты на экзаменационных выборках ИС, состав элементов с разбивкой на производственные партии был заранее известен. В табл. 2 показаны результаты разбиения этих выборок. Заключение. Применение критерия силуэта позволяет эффективно определять число производственных партий в сборной партии, что, в свою очередь, позволяет повысить эффективность алгоритма автоматической группировки и более точно классифицировать электрорадиоизделия.

作者简介

V. Orlov

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. Masich

Reshetnev Siberian State Aerospace University

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

参考

补充文件