Методы и алгоритмы отбора метрик программной инженерии в условиях отсутствия размеченных данных и моделей машинного обучения тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Холматова Замира Шухратовна

• Холматова Замира Шухратовна
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Холматова Замира Шухратовна

Введение

Глава 1. Обзор метрик программной инженерии и методов их

отбора

1.1 Метрики программной инженерии

1.1.1 Роль метрик в программной инженерии

1.1.2 Метрики поздних этапов жизненного цикла разработки программного обеспечения

1.2 Проблема избыточности метрик

1.3 Методы отбора метрик

1.4 Выводы

Глава 2. Методика отбора метрик программной инженерии

2.1 Представление репозитория для анализа метрик

2.2 Подход к отбору метрик программной инженерии

2.2.1 Ошибка Сэммона

2.2.2 Метоя роя частиц

2.2.3 Генетический алгоритм

2.2.4 Агрегация результатов

2.3 Описание экспериментов

2.3.1 Данные

2.3.2 Детали реализации

2.4 Результаты и анализ

2.4.1 Результаты на обучающем наборе данных

2.4.2 Сравнение с результатами на валидационном наборе данных

2.4.3 Ограничения

2.5 Выводы

Глава 3. Анализ корреляции между метриками

3.1 Методы определения корреляции между метриками

Стр.

3.2 Мета-анализ в программной инженерии

3.3 Теоретические основы мета-анализа

3.3.1 Протокол проведения мета-анализа

3.3.2 Размеры эффектов

3.3.3 Мета-аналитические модели

3.4 Мета-анализ как метод агрегации результатов различных исследований

3.4.1 Применение мета-анализа для определения энергоэффективного языка программирования

3.4.2 Применение мета-анализа для определения энергоэффективного алгоритма сортировки

3.4.3 Ограничения мета-анализа

3.5 Определение пар коррелируемых метрик

3.5.1 Методика определения коррелируемых метрик

3.5.2 Анализ результатов

3.6 Выводы

Глава 4. Модифицированная методика отбора метрик

4.1 Предлагаемая модифицированная методика

4.1.1 Мета-анализ корреляций

4.1.2 Метод исключения коррелируемых метрик

4.2 Описание экспериментов

4.3 Анализ результатов

4.4 Выводы

Заключение

Список сокращений и условных обозначений

Словарь терминов

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

Список рисунков

Список таблиц

Стр.

Приложение А. Метрики, используемые в исследовании по

изучению применения мета-анализа для семейств экспериментов

Приложение Б. Пары метрик, демонстрирующих высокую

корреляцию

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы отбора метрик программной инженерии в условиях отсутствия размеченных данных и моделей машинного обучения»

Введение

Актуальность метрик программного обеспечения была осознана с самого начала развития программной инженерии, когда еще более 50 лет назад исследователи начали рассматривать их многогранное применение [1]. Например, уже в середине 1960-х годов метрика под названием "Число строк кода" (англ. LOC - lines of code) использовалась инженерами-программистами для измерения усилий и производительности [2]. Основываясь на этой метрике исследователи строили модели по оцениванию стоимости и качества программного продукта [3; 4].

В 70-х годах прошлого столетия с увеличением разнообразия в языках программирования практики и ученые в области программной инженерии признали очевидный недостаток использования числа строк кода как метрики для предсказания усилий или качества программ: например, число строк кода, написанных на ассемблере, несопоставимо с числом строк кода, созданных на высокоуровневом языке [2].

Однако отсутствие надежных инструментов для сбора метрик и ограничение доступности индустриально значимых метрик считалось основным препятствием на пути развития данной области [2]. Вычисление метрик было сложной задачей, требующей использования дорогостоящих инструментов и/или глубоких знаний семантики языков программирования. Например, в работах Мюллера для анализа и визуализации различных аспектов системы использовался байт-код программы (промежуточный, машинно-независимый код низкого уровня) [5; 6]. В качестве другого примера можно рассмотреть проект Genoa - анализатор кода, который требовал от своих пользователей, как минимум, понимания таких концепций, как абстрактные синтаксические деревья или язык спецификаций GENII [7]. Для использования этих приложений простым разработчикам часто не хватало специальных знаний.

Благодаря масштабным исследованиям и разработкам в этой области, проводимым международными исследовательскими группами, метрики стали доступными для вычисления, чем вызвали рост интереса у индустриальных компаний. К началу текущего столетия Фентону [2] удалось систематизировать метрики: согласно его классификации - любая метрика измеряет или предсказывает какой-либо атрибут (внутренний или внешний) некоторого

продукта, процесса или ресурса. Объяснение связи метрик с целями и задачами продуктовой разработки способствовало повышению интереса к ним со стороны индустриальных компаний и их активному использованию руководителями для поддержки принятия управленческих решений.

В контексте управления продуктом или проектом метрики используются для решения задачи оценки качества программного обеспечения [8—11]. Ученые выяснили, что несмотря на то, что большинство дефектов появляются на ранних этапах разработки, более половины из них удается выявить лишь на поздних этапах жизненного цикла создания программного обеспечения, так как именно на этих этапах становится возможным вычисление показателей, относящихся к различных свойствам кода. Поэтому определение самих поздних этапов и анализ метрик этих этапов сможет способствовать более глубокому пониманию фаз разработки, что, в свою очередь, приведет к принятию обоснованных решения для успешного управления продуктом.

И сегодня, благодаря инструментам, разработанным за последние 25 лет [12; 13] (включая инструменты с открытым исходным кодом [14]), для исследователей и разработчиков стало возможным вычислять огромное количество метрик, таких как объем вклада каждого разработчика, количество изменений в файлах и многих других. Однако возможность рассмотрения огромного количества программных метрик породила следующие проблемы:

1. Использование слишком большого количества метрик ставит перед пользователями проблему достоверности статистического анализа. Например, коллинеарность между метриками увеличивает дисперсию между ними и, таким образом, приводит к неправильному определению доминирующих предикторов в регрессионном анализе [15].

2. Большие объемы данных могут скрывать шум, который способен привести исследователей к неверным результатам при работе со статистическими моделями. Без механизма отбора признаков при наличии большого количества зашумленных переменных статистические модели суммируют небольшие шумовые вклады, что приводит их к большим ошибкам предсказания [16].

3. Неэффективное управление данными, включая хранение, предварительную обработку и увеличение вычислительной сложности операций над данными [17].

Данная проблема называется отбором признаков и имеет следующую формулировку:

min C(X,XS), (1)

sc{i,...,P},\s\=k

где X Е Щпхр - матрица признаков, п - количество наблюдений, р - количество признаков, Xs - матрица, составленная из колонок X с индексами из S, L - целевая функция, количественно характеризующую потерю информации при переходе от полного набора признаков X к уменьшенному Xs.

Таким образом, для решения этой задачи в области программной инженерии требуется найти такое подмножество метрик, которое бы дало минимальное значение целевой функции. Ученые уже предложили различные подходы к отбору метрик, которые можно разделить на две группы:

1. требующие размеченных данных;

2. не требующие размеченных данных.

Размеченные данные означают, что данные были помечены описательной информацией или классифицированы экспертом (человеком или алгоритмом машинного обучения). Поэтому исследования первой группы требуют, чтобы данные были "размечены". Исследователи в этих работах пытаются удалить некоторые метрики из исходного набора и оценить производительность алгоритмов машинного обучения с учителем до и после удаления, стремясь минимизировать целевую функцию, отражающую разницу между замеренной производительностью [18—27]. Однако предложенные методы могут не подойти для задач, которые решаются другими алгоритмами обучения с учителем. Например, подход для отбора метрик, предложенный в рамках решения задачи предсказания дефектов, может оказаться не столько эффективным при решении задачи оценки стоимости программного обеспечения. Это связано с тем, что разметка данных часто зависит от контекста и может быть субъективной, что приводит к менее обобщаемым результатам.

Исследования второй группы включают в себя методы, которые уменьшают количество метрик, не требуя размеченных данных. В таких исследованиях ученые сравнивали результаты работы алгоритмов машинного обучения без учителя, таких как кластеризация, или пытались извлечь тематику и создать графы знаний [28; 29]. Главный недостаток методов из второй группы заключается в том, что разная производительность алгоритмов

обучения без учителя, применяемых к исходному и сокращенному набору метрик, не означает, что метод поиска оптимального набора метрик работает плохо. Например, метод к-средних может плохо справиться с кластеризацией данных с выбросами или достаточно похожими метриками, а затем правильно кластеризовать уменьшенный набор данных. В таком случае выводы по оптимальному набору метрик могут быть противоречивыми и ненадежными. При использовании методов кластеризации на основе плотности возникают сложности с выбором подходящих уровней плотности: уровень плотности, выбранный для кластеризации всего набора метрик, может не соответствовать кластеризации уменьшенного набора [30].

Помимо предложения самого метода для отбора метрик программной инженерии, важную роль имеет исследование и определение коррелируемых метрик. Анализ коррелируемых метрик позволяет:

— улучшить процесс отбора за счет исключения избыточной информации;

— повысить релевантность выявленных метрик с учетом взаимосвязи между ключевыми свойствами программного обеспечения;

Более того, исключение коррелируемых метрик способствует улучшению предсказаний моделей машинного обучения. Многие исследователи изучали подходы к обнаружению корреляций между метриками [31—35]. В связи с тем, что корреляция замеряется между разными метриками отдельно для различных программных продуктов, многие работы для получения общего коэффициента корреляции, справедливого для всех рассмотренных продуктов, учитывали только силу, направленность и значимость взаимосвязи. Однако такой подход позволяет провести тестирование только слабых гипотез (например, равна ли нулю корреляция или нет), но никак не посчитать суммарный коэффициент корреляции [36]. В качестве надежного метода для агрегации результатов различных исследований учеными был предложен мета-анализ. В данной диссертации проблема применения мета-анализа в программной инженерии рассматривается в качестве отдельной задачи с предложением подхода для объединения как результатов различных исследований, так и результатов семейств экспериментов.

Данная диссертационная работа призвана внести вклад в решение проблемы отбора метрик программной инженерии: в ней определены метрики программной инженерии, применяемые на поздних этапах жизненного цикла разработки программного обеспечения; предложена

новая методика, не требующая размеченных данных или применения моделей машинного обучения, для отбора метрик программной инженерии; модифицирована предложенная методика отбора метрик путем включения в неё возможности учета корреляции между метриками; предложен и протестирован протокол проведения мета-анализа как метода агрегации результатов различных исследований; определены коррелируемые пары метрик, а также энергоэффективные язык программирования и алгоритм сортировки при помощи мета-анализа.

Целью настоящей диссертации является разработка подходов, не требующих размеченных данных или применения моделей машинного обучения, для отбора метрик программной инженерии, которые можно вычислить на последних этапах жизненного цикла разработки программных систем.

Для достижения поставленной цели были решены следующие задачи:

1. Определить поздние этапы жизненного цикла разработки программного обеспечения и метрики, применяемые на этих этапах;

2. Разработать методику, не требующую размеченных данных или применения моделей машинного обучения, для отбора метрик программной инженерии и реализовать соответствующий программный комплекс;

3. Провести с помощью разработанного программного комплекса вычислительные эксперименты по отбору метрик;

4. Предложить протокол для проведения мета-анализа как метода агрегации результатов различных исследований;

5. Провести вычислительные эксперименты по применению мета-анализа как метода агрегации результатов различных исследований;

6. Провести при помощи мета-анализа вычислительные эксперименты для поиска коррелируемых пар метрик программной инженерии, применяемых на поздних этапах разработки;

7. Разработать модифицированную версию методики, не требующей размеченных данных или применения моделей машинного обучения, для отбора метрик программной инженерии путем включения анализа корреляций;

8. Реализовать программный комплекс, соответствующий модифицированной версии предложенной методики, и провести с

его помощью вычислительные эксперименты по отбору метрик. Сравнить полученные результаты с результатами работы изначально предложенной методики.

Научная новизна:

1. Впервые предложена методика отбора метрик программной инженерии, основанная на методе роя частиц с ошибкой Сэммона и не требующая размеченных данных или применения моделей машинного обучения;

2. Предложен протокол проведения мета-анализа как метода агрегации результатов различных исследований, благодаря следованию этому протоколу были выявлены проблемы, препятствующие широкому распространению мета-анализа как метода агрегации результатов различных исследований в области программной инженерии;

3. Определен энергоэффективный язык программирования путем систематизации публикаций в области разработки энергоэффективных приложений и применения мета-анализа как метода агрегации результатов различных исследований;

4. Определен энергоэффективный алгоритм сортировки путем систематизации публикаций в области разработки энергоэффективных приложений и применения мета-анализа как метода агрегации результатов различных исследований;

5. Определены коррелируемые пары метрик, применяемых на поздних этапах разработки программного обеспечения, для языка программирования Java путем применения мета-анализа как метода агрегации результатов семейств экспериментов;

6. Дополнена анализом корреляций ранее предложенная оригинальная методика отбора метрик программной инженерии, основанная на методе роя частиц с ошибкой Сэммона и не требующая размеченных данных или применения моделей машинного обучения;

7. Определены поздние этапы жизненного цикла разработки программного обеспечения и метрики, применяемые на этих этапах, путем систематизации публикаций в этой области.

Теоретическая и практическая значимость представляемой работы заключается в следующем:

1. Предложенная методика отбора метрик программной инженерии, основанная на методе роя частиц с ошибкой Сэммона, не требует размеченных данных или применения моделей машинного обучения, поэтому может быть применена для широкого класса задач в качестве механизма отбора признаков;

2. Дополненная методика отбора метрик программной инженерии способна учитывать корреляцию между метриками, что делает её подходящей для задач, где важно исключить избыточную информацию;

3. Наборы метрик, найденные при помощи предложенных методик отбора, могут быть полезны для практиков и исследователей в области разработки программного обеспечения в качестве основы для управления или анализа программного обеспечения;

4. Результаты исследования мета-анализа как метода агрегации результатов семейств экспериментов, включая найденные коррелируемые метрики, позволят профильным специалистам в области программного обеспечения избежать сбора избыточной информации и сосредоточиться только на информативных метриках;

5. Проведенное при помощи мета-анализа сравнение энергоэффективности языков программирования может быть полезно при выборе технологических средств для создания энергоэффективных приложений;

6. Проведенное при помощи мета-анализа сравнение энергоэффективности алгоритмов сортировки может быть полезно при выборе технологических средств для создания энергоэффективных приложений;

7. Проведенная систематизация публикаций о поздних этапах жизненного цикла разработки программного обеспечения упрощают поиск и выбор конкретных метрик, которые могут быть применены на каждом из поздних этапов.

Методология и методы исследования. При решении поставленных задач использовались методы:

- теории вероятностей;

- теории оптимизации;

- математической статистики;

- машинного обучения. Были также использованы также подходы объектно-ориентированного программирования. Для создания комплексов программ применялись языки Python и R.

Основные положения, выносимые на защиту:

1. Разработана методика, основанная на методе роя частиц с ошибкой Сэммона, которая позволит проводить отбор метрик программной инженерии в отсутствии размеченных данных или применения моделей машинного обучения;

2. Применен мета-анализ к семействам экспериментов и результатам исследований различных ученых, позволивший выявить коррелируемые пары метрик программной инженерии и существенные проблемы, препятствующие широкому распространению мета-анализа как подхода для систематизации различных научных трудов в программной инженерии;

3. Модифицирована предложенная методика, основанная на методе роя частиц с ошибкой Сэммона, путем включения анализа корреляций между метриками программной инженерии.

Степень достоверности полученных результатов обеспечивается рядом проведенных вычислительных экспериментов с использованием данных, состоящих из метрик программной инженерии для репозиториев с открытым исходным кодом на языке Java, а также сравнением и агрегацией результатов исследований других ученых, опубликованных в рецензируемых источниках.

Апробация работы. Основные результаты работы были представлены автором на следующих научных конференциях:

1. Международная конференция "ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering" (ESEC/FSE 2020), 2020, Sacramento, California, United States;

2. Международная конференция "European Symposium on Software Engineering" (ESSE 2021), 2021, Larissa, Greece;

3. Международная конференция "Computing Conference", 2022, Virtual Event;

4. Международная конференция "9th International Conference on Data Mining and Big Data" (DMBD 2024), 2024, Ho Chi Minh City, Vietnam.

Исследования по теме диссертации поддержаны Аналитическим центром при Правительстве Российской Федерации (договор №70-2021-00143 от 01.11.2021, ИГК 000000D730324P540002), грантом Российского научного фонда (договор №19-19-00623).

Личный вклад. Результаты, представленные в работе [37; 38], получены автором самостоятельно. Работа над публикациями [39—43] проводилась совместно с соавторами, причём вклад автора является определяющим: в работах [39; 42] все эксперименты проведены автором лично и результаты получены автором самостоятельно; в работе [43] автором была выбрана методология, создан программный комплекс для проведения экспериментов и подготовлены к публикации результаты проведенных экспериментов; в работе [40] вклад автора состоит в выборе методологии исследования, подготовке результатов проведенных экспериментов к публикации и научном руководстве; в работе [41] автор участвовал в отборе, оценке качества статей и формулировании ответов на поставленные исследовательские вопросы.

Публикации. Основные результаты по теме диссертации изложены в 7 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК (К1) и индексируемых Web of Science и Scopus (Q1), 1 - в журнале, рекомендованном ВАК (К2), 4 —в тезисах докладов, индексируемых Web of Science и Scopus.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 2 приложений. Полный объём диссертации составляет 133 страницы, включая 11 рисунков и 33 таблицы. Список литературы содержит 198 наименований.

Глава 1. Обзор метрик программной инженерии и методов их отбора

Метрики программной инженерии играют важнейшую роль в анализе качества программного обеспечения. Однако, анализ современных практик показал, что полноценно оценить качество разрабатываемого продукта становится возможным только на последних этапах жизненного цикла разработки. Более того, благодаря повышенному интересу индустрии к показателям программных продуктов, произошло бурное развитие инструментов (например, статических анализаторов) для вычисления метрик. Стало возможным вычисление широкого круга показателей, что, в свою очередь, привело к проблемам с выбором минимально необходимого набора метрик.

В связи в рамках данной главы предпринята попытка систематизации подходов к решению поставленной проблемы, а именно :

— определению метрик оценки качества программного обеспечения на поздних этапах жизненного цикла разработки;

— формулированию проблемы избыточного количества метрик;

— анализу существующих методов отбора метрик программной инженерии.

1.1 Метрики программной инженерии

В рамках данной главы автором диссертации совместно с соавторами был проведен обзор литературы, посвященный анализу программного обеспечения на поздних этапах жизненного цикла: раздел 1.1.2 представляет поздние этапы, а также методы и метрики, применяемых на них.

1.1.1 Роль метрик в программной инженерии

Одним из важнейших факторов успеха программного продукта является его качество. Контроль над качеством программного обеспечения (ПО) требует внедрения программных метрик [44—46]. Согласно определению Фентона [2], программные метрики - это собирательный термин, который используется для описания широкого спектра видов деятельности, связанных с измерениями в области разработки ПО. Фентон также предложил классификацию, согласно которой, любая метрика программной инженерии нацелена на измерение или прогноз какого-либо атрибута (внутреннего или внешнего) какого-либо продукта, процесса или ресурса (таблица 1).

Таблица 1 — Классификация метрик программной инженерии

Сущность Атрибуты

Внутренние Внешние

Продукт

Спецификации размер, повторное понятность,

использование, функциональная ремонтопригодность,

корректность, ...

Дизайн размер, модульность, качество, сложность,

Код наследование, . . . фунциональность, надежность,

алгоритмическая используемость,

сложность, ...

Тестовые данные размер, уровень надежность,

покрытия, ... используемость,

Процесс

Построение спецификаций время, усилия, количество изменений, . . . качество, стоимость,

Проработка дизайна время, усилия, количество ошибок, стоимость, . . .

Тестирование время, усилия, количество ошибок в коде, . . . стоимость, стабильность, ...

Ресурсы

Продолжение на следующей странице

Сущность Атрибуты

Внутренние Внешние

Персонал время, оплата, ... продуктивность, опыт, . . .

Команда размер, уровень коммуникации, ... продуктивность, качество, ...

Эффективное использование метрик позволяет минимизировать затраты, отслеживать использование ресурсов и поддерживать ожидаемые результаты. Однако эффективность этих действий сильно зависит от фаз процесса разработки ПО. Различные модели жизненного цикла разработки определяют отличные друг от друга наборы фаз, но при этом сохраняя общую последовательность шагов:

1. Понимание проблемы;

2. Разработка плана решения;

3. Реализация запланированного решения;

4. Тестирование созданного решения;

5. Внедрение и обслуживание продукта.

Чем раньше в рамках жизненного цикла начнется измерение качества программного обеспечения, тем больше шансов сделать его разработку экономически эффективной, уложиться в график и бюджет.

Стоимость устранения дефектов программного обеспечения в рамках жизненного цикла разработки программного обеспечения зависит от времени -чем раньше будут определены ошибки, тем больше финансовых затрат можно избежать. Например, ошибки на этапе приемки обходятся в 4-15 раз дороже, чем на этапе проектирования, а ошибки, обнаруженные на этапе сопровождения, обходятся в 1000 раз дороже, чем на этапе управления требованиями [47].

Однако, несмотря на то, что сами 70% дефектов появляются уже на ранних этапах, обнаружить более 80% из них удается лишь на поздних этапах - интеграции (50%) и развертывании (30%). Именно во время интеграции удается выявить модули, склонные к сбоям в работе. Более того, при внесении дополнительных изменений в программное обеспечение необходимо проводить всевозможные тесты, чтобы убедиться, что интеграции в системе работают должным образом [48; 49]. Но постоянное повторное выполнение всех тестов увеличивает время выхода продукта на рынок, а

также количество затрачиваемых средств и ресурсов. При помощи методов прогнозирования неисправностей программного обеспечения можно повысить качество программного обеспечения уже на этапе разработки и снизить затраты на устранение сбоев [50].

1.1.2 Метрики поздних этапов жизненного цикла разработки

программного обеспечения

Для эффективной борьбы с дефектами программного обеспечения требуется изучение критериев качества продукта на поздних этапах жизненного цикла разработки. В целях систематизации информации о существующих поздних фазах жизненного цикла разработки программного обеспечения, соответствующих метриках для измерения и оценки качества программных продуктов автором данного диссертационного исследования совместно с соавторами был произведен литературный обзор [41]. Целью проводимого обзора является изучение следующих исследовательских вопросов:

RQ1. Какие фазы являются поздними фазами жизненного цикла процесса разработки программного обеспечения?

RQ2. Какие существуют методы оценки качества программного обеспечения на этих этапах?

RQ3. Какие существуют метрики качества программного обеспечения на поздних этапах, которые можно отслеживать с помощью инструментов автоматизации процессов сборки (DevOps)?

Поскольку охват всех исследований в научной области - процесс трудоемкий, поиск исследований по данной тематике осуществлялся авторами только в двух поисковых системах - Scopus и Web of Science. Исходя из поставленных исследовательских вопросов, были сформированы ключевые слова, которые использовались для создания поисковых запросов:

RQ1. Software development AND development process AND process life cycle;

RQ2. Software quality AND assessment methods;

RQ3. Software AND quality metrics AND late phases.

Авторами были проанализированы исследования, полученные в результате поисковых запросов, для их дальнейшего отбора в финальный список статей, отвечающих на поставленные вопросы. Отбор проводился путем сканирования названия, аннотации и ключевых слов. Отбор прошли работы, написанные на английском языке и опубликованные за последние 20 лет. всего была идентифицирована 181 публикация: 110 публикаций из научной базы Scopus, 71 - из Web of Science.

После этого авторами осуществлялась проверка отобранных работ на релевантность, которая требовала прочтения полного текста статьи. Проведенная оценка качества обнаруженных работ определила финальный набор из 26 публикаций, который представлен в таблице 2.

Таблица 2 — Выбранные публикации в области измерения и оценки качества ПО на поздних этапах жизненного цикла разработки

Список литературы диссертационного исследования кандидат наук Холматова Замира Шухратовна, 2025 год

Источник

Пропускная способность

Производительность системы

Среднее время до отказа (MTTF)

Среднее время до отказа (MTBF)

Общее количество работы, выполненной за определенный период времени

Точность, эффективность и скорость выполнения инструкций компьютерной программы Среднее количество времени, которое неремонтопригодный модуль работает до того, как он выйдет из строя

Прогнозируемое время,

прошедшее между отказами системы при нормальной работе системы

[66]

[66]

[66]

Следует отметить, что представленные списки метрик могут являться не полностью исчерпывающими, т.к. обзор литературы проводился лишь по двум базам данных. Тем не менее, проведенное исследование показало, что многие найденные метрики измеряют схожую, а порой дублирующуся информацию. Изучая метрики из приведенных выше таблиц можено заметить, что некоторые метрики:

— взаимосвязаны (например, CC, ev(G), iv(G) - все три метрики отражают сложность кода);

— производны от других (например, TNT включает в себя NFT и NPT).

Это наблюдение стало предпосылкой к изучению вопроса отбора

наименьшего, но в то же время исчерпывающего набора метрик, описывающего программное обеспечение с точки зрения различных атрибутов, таких как, например, размер и сложность.

1.2 Проблема избыточности метрик

Анализ таблиц 3, 4 и 5, демонстрирует, что для более раннего прогнозирования качества программного обеспечения на поздних этапах стоит сфокусироваться на продуктовых метриках - метриках, используемых для измерения различных атрибутов исходного кода, таких как, например, размер или сложность.

Действительно, метрики исходного кода, такие как количество строк кода (LOC), цикломатическая сложность (CC) [76] и метрики Холстеда [77], широко известны и изучаются уже с 60х годов прошлого столетия. Более того, метрики исходного кода используются в качестве входных данных для предсказания дефектов программного обеспечения или определения взаимосвязей в коде [55; 70; 78]. И как уже было упомянуто во введении, благодаря исследованиям и разработкам, созданным за последние 25 лет, стало возможным вычисление большого количества метрик. Систематизировав исследования, опубликованные только с 2010 по 2015 годы, ученые обнаружили почти 300 различных метрик, используемых в 226 статях [79].

Однако возможность рассмотрения большого количества программных метрик породила следующие проблемы:

1. Использование слишком большого количества метрик ставит перед пользователями проблему достоверности статистического анализа. Например, коллинеарность между метриками увеличивает дисперсию между ними и, таким образом, приводит к неправильному определению доминирующих предикторов в регрессионном анализе [15]. Математически можно записать задачу (модель) регрессии в виде Y = ХА + Ь, где Y - зависимая переменная, X - набор независимых переменных (в данной работе метрик), А, b - параметры модели. Провести оценку А можно следующим образом: А = (XтX)-1ХтY. Если X почти линейно зависим, то XтX почти сингулярно [15]. Поэтому оценка А будет неустойчивой, то есть небольшие изменения в X будут вызывать огромные колебания в А.

2. Большие объемы данных могут скрывать шум, который способен привести исследователей к неверным результатам при работе со статистическими моделями. Без механизма отбора признаков при наличии большого количества зашумленных переменных статистические модели суммируют небольшие шумовые вклады, что приводит их к большим ошибкам предсказания [16].

3. Неэффективное управление данными, включая хранение, предварительную обработку и увеличение вычислительной сложности операций над данными [17].

Для решения описанной проблемы требуется идентификация подходов, которые помогают выбрать минимальный, но в то же время исчерпывающий набор метрик программной инженерии. Сама проблема уже изучалась различными исследователями и в машинном обучении она называется "отбором признаков".

Пусть X Е Rnxp - матрица признаков, где п - количество наблюдений, а р - количество признаков. Задача отбора признаков состоит в том, чтобы найти такое подмножество индексов S С {1,...,р} размерности к < р, которое бы минимизировало целевую функцию С:

min £(X,XS), (1.1)

sc{i,..,P},\si=k

где Xs - это матрица, составленная из колонок X с индексами из S.

При такой постановке проблемы перед исследователями появляются следующие две задачи:

1. Определение целевой функции С:

— необходимо определить, что будет являться индикатором того, насколько хорошо выбранное подмножество отражает полный набор метрик.

2. Выбор алгоритма оптимизации:

— полный перебор всех возможных подмножеств признаков является комбинаторной задачей, требующей использования алгоритмов оптимизации.

1.3 Методы отбора метрик

В данной главе будут разобраны методы и алгоритмы, предложенные учеными, для решения проблемы отбора метрик. Найденные автором подходы для поиска оптимального набора метрик можно разделить на две группы:

— исследования, требующие размеченных данных;

— исследования, не требующие размеченных данных.

Размеченные данные означают, что данные были помечены описательной информацией или классифицированы экспертом (человеком или алгоритмом машинного обучения). Поэтому исследования первой группы требуют, чтобы данные были "размечены".

В большом количестве исследований, посвященных решению проблемы отбора метрик, ученые пытаются удалить некоторые метрики из исходного набора путем оценивания производительности алгоритмов машинного обучения с учителем до и после удаления, стремясь минимизировать разницу между замеренной производительностью [18—27].

, л1111?,,, *C{f{Х^№))' (1.2)

где f : Rp ^ R - модель машинного обучения.

Например, Гао и др. [18], используя тест Хи-квадрат, индекс Джини, тест Колмогорова-Смирнова и метод под названием Relief, сократили набор из 42 метрик до 6, тем самым улучшив производительность модели предсказания

дефектов. Ученые сравнивали метрику ЛИС по результатам работы модели с полным набором признаков и уменьшенным. Наиболее важными метриками оказались количество отдельных файлов, количество вносящих изменения разработчиков, процент развертывания модуля и цикломатическая сложность. Шиваджи и др.[26] также тщательно изучили различные методы отбора метрик и обнаружили, что даже 1% от первоначального числа метрик может обеспечить высокую производительность при выявлении ошибок в изменениях кода. В своей работе исследователи сравнивали Р-метрику по итогам работы модели на полном и уменьшенном наборах метрик.

Однако, подходы, предложенные в приведенных исследования, требуют размеченных данных, что подразумевает под собой зависимость этих подходов от контекста поставленной задачи, для которой определялся минимальный набор метрик.

Исследования второй группы включают методы, которые сокращают количество метрик без необходимости в размеченных данных. В таких исследованиях ученые сравнивали результаты работы алгоритмов машинного обучения без учителя, таких как кластеризация, или пытались извлечь тематику и создать графы знаний [28; 80]. Постановка задачи отбора метрик в данном случае остается прежней, представленной уравнением (1.2), но только / : ^ К уже представляет собой модель машинного обучения без учителя.

В качестве примера можно привести работы Туран и Чаталтепе [28], где ученые проверили изменения в кластерах до и после применения метода главных компонент. Аналогичным образом Ни и др.[80] ранжировали признаки в соответствии с их влиянием на кластеры, основанные на плотности.

Однако, ограничение методов из второй группы заключается в том, что различия в результатах работы алгоритмов обучения без учителя, применяемых к исходному и сокращенному наборам показателей, не означают, что метод отбора работает плохо. Например, алгоритм к-средних может дать сбой при кластеризации данных с выбросами или избыточными метриками, а затем корректно сгруппировать сокращенный набор данных. Таким образом, выводы по наиболее важным метрикам могут быть противоречивыми и ненадежными. Если речь идет о кластеризации на основе плотности, то также возникают трудности с выбором подходящих уровней плотности: уровень плотности, выбранный для кластеризации всего набора показателей, может не соответствовать кластеризации уменьшенного [30].

Тем не менее, существуют методы, которые пытаются нелинейно сохранить расстояния или сходства между точками [81]. Примерами таких методов являются многомерное шкалирование (МЭБ) [82], изометрическое отображение (1эотар) [83], отображение Сэммона [84]. Однако упомянутые методы в качестве результатов предоставляют не подмножество изначальных признаков, а их комбинации. Такие преобразования является нежелательным для решения проблемы, рассматриваемой в данной диссертации. Метрики программного обеспечения часто служат "страховочным тросом" для компаний [85]. Руководителям проектов в области информационных технологий важно оценивать текущий статус программного обеспечения, чтобы можно было предотвратить нежелательные сценарии и остаться конкурентоспособными.

Тем не менее, упомянутые выше подходы могут быть адаптированы к задаче выбора метрик: функция Крускала или ошибка Саммона - целевые функции этих алгоритмов могут быть использованы для измерения того, насколько хорошо выбранный набор метрик соответствует полному набору [86—89]. Исследователи могут оценить расстояния между точками в двух различных пространствах - образованным полным набором метрик и его подмножеством, а полученные расстояния подставить в целевую функцию. Значение, близкое к нулю для целевой функции, укажет на то, что выбранное подмножество признаков способно сохранить топологию исходного набора данных.

С точки зрения программного обеспечения можно рассмотреть каждый класс (метод, модуль, файл и т.д.) в его исходном коде как точку в к-мерном пространстве, где каждая ось отражает ту или иную метрику. Расстояния между точками отражают отношения между ними: если две точки находятся близко друг к другу, то они обладают аналогичными характеристиками (например, два класса имеют одинаковое количество методов), и наоборот. Ошибка Саммона или функция Крускала в данном случае количественно оценивает сохранение таких отношений. Например, если рассматривать классы с\ = (4,6,3) и с2 = (4,18,9), представленные тремя метриками, то удаление первой метрики не окажет существенного влияния на евклидово расстояние между с\ и с2, поскольку оно одинаково для обоих классов. Таким образом, метрики 2 и 3 являются более информативными для описания различий между классами.

Однако, чтобы определить подмножество метрик, дающее минимальное значение, необходимо провести расчет целевой функции для всех потенциальных подмножеств. Вычисление функции Крускала или ошибки Сэммона для всех возможных подмножеств является комбинаторной задачей. Самый популярный метод оптимизации, генетический алгоритм (СЛ), показал хорошую производительность при решении комбинаторных задач [90]. Кроме того, другой подход, называемый методом роя частиц (РБО), был признан эффективным методом для решения оптимизационных задач в дискретном пространстве [91; 92] - тех задач, аналогичную которым требуется решить для поиска оптимального набора метрик при помощи функции Крускала или ошибки Сэммона. Однако выводы исследователей по этим методам оптимизации неоднозначны: РБО оказался более эффективным с вычислительной точки зрения [91; 92], в то время как СЛ демонстрирует значительно лучшие результаты сходимости к оптимальному решению [90].

И РБО, и СЛ уже использовались в алгоритмах выбора признаков для решения задач программной инженерии, таких как предсказание дефектов [8—11], оценка усилий разработчиков [93], определение путей тестирования [94] и обнаружение частей кода для рефакторинга [95]. Сравнивая два выбранных метода оптимизации, исследователи выяснили, что РБО проще в реализации и быстрее по времени вычислений [96], а СЛ демонстрирует меньшую склонность к преждевременной сходимости [97; 98]. РБО идентифицирует решения, расположенные гораздо ближе друг к другу, что часто приводит к локальному экстремуму [97; 98]. В генетических алгоритмах решения обычно группируются вблизи нескольких "хороших" точек.

1.4 Выводы

В данной главе были изучены вопросы мониторинга качества программного обеспечения на поздних этапах жизненного цикла процесса разработки. В рамках проведенного исследования были определены:

1. этапы, которые рассматриваются учеными как поздние фазы жизненного цикла, - разработка, тестирование и развертывание;

2. методы, используемые для оценки качества программных продуктов на поздних этапах, - статический анализ кода;

3. метрики, используемые для оценки качества программных продуктов на поздних этапах, - представлены в таблицах 3, 4 и 5.

Проведенное исследование подсветило разнообразие продуктовых метрик, применяемых на последних этапах жизненного цикла разработки: благодаря прорывным исследованиям и разработкам в области анализа программного обеспечения, современные инструменты позволяют вычислить почти 300 метрик (согласно обзору литературы, опубликованной с 2010 по 2015 года в данной области).

Тем не менее, возможность вычисления такого большого количества метрик приводит к проблемам, связанным с анализом и интерпретацией большого количества данных. В связи с этим возникла необходимость в исследовании методов отбора метрик. Обзор существующих подхов к отбору метрик показал, что методы отбора метрик можно разделить на две условные группы:

— требующие размеченных данных;

— не требующие размеченных данных.

Методы, требующие размеченных данных, зависят от контекста поставленной задачи, в рамках который выполняется отбор. Методы, не использующие размеченных данных, основываются на сравнении результатов работы моделей машинного обучения без учителя. Однако требуется предельная аккуратность в интерпретации, так как различия в результатах работы алгоритмов обучения без учителя, применяемых к исходному и сокращенному наборам показателей, могут отражать не качества метода отбора, а специфику и тонкости работы используемых алгоритмов.

Тем не менее, анализ методов, способных сохранить сходства между точками при переходе из пространства большей размерности в пространство меньшей размерности, показал, что целевые функции таких методов могут стать основой нового подхода для отбора метрик. Данное наблюдение и стало предпосылкой разработки методики, описанной в следующей главе.

Глава 2. Методика отбора метрик программной инженерии

Анализ, проведенный в предыдущей главе, подтвердил важность и эффективность метрик для анализа качества программного обеспечения особенно на поздних этапах жизненного цикла разработки, когда становится возможным выявление ошибок или частей кода, требующих рефакторинга. Однако доступность вычисления огромного количества метрик привела к трудностями со сбором необходимой для анализа информации, в связи с чем возникла потребность в методах и моделях для отбора метрик. Данная глава посвящена представленой в работе [42] методике, целью которой является отбор метрик в условиях отсутствия размеченных данных или применения моделей машинного обучения.

В данной главе автором совместно с соавторами [42] были предприняты попытки:

1. формализации модели программного обеспечения, основанной на метриках уровня классов и методов;

2. разработки методики, которая может определить минимальное подмножество метрик, объясняющих "структуру" репозитория программного обеспечения. Репозиторий описывается набором метрик на уровне классов или методов, а термин "структура" в данном случае выражает геометрические соотношения между классами или методами репозитория. Каждый класс или метод описывается точкой в пространстве, где каждая ось отражает разные метрики. Следовательно, близкое расположение точек указывает на то, что классы или методы имеют похожие свойства (например, одинаковое количество переменных или строк кода), и наоборот. С точки зрения разработки программного обеспечения, поддержание согласованной "структуры" в рамках ограниченного набора метрик может повысить эффективность анализа качественных характеристик программного обеспечения, таких как подверженность сбоям, восстанавливаемость и т.д. [99; 100]. Эти характеристики как раз можно будет определить, сгруппировав классы или методы на основе расстояний между ними. Поэтому цель данного пункта - уменьшить количество метрик при сохранении геометрических соотношений;

3. проверки работоспобности предлагаемой методики путем ее применения к большому набору метрик, собранному с репозиториев с открытым исходным кодом на языке программирования Java;

4. определения минимального набора метрик на уровне классов и методов для репозиториев, собранных во время работы над пунктом 3.

2.1 Представление репозитория для анализа метрик

В данной диссертационной работе программное обеспечение рассматривается с точки зрения своего исходного кода, хранилище которого называется репозиторием. Поэтому вычисление и анализ метрик проводились для репозиториев, соответствующих тому или иному программному продукту.

В рамках данной главы предложена формализация представления репозитория, основанного на метриках уровня классов и методов. Такое представление репозиториев позволило в дальнейшем определить оптимальное подмножество метрик.

В данной работе каждый репозиторий был представлен в виде матрицы:

где хп = (хп\,хп2,...,хпк), определяет класс или метод п репозитория X. В рамках диссертации считается, что х^ € К - значение ]-й метрики для ¿-го класса.

Каждый класс хп рассматривается, как точка в п-мерном пространстве с метрикой:

где d - это евклидова метрика, а d¡n - евклидово расстояние между г-м и n-м классами.

Такое представление репозиториев позволяет анализировать их атрибуты, выраженные метриками на уровне классов или методов. В связи с тем, что каждый класс или метод описывается вектором чисел, то близость самих классов или методов с точки зрения евклидова расстояния в пространстве

X = (Ж1,Ж2, ... ,хп)т,

(2.1)

отражает схожесть их свойств (например, сложность, связность). В таком случае, расстояние между сущностями кода служит индикатором их сходства. Тогда к задаче отбора метрик, определенной математическим выражением (1.1), можно подойти через сохранение сходства, т.е. расстояния, между классами или методами.

Таким образом, предлагаемая модель не только формализует свойства репозитория через метрическое пространство, но и формирует основу решения задачи отбора метрик, к которой можно подойти с точки зрения сохранения сходства между сущностями кода.

2.2 Подход к отбору метрик программной инженерии

Целью данной диссертации является разработка методики для отбора метрик, применяемых на поздних этапах жизненного цикла разработки. Анализ литературы выявил необходимость в методах, не требующих размеченных данных или применения моделей машинного обучения.

Проблема отбора метрик описана выражением (1.1) раздела 1.2. Как уже было указано, для её решения требуется определение:

— целевой функции;

— алгоритма оптимизации.

Обзор литературы показал, что в качестве целевой функции можно рассматривать целевые функции существующих методов, таких как МВБ, ¡эошар или отображение Сэммона. МВБ и ¡эошар имеют одну и ту же целевую функцию, названную функцией Крускала:

где - расстояние между г-й и у-й точками (классами или методами) в пространстве высокой размерности (представленном всем множеством метрик), ^ - расстояние между теми же точками в пространстве меньшей размерности (представленном некоторым подмножеством метрик). Чем меньше значение функции, тем сильнее подмножество метрик отражает исходное множество.

(2.2)

Разница между МЭБ и ¡эошар заключается в том, что МЭБ использует евклидово расстояние, а ¡эошар - геодезическое.

Целевая функция отображения Сэммона представляет собой взвешенную версию функции Крускала [83]. Поэтому в данном исследовании используется только эта функция для минимизации. Детали и формула для вычисления ошибки Сэммона описаны в соответствующей главе ниже.

И поскольку вычисление ошибки Сэммона для всех возможных подмножеств является комбинаторной задачей, для нахождения минимума этой функции необходимо обратиться к методам оптимизации. Анализ литературы показал, что подходящими для решения этой задачи являются методы РБО и СЛ [101; 102]. Поэтому предлагаемый методологический конвейер состоит из следующих частей:

1. сбор данных (выбор репозиториев и вычисление метрик);

2. поиск подмножеств метрик с наименьшей ошибкой Сэммона при помощи РБО;

3. агрегирование результатов, полученных при помощи РБО и ошибки Саммона;

4. поиск подмножеств метрик с наименьшей ошибкой Сэммона при помощи СЛ;

5. агрегирование результатов, полученных при помощи СЛ и ошибки Сэммона.

Представленный подход также изображен на рисунке 2.1.

Рисунок 2.1 — Схема предлагаемого подхода

Теоретические основы РБО и СЛ также более подробно представлены в следующих подраделах текущей главы.

2.2.1 Ошибка Сэммона

Линейные проекции, как, например, метод главных компонент [28], пытается сохранить ту же величину исходной дисперсии без учета структуры самих данных. Джон Сэммон [84] предложил алгоритм, который направлен на сохранение структуры, представленной п точками в ^-мерном пространстве, путем нахождения представления такого же количества точек в /-мерном пространстве, где I < к.

Например, X - это набор входных векторов из пространства размерности к и У = (у\,у2,... ,Уп)Т - это набор векторов, который необходимо найти в /-мерном пространстве, где уп = (уп1,уп2,... ,Уп1 )Т. Чтобы найти У, Сэммон предложил минимизировать следующее выражение, называемое ошибкой Сэммона:

Е = - ^)2, (2.3)

г<3

где - это расстояние между Хг и х^, ^ - между у { и у^.

Целью предлагаемого в диссертационном исследовании метода является приближение расстояний между точками (классами или методами) при помощи выбора меньшего набор метрик. Для этого выбирается I, (I < к), столбцов (метрик) из матрицы X и вычисляется ошибка Сэммона между X и матрицей с уменьшенным числом метрик. Для вычисления ошибки Сэммона принято использовать евклидово расстояние [84].

Как уже было упомянуто, каждый класс или метод репозитория описывается набором к метрик, что позволяет представить его как точку в ^-мерном пространстве. Расстояния между точками отражают взаимосвязи между ними: если две точки расположены близко друг к другу, они обладают почти одинаковыми свойствами (например, два класса имеют одинаковое количество методов), и наоборот. Ошибка Сэммона как раз оценивает,

насколько хорошо выбранные метрики сохраняют расстояния между классами или методами.

2.2.2 Метоя роя частиц

Метод роя частиц (РБО) является одним из алгоритмов оптимизации, используемых в предложенном подходе [101]. В этом алгоритме частица представляет собой набор метрик. Каждая метрика кодируется числом. Например, в данном исследовании используется кодировка числом с плавающей точкой для управления количеством метрик в подмножестве: если частица представлена вектором чисел [0.91,0.12,0.42,0.61,0.33], то для вычисления значения целевой функции для подмножества из двух метрик на этой частице необходимо

1. взять индексы двух наибольших по величине значений вектора;

2. посчитать значение целевой функции на метриках, имеющих найденные индексы.

Метод РБО, изпользующийся в данной работе для выбора метрик, базируется на оригинальной статье - работе авторов метода, Кеннеди и др. [101]. Реализованный метод представлен в алгоритме 1, а используемая в нем нотация - в таблице 6.

Таблица 6 — Нотация, используемая в методе роя частиц и генетическом алгоритме

Обозначение Описание

X Матрица репозитория

/ (*) Целевая функция (ошибка Сэммона (2.3))

N Размер популяции (количество частиц)

п Количество метрик в оптимальном подмножестве

Чг = Ы, .. , Ч_гг\ Вектор члена популяции, где ^ Е (0,1) - число с плавающей точкой, кодирующее метрику Хк, а к Е [1,п] - индекс метрики

дЪезЬ Член с наименьшим значением целевой функции среди популяции

Рс Вероятность скрещивания

Продолжение на следующей странице

Обозначение Описание

\рИ 1 ... 1 вт] Щ = \ьц, . . . Т ± тах 'рЬезЬг дЪезЬ Вектор позиции частицы, где е^ Е (0,1) - число с плавающей точкой, кодирующее метрику х^, а к Е \1, п] - индекс метрики Вектор скорости частицы, где Е (0,1), а к Е \1, п] - индекс метрики Максимальное количество итераций Лучшая позиция частицы г (с наименьшим значением целевой функции) Лучшая глобальная позиция (позиция частицы с наименьшим значением целевой функции)

2.2.3 Генетический алгоритм

Второй подход, который можно использовать для минимизации ошибки Сэммона, - это генетический алгоритм. Генетический алгоритм создает начальную популяцию, а затем пытается улучшить ее путем эволюции [102]. Эволюция в большинстве случаев осуществляется с помощью отбора родителей, скрещивания и мутации. Каждый член популяции представляет собой набор закодированных метрик. Как и в случае с РБО, в данном исследовании метрики в каждом члене популяции закодированы числом с плавающей точкой для контроля количества метрик, включенных в конечное подмножество [103]. Кодирование с плавающей точкой позволяет сортировать метрики и затем выбирать необходимое их количество для вычисления целевой функции. Генетический алгоритм для поиска оптимального подмножества метрик, реализованный в данной работе описан алгоритмом 2. Используемая в алгоритме нотация представлена в таблице 6.

Алгоритм 1: Метод роя частиц Входные данные: /(х), X, п, Ттах = 20, N = 20 Выходные данные: дЬевЬ

Инициализировать е = [е\,..., е^], V = ,..., ), ы = 0.6; цикл г ^ 1 от N выполнять

Посчитать значение /(х) на X[[аг§тахп(е^)]]; Выбрать рЬе,Б1^; конец

Установить дЪев1 пустым;

Установить количество итераций £ = 0;

до тех пор, пока £ не достигнет Ттах выполнять

цикл г ^ 1 от N выполнять

Обновить векторы скоростей VI и позиций е^.

уг = + с^^рЬеви -

С2Г2(рЬези[дЬе8г] - ег), (2.4)

ег = (ег + уг),

где Г\ и г2 - два случайных и независимых вектора из (0,1); С\ = 2 и с2 = 2 - когнитивный и социальный коэффициенты обучения;

Посчитать значение /(х) на X[[аг§тахп(е^)]]; Обновить pbesti и дЬев^ конец

Увеличить £ на единицу; конец

Алгоритм 2: Генетический алгоритм

Входные данные: f (х), X, Ттах = 20, N = 20, к = 3 Выходные данные: qbest

Инициализировать q = [q\, . . . , q^], qbest = 0, t = 0; до тех пор, пока t не достигнет Ттах выполнять цикл г ^ 1 от N выполнять

Посчитать значение f (х) на X[[argmaxn(e^)]]; конец

Обновить qbest;

Инициализировать родителей par = [ ]; цикл г ^ 1 от N выполнять

Случайно выбрать члена популяции s; цикл j ^ 1 от N с шагом к — 1 выполнять если f (argmaxn(qj)) < f (argmaxn(s)) тогда S = Яг;

конец

Добавить s в par ; конец

Инициализировать детей с = [ ]; цикл т ^ 1 от N с шагом 2 выполнять

Провести скрещивание рагт и рагт+\ с вероятностью рс Получить двух детей child\ и child2; цикл к ^ 1 от 2 выполнять

цикл I ^ 1 от len(childk) выполнять

childk[/] + Y, если р > 0.5

= 0.6;

childk [I] =

childk [l], if P ^ 0.5

(2.5)

где р, у Е (0,1) - случайная величина; конец

Добавить сЫМк в с; конец конец

Заменить q на с; Увеличить t на единицу; конец

2.2.4 Агрегация результатов

Для обобщения результатов экспериментов, была применена методика, аналогичная подсчету голосов в мета-анализе [36; 104]. Подсчет голосов подразумевает сравнение количества исследований со значимыми положительными результатами и значимыми отрицательными результатами; проще говоря, если большинство исследований, в которых рассматривался один и тот же эффект, дали положительные значимые результаты, то этот эффект считается положительным, и наоборот. В данном исследовании похожим образом определялось оптимальное подмножество метрик. каждое оптимальное подмножество разного размера определялось как набор метрик, часто встречающихся в отдельных подмножествах каждого репозитория.

2.3 Описание экспериментов

Опираясь на рисунок 2.1, прежде всего для проведения экспериментов был осуществлен сбор данных - выбор репозиториев и подсчет метрик.

Поиск оптимальных подмножеств при помощи РБО и СЛ реализовывался отдельно для метрик на уровне класса и отдельно на уровне метода. Более того, все шаги поиска исполнялись с разными размерами подмножеств метрик (от 2 до кол-ва классов или методов, уменьшенного на единицу), таким образом, предоставляя возможность анализа способности подмножеств, содержащих маленькое количество метрик, сохранять геометрическую структуру.

2.3.1 Данные

В настоящем исследовании в качестве источника данных рассматривается Github - крупнейший сервис для разработки программного обеспечения. Основным языком программирования для анализа был выбран Java - один из самых популярных языков на GitHub [105]. Java является основным

языком для крупных и широко используемых продуктов, таких как IntelliJ IDEA [106] или Apache Hadoop [107]. Для включения в эксперименты только популярных и продолжающих развитие репозиториев, в данной работе были установлены минимальные значения количества звезд и коммитов, которые каждый репозиторий должен иметь. Поэтому репозитории для включения в анализ должны были удовлетворять следующим критериям:

— код в репозитории написан на Java;

— репозиторий содержит не менее 10 коммитов;

— репозиторий имеет не менее 100 звезд;

— проект включает только библиотеки с открытым исходным кодом.

При помощи этих критериев были собраны 1000 репозиториев, что

составляет 4,5% открытых и сархивированных репозиториев с не менее чем 100 звездами. Собранный набор охватывает наиболее популярные темы на GitHub, такие как "java", "spring-boot", "redis", "docker", "machine-learning".

Для подсчета метрик кода был использован инструмент под названием SourceMeter [108]. Этот инструмент поддерживает вычисление более 60 метрик, связанных с размером, объектами и сложностью кода, на уровне классов, методов, файлов и других сущностей проекта. Даная работа сфокусирована на внутренних продуктовых метриках (согласно таксономии Фентона и др. [109]), описывающих структуру кода на уровне классов и методов. Таблицы 7 и 8 показывают метрики, рассчитанные для 1000 проектов.

Таблица 7 — Метрики классов и их аббревиатуры

Название метрики Аббревиатура

Отсутствие связности методов класса LCOM

Уровень вложенности NL

Уровень вложенности ЕЬе-К NLE

Суммарная сложность методов класса WMC

Связь класса с другими CBO

Обратная связь класса с другими CBOI

Количество входящих вызовов NII

Количество исходящих вызовов NOI

Набор ответов класса RFC

Плотность комментариев CD

Количество строк с комментариями CLOC

Глубина дерева наследования DIT

Количество предков NOA

Количество детей NOC

Продолжение на следующей странице

Название метрики Аббревиатура

Количество потомков NOD

Количество родителей NOP

Количество строк кода LOC

Количество логических строк кода LLOC

Количество атрибутов NA

Количество методов NM

Количество публичных атрибутов NPA

Количество публичных методов NPM

Количество объявлений NOS

Общее количество строк кода TLOC

Общее количество логических строк кода TLLOC

Общее количество атрибутов TNA

Общее количество методов TNM

Общее количество публичных атрибутов TNPA

Общее количество публичных методов TNPM

Общее количество объявлений TNOS

Таблица 8 — Метрики методов и их аббревиатуры

Название метрики Аббревиатура

Количество строк повторяющегося кода LDC

Количество логических строк повторяющегося LLDC

кода

Расчетная продолжительность программы по HCPL

Холстеду

Сложность по Холстеду HDIF

Усилия по Холстеду HEFF

Количество доставленных ошибок по Холстеду HNDB

Продолжительность программы по Холстеду HPL

Словарь программы по Холстеду HPV

Время, необходимое для программы, по HTRP

Холстеду

Объем по Холстеду HVOL

Индекс поддерживаемости MI

Цикломатическая сложность по МакКэйбу McCC

Уровень вложенности NL

Уровень вложенности ЕЬе-К NLE

Количество входящих вызовов NII

Количество исходящих вызовов NOI

Плотность комментариев CD

Количество строк с комментариями CLOC

Количество строк с документацией DLOC

Общая плотность комментариев TCD

Общее количество строк с комментариями TCLOC

Продолжение на следующей странице

Название метрики Аббревиатура

Количество логических строк кода ььос

Количество строк кода ьос

Количество объявлений N08

Количество параметров NUMPAR

Общее количество логических строк кода тььос

Общее количество строк кода тьос

Общее количество объявлений TN0S

Для экспериментов были использованы 30 продуктовых метрик на уровне класса и 28 - на уровне метода. Данные для экспериментов были разделены на обучающий и валидационный наборы в пропорции 80/20. Описательная статистика обоих наборов приведена в таблице 9, а распределение выборок по количеству классов и методов - в таблице 10.

Таблица 9 — Описание обучающего и валидационного набора данных

Выборка Кол-во проектов Кол-во классов Кол-во методов

Обучающая 800 155240 720107

Валидационная 200 43045 205948

Таблица 10 — Распределение выборок по количеству классов и методов

Выборка < 500 501-1000 > 1000

Обучающая (классы) 716 72 12

Обучающая (методы) 425 144 230

Валидационная (классы) 179 18 3

Валидационная (методы) 86 41 73

2.3.2 Детали реализации

Перед проведением экспериментов оба набора данных (обучающий и валидационный) были предварительно нормализованы. Обучающий набор данных был использован для проведения экспериментов по поиску оптимальных подмножеств метрик на уровне классов и методов. Для проверки

способности найденных подмножеств метрик демонстрировать столь же маленькие значения ошибки Сэммона на других репозиториях использовался валидационный набор данных.

Сначала на обучающем наборе данных был применен РБО для минимизации ошибки Сэммона (2.3) отдельно для метрик на уровне классов и отдельно на уровне методов. Эксперименты были проведены в каждом репозитории, варьируя количество метрик в подмножествах на уровне классов - от 2 до 29, методов - от 2 до 27. Каждый эксперимент повторялся 3 раза. Итоговое оптимальное помножество метрик в каждом репозитории для каждого количества метрик определялось путем выбора наименьшего зафиксированного в трех попытках значения.

Далее на обучающем наборе данных был применен СЛ для поиска минимального значения ошибки Сэммона (2.3). Как и в случае с РБО, эксперименты проводились по три раза для каждого репозитория с разным количеством метрик на уровне классов и методов. Результат определялся путем выбора наименьшего значения ошибки Сэммона в трех попытках.

2.4 Результаты и анализ

В данном разделе представлены результаты работы РБО и СЛ с ошибкой Сэммона на обучающем и валидационном наборе данных.

2.4.1 Результаты на обучающем наборе данных

Минимальные, средние и максимальные значения ошибок Сэммона для каждого количества метрик в обучающем наборе репозиториев уровней классов и методов представлены на рисунках 2.2 и 2.3. Таблицы 11 и 12 показывают количество вхождений каждой метрики в подмножества от 2 до 15 метрик на уровне класса и метода, соответственно.

Рисунок 2.2

а н о

0,5 0,4

6 0,3

а к б и

в

о 0,1

0,2

0

29

5 10 15 20 25

Количество метрик

Ошибки Сэммона, полученные при помощи РБО для метрик на уровне классов

а н о

э С

а к б и

ш

О

0,4

0,3

0,2

0,1

0

1 1 — Средн. --- Мин. ........Макс.

\ \ \ \ - \ \ \ \ \ \ " " ~---------

2527

Рисунок 2.3

5 10 15 20

Количество метрик

Ошибки Сэммона, полученные при помощи РБО для метрик на

уровне метода

Аналогичные таблицы, демонстрирующие количество вхождений каждой метрики в подмножества от 2 до 15 метрик на уровне класса и метода, представлены и для СЛ (таблицы 13 и 14). Также результаты применения СЛ на обучающем наборе данных представлены на рисунках 2.4 и 2.5.

Таблица 11 — Результаты РБО с ошибкой Сэммона для метрик на уровне классов

2 3 4 5 6 7 8 9 10 11 12 13 14 15

0,55 0,43 0,39 0,31 0,28 0,22 0,19 0,18 0,15 0,13 0,11 0,09 0,08 0,06

ОБ 266 341 407 446 486 521 550 569 589 631 623 654 676 693

КОР 195 258 308 332 374 405 418 462 482 477 514 539 551 560

КЬЕ 122 187 241 300 341 385 418 469 471 503 542 559 606 610

Б1Т 118 166 219 242 265 327 336 384 413 440 465 484 506 543

ОБО 88 146 190 238 285 318 367 397 451 469 482 528 559 578

КЬ 80 156 192 227 265 301 325 362 406 438 465 490 524 555

КА 74 98 140 197 224 283 312 353 414 426 453 490 511 533

ТКА 63 108 158 204 238 249 325 337 353 403 433 457 488 523

ША 82 109 136 177 227 240 280 308 327 364 399 421 457 472

ОБО1 42 67 98 128 156 198 235 275 295 322 383 407 464 472

КМ 29 60 85 109 135 163 224 239 270 316 340 352 402 427

КРМ 33 70 92 113 160 178 208 241 272 282 337 378 388 415

ЬООМ5 29 55 89 113 147 175 210 242 273 310 335 359 402 428

ЯРО 46 66 100 131 149 184 182 230 260 292 319 359 396 413

ТКРМ 44 62 79 113 149 174 211 227 252 290 312 342 350 421

ТКМ 43 59 78 115 137 176 195 219 251 305 314 327 360 379

Ш1 27 51 71 95 130 153 176 218 247 262 302 315 346 399

ТЬЬОО 25 39 55 77 94 129 141 171 192 256 255 302 324 361

ТЬОО 20 40 47 84 86 120 156 157 207 226 266 289 303 332

ЬОО 13 27 44 57 94 103 127 161 175 173 221 264 287 324

ТШБ 26 35 59 81 93 120 146 170 216 221 253 283 293 337

WMО 35 36 72 66 89 109 152 174 184 224 249 273 308 337

ОЬОО 27 38 37 61 86 100 108 127 156 171 199 226 234 276

ТКРА 19 18 24 40 52 79 91 106 132 139 175 187 218 225

КОБ 18 38 49 68 76 86 131 150 170 189 213 258 269 314

Ш 17 24 47 74 87 110 106 129 150 185 203 240 264 309

ЬЬОО 12 28 49 65 92 99 126 156 178 210 239 258 311 307

КРА 5 13 23 25 40 62 72 76 89 120 129 152 154 183

КОБ 2 2 5 8 20 27 34 46 70 77 95 123 135 150

ШО 0 3 6 14 23 26 38 45 55 79 85 84 114 124

Таблица 12 — Результаты Р8О с ошибкой Сэммона для метрик на уровне метода 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0,50 0,44 0,33 0,26 0,23 0,18 0,15 0,12 0,10 0,09 0,07 0,06 0,05 0,04

ШМРАК 319 433 519 564 615 652 673 681 709 732 738 746 763 768

ОБ 259 302 362 442 469 507 550 573 583 623 645 645 672 673

ТОБ 115 227 324 367 450 489 522 545 569 602 596 642 650 668

КЬЕ 86 176 251 328 389 439 453 530 551 598 609 633 653 665

N01 76 134 189 255 305 348 380 422 468 490 513 539 556 588

кь 73 121 174 210 273 322 365 394 439 472 505 533 570 608

ГОШ 103 142 179 232 262 331 372 419 447 483 504 559 565 615

М1 115 138 167 217 234 286 320 349 395 422 469 487 526 585

ИРУ 67 101 138 187 217 270 313 390 413 437 479 531 554 595

N11 49 81 121 167 210 262 297 327 366 409 446 484 525 567

ИОРЬ 26 45 73 112 150 173 223 241 289 332 375 418 449 486

ТКО8 31 52 71 100 106 141 190 225 264 301 331 372 413 447

ИРЬ 29 34 48 67 103 121 160 181 237 277 316 381 413 447

N08 40 43 70 91 109 146 174 201 244 285 329 366 401 433

ТььОО 23 49 70 81 118 141 179 201 247 269 320 332 397 406

ТЬОО 49 54 74 84 105 129 147 205 234 271 303 344 370 403

ЬОО 27 42 61 65 80 116 150 179 217 243 274 316 354 384

ИКБВ 10 22 29 39 49 66 98 114 142 162 203 233 263 291

ЬЬОО 20 23 36 53 75 74 118 150 173 194 242 286 334 369

ТОЬОО 20 48 54 70 91 117 127 159 194 215 238 270 308 335

БЬОО 40 77 102 110 153 166 207 216 236 256 279 305 337 360

ОЬОО 10 22 31 62 80 90 121 152 173 204 238 252 293 308

ИУОЬ 7 19 29 36 48 61 86 105 129 163 196 217 255 317

МсОО 3 7 17 25 58 62 77 100 108 137 164 193 213 246

ИТЯР 1 4 4 8 12 21 20 29 33 53 60 71 84 100

ЬБО 1 3 1 10 12 23 24 38 48 66 80 88 100 117

ИЕРР 1 0 2 10 14 23 19 31 43 46 82 79 86 99

ЬЬБО 0 1 4 8 13 24 35 43 49 58 66 78 96 120

Таблица 13 — Результаты СЛ с ошибкой Саммона для метрик на уровне классов

2 3 4 5 6 7 8 9 10 11 12 13 14 15

0,55 0,43 0,39 0,31 0,28 0,22 0,19 0,18 0,15 0,13 0,11 0,09 0,08 0,06

ОБ 303 377 403 439 486 519 539 586 599 609 629 650 677 697

N0? 236 257 303 349 367 418 417 436 453 483 496 527 541 537

КЬЕ 129 189 277 314 355 409 428 456 482 506 531 565 596 616

Б1Т 116 163 208 238 287 303 355 354 404 427 463 472 497 505

ОБО 101 160 193 246 289 322 359 380 414 434 467 496 509 553

NL 89 162 174 234 241 289 338 352 401 410 459 487 489 528

NЛ 59 106 151 176 224 245 282 296 350 375 413 440 469 502

TNA 62 92 138 184 197 232 271 307 306 351 399 434 450 485

N0Л 71 127 150 167 206 220 253 303 316 360 382 417 442 471

0Б01 43 62 105 143 175 212 245 289 302 329 355 397 425 454

N01 25 53 78 119 143 172 206 223 249 310 310 352 369 411

L00M5 39 65 91 125 173 179 211 240 261 308 368 372 426 422

N?M 29 47 87 122 133 183 222 245 271 297 347 359 384 406

ЯРО 61 80 104 104 149 176 198 237 283 291 310 309 400 421

TN?M 27 53 82 110 142 163 187 220 217 254 280 324 339 417

NM 26 50 77 122 149 161 192 240 255 274 320 342 351 417

TNM 20 47 60 86 98 157 175 204 251 272 305 332 364 369

TLL0C 16 24 59 73 98 126 142 182 232 233 259 293 325 368

L00 12 24 45 68 87 116 140 188 193 236 260 291 339 349

TL00 10 30 54 81 91 123 148 175 216 220 238 289 303 324

LL00 9 21 48 67 98 127 132 179 186 241 266 286 326 334

WMО 32 50 65 73 95 134 173 170 195 248 263 264 292 333

0L00 27 31 50 68 91 114 121 155 163 199 230 246 277 311

TN0S 20 36 47 77 98 99 144 171 194 209 250 276 317 322

N11 17 32 47 67 89 109 134 158 201 231 235 274 285 318

N0S 12 36 49 59 95 118 141 147 199 227 241 264 297 330

TN?Л 4 15 20 33 51 47 78 85 132 138 159 194 206 243

NPA 4 8 20 32 50 62 70 101 109 140 148 172 208 208

N00 1 1 6 17 21 38 48 56 91 87 103 132 157 165

N00 0 2 9 7 22 27 51 65 75 101 114 144 140 184

Таблица 14 — Результаты СЛ с ошибкой Саммона для метрик на уровне методов 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0,50 0,44 0,33 0,26 0,23 0,18 0,15 0,13 0,10 0,09 0,07 0,06 0,05 0,04

ОБ 315 315 323 383 428 463 485 524 558 560 572 619 638 658

ШМРЛК 308 423 472 537 566 623 646 656 682 706 725 734 742 764