Оригинал статьи: Shahmohammadi G., Jalili S., Hasheminejad S. M. H. Identification of System Software Components Using Clustering Approach, Journal of Object Technology. – 2010. – Т. 9. – №. 6. – С. 77-98.
В статье предлагается использовать кластеризацию вариантов использования с целью определения компонент системы и их зон ответственности. Для определения важности признаков вариантов используется анализ чувствительности. Также для определения числа кластеров используется метрика внутренной сплоченности между кластерами и между их объединениями. Достоинства предложенного метода следующие:
Рассматриваем граф:
Пусть <latex>N</latex> – число вариантов использования.
1. Матрица схожести <latex>S</latex> - матрица размера NхN, где
Матрицу схожести удобно использовать в случае, если признаки бинарные. Элементы матрицы обычно вычисляются следующим образом. Пусть <latex>n_{00}\ (n_{11})</latex> — число признаков, которые отсуствуют (присутствуют) у обоих объектов. <latex>n_{01},\ (n_{10})</latex> — число признаков, которые есть только у первого (второго) объекта. Ниже приведены формулы, использующиеся для подсчета схожести объектов: <latex> s_{ij} = \frac{n_{11} + n_{00}}{n_{11} + n_{00} + w(n_{01} + n_{10})},</latex>
<latex>s_{ij} = \frac{n_{11}}{n_{11} + w(n_{01} + n_{10})}</latex>, где параметр w берут обычно из множества <latex>\{1/2, 1, 2\}.</latex>
2. Матрица расстояний <latex>D</latex> между объектами - матрица размера NxN, где:
Матрицу расстояний удобно использовать, если признаки - числа. Элементы матрицы считаются по косинусному расстоянию: <latex>d_{ij} = 1 - \frac{\vec{v_{i}} \cdot \vec{v_{j}}}{\sqrt{||\vec{v_i}||_2 * ||\vec{v_j}||_2}}.</latex>
Более подробное описание см. [1,2].
1. CH - индекс. <latex> CH(K) = \frac{Tr(S_b)}{K-1} / \frac{Tr(S_w)}{N - K} \rightarrow max_{K},</latex> где <latex>Tr(S_b)</latex> — среднее расстояние внутри между точками внутри кластеров, <latex>Tr(S_w)</latex> — между точками разных кластеров.
2. Ray и Turi индекс. Пусть <latex>\{z_1, \ldots, z_K\}</latex> — центры кластеров. <latex> Validity(K) = Intra / Inter \rightarrow max_{K} </latex> <latex> Intra = \frac{1}{N} \sum_{i=1}^{k}\sum_{x\in C_i} ||x - z_i||^2</latex> — среднее расстояние до центра кластера. <latex> Inter = min(||z_i - z_j||^2), i = 1, \ldots , K - 1; j = i + 1, \ldots, K.</latex>— минимальное расстояние между центрами кластеров.
признаки выделяются с использованием диаграммы классов, коллобораций и диаграммы вариантов использования. Признаки:
1. Актеры. Актер, который вызывает данный вариант использования. 1 в колонке того актора, который вызывает данный сценарий, во всех остальных 0.
2. Классы-сущности. По одной колонке для каждого класса-сущности. 1 если данный класс присутствует и варианте использования, иначе 0.
3. Управляющие классы - классы, ответственные за взаимодействие между классами-сущностями и классами интерфейсов. Аналогично по колонке для каждого класса.
4. Отношения между вариантами использования.
5. Вес управляющего класса. <latex>WCC_i = \frac{Nec_i + Nic_i}{\sum_{j=1}^m Nec_j + \sum_{j=1}^{l} Nic_j},</latex> где <latex>Nec_i</latex> - число сущностей, находящихся под контролем класса <latex>i</latex>, <latex>Nic_i</latex> - число интерфейсов, находящихся под контролем класса <latex>i</latex>, <latex>m</latex> – предполагаемое число сущностей, <latex>l</latex> – предполагаемой число интерфейсов. 6. Ассоциативный вес варианта использования <latex>AWUC = \frac{N_{CC_j} + N_{aec_j} + N_{ec_j}}{\sum_{j=1}^{u}(N_{CC_j} + N_{aec_j} + N_{ec_j})},</latex> где <latex>N_{CC_j}</latex> – число управляющих классов, связанных с данным вариантом использования, <latex>N_{aec_i}</latex> – число отношений между сущностями и данным вариантом использования, <latex>N_{ec_i}</latex> – число сущностей, связанных с данным вариантом использования.
6. Коэффициент сходства данного варианта использования с остальными вариантами. Считается между конкретным вариантом использования и всеми остальными, используя формулу для подсчета элементов матрица похожести.
При подсчете матрицы нужно учитывать, что признаки вариантов использования есть бинарные, а есть числовые. Поэтому сходство вариантов использования считается по формуле: <latex>s(i, j) = \frac{w_1s_1(i,j) + w_2s_2(i,j)}{w_1 + w_2},</latex> где <latex>s_1(i,j)</latex> – мера сходства, посчитанная только на бинарный признаках по формуле подсчета элементов матрицы похожести c <latex>w = 1,</latex> <latex>s_2(i,j) = 1 - d(i,j)</latex> – мера сходства для числовых признаков, где <latex>d_{ij}</latex> считается по формуле \ref{desim}, <latex>w_1, w_2</latex> - веса, подобраны в соответствии с важностью матриц схожести и расстояний, авторы положили <latex>w_1 = w_2 = 0.5.</latex>
Сначала авторы статьи выбрали наиболее подходящий способ кластеризации. Для этого они привлекли экспертов и считали ошибку по формуле: <latex> Error = \frac{1}{2} \sum_{i=1}^{K} NC_{i} \bigtriangleup NE_{i},</latex> где кластер <latex>NC_{i}</latex> разметил метод кластеризации, <latex>NE_{i}</latex> – кластер, размеченный экспертом. Авторы усреднили ошибку между 4 различными системами:
По следующей формуле: <latex>QCF_i = \frac{1}{4}\sum_{j=1}^{4}\frac{NCE_{ij}}{NUC_{j}},</latex> где <latex>NCE_{ij}</latex> – ошибка <latex>i</latex>-ого метода кластеризации на j-ой системе, <latex>NUC_{j}</latex> – число вариантов использования в j-ой системе.
Далее авторы провели анализ чувствительности признаков – они удаляли поочередно признаки и смотрели, ухудшилось ли качество. Если не уменьшалось, то удаляли этот признак. Таким образом авторы получили набор признаков, достаточный для качественной кластеризации.
Лучшим методом кластеризации оказался метод RBR, средняя ошибка: 0.05, далее прямой поиск кластеров с результатом 0.095. Среди методов оценки числа кластеров лучше оказался метод 2 - Ray и Tury индекс, его погрешность не более одного кластера (в сравнении с экспертной оценкой числа кластеров). Анализ влияния признаков показал, что признаки на основе актеров, управляющих классов и классов-сущностей важны, при их удалении качество кластеризации ухудшалось на всех системах. Далее авторы попробовали поменять веса <latex>w_1</latex> и <latex>w_2</latex> при подсчете матрицы сходства вариантов использования. Оказалось, что веса <latex>w_1 = w_2 = 0.5</latex> оптимальны для задачи кластеризации. Авторы сравнили свой метод с методом Кима и оказалось, что их метод дает меньшую ошибку на всех рассмотренных системах.