Editing Granular computing (section)

====Equivalence class granulation====
We illustrate with an example.  Consider the attribute-value system below:

:{| class="wikitable" style="text-align:center; width:30%" border="1"
|+ Sample Information System
! Object !! <math>P_1</math> !! <math>P_2</math> !! <math>P_3</math> !! <math>P_4</math> !! <math>P_5</math>
|-
! <math>O_1</math>
| 1 || 2 || 0 || 1 || 1
|-
! <math>O_2</math>
| 1 || 2 || 0 || 1 || 1
|-
! <math>O_3</math>
| 2 || 0 || 0 || 1 || 0
|-
! <math>O_4</math>
| 0 || 0 || 1 || 2 || 1
|-
! <math>O_5</math>
| 2 || 1 || 0 || 2 || 1
|-
! <math>O_6</math>
| 0 || 0 || 1 || 2 || 2
|-
! <math>O_7</math>
| 2 || 0 || 0 || 1 || 0
|-
! <math>O_8</math>
| 0 || 1 || 2 || 2 || 1
|-
! <math>O_9</math>
| 2 || 1 || 0 || 2 || 2
|-
! <math>O_{10}</math>
| 2 || 0 || 0 || 1 || 0
|}

When the full set of attributes <math>P = \{P_1,P_2,P_3,P_4,P_5\}</math> is considered, we see that we have the following seven equivalence classes or primitive (simple) concepts:

:<math>
\begin{cases} 
\{O_1,O_2\} \\ 
\{O_3,O_7,O_{10}\} \\ 
\{O_4\} \\ 
\{O_5\} \\
\{O_6\} \\
\{O_8\} \\
\{O_9\} \end{cases}
</math>

Thus, the two objects within the first equivalence class, <math>\{O_1,O_2\},</math> cannot be distinguished from one another based on the available attributes, and the three objects within the second equivalence class, <math>\{O_3,O_7,O_{10}\},</math> cannot be distinguished from one another based on the available attributes.  The remaining five objects are each discernible from all other objects.  Now, let us imagine a projection of the attribute value system onto attribute <math>P_1</math> alone, which would represent, for example, the  view from an observer which is only capable of detecting this single attribute. Then we obtain the following much coarser equivalence class structure.

:<math>
\begin{cases} 
\{O_1,O_2\} \\ 
\{O_3,O_5,O_7,O_9,O_{10}\} \\ 
\{O_4,O_6,O_8\} \end{cases}
</math>

This is in a certain regard the same structure as before, but at a lower degree of resolution (larger grain size).  Just as in the case of [[#Value granulation (discretization/quantization)|value granulation (discretization/quantization)]], it is possible that relationships (dependencies) may emerge at one level of granularity that are not present at another.  As an example of this, we can consider the effect of concept granulation on the measure known as ''attribute dependency'' (a simpler relative of the [[mutual information]]).

To establish this notion of dependency (see also [[rough sets]]), let <math>[x]_Q = \{Q_1, Q_2, Q_3, \dots, Q_N \}</math> represent a particular concept granulation, where each <math>Q_i</math> is an equivalence class from the concept structure induced by attribute set {{mvar|Q}}.  For example, if the  attribute set {{mvar|Q}} consists of attribute <math>P_1</math> alone, as above,  then the concept structure <math>[x]_Q</math> will be composed of 
:<math>\begin{align}
Q_1 &= \{O_1,O_2\}, \\
Q_2 &= \{O_3,O_5,O_7,O_9,O_{10}\}, \\
Q_3 &= \{O_4,O_6,O_8\}.
\end{align}</math> 
The '''dependency''' of attribute set {{mvar|Q}} on another attribute set {{mvar|P}}, <math>\gamma_P(Q),</math> is given by

:<math>
\gamma_{P}(Q) =  \frac{\left | \sum_{i=1}^N {\underline P}Q_i \right |} {\left | \mathbb{U} \right |} \leq 1
</math>

That is, for each equivalence class <math>Q_i</math> in <math>[x]_Q,</math> we add up the size of its "lower approximation" (see [[rough sets]]) by the attributes in {{mvar|P}}, i.e., <math>{\underline P}Q_i.</math> More simply, this approximation  is the number of objects which on attribute set {{mvar|P}} can be positively identified as belonging to target set <math>Q_i.</math> Added across all equivalence classes in <math>[x]_Q,</math> the numerator above represents the total number of objects which—based on attribute set {{mvar|P}}—can be positively categorized according to the classification induced by  attributes {{mvar|Q}}.  The dependency ratio therefore expresses the proportion (within the entire universe) of such classifiable objects, in a sense capturing the "synchronization" of the two concept structures <math>[x]_Q</math> and <math>[x]_P.</math> The dependency <math>\gamma_{P}(Q)</math> "can be interpreted as a proportion of such objects in the information system for which it suffices to know the values of attributes in {{mvar|P}} to determine the values of attributes in {{mvar|Q}}" (Ziarko & Shan 1995).

Having gotten definitions now out of the way, we can make the simple observation that the choice of concept granularity (i.e., choice of attributes) will influence the detected dependencies among attributes.  Consider again the attribute value table from above:

:{| class="wikitable" style="text-align:center; width:30%" border="1"
|+ Sample Information System
! Object !! <math>P_1</math> !! <math>P_2</math> !! <math>P_3</math> !! <math>P_4</math> !! <math>P_5</math>
|-
! <math>O_1</math>
| 1 || 2 || 0 || 1 || 1
|-
! <math>O_2</math>
| 1 || 2 || 0 || 1 || 1
|-
! <math>O_3</math>
| 2 || 0 || 0 || 1 || 0
|-
! <math>O_4</math>
| 0 || 0 || 1 || 2 || 1
|-
! <math>O_5</math>
| 2 || 1 || 0 || 2 || 1
|-
! <math>O_6</math>
| 0 || 0 || 1 || 2 || 2
|-
! <math>O_7</math>
| 2 || 0 || 0 || 1 || 0
|-
! <math>O_8</math>
| 0 || 1 || 2 || 2 || 1
|-
! <math>O_9</math>
| 2 || 1 || 0 || 2 || 2
|-
! <math>O_{10}</math>
| 2 || 0 || 0 || 1 || 0
|}

Consider the dependency of attribute set  <math>Q = \{P_4, P_5\}</math> on attribute set <math>P = \{P_2, P_3\}.</math>  That is, we wish to know what proportion of objects can be correctly classified into classes of <math>[x]_Q</math> based on knowledge of <math>[x]_P.</math> The equivalence classes of <math>[x]_Q</math> and of <math>[x]_P</math> are shown below.

:{| class="wikitable"
|-
! <math>[x]_Q</math>
! <math>[x]_P</math>
|-
| <math>
\begin{cases} 
\{O_1,O_2\} \\ 
\{O_3,O_7,O_{10}\} \\ 
\{O_4,O_5,O_8\} \\
\{O_6,O_9\}\end{cases}
</math>
| <math>
\begin{cases} 
\{O_1,O_2\} \\ 
\{O_3,O_7,O_{10}\} \\ 
\{O_4,O_6\} \\
\{O_5,O_9\} \\
\{O_8\}\end{cases}
</math>
|}

The objects that can be ''definitively'' categorized according to concept structure <math>[x]_Q</math> based on <math>[x]_P</math> are those in the set <math>\{O_1,O_2,O_3,O_7,O_8,O_{10}\},</math> and since there are six of these, the dependency of {{mvar|Q}} on {{mvar|P}}, <math>\gamma_{P}(Q) = 6/10.</math> This might be considered an interesting dependency in its own right, but perhaps in a particular data mining application only stronger dependencies are desired.

We might then consider the dependency of the smaller attribute set  <math>Q = \{P_4\}</math> on the attribute set <math>P = \{P_2, P_3\}.</math>  The move from <math>Q = \{P_4, P_5\}</math> to <math>Q = \{P_4\}</math> induces a coarsening of the class structure <math>[x]_Q,</math> as will be seen shortly.  We wish again to know what proportion of objects can be correctly classified into the (now larger) classes of <math>[x]_Q</math> based on knowledge of <math>[x]_P.</math> The equivalence classes of the new <math>[x]_Q</math> and of <math>[x]_P</math> are shown below.

:{| class="wikitable"
|-
! <math>[x]_Q</math>
! <math>[x]_P</math>
|-
| <math>
\begin{cases} 
\{O_1,O_2,O_3,O_7,O_{10}\} \\ 
\{O_4,O_5,O_6,O_8,O_9\} \end{cases}
</math>
| <math>
\begin{cases} 
\{O_1,O_2\} \\ 
\{O_3,O_7,O_{10}\} \\ 
\{O_4,O_6\} \\
\{O_5,O_9\} \\
\{O_8\}\end{cases}
</math>
|}

Clearly, <math>[x]_Q</math> has a coarser granularity than it did earlier.  The objects that can now be ''definitively'' categorized according to the concept structure <math>[x]_Q</math> based on <math>[x]_P</math> constitute the complete universe <math>\{O_1,O_2,\ldots,O_{10}\}</math>, and thus  the dependency of {{mvar|Q}} on {{mvar|P}}, <math>\gamma_{P}(Q) = 1.</math> That is, knowledge of membership according to category set  <math>[x]_P</math> is adequate to determine category membership in <math>[x]_Q</math> with complete certainty; In this case we might say that <math>P \rightarrow Q.</math> Thus, by coarsening the concept structure, we were able to find a stronger (deterministic) dependency.  However, we also note that the classes induced in <math>[x]_Q</math> from the reduction in resolution necessary to obtain this deterministic dependency are now themselves large and few in number; as a result, the dependency we found, while strong, may be less valuable to us than the weaker dependency found earlier under the higher resolution view of <math>[x]_Q.</math>

In general it is not possible to test all sets of attributes to see which induced concept structures yield the strongest dependencies, and this search must be therefore be guided with some intelligence.  Papers which discuss this issue, and others relating to intelligent use of granulation, are those by Y.Y. Yao and [[Lotfi Zadeh]] listed in the [[#References]] below.