Identification of System Software Components Using Clustering Approach

Оригинал статьи: 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.

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

1. Не нужно взвешивать признаки
2. Можно проводить анализ влияния признаков на точность кластеризации
3. Новый точный метод идентификации компонент и их зон ответственности

Рассматриваем граф:

• вершины - объекты с наборами признаков (варанты использования)
• вершины соединяются ребрами с весами, вес ребра - коэффициент схожести объектов. Вычисляется на основе признаков.

Пусть <latex>N</latex> – число вариантов использования.

1. Матрица схожести <latex>S</latex> - матрица размера NхN, где

• <latex>s_{ij} = s_{ji},</latex>
• <latex>s_{ii} = 1,</latex>
• <latex>0 ⇐ s_{ij} ⇐ 1\ \forall 1 ⇐ i,j ⇐ N.</latex>

Матрицу схожести удобно использовать в случае, если признаки бинарные. Элементы матрицы обычно вычисляются следующим образом. Пусть <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} = d_{ji},</latex>
• <latex>d_{ii} = 1,</latex>
• <latex>0 ⇐ d_{ij} ⇐ 1\ \forall 1 ⇐ i,j ⇐ N.</latex>

Матрицу расстояний удобно использовать, если признаки - числа. Элементы матрицы считаются по косинусному расстоянию: <latex>d_{ij} = 1 - \frac{\vec{v_{i}} \cdot \vec{v_{j}}}{\sqrt{||\vec{v_i}||_2 * ||\vec{v_j}||_2}}.</latex>

• Иерархическая кластеризация. Сначала считаем, что всего N кластеров : <latex>\{C_1, \ldots, C_N \}</latex>, потом соединяем пару тех <latex>i,j</latex>, где <latex>d(C_i, C_j) = \min_{i\in C_i, j\in C_j} d_{ij}.</latex> Продолжаем итеративно, пока не останется K кластеров.

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

• RB - разделение. K - 1 раз разбиваем кластеры на 2, оптимизируя значение кластерной функции. Обычно берут отношение средней попарной похожести элементов внутри кластера к средней похожести элементов внутри кластера с элементами вне кластера.

• RBR - разделение. Так же, как RB, но в конце все разделения оптимизируются с одновременно.

• Прямая кластеризация. Одновременно ищутся все K кластеров.

• Fuzzy Clustering Method. Ищет разделения объектов, минимизируя функцию потерь.

• Алгоритмы из теории графов. Бинаризуем матрицу схожести S по порогу (ребро остается, если вес больше порога, иначе ребра нет), далее применяются алгоритмы поиска кластеров в графе.

• E- Neural Networks-Based Clustering. Номер кластера определятся номером нейрона, имеющего наибольшую активацию на данный объект.

Более подробное описание см. [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. Отношения между вариантами использования.

• extend - 1 всем, кто связан данным отношением с каким-то конкретным вариантом использования и самому варианту использования.
• generalize – аналогично extend.
• include – если <latex>U_i, U_j</latex> связаны отношением include, то 1 в колонке для <latex>U_i</latex> и для всех других <latex>U_k,</latex> связанных отношением include с <latex>U_j.</latex>

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 различными системами:

• Education System(ES),
• Online Stock Brokerage System(OSBS),
• Chain-Store System(CSS),
• Home Appliance Control System(HACS).

По следующей формуле: <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> оптимальны для задачи кластеризации. Авторы сравнили свой метод с методом Кима и оказалось, что их метод дает меньшую ошибку на всех рассмотренных системах.

1. R. Xu and D. Wunsch, “Survey of Clustering Algorithms , ” IEEE Transactions on Neural Networks, Vol. 16, No. 3, MAY 2005, pp. 645- 678.
2. G. Karypis, CLUTO: A Clustering Toolkit. Dept. of Computer Science, University of Minnesota, USA, 2002.