mdd:uc_clustering [objectoriented.ru]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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.
==== Краткое описание ====

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

  - Не нужно взвешивать признаки
  - Можно проводить анализ влияния признаков на точность кластеризации
  - Новый точный метод идентификации компонент и их зон ответственности
==== Матрицы взаимоотношений объектов ====

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

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

Пусть <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. Коэффициент сходства данного варианта использования с остальными вариантами. Считается между конкретным вариантом использования и всеми остальными, используя формулу для подсчета элементов матрица похожести.


==== Cоздание матрицы сходства вариантов использования ====

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


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


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