Podręcznik: Relacja zgodności i relacja nierozróżnialności

7. Analiza i eksploracja danych

7.3. Relacja zgodności i relacja nierozróżnialności

W podrozdziale przedstawiamy notację relacji nierozróżnialności, która jest podstawowym pojęciem w dziedzinie eksploracji danych. Podobne pojęcie nazywane relacją zgodności (tolerancji) jest stosowane w dziedzinie układów logicznych. Jest używane głównie do celów dekompozycji układów kombinacyjnych [2.17], oraz logiki sekwencyjnej [2.22]. Na bazie tej relacji skonstruowano pojęcie
r-podziału, które znajduje zastosowanie w syntezie logiki wielowartościowej, a tym samym może być zastosowane do reprezentacji zarówno systemów informacyjnych jak i systemów decyzyjnych.

Niech $A=( U,A\cup D)$ , będzie systemem decyzyjnym, wtedy z każdym podzbiorem $B\subseteq A$ kojarzymy relację równoważności $IND_{A}(B)$ :

$IND_{A}( B) =\left\{( u_{p} ,u_{q}) \in U^{2} :\forall a_{i} \in B,\rho ( u_{p} ,a_{i}) =\rho ( u_{q} ,a_{i})\right\}$

$IND_{A}( B)$ nazywamy B-relacją nierozróżnialności [2.24].

Jednakże, dla systemu decyzyjnego przedstawionego w tablicy 2.30, symbol „*” dla obiektu może wyrażać wartość 0 lub 1. W rezultacie, obiekt przedstawia wiele wierszy tablicy. Stąd, klasyfikacja z użyciem relacji nierozróżnialności nie znajduje zastosowania. Aby rozwiązać ten problem wprowadzamy relację zgodności.

Wartości atrybutów a_i, tj. r_pi = r(u_p,a_i) oraz r_qi = r(u_q,a_i) nazywamy zgodnymi (r_pi ~ r_qi) wtedy i tylko wtedy, gdy r_pi = r_qi lub r_pi = * lub r_qi = *, gdzie „*” oznacza przypadek, dla którego wartość atrybutu jest „do not care”. Z drugiej strony, jeżeli r_pi oraz r_qi są zdefiniowane i są różne mówimy, że r_pi jest nie zgodne z r_qi i tę relację oznaczamy przez r_p r_qi.

Na podstawie tej definicji mówimy o relacji zgodności COM_A(B) określonej dla każdego zbioru B Í A:

COM_A(B) = {(up,uq) Î U 2: " ai Î B, r(up,ai) ~ r(uq,ai)},

gdzie o obiektach p oraz q, które spełniają relację COM_A(B) mówimy, że są zgodne w zbiorze B. Obiekty zgodne w zbiorze B = A nazywamy po prostu zgodnymi.

Relacja zgodności, nazywana również relacją tolerancji, jest zwrotna i symetryczna, a stąd generuje klasy zgodności na zbiorze obiektów U. Relacja zgodności pozwala na klasyfikowanie obiektów, ale klasy obiektów nie tworzą podziałów na zbiorze U, jak to jest w przypadku relacji nierozróżnialności. COM_A(B) klasyfikuje obiekty grupując je w klasy zgodności, tj. U|COM_A(B) gdzie B Í A.

Stąd, dowolny zbiór obiektów U reprezentujący system informacyjny lub system decyzyjny może zostać przypisany wielokrotnie i do różnych klas dla danego podzbioru atrybutów A. Taką rodzinę klas nazywamy r-podziałem i oznaczamy przez P(B), gdzie B jest wybranym podzbiorem zbioru A = {a1 ,..., am}.

r-podział na zbiorze U może być postrzegany jako zbiór nierozłącznych podzbiorów U, których suma jest równa U. Wszystkie symbole i operacje dla algebry podziałów [2.22], mogą zostać bezpośrednio zastosowane do algebry r-podziałów. W szczególności relacja mniejszy lub równy dla dwóch r-podziałów P₁ oraz P₂ (P₁ £ P₂) zachodzi wtedy i tylko wtedy, gdy dla każdej klasy z r-podziału P₁, oznaczanej w skrócie przez K_i(P₁) istnieje K_j(P₂) taka, że K_i(P₁) Í K_j(P₂).

r-podział na jednoelementowym zbiorze B = {ai} oznaczamy przez P(a_i) lub po prostu $\prod\nolimits _{a_{i}}$ .

r-podział indukowany przez zbiór B jest iloczynem r-podziałów indukowanych przez pojedyncze atrybuty a_iÎ B.