The purpose of this note is to augment information systems with a relation of betweenness among things in the universe of the system and derive from it a geometric representation of granules of things in Euclidean spaces. Next, the notion of betweenness renders a service in introducing a new notion of a hypergranule. An application to conflict resolution by defining coalitions of agents as granules or hyper-granules and their mixed strategies as elements of convex hulls spanned on things defining the granule is proposed. Finally, hyper-granules offer a new classifying algorithm which exploits neighborhoods of things and in a sense is an improved with respect to similarity variant of nearest neighbor classifier.
We would like to recall here basic facts about notions mentioned in Abstract, to make this note self–contained. We begin with the Lukasiewicz rough inclusion. 1.1
The Lukasiewicz Rough Inclusion
Given a set of things U , a rough inclusion is a ternary relation μ ⊆ U × U × [
dmu(x, y) = min{sup{r : μ(x, y, r)}, sup{s : μ(y, x, s)}}. (1)
Proposition 1. dμ(x, y) = 1 if and only if x = y.
In the case when things in the universe U are described by means of a finite set A of
attributes so each thing x ∈ U is represented by its information set {a(x) : a ∈ A},
we can define the Lukasiewicz rough inclusion μL by taking as its value on a pair x, y
in U the quotient of the cardinality of the indiscernibility set IN D(x, y) = {a ∈ A :
a(x) = a(y)} and the cardinality of the set A:
(2)
(3)
cf., [
Betweenness
μL(x, y) =
card(IN D(x, y))
card(A)
,
The notion of betweenness plays an essential role in axiomatization of elementary
geometry of Euclidean spaces due to Tarski, see Tarski and Givant [
Van Benthem [
N (x, y, z) if and only if dμ(x, y) > dμ(z, y).
The relation N thus defined, does satisfy all axioms for nearness in Van Benthem
[
Betweenness relation in the sense of Van Benthem TB(z, u, v) (‘u is between z
and v’) introduced in Van Benthem [
TB(z, u, v) ⇔ [for each w ∈ U (u = w) or N (u, z, w) or N (u, v, w)]. (4) This means that for each thing w distinct from z, either u is closer to z than is w or u is closer to v than is w. 2
Granules from Indiscernible Things We assume that things in the set U are described by means of values of N real valued attributes in the set A; from this point of view the set U becomes the set R(U ) ⊆ RN of vectors in RN . As said above, each thing x ∈ U is represented by the vector [ai(x)]iN=1 where < a1, a2, . . . , aN > is a fixed ordering of attributes.
card(Δ) = δ · N.
Example 1. We consider things a, b and a thing c which agrees with a and b on the set Δ and has 21 · (N − δ · N ) attribute values in common with a and 12 · (N − δ · N ) attribute values in common with b; we assume for simplicity that it is possible otherwise we should consider ⌊ 21 · (N − δ · N )⌋ and ⌈ 12 · (N − δ · N )⌉, respectively which would only make calculations more cumbersome. Please observe that we do not specify positions of values, i.e., we do not specify particular attributes on which these values are taken, with exception for Δ only. Therefore, it makes sense to identify all such things into a class [c] in which all things have values on attributes in Δ same as a and b and share with each of a, b one half of the remaining values.
Proof. We find the distance dμL between a, c and b, c with respect to the rough inclusion μL; by definition (1), dμL (a, c) = δ · N + 21 · (N − δ · N )
N = 1 + δ 2 = dμL (c, b).
(6)
We now consider an arbitrary thing x which for some quotient α in [
N = β + (α − β) · δ,
(7) = 1 − β + (α + β − 1) · δ.
(8) and dμL (x, b) ≤ α · δ · N + (1 − β) · (N − δ · n)
N Let us assume, to the contrary, that (1) dμL (x, a) > dμL (c, a) and (2) dμL (x, b) > dμL (c, b).
Condition (1) means after substitution of values in (6) and (7) that β + (α − β) · δ > (5) (9) i.e., 1 δ α · δ + β · (1 − δ) > + .
2 2
α · δ − β · (1 − δ) > · δ − 3 2
We have already observed that we have not specified the attributes selected and
actually we have discussed classes of equivalence of things, two things x, y being
equivalent if and only if they have had same fractions of attribute values for attributes
in Δ and same fraction of attribute values not in Δ. Hence, for fractions γ of values
in Δ and ε of values in A \ Δ common with a, and, at most 1 − ε values of attributes
in A \ Δ in common with b, we denote with the symbol [γ, ε] the class of things
satisfying those conditions. We regard, hence, the vector [γ, ε] as the representation of
that class in the vector space R2, the representation space. In particular, the thing a is
represented as [
Proposition 3. For α ∈ [
Proof. This proof goes on similar lines as proof of the previous proposition. Let d denotes the class [1, α] and let x be in the class [γ, ε]. Assuming to the contrary that (1)dμL (x, a) > dμL (d, a) and (2) dmuL (x, b) > dmuL (d, b), we obtain inequalities and,
γ · δ + ε · (1 − δ) > δ + α · (1 − δ), γ · δ + (1 − ε) · (1 − δ) > δ + (1 − α) · (1 − δ).
2 · γ · δ > 2 · δ, i.e., γ > 1, impossible. The proposition is proved.
It turns out that the whole interval from [
The Case Δ = ∅
In this case δ = 0 and our proofs above are not valid. In this case, given things a, b in
U , with IN D(a, b) = ∅, for a choice of γ ∈ [
Proposition 4. For each choice of γ ∈ [
Proof. For a point [ε, δ] with ε, δ ∈ [
GB(x, a1, a2, . . . , an) (‘x is between a1, a2, . . . , an’) if and only if for each thing y 6= x he thing x is closer than y to some ai in the mereological sense of (3). 2.2
The General Case
We consider a set V = {a1, a2, . . . , an} of things in U . For a choice of γ1, γ2, . . . ,
γn ∈ [
Proposition 6. The relation GB(x, a1, a2, . . . , an) holds for a class x= ({a1, ..., an}, [γ1, γ2, . . . , γn]) (17) if and only if [γ1, γ2, . . . , γn] belongs in the convex hull of vectors [1, 0, 0..., 0], [0, 1, 0, 0, ..., 0], ..., [0, 0, ..., 0, 1] representing, in this order, classes a1, a2, ..., an. 3
A Geometric Representation of Granulation In the general case, the process of forming of a class x=(V, γ) represented by the vector γ = [γ1, γ2, ..., γn] can be regarded as forming of a granule of things gr(V, γ). This granulation process is different of previously considered in that it does involve a sort of Y j≤n
N − Pk<j γk · N γj · N
. φ(N, 1) = 1,
N φ(N, k + 1) = X φ(N − j, k).
j=0
a shuffling map, which takes into x things having specified fractions of attribute values
in common with the corresponding classes ai but over arbitrary sets of attributes of
cardinality γi · N . This secures a kind of control over values in contradiction to our
previous granulation paradigm in which only a fixed part of a given thing attribute
values was coming from the granule center, cf., [
For a given vector γ=[γ1, γ2, . . . , γn] in the representation space, representing the granule gr(V, γ), the size of the granule gr(V, γ) is The number of granules of type represented by a vector γ = [γ1, γ2, . . . , γn] is the number of sequences k1, k2, . . . , kn of natural numbers such that Pi ki = N , i.e., it equals the number of integer–valued vectors on the hyperplane Pi xi = N , given recurrently by the function φ(N, n): (18) (19) (20)
described above; in reality, only a small fraction of those objects will exist in the set U .
3.1
Granular Classifiers Assume that a decision partition is imposed on the things in the set U into decision classes D1, D2, . . . , Dm. For a U–granule g = gU (γ), we denote with P r[g, Di] the probability that a randomly chosen thing in g is assigned to the class Di. Then the Bayesian decision on g is the class D(g) = Di∗ such that P r[g, Di∗ ] = max{P r[g, Di] : i = 1, 2, . . . , m}.
4
An Application Proposal: Conflict Resolution
We propose to apply the afore described results to the problem of conflict resolution.
In a conflict, we have a finite number of agents declaring their standpoints on a
number of issues; those standpoints are conflicting, i.e., on each issue there are agents
having distinct standpoints. A resolution of a conflict means some process leading to
a rationally chosen set of non–conflicting standpoints for all agents. Examples can be
saddle points in two–person zero–sum games, either for pure or mixed strategies, or,
the Nash equilibrium points in continuous convex–concave games. In each of these
cases, agents reach a set of strategies which is satisfying for each of them.
Such a rationale is difficult to be obtained in less formalized conflicts, and, our
example deals with such a conflict. We base our approach on the example of a
conflict in Pawlak [
Example 2. The conflict described in [
A3 A4 A5 A6 0 1 1 1 1 1 N 0 0 0 1 0 0 0 N N 0 0 N 0 1 0 0 0 0
N 1 0 N 1
In this case, the set of agents V = {Ai1 , Ai2 , . . . , Aik } forming a granule is called a coalition, and standpoints of them on issues are their pure strategies. Given coefficients γ1, ..., γk summing up to 1, sequences of issues in the granule (V, [γ1, ..., γk]) are mixed strategies of agents. Given a partition of the set of agents into coalitions C1, C2, ..., Cm, we call a conflict resolution a set i1, i2, ..., im} of mixed strategies issued from granules generated by C1, C2, .., Cm which are consistent, i.e., conflict–less.
We decide to consider coalitions V1 = {A1, A6} and V2 = {A2, A3, A4, A5}. Forming all possible granules over V1 and V2 yields possible mixed strategies of both coalitions. Due to their number, we list in Figs.2,3 a selection of six of those strategies for each of the two coalitions. We find exemplary boldfaced mixed strategies N1ON1 for the coalition V 1 and NN0NN for the coalition V 2 which are identical for both coalitions: each of them can provide a conflict resolution; it is true that this requires a ‘gentleman’s agreement’ to accept the results of this procedure; for instance, each of these solutions would require that A1 gives up on its standpoint on issue I1, which in real practice can be impossible due, e.g., to political and religious reasons. The specific bargained for standpoints can be: 01001, 11001, 01011, 11011. The approach presented above begins with a group G of things and ends with the notion of collection of things between G. Among those things are virtual ones not present in the decision/information system. Therefore, we now propose the analysis from the viewpoint of things in the information system.
∀x ∈ X .∃Y ⊆ X \ {x}.Btw(x, Y ). (21)
Lemma 2. For each y ∈/ X , it is true that Btw(y, Y ) holds for no Y ⊆ X . Moreover, there exists an attribute a such that the value a(y) 6= a(x) for each x ∈ X . Contrarily, for each x ∈ X , and, for each attribute a, it is true that a(x) ∈ {a(y) : y ∈ X \ {x}.
For the hyper–granule X , we consider the complementary set of objects U \ X ; let X ′ be a hyper–granule of objects in U \ X . Iterating this procedure, we define in the universe set U a set of hyper–granules {X (i) : i ∈ I}, where X (j+1) is a hyper–granule in the set U \ Si≤j X (i). The remnant of U consist of outliers unable to enter any hyper–granule.
We denote with the symbol H(x) the hyper–granule containing the thing x. For a thing x, we consider sets of thing in H(x) \ {x} which we denote with the generic symbol N (x) with the property that Btw(x, N (x)) and all coordinates of the vector representing x with respect to N (x) are positive; we will call any such set a neighborhood of x; in the example in Fig.4, for instance, N (4) = {8, 10}.
A neighborhood N (x) of x is irreducible if it is of minimal possible cardinality; such is N (4) pointed to above.. 6
Applications: Hyper–Granules as Coalitions in Conflicts and a Decision Prediction Modal Logic
6.1
Hyper–Granules as Coalitions in Conflicts We return to Fig. 1, showing standpoints of agents A1–A6 on issues I1–I5. As before, we regard the standpoint N as ‘don’t care’ a fortiori N can be 0 or 1. We observe that A1 cannot be considered as a candidate to the hyper–granule of A2–A6 as the issue I1 on A1 takes value 0 not taken by any of A2–A6.
On the other hand, due to our convention about N , agents A2–A6 make a hyper– granule X . This hyper–granule can produce a between element N N 0N N representing sixteen specific bargaining propositions, from 00000 to 11011. The agent A1 remains as an outlier due to value 0 on I1 which cannot be supplied by any other agent. The bargaining between X and A1 can focus on I3 on which A1 takes value of
6.2
A Decision Prediction Logic and a Decision Assignment Algorithm We will regard the universe U of the informaton system as the training set on which the decision is given, and we consider the additional test set on which decision is to be learned on the basis of its values on U .
L = ¬M ¬. x |= L(φ ⇒ ψ) ⇒ (x |= Lφ ⇒ x |= Lψ). x |= Lφ ⇒ x |= φ. (24) (25) (26) (27)
set of decision values; the formula x |= (vd ∈ A) reads that decision value proposed for x is in the set A of decision values. Necessitation means stressing this hypothesis by conforming it on all neighborhoods of x, and, possibility indicates possible sets of values of decision for x. 7
Appendix: Computational Aspects of Hyper–Granules We consider an information system S = (U, A, V ) where U is a set of things, A is a set of attributes,and, V is a set of attribute values. We will need the notion of a dual information matrix S∗ defined as the triple (A, V, U ), where for each pair (a, v) the entry in the cell S∗(a, v) is {x ∈ U : a(x) = v}. (28)
Computing hyper–granules
HYPER–GRANULE (U,A,V) 1. Form the dual information matrix S∗;
3. if there is a cell (a, v) such that S∗(a, v) = {x}
The complexity of the algorithm is Θ(|A| · |V | · |U |) as we do take into account neither the cost of inserting a symbol into a cell nor deleting it from a cell. We consider an information system TEST in Fig. 4. The dual information matrix TEST∗ is shown in Fig. 5. We have to remove from all cells the things 2, 5, 9. As each remaining cell is either empty or some at least two–element set, the hyper–granule is X = {1, 3, 4, 6, 7, 8, 10}. For the remaining subsystem TEST1=(A, V, {2, 5, 9}), we obtain the dual information matrix TEST1∗ shown in Fig. 6. After steps 2–4 of the algorithm, all cells are empty so there is no second hyper–granule: things 2, 5, 9 are outliers. We would like to observe in addition that it is easy to read off from the dual information matrix the coordinates of a thing in the representation space; e.g., the thing 4 can be represented as the vector [0, 0, 0, 0, 0, 0, 0, 31 , 0, 23 ] in the simplex spanned on unit vectors representing, respectively, things 1, 2, ..., 10 in the vector space R10. Hence, N (4) = {8, 10} is an irreducible neighborhood of the thing 4; another irreducible neighborhood of 4 is {1, 10} with coordinates [ 21 , 0, ..., 0, 12 ]. 7.1
A Decision Assigning Algorithm For a new test thing y, we consider in the universe U (the training set) the hyper–granule H(y) ⊆ U ∪ {y} along with irreducible neighborhoods N1(y), . . . , Nk(y) (if there are any). Let D(y) ⊆ Vd be the least set of decision values with the property that If x ∈ [ Ni(y) then d(x) ∈ D(y).
i By (22), the hypothetical d(y) belongs in D(y). Now, given j ≤ k, the neighborhood Nj (y) votes for decision value dj (y) in the manner as follows. For z ∈ Nj (y), we denote with qj (z) the coordinate with which z enters the vector representing y with respect to N (y). Then (29) (30) (32) where || − || is a metric chosen for Euclidean space containing Vd. Given a parameter p ≤ k, we select p neighborhoods from among N1(y), N2(y), . . . , Nk(y) with greatest values of qj = maxzqj (z) and let d(y) = argminv∈D(y)||v − X j≤p Pj≤p qj qj · dj (y)||.
(31) This approach may be regarded as a two–step variant of nearest neighbor classifier: neighborhoods which are irreducible are at the same time closest to the thing; an important factor not present in usual nearest neighbor classifiers is that neighborhoods guarantee also that attribute values in the thing come from neighborhood members which double stresses the similarity among the thing and neighborhood members.
I(x, y) = {a ∈ A : a(x) = a(y)}, f (x, y) = card(I(x, y)) card(A) . 1 2 3 4 5 6 7 8 9 10 For X ⊆ A and x ∈ U , we let V (x, X) = the sequence a(x) : a ∈ X in the assigned order of attributes; the symbol 0n denotes the sequence of length n of 0.
Procedure Irreducible Neighborhood(x)
variable sets z, Az(x, y), nz(x, y), N (x, y), vz(x, y) Initialization: N (x, y) ← ∅, 1. order coefficients f (x, y) in descending order 2. in descending order of f (x, y) do
while Az(x, y) 6= A do 4. z ← {y}, A{y}(x, y) ← I(x, y), n{y}(x, y) ← {y}, v{y}(x, y) ← [V (x, I(x, y)), 0|A|−|I(x,y)|]
(A \ Az(x, y)) ∩ I(x, z′) 6= ∅ do 6.
Az∪{z′}(x, y) ← Az(x, y) ∪ (A \ Az(x, y)) ∩ I(x, z′)), ∈/ z such that nz∪{z′}(x, y) ← nz(x, y) ∪ {z′}, z ← z ∪ {z′}, p(z′) ← |V (x, (A \ Az(x, y)) ∩ I(x, z′))| 7. if Az(x, y) = A then
N (x, y) ← N (x, y) ∪ {nz(x, y)} vz∪{z′}(x, y) = vz(x, y) + [0|A|−|vz(x,y)|, V (x, (A I(x, z′), 0|A|−|vz(x,y)|−|V (x,(A\Az(x,y))∩I(x,z′)|], \
Az(x, y)) ∩ 9. from Sy N (x, y) output the list of sets of minimal cardinality=the list of irreducible neighborhoods of x with respect to the irreducible neighborhood nz(x, y).
|I(x,y)| 10. |I(x,y)|+P z′∈nz\{y} p(z′) is the coordinate of y in the representation vector of p(z′) x, and, |I(x,y)|+P z′∈nz\{y} p(z′) is the coordinate of z′ in the representation vector of x As an example let us assign decision values to things 1, 2, . . . , 10 in TEST, in Fig. 7.1. For simplicity, the thing 4 is regarded as a test thing. The set D(4) is {0, 1}. Irreducible neighborhoods of 4 are of cardinality 2 and they are: N1(4) = {1, 10} with coordinates [ 61 , 56 ]; N2(4) = {1, 10} with coordinates [ 46 , 62 ]; N3(4) = {7, 8} with coordinates [ 62 , 46 ]; N4(4) = {8, 10} with coordinates [ 61 , 65 ].
Now, N1(4) votes for 13 · 1 + 32 · 1 = 1 = d1(4);
N2(4) votes for 64 · 0 + 26 · 1 → 0 = d2(4); N3(4) votes for 62 · 1 + 46 · 1 = 1 = d3(4);
N4(4) votes for 31 · 1 + 23 · 1 = 1 = d4(4).
The final decision value is the nearest of 0, 1 to the value 32 ·1+ 56 ·1+ 64 ·0+ 64 ·1 = 1137 which 23 + 56 + 46 + 64 is d(4) = 1. value 0 2 1 new thing 1 2 1 1 0 1