# Binary Classification of Multigranulation Searching Algorithm Based on Probabilistic Decision

Authors: Qinghua Zhang; Tao Zhang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Multigranulation computing, which adequately embodies the model of human intelligence in process of solving complex problems, is aimed at decomposing the complex problem into many subproblems in different granularity spaces, and then the subproblems will be solved and synthesized for obtaining the solution of original problem. In this paper, an efficient binary classification of multigranulation searching algorithm which has optimal-mathematical expectation of classification times for classifying the objects of the whole domain is established. And it can solve the binary classification problems based on both multigranulation computing mechanism and probability statistic principle, such as the blood analysis case. Given the binary classifier, the negative sample ratio, and the total number of objects in domain, this model can search the minimum mathematical expectation of classification times and the optimal classification granularity spaces for mining all the negative samples. And the experimental results demonstrate that, with the granules divided into many subgranules, the efficiency of the proposed method gradually increases and tends to be stable. In addition, the complexity for solving problem is extremely reduced.


---

## Body

## 1. Introduction

With the rapid development of modern science and technology, the daily information which people are facing is dramatically increasing, and it is urgent to find a simple and effective way to process the complex information. So the rise and development of multigranulation computing [1–8] have been promoted by this demand. Information granulation had attracted researchers’ great attention since a paper that focused on discussing information on granulation published by professor Zadeh in 1997 [9]. In 1985, a paper named “Granularity” was published by Professor Hobbs in the International Joint Conference on Artificial Intelligence held in Los Angeles, United States. It focuses on the granulation of decomposition and synthesis and how to obtain and generate different granularity [10]. These studies play a leading role not only in granular computing methodology [11–17], but also in dealing with complex information [18–22]. Subsequently, the number of researches focused on granular computing has rapidly increased. Many scholars successfully use the basic theoretical model of multigranulation computing to deal with practical problems [23–29]. Currently, multigranulation computing becomes a basic theoretical model to solve the complex problems and discover knowledge from mass information [30, 31].Multigranulation computing method is mainly aimed to establish a multilevels or multidimensional computing model, and then we need to find the solving way and synthesis strategies in different granularity spaces for solving complex problem. Complex information will be subdivided into lots of simple information in the different granularity spaces [32–35]; then, effective solutions will be obtained by data mining and knowledge discovery techniques to deal with simple information. So it can solve the complex problems in different granularity or dimensions. Aiming at large-scale binary classification problem, it is an important issue to determine the class of all objects in domain by using as little times as possible. And this issue attracts a large number of researchers’ attention [36–39]. Supposing we have a binary classification algorithm and N is the number of all objects in domain and p is the probability of negative samples in domain. Then we need to give the class of all objects in domain. The traditional method will search each object one by one by the binary classification algorithm and it is simple but has many heavy workloads when facing a large number of objects set. Therefore, some researchers have proposed group classification that each object is composed of a lot of samples, and this method improves the searching efficiency [40–42]. For example, how can we effectively complete the binary classification tasks with minimum classification times when facing the massive blood analysis? The traditional method is to test per person once. However, it is a heavy workload when facing many thousands of objects. But, to a certain extent, the single-level granulation method (namely, single-level group testing method) can reduce the workload.In 1986, Professor Mingmin and Junli proposed that using the single-level group testing method can reduce the workloads of massive blood analysis when the prevalence ratep of a sickness is less than about 0.3 [43]. In this method, all objects will be subdivided into many small subgroups, and then every subgroup will be tested. If the testing result of a subgroup is sickness, we will diagnose the result of each object by testing all the objects in this subgroup one by one. Else if its result is health, we can diagnose that all objects in this subgroup are heathy. But for millions and even billions of objects, can this kind of single-level granulation method still effectively solve the complex problem? At present, there are lots of methods about the single-level granulation searching model [44–54], but the studies on the multilevels granulation searching model are few [55–59]. A binary classification of multilevels granulation searching algorithm, namely, establishing an efficient multigranulation binary classification searching model based on hierarchical quotient space structure, is proposed in this paper. This algorithm combines the falsity and truth preserving principles in quotient space theory and mathematical expectations theory. Obviously, on the assuming that p is the probability of negative samples in domain, the smaller p, the higher efficiency of this algorithm. A large number of experimental results indicate that the proposed algorithm has high efficiency and universality.The rest of this paper is organized as follows. First, some preliminary concepts and conclusions are reviewed in Section2. Then, the binary classification of multigranulation searching algorithm is proposed in Section 3. Next, the experimental analysis is discussed in Section 4. Finally, the paper is concluded in Section 5.


## 2. Preliminary

For convenience, some preliminary concepts are reviewed or defined at first.Definition 1 (quotient space model [60]).
Suppose that triplet(X,F,T) describes a problem space or simply space (X,F), where X denotes the universe and F is the structure of universe X. T indicates the attributes (or features) of universe X. Suppose that X represents the universe with the finest granularity. When we view the same universe X from a coarser granularity, we have a coarse-granularity universe denoted by [X]. Then we can have a new problem space X,F,T. The coarser universe [X] can be defined by an equivalence relation R on X. That is, an element in [X] is equivalent to a set of elements in X, namely, an equivalence class X. So [X] consists of all equivalence classes induced by R. From F and T, we can define the corresponding [F] and [T]. Then we have a new space X,F,T called a quotient space of original space (X,F,T).Theorem 2 (falsity preserving principle [61]).
If a problem[A]→[B] on quotient space X,F,T has no solution, then problem A→B on its original space (X,F,T) has no solution either. In other words, if A→B on (X,F,T) has a solution, then [A]→[B] on X,F,T has a solution as well.Theorem 3 (truth preserving principle [61]).
A problem[A]→[B] on quotient space X,F,T has a solution, if for [x], h-1([x]) is a connected set on X, and problem A→B on (X,F,T) has a solution. h:X→[X] is a natural projection that is defined as follows:(1)hx=X,h-1u=x∣hx∈u.Definition 4 (expectation [62]).
LetX be a discrete random variable. The expectation or mean of X is defined as μ=EX=∑xxpX=x, where p(X=x) is the probability of X=x.
In the case thatX takes values from an infinite number set, μ becomes an infinite series. If the series converges absolutely, we say the expectation E(X) exists; otherwise, we say that the expectation of X does not exist.Lemma 5 (see [43]).
Letfq(x)=1/x+1-qx(x=2,3,4,…,q∈(0,1)) be a function with integer variable. If fq(x)<1 always holds for all x, then q∈(e-e-1,1).Lemma5 is the basis of the following discussion.Lemma 6 (see [42, 63]).
Letf(x)=[x] denote a top integral function. And let fq(x)=1/x+1-qx(x=2,3,4,…,q∈(0,1)) be a function with integer variable. fqx will reach its minimum value when x=1/p+p2/2 or x=1/p+p2/2+1,  x∈1,1-1/ln⁡q.Lemma 7.
Letgx=xqxe-e-1<q<1 be a function. If 2≤c≤1-1/ln⁡q and 1≤i<c/2, then the inequality (gi+gc-i)/2≤gc-1/2+gc+1/2/2<gc/2 holds.Proof.
We can obtain the first and second derivatives ofg(x) as follows:(2)g′x=qx1+xln⁡q,g′′x=qxln⁡q2+xln⁡q,g′′x=qxln⁡q2+xln⁡q<0,1≤x<x0,qxln⁡q2+xln⁡q=0,x=x0,qxln⁡q2+xln⁡q>0,x>x0,wherex0=-2ln⁡q,e-e-1<q<1.So, we can draw a conclusion that g(x) is a convex function (property of convex function is shown in Figure 1) when 1≤x<1-1/ln⁡q<x0=-2/ln⁡q. According to the definition of convex function, the inequality (gi+gc-i)/2≤(gc-1/2+gc+1/2)/2<gc/2 holds permanently. So Lemma 7 is proved completely.Figure 1
Property of convex function.


## 3. Binary Classification of Multigranulation Searching Model Based on Probability and Statistics

Granulation is seen as a way of constructing simple theories out of more complex ones [1]. At the same time, the transformation between two different granularity layers is mainly based on the falsity and truth preserving principles in quotient space theory. And it can solve many classical problems such as scale ball game and branch decisions. All the above instances just clearly embody the ideas to solve complex problems with multigranulation methods.In the second section, the relevant concepts about multigranulation computing theory and probability theory are reviewed. Of course, a multigranulation binary classification searching model not only solves practical complex problems with less cost, but also can be easily constructed. And this model may also play a certain role in the inspiration for the applications of multigranulation computing theory.Generally, supposing a nonempty finite setU=x1,x2,…,xn, where xii=1,2,3,…,n is a binary classification object, the triples U,2U,p is called a probability quotient space with probability p, where p is the negative sample rate in U. 2U is the structure of universe U. And let  U1,U2,…,Ut  (⋃i=1tUi=U,Um∩Un=Φ,m,n∈1,2,…,t,m≠n) be called a random partition space on probability quotient space. There is an example of binary classification of multigranulation searching model.Example 8.
On the assumption that many people need to do blood analysis of physical examination for diagnosing a disease (there are two classes, normal stands for health and abnormal stands for sickness), the domainU={x1,x2,…,xn} stands for all the people. Let N denote the number of all people, and p stands for the prevalence rate. So the quotient space of blood analysis of physical examination is (U,2U,p). Besides, we also know a binary classifier (or a reagent) that diagnoses a disease by testing blood sample. How can we complete all the blood analysis with the minimal classification times? Namely, how can we determine the class of all objects in domain. There are usually three ways as follows.Method 9 (traditional method).
In order to accurately diagnose all objects, every blood sample will be tested one by one, so this method needs to searchN times. This method is just like the classification process of machine learning.Method 10 (single-level granulation method).
This method is to mixk blood samples to a group where k may be 1,2,3,…,n; namely, the original quotient space will be random partition to (U1,U2,…,Ut)(⋃i=1tUi=U,Um∩Un=Φ,m,n∈1,2,…,t,m≠n). And then each mixed blood group will be tested once. If the testing result of a group is abnormal, and according to Theorem 2, we know that this abnormal group has abnormal object(s). In order to make a diagnosis, all of the objects in this group should be tested once again one by one. Similarly, if the testing result of a group is normal, and according to Theorem 3, we know that all of the objects are normal in this group. Therefore, all k objects in this group only need one time to make a diagnosis. The binary classifier can also classify the new blood sample that consists of k blood samples, in this process.
If every group has been mixed by large-scale blood samples (namely,k is a large number) and when some groups are tested to be abnormal, that means lots of objects must be tested once again one by one. In order to reduce the classification times, this paper proposes a multilevels granulation model.Method 11 (multilevels granulation method).
Firstly, each mixed blood group which containsk1 samples (objects) will be tested once, where k1 may be 1,2,3,…,n; namely, the original quotient space will be random partition to (U1,U2,…,Ut)(⋃i=1tUi=U,Um∩Un=Φ,m,n∈1,2,…,t,m≠n). Next, if some groups are tested to be normal, that means all objects in those groups are normal (health). Therefore, all k1 objects only need one time to make a diagnosis in this group. Else if some groups are tested to be abnormal, those groups will be subdivided into many smaller subsets (subgroups) which contain k2  (k2<k1) objects: namely, the quotient space of an abnormal group Ui will be random partition to (Ui1,Ui2,…,Uil)(⋃j=1lUij=Ui,Uim∩Uin=Φ,m,n∈{1,2,…,l},m≠n,l<k1). Finally each subgroup will be tested once again. Similarly, if a subgroup is tested to be normal, it is confirmed that all objects are health in corresponding subgroup, and if a subgroup is tested to be abnormal, it will be subdivided into smaller subgroups which contain k3  (k3<k2) objects once again. Therefore, the testing results of all objects can be ensured by repeating the above process in a group until the number of objects is equal to 1 or its testing result is normal in a subgroup. Then, the searching efficiency of the above three methods is analyzed as follows.In Method9, every object has to be tested once for diagnosing a disease, so it must take up N times in total.In Method10, the original problem space is subdivided into many disjoint subspaces (subsets). If some subsets are tested to be normal that means all objects need only to be tested once. Therefore, the classification times can be reduced if the probability p is small enough in some degree [9].In Method11, the key is trying to find the optimal multigranulation space for searching all objects, so a multilevels granulation model needs to be established. There are two questions. One is grouping strategy: namely, how many objects are contained in a group? The other one is optimal granulation levels: namely, how many levels should be granulated from the original problem space?In this paper, we mainly solve the two questions in Method11. According to the truth and falsity preserving principle in quotient space theory, all normal parts of blood samples could be ignored. Hence, the original problem will be simplified to a smaller subspace. This idea not only reduces the complexity of the problem, but also improves the efficiency of searching abnormal objects.Algorithm Strategy. Example 8 can be regarded as a tree structure which each node (which stands for a group) is an x-tuple. Obviously, the searching problem of the tree has been transformed into a hierarchical reasoning process in a monotonous relation sequence. The original space has been transformed into a hierarchical structure where all subproblems will be solved in different granularity levels. Firstly, the general rule can be concluded by analyzing the simplest hierarchy and grouping case which is the single-level granulation. Secondly, we can calculate the mathematical expectation of the classification times of blood analysis. Finally, an optimal hierarchical granulation model will be established by comparing with the expectation of classification times.Analysis. Supposing that there is an object set Y={y1,y2,…,yn}, the prevalence rate is p. So the probability of an object that appears normal in blood analysis is q=1-p. The probability of a group which is tested to be normal is qk1, and to be abnormal is 1-qk1, where k1 is the objects number of a group.


### 3.1. The Single-Level Granulation

Firstly, the domain (which containsN objects) is randomly subdivided into many subgroups, where each subset contains k1 objects. In other words, a new quotient space [Y1] is obtained based on an equivalence relation R. Then supposing that the average classification time of each object is a random variable Y1, so the probability distribution of Y1 is shown in Table 1.Table 1
The probability distribution ofY1.
Y 1 1 / k 1 1 / k 1 + 1 p Y 1 = y 1 q k 1 1 - q k 1Thus, the mathematical expectation ofY1 can be obtained as follows:(3)E1Y1=1k1×qk1+1+1k1×1-qk1=1k1+1-qk1.Then, the total mathematical expectation of the domain can be obtained as follows:(4)N×E1Y1=N×1k1×qk1+1+1k1×1-qk1.When the probability ofp keeps unchanged and k1 satisfies inequality E1(Y1)<1, this single-level granulation method can reduce classification times. For example, if p=0.5 and k1>1, and according to Lemma 5, E1(k1)>1 no matter what the value of k1. Then this single-level granulation method is worse than traditional method (namely, testing every object in turn). Conversely, if p=0.001 and k1=32, E1(Y1) will reach its minimum value, and the classification time of single-level granulation method is less than the traditional method. Let N=10000; the total of classification times is approximately equal to 628 as follows: (5)N×E1Y1=10000×132×q32+1+132×1-q32≈628.This shows that this method can greatly improve the efficiency of diagnosing and reduce 93.72% classification times in the single-level granulation method. If there is an extremely low prevalence rate, for example, p=0.000001, the total of classification times reaches its minimum value when each group contains 1001 objects (namely, k1=1001). If every group is subdivided into many smaller subgroups again and repeating the above method, can the total of classification times be further reduced?


### 3.2. The Double-Levels Granulation

After the objects of domain are granulated by the method of Section3.1, the original objects space becomes a new quotient space in which each group has k1 objects. According to the falsity and truth preserving principles in quotient space theory, if the group is tested to be abnormal, it can be granulated into many smaller subgroups. The double-levels granulation can be shown in Figure 2.Figure 2
Double-levels granulation.Then, the probability distribution of the double-levels granulation is discussed as follows.If each group containsk1 objects and tested once in the 1st layer, the average of classification times is 1/k1 for each object. Similarly, the average of classification times of each object is 1/k2 in the 2nd layer. When a subgroup contains k2 objects and is tested to be abnormal, every object has to be retested one by one once again in this subgroup, so the total of classification times of each object is equal to 1/k2+1.For simplicity, suppose that every group in the 1st layer will be subdivided into two subgroups which, respectively, containk21 and k21 objects in the 2nd layer.The classification time is shown in Table2 (✗ represents the testing result which is abnormal and ✓ represents normal).Table 2
The average classification times of each object with different results.
Times Objects k 1 k 21 k 22 Result 1 ✓ ✓ ✓ 3 + k 21 ✗ ✗ ✓ 3 + k 22 ✗ ✓ ✗ 3 + k 1 ✗ ✗ ✗For instance, letk1=8,  k21=4, and k22=4; there are four kinds of cases to happen.Case 1.
If a group is tested to be normal in the 1st layer, so the total of classification times of this group isk1×1/k1=1.Case 2.
If a group is tested to be abnormal in the 1st layer and its one subgroup is tested to be abnormal, and the other subgroup is also tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21+1)+k22×(1/k1+1/k22)=3+k21=7.Case 3.
If a group is tested to be abnormal in the 1st layer, its one subgroup is tested to be normal, and the other subgroup is tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21)+k22×(1/k1+1/k22+1)=3+k22=7.Case 4.
If a group is tested to be abnormal in the 1st layer, and its two subgroups are tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21+1)+k22×(1/k1+1/k22+1)=3+k1=11.Suppose each group containsk1 objects in the 1st layer, and their every subgroup has k2 objects in the 2nd layer. Supposing that the average classification times of each object is a random variable Y2, then the probability distribution of Y2 is shown in Table 3.Table 3
The probability distribution ofY2.
Y 2 1 / k 1 1 / k 1 + 1 / k 2 1 / k 1 + 1 / k 2 + 1 p Y 2 = y 2 q k 1 1 - q k 1 × q k 2 1 - q k 1 × 1 - q k 2Thus, in the 2nd layer, the mathematical expectation ofY2 which is the average classification times of each object is obtained as follows: (6)E2Y2=1k1×qk1+1k1+1k2×1-qk1×qk2+1+1k1+1k2×1-qk1×1-qk2=1k1+1-qk1×1k2+1-qk2.As long as the number of granulation levels increases to 2, the average classification times of each object will be further reduced: for instance, whenp=0.001 and N=10000. As we know, the minimum expectation of the total of classification times is about 628 with k1=32 in the single-level granulation. And according to (6) and Lemma 6, E2(Y2) will reach minimum value when k2=16. The minimum mathematical expectation of each object’s average classification times is shown as follows:(7)N×E2X=N×1k1×qk1+1k1+1k2×1-qk1×qk2+1+1k1+1k2×1-qk1×1-qk2≈338.The mathematical expectation of classification times can save 96.62% compared with traditional method and save 46.18% compared with single-level granulation method. Next we will discussi-levels granulation (i=3,4,5,…,n).


### 3.3. Thei-Levels Granulation

For blood analysis case, the granulation strategy inith layer is concluded by the known objects number of each group in previous layers (namely, k1,k2,…,ki-1 are known and just only ki is unknown). According to the double-levels granulation method, and supposing that the classification time of each object is a random variable Yi in the i-levels granulation, so the probability distribution of Yi is shown in Table 4.Table 4
The probability distribution ofYi.
Y i p Y i = y i 1 k 1 q k 1  1 k 1 + 1 k 2 1 - q k 1 × q k 2  ⋮ ⋮  ∑ j = 1 i 1 k j 1 - q k 1 × 1 - q k 2 × ⋯ × 1 - q k i - 1 × q k i  ∑ j = 1 i 1 k j + 1 1 - q k 1 × 1 - q k 2 × ⋯ × 1 - q k i - 1 × 1 - q k iObviously, the sum of probability distribution is equal to 1 in each layer.Proof.
Case 1 (the single-level granulation). One has(8)qk1+1-qk1=1.
Case 2 (the double-levels granulation). One has(9)qk1+1-qk1×qk2+1-qk1×1-qk2=qk1+1-qk1×qk2+1-qk2=qk1+1-qk1×1=1.
Case 3 (the i-levels granulation). One has(10)qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1×qki+1-qk1×1-qk2×⋯×1-qki=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1×qki+1-qki=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×qki-1+1-qki-1=⋯=qk1+1-qk1×1=1.
The proof is completed.Definition 12 (classification times expectation of granulation).
In a probability quotient space, a multilevels granulation model will be established from domainU={x1,x2,…,xn} which is a nonempty finite set, the health rate is q, the max granular levels is L, and the number of objects in ith layer is ki,  i=1,2,…,L. So the average classification time of each objects is Ei(Yi) in ith layer.(11)EiYi=1k1+∑i=2L1ki×∏j=1i-11-qkj+∏i=1L1-qki.In this paper, we mainly focus on establishing a minimum granulation expectation model of classification times by multigranulation computing method. For simplicity, the mathematical expectation of classification times will be regarded as the measure of contrasting with the searching efficiency. According to Lemma5, the multilevels granulation model can simplify the complex problem only if the prevalence rate p∈0,1-e-e-1 in the blood analysis case.Theorem 13.
Let the prevalence ratep∈(0,0.3); if a group is tested to be abnormal in the 1st layer (namely, this group contains abnormal objects), the average classification times of each object will be further reduced by subdividing this group once again.Proof.
The expectation difference between the single-level granulationE1(Y1) and the double-levels granulation E2(Y2) can adequately embody their efficiency. Under the conditions of e-e-1<q<1 and 1≤k2<k1, and according to (3) and (6), the expectation difference E1(Y1)-E2(Y2) is shown as follows:(12)E1Y1-E2Y2=1k1+1-qk1-1k1+1-qk1×1k2+1-qk2=1-qk1×1-1k2+1-qk2>0.According to Lemma 5, 1-qk1>0 and fqk2=1/k2+1-qk2<1 always hold; then we can get 1-(1/k2+1-qk2)>0. So the inequality E1(X)-E2(X)>0 is proved successfully.Theorem13 illustrates that it can reduce classification times by continuing to granulate the abnormal groups into the 2nd layer when k1>1. There is attempt to prove that the total of classification times will be further reduced by continuously granulating the abnormal groups into ith layers until a group’s number is no less than 1.Theorem 14.
Supposing the prevalence ratep∈(0,0.3), if a group is tested to be abnormal (namely, this group contains abnormal objects), the average classification times of each object will be reduced by continuously subdividing the abnormal group until the objects number of its subgroup is no less than 1.Proof.
The expectation difference between(i-1)-levels granulation Ei-1(Yi-1) and i-levels granulation Ei(Yi) reflects their efficiency. On the condition of e-e-1<q<1 and 1≤ki<ki-1, and according to (11), the expectation difference Ei-1(Yi-1)-Ei(Yi) is shown as follows:(13)Ei-1Yi-1-EiYi=1k1+∑l=2i-11kl×∏j=1l-11-qkj+∏l=1i-11-qkl-1k1+∑l=2i1ki×∏j=1l-11-qkj+∏l=1L1-qkl=1-qk1×⋯×1-qki-1×1-1ki+1-qki>0.Because 1-qk1×⋯×1-qki-1>0 is known, according to Lemma 5 and ki≥1, we can get (1/ki+1-qki)<1: namely 1-(1/ki+1-qki)>0. So Ei-1-Ei>0 is proved successfully.Theorem14 shows that this method will continuously improve the searching efficiency in the process of granulating abnormal groups from 1st layer to ith layer because Ei-1(Yi-1)-Ei(Yi)>0 always holds. However, it is found that the classification times cannot be reduced when the objects number of an abnormal group is less than or equal to 4, so the objects of this abnormal group should be tested one by one. In order to achieve the best efficiency, then we will explore how to determine the optimum granulation, namely, how to determine the optimum objects number of each group and how to obtain the optimum granulation levels.


### 3.4. The Optimum Granulation

It is a difficult and key point to explore an appropriate granularity space for dealing with a complex problem. And it not only requires us to keep the integrity of the original information but also simplify the complex problem. So we take the blood analysis case as an example to explain how to obtain the optimum granularity space in this paper. Suppose the conditione-e-1<q<1 always holds.Case 1 (granulating abnormal groups from the 1st layer to the 2nd layer). (a) If k1 is an even number, every group which contains k1 objects in 1st layer will be subdivided into two subgroups into 2nd layer.Scheme 15.
Supposing the one subgroup of the 2nd layer hasi  (1≤i<k1/2) objects, according to formula (6), the expectation of classification times for each object is E2(i). And the other subgroup has (k1-i) objects, so the expectation of classification times for each object is E2(k1-i). The average expectation of classification times for each object in the 2nd layer is shown as follows:(14)i×E2i+k1-i×E2k1-ik1.Scheme 16.
Suppose every abnormal group in 1st layer is average subdivided into two subgroups: namely, each subgroup hask1/2 objects in the 2nd layer. According to formula (6), the average expectation of classification times for each object in the 2nd layer is shown as follows:(15)2×k1/2×E2k1/2k1=k1×E2k1/2k1.The expectation difference between the above two schemes embodies their efficiency. In order to prove that Scheme16 is more efficient than Scheme 15, we only need to prove that the following inequality is correct: namely,(16)i×E2i+k1-i×E2k11-ik1-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx(e-e-1<q<1), and according to Lemma 7, then, we have(17)gi+gc-i2<gc2⟹i×qi+k1-i×qk1-i2<k12×qk1/2⟹i×qi+k1-i×qk1-i<k1×qk1/2⟹i×1k1+1-qk1×1+1i-qi+k1-i×1k1+1-qk1×1+1k1-i-qk1-i>k11k1+1-qk1×1+2k2-qk1/2⟹i×E2i+k1-i×E2k11-ik1-k1×E2k1/2k1>0.
The proof is completed.Therefore, if every group hask1 (k1 is an even number and k1>1) objects in the 1st layer that need to be subdivided into two subgroup, Scheme 16 is more efficient than Scheme 15.The experiment results have verified the above conclusion in Table5. Let p=0.004 and k1=16. When every subgroup contains 8 objects in the 2nd layer, the expectation of classification times obtains minimum value for each object, where k21 is the number of the one subgroup in the 2nd layer, k22 is the number of the other subgroup, and E2 is the corresponding expectation of classification times for each object.Table 5
The changes of average expectation with different objects number in two groups.
( k 21 , k 22 ) ( 1,15 ) ( 2,14 ) ( 3,13 ) ( 4,12 ) ( 5,11 ) ( 6,10 ) ( 7,9 ) ( 8,8 )  E 2 0.07367 0.07329 0.07297 0.07270 0.07249 0.07234 0.07225 0.07222(b) Ifk1 is an even number, every group which contains k1 objects in 1st layer will be subdivided into three subgroups into 2nd layer.Scheme 17.
In the 2nd layer, if the first subgroup hasi  (1≤i<k1/2) objects, the average expectation of classification times for each object is E2(i). If the second subgroup has j(1≤j<k1/2) objects, the expectation of classification times for each object is E2(j). Then the third subgroup has (k1-i-j) objects, and the average expectation of classification times for each object is E2(k1-i-j). So the average expectation of classification times for each object in the 2nd is shown as follows:(18)i×E2i+j×E2j+k1-i-j×E2k1-i-jk1.Similarly, it is easy to be prove that Scheme16 is also more efficient than Scheme 17. In other words, we only need to prove the following inequality: namely,(19)i×E2i+j×E2j+k1-i-j×E2k1-i-jk1-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx  (e-e-1<q<1), and according to Lemma 7, then we have(20)gi+gc-i2<gc2⟹t×qi+k1-t×qk1-t2<k12×qk1/2⟹i×qi+j×qj+k1-i-j×qk1-i-j2<k12×qk1/2⟹i×qi+j×qj+k1-i-j×qk1-i-j<k1×qk1/2⟹i×1k1+1-qk1×1+1i-qi+j×1k1+1-qk1×1+1j-qj+k1-i-j×1k1+1-qk1×1+1k1-i-j-qk1-i-j>k1×1k1+1-qk1×1+2k2-qk1/2⟹i×E2i+j×E2j+k1-i-j×E2k1-i-jk1-k1×E2k1/2k1>0.
The proof is completed.Therefore, if every group which containsk1 (is an even number and k1>1) objects needs to be subdivided into three subgroups in the first layer, Scheme 16 is more efficient than Scheme 17.The experimental results have verified the above conclusion in Table6. Let p=0.004 and k1=16. When every subgroup contains 8 objects in the 2nd layer, the average expectation of classification times reaches minimum value for each object. In Table 6, the first line stands for the objects number of first group in the 2nd layer and the first row stands for the objects number of second group, and data stands for the corresponding average expectation of classification times. For example, 1,1,7.7143 expresses that the objects number of three groups, respectively, is 1, 1, and 14, and the average classification time for each object is E2=0.077143 in the 2nd layer.Table 6
The changes of average expectation with different objects number of three groups.
Objects Objects 1 2 3 4 5 Expectation (×10−2) 1 7.7143 7.6786 7.6488 7.6250 7.6072 2 7.6786 7.6458 7.6189 7.5980 7.5831 3 7.6488 7.6189 7.5950 7.5770 7.5651 4 7.6250 7.5980 7.5770 7.5620 7.5530 5 7.6072 7.5831 7.5651 7.5530 7.5470 6 7.5953 7.5742 7.5591 7.5500 7.5470 7 7.5894 7.5712 7.5591 7.5530 7.5530 8 7.5894 7.5742 7.5651 7.5620 7.5651 9 7.5953 7.5831 7.5770 7.5770 7.5980(c) When an abnormal group containsk1 (even) objects and it needs to be further granulated into the 2nd layer, Scheme 16 still has the best efficient.There are two granulation schemes. Scheme18 is that the abnormal groups are randomly subdivided into s(s<k1) subgroups in the 1st layer, and Scheme 16 is that the abnormal groups are averagely subdivided into two subgroups in the 1st layer.Scheme 18.
Supposing an abnormal group will be subdivided intos(s<k1) subgroups. The first group has x1(1≤x1<k1/2) objects and the average expectation of classification times for each object is E2(x1); the 2nd subgroup has x2(1≤x2<k1/2) objects and the average expectation of classification times for each object is E2x2,…; ith subgroup has xi(1≤xi<k1/2) objects and the average expectation of classification times for each object is E2xi,…; sth subgroup has xs(1≤xs<k1/2) objects and the average expectation of classification times for each object is E2(xs). Hence, the average expectation of classification times for each object in the 2nd layer is shown as follows:(21)1k1×∑j=1sxj×E2xj.Similarly, in order to prove that Scheme16 is more efficient than Scheme 18, we only need to prove the following inequality: namely,(22)1k1×∑j=1sxj×E2xj-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx(e-e-1<q<1), and according to Lemma 7. Then, we have(23)∑i=1sgxi2<gc2⟹∑i=1sxi×qxi2<k12×qk1/2⟹∑j=1sxj×1k1+1-qk1×1+1xj-qxj>k1×1k1+1-qk1×1+2k2-qk1/2⟹1k1×∑j=1sxj×E2xj-k1×E2k1/2k1>0.
The proof is completed.Therefore, when every abnormal group which containsk1 (which is an even number and k1>1) in the 1st layer objects needs to be granulated into many subgroups, Scheme 16 is more efficient than other schemes.(d) In a similar way, when every abnormal group which containsk1 (k1 is an odd number and k1>1) objects in the 1st layer will be granulated into many subgroups, the best scheme is that every abnormal group is uniformly subdivided into two subgroups: namely, each subgroup contains (k1-1)/2 or (k1+1)/2 objects in the 2nd layer.Case 2 (granulating abnormal groups from the 1st layer to ith layer)Theorem 19.
Inith layer, if the objects number of each abnormal group is more than 4, then the total of classification times can be reduced by keeping on subdividing the abnormal groups into two subgroups which contain equal objects as far as possible. Namely, if each group contains ki objects in ith layer, then each subgroup may contain ki/2 or (k1-1)/2 or (k1+1)/2 objects in (i+1)th layer.Proof.
In the multigranulation method, the objects number of each subgroup in the next layer is determined by the objects number of group in the current layer. In other words, the objects number of each subgroup in the(i+1)th layer is determined by the known objects number of each group in ith layer.
According to recursive idea, the process of granulating abnormal group fromith layer into (i+1)th layer is similar to that 1st layer into 2nd layer. It is known that the best efficient way is as far as possible uniformly subdividing an abnormal group in current layer into two subgroups in next layer when granulating abnormal group from 1st layer into 2nd layer. Therefore, the best efficient way is also as far as possible uniformly subdividing each abnormal group in ith layer into two subgroups in (i+1)th layer. The proof is completed.Based onk1 which is the optimum objects number of each group in 1th layer, then the optimum granulation levels and their corresponding objects number of each group could be obtained by Theorem 19. That is to say, ki+1=ki/2 (or ki+1=(ki-1)/2 or ki+1=(ki+1)/2), where ki(ki>4) is the objects number of each abnormal group in ith (1≤i≤s-1) layer, and s is the optimum granulation levels. Namely, in this multilevels granulation method, the final structure of granulating abnormal group from the 1st layer to last layer is similar to a binary tree, and the origin space can be granulated to the structure which contains many binary trees.According to Theorem19, multigranulation strategy can be used to solve the blood analysis case. When facing the different prevalence rates, such as p1=0.01, p2=0.001, p3=0.0001, p4=0.00001, and p5=0.000001, the best searching strategy is that the objects number of each group in the different layers is shown in Table 7 (ki stands for the objects number of each groups in ith layer and Ei stands for the average expectation of classification times for each object).Table 7
The best testing strategy in different layers with the different prevalence rates.
p E i ( k 1 , k 2 , … , k i ) 0.01 0.157649743271 (11, 5, 2) 0.001 0.034610328332 (32, 16, 8, 4) 0.0001 0.010508158027 (101, 50, 25, 12, 6, 3) 0.00001 0.003301655870 (317, 158, 79, 39, 19, 9, 4) 0.000001 0.001041044160 (1001, 500, 250, 125, 62, 31, 15, 7, 3)Theorem 20.
In the above multilevels granulation method,ifpwhich is the prevalence rate of a sickness (or the negative sample ratio in domain) tends to 0, the average classification times for each object tend to be 1/k1; in other words, the following equation always holds:(24)limp→0Ei=1k1.Proof.
According to Definition12, let q=1-p,  q→1; we have(25)Ei=1k1+1-qk1×1k2+1-qk2×1k3+1-qk3×1k4+1-qk4×⋯×1ki-1+1-qki-1×1ki+1-qki⋯.According to Lemma 6, k1=1/(p+p2/2) or k1=1/(p+p2/2)+1. And then let (26)T=1k2+1-qk2×1k3+1-qk3×1k4+1-qk4×⋯×1ki-1+1-qki-1×1ki+1-qki⋯,so limq→1⁡Ti=0 and limq→1⁡Ei=1/k1. The proof is completed.LetE=(1/k1)/Ei. The changing trend between T and E with the variable q is shown in Figure 3.Figure 3
The changing trend aboutT and E with q.


### 3.5. Binary Classification of Multigranulation Searching Algorithm

In this paper, a kind of efficient binary classification of multigranulation searching algorithm is proposed through discussing the best testing strategy of the blood analysis case. The algorithm is illuminated as follows.Algorithm 21.
Binary classification of multigranulation searching algorithm (BCMSA).Input. A probability quotient space Q=(U,2U,p).Output. The average classification times expectation of each object E.Step 1. k1 will be obtained based on Lemma 6. i=1,  j=0 and searching_numbers=0 will be initialized.Step 2. Randomly dividing Uij into si subgroups Ui1,Ui2,…,Uisi. (si=Nij/ki, where Nij stands for the number of objects in Uij,  U10=U1).Step 3. For i to log2Nij. (log2Nij stands for log2Nij and will round down to the nearest integer which is less than it ).Forj to si.IfTest(Uij)>0 and Nij>4. Then searching_numbers+1,  Ui+1=Uij,  i+1, go to Step 2 (Test function is a searching method).IfTest(Uij)=0. Then searching_numbers+1,  i+1.IfNij≤4. Go to Step 4.Step 4. searching_numbers+∑Uij,  E=(searching_numbers+UN)/N.Step 5. Return E.The algorithm flowchart is shown in Figure4.Figure 4
Flowchart of BCMSA.Complexity Analysis of Algorithm21. In this algorithm, the best case is p where the prevalence rate tends to be 0, and the classification time is N∗Ei≈N/k1≈N∗(p+(p2/2)), which tends to 1, so the time complexity of computing is O(1). But the worst case is p which tends to be 0.3, and the classification times tend to N, so the time complexity of computing is O(N).


## 3.1. The Single-Level Granulation

Firstly, the domain (which containsN objects) is randomly subdivided into many subgroups, where each subset contains k1 objects. In other words, a new quotient space [Y1] is obtained based on an equivalence relation R. Then supposing that the average classification time of each object is a random variable Y1, so the probability distribution of Y1 is shown in Table 1.Table 1
The probability distribution ofY1.
Y 1 1 / k 1 1 / k 1 + 1 p Y 1 = y 1 q k 1 1 - q k 1Thus, the mathematical expectation ofY1 can be obtained as follows:(3)E1Y1=1k1×qk1+1+1k1×1-qk1=1k1+1-qk1.Then, the total mathematical expectation of the domain can be obtained as follows:(4)N×E1Y1=N×1k1×qk1+1+1k1×1-qk1.When the probability ofp keeps unchanged and k1 satisfies inequality E1(Y1)<1, this single-level granulation method can reduce classification times. For example, if p=0.5 and k1>1, and according to Lemma 5, E1(k1)>1 no matter what the value of k1. Then this single-level granulation method is worse than traditional method (namely, testing every object in turn). Conversely, if p=0.001 and k1=32, E1(Y1) will reach its minimum value, and the classification time of single-level granulation method is less than the traditional method. Let N=10000; the total of classification times is approximately equal to 628 as follows: (5)N×E1Y1=10000×132×q32+1+132×1-q32≈628.This shows that this method can greatly improve the efficiency of diagnosing and reduce 93.72% classification times in the single-level granulation method. If there is an extremely low prevalence rate, for example, p=0.000001, the total of classification times reaches its minimum value when each group contains 1001 objects (namely, k1=1001). If every group is subdivided into many smaller subgroups again and repeating the above method, can the total of classification times be further reduced?


## 3.2. The Double-Levels Granulation

After the objects of domain are granulated by the method of Section3.1, the original objects space becomes a new quotient space in which each group has k1 objects. According to the falsity and truth preserving principles in quotient space theory, if the group is tested to be abnormal, it can be granulated into many smaller subgroups. The double-levels granulation can be shown in Figure 2.Figure 2
Double-levels granulation.Then, the probability distribution of the double-levels granulation is discussed as follows.If each group containsk1 objects and tested once in the 1st layer, the average of classification times is 1/k1 for each object. Similarly, the average of classification times of each object is 1/k2 in the 2nd layer. When a subgroup contains k2 objects and is tested to be abnormal, every object has to be retested one by one once again in this subgroup, so the total of classification times of each object is equal to 1/k2+1.For simplicity, suppose that every group in the 1st layer will be subdivided into two subgroups which, respectively, containk21 and k21 objects in the 2nd layer.The classification time is shown in Table2 (✗ represents the testing result which is abnormal and ✓ represents normal).Table 2
The average classification times of each object with different results.
Times Objects k 1 k 21 k 22 Result 1 ✓ ✓ ✓ 3 + k 21 ✗ ✗ ✓ 3 + k 22 ✗ ✓ ✗ 3 + k 1 ✗ ✗ ✗For instance, letk1=8,  k21=4, and k22=4; there are four kinds of cases to happen.Case 1.
If a group is tested to be normal in the 1st layer, so the total of classification times of this group isk1×1/k1=1.Case 2.
If a group is tested to be abnormal in the 1st layer and its one subgroup is tested to be abnormal, and the other subgroup is also tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21+1)+k22×(1/k1+1/k22)=3+k21=7.Case 3.
If a group is tested to be abnormal in the 1st layer, its one subgroup is tested to be normal, and the other subgroup is tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21)+k22×(1/k1+1/k22+1)=3+k22=7.Case 4.
If a group is tested to be abnormal in the 1st layer, and its two subgroups are tested to be abnormal in the 2nd layer, so the total of classification times of this group isk21×(1/k1+1/k21+1)+k22×(1/k1+1/k22+1)=3+k1=11.Suppose each group containsk1 objects in the 1st layer, and their every subgroup has k2 objects in the 2nd layer. Supposing that the average classification times of each object is a random variable Y2, then the probability distribution of Y2 is shown in Table 3.Table 3
The probability distribution ofY2.
Y 2 1 / k 1 1 / k 1 + 1 / k 2 1 / k 1 + 1 / k 2 + 1 p Y 2 = y 2 q k 1 1 - q k 1 × q k 2 1 - q k 1 × 1 - q k 2Thus, in the 2nd layer, the mathematical expectation ofY2 which is the average classification times of each object is obtained as follows: (6)E2Y2=1k1×qk1+1k1+1k2×1-qk1×qk2+1+1k1+1k2×1-qk1×1-qk2=1k1+1-qk1×1k2+1-qk2.As long as the number of granulation levels increases to 2, the average classification times of each object will be further reduced: for instance, whenp=0.001 and N=10000. As we know, the minimum expectation of the total of classification times is about 628 with k1=32 in the single-level granulation. And according to (6) and Lemma 6, E2(Y2) will reach minimum value when k2=16. The minimum mathematical expectation of each object’s average classification times is shown as follows:(7)N×E2X=N×1k1×qk1+1k1+1k2×1-qk1×qk2+1+1k1+1k2×1-qk1×1-qk2≈338.The mathematical expectation of classification times can save 96.62% compared with traditional method and save 46.18% compared with single-level granulation method. Next we will discussi-levels granulation (i=3,4,5,…,n).


## 3.3. Thei-Levels Granulation

For blood analysis case, the granulation strategy inith layer is concluded by the known objects number of each group in previous layers (namely, k1,k2,…,ki-1 are known and just only ki is unknown). According to the double-levels granulation method, and supposing that the classification time of each object is a random variable Yi in the i-levels granulation, so the probability distribution of Yi is shown in Table 4.Table 4
The probability distribution ofYi.
Y i p Y i = y i 1 k 1 q k 1  1 k 1 + 1 k 2 1 - q k 1 × q k 2  ⋮ ⋮  ∑ j = 1 i 1 k j 1 - q k 1 × 1 - q k 2 × ⋯ × 1 - q k i - 1 × q k i  ∑ j = 1 i 1 k j + 1 1 - q k 1 × 1 - q k 2 × ⋯ × 1 - q k i - 1 × 1 - q k iObviously, the sum of probability distribution is equal to 1 in each layer.Proof.
Case 1 (the single-level granulation). One has(8)qk1+1-qk1=1.
Case 2 (the double-levels granulation). One has(9)qk1+1-qk1×qk2+1-qk1×1-qk2=qk1+1-qk1×qk2+1-qk2=qk1+1-qk1×1=1.
Case 3 (the i-levels granulation). One has(10)qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1×qki+1-qk1×1-qk2×⋯×1-qki=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1×qki+1-qki=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×1-qki-1=qk1+1-qk1×qk2+⋯+1-qk1×1-qk2×⋯×qki-1+1-qki-1=⋯=qk1+1-qk1×1=1.
The proof is completed.Definition 12 (classification times expectation of granulation).
In a probability quotient space, a multilevels granulation model will be established from domainU={x1,x2,…,xn} which is a nonempty finite set, the health rate is q, the max granular levels is L, and the number of objects in ith layer is ki,  i=1,2,…,L. So the average classification time of each objects is Ei(Yi) in ith layer.(11)EiYi=1k1+∑i=2L1ki×∏j=1i-11-qkj+∏i=1L1-qki.In this paper, we mainly focus on establishing a minimum granulation expectation model of classification times by multigranulation computing method. For simplicity, the mathematical expectation of classification times will be regarded as the measure of contrasting with the searching efficiency. According to Lemma5, the multilevels granulation model can simplify the complex problem only if the prevalence rate p∈0,1-e-e-1 in the blood analysis case.Theorem 13.
Let the prevalence ratep∈(0,0.3); if a group is tested to be abnormal in the 1st layer (namely, this group contains abnormal objects), the average classification times of each object will be further reduced by subdividing this group once again.Proof.
The expectation difference between the single-level granulationE1(Y1) and the double-levels granulation E2(Y2) can adequately embody their efficiency. Under the conditions of e-e-1<q<1 and 1≤k2<k1, and according to (3) and (6), the expectation difference E1(Y1)-E2(Y2) is shown as follows:(12)E1Y1-E2Y2=1k1+1-qk1-1k1+1-qk1×1k2+1-qk2=1-qk1×1-1k2+1-qk2>0.According to Lemma 5, 1-qk1>0 and fqk2=1/k2+1-qk2<1 always hold; then we can get 1-(1/k2+1-qk2)>0. So the inequality E1(X)-E2(X)>0 is proved successfully.Theorem13 illustrates that it can reduce classification times by continuing to granulate the abnormal groups into the 2nd layer when k1>1. There is attempt to prove that the total of classification times will be further reduced by continuously granulating the abnormal groups into ith layers until a group’s number is no less than 1.Theorem 14.
Supposing the prevalence ratep∈(0,0.3), if a group is tested to be abnormal (namely, this group contains abnormal objects), the average classification times of each object will be reduced by continuously subdividing the abnormal group until the objects number of its subgroup is no less than 1.Proof.
The expectation difference between(i-1)-levels granulation Ei-1(Yi-1) and i-levels granulation Ei(Yi) reflects their efficiency. On the condition of e-e-1<q<1 and 1≤ki<ki-1, and according to (11), the expectation difference Ei-1(Yi-1)-Ei(Yi) is shown as follows:(13)Ei-1Yi-1-EiYi=1k1+∑l=2i-11kl×∏j=1l-11-qkj+∏l=1i-11-qkl-1k1+∑l=2i1ki×∏j=1l-11-qkj+∏l=1L1-qkl=1-qk1×⋯×1-qki-1×1-1ki+1-qki>0.Because 1-qk1×⋯×1-qki-1>0 is known, according to Lemma 5 and ki≥1, we can get (1/ki+1-qki)<1: namely 1-(1/ki+1-qki)>0. So Ei-1-Ei>0 is proved successfully.Theorem14 shows that this method will continuously improve the searching efficiency in the process of granulating abnormal groups from 1st layer to ith layer because Ei-1(Yi-1)-Ei(Yi)>0 always holds. However, it is found that the classification times cannot be reduced when the objects number of an abnormal group is less than or equal to 4, so the objects of this abnormal group should be tested one by one. In order to achieve the best efficiency, then we will explore how to determine the optimum granulation, namely, how to determine the optimum objects number of each group and how to obtain the optimum granulation levels.


## 3.4. The Optimum Granulation

It is a difficult and key point to explore an appropriate granularity space for dealing with a complex problem. And it not only requires us to keep the integrity of the original information but also simplify the complex problem. So we take the blood analysis case as an example to explain how to obtain the optimum granularity space in this paper. Suppose the conditione-e-1<q<1 always holds.Case 1 (granulating abnormal groups from the 1st layer to the 2nd layer). (a) If k1 is an even number, every group which contains k1 objects in 1st layer will be subdivided into two subgroups into 2nd layer.Scheme 15.
Supposing the one subgroup of the 2nd layer hasi  (1≤i<k1/2) objects, according to formula (6), the expectation of classification times for each object is E2(i). And the other subgroup has (k1-i) objects, so the expectation of classification times for each object is E2(k1-i). The average expectation of classification times for each object in the 2nd layer is shown as follows:(14)i×E2i+k1-i×E2k1-ik1.Scheme 16.
Suppose every abnormal group in 1st layer is average subdivided into two subgroups: namely, each subgroup hask1/2 objects in the 2nd layer. According to formula (6), the average expectation of classification times for each object in the 2nd layer is shown as follows:(15)2×k1/2×E2k1/2k1=k1×E2k1/2k1.The expectation difference between the above two schemes embodies their efficiency. In order to prove that Scheme16 is more efficient than Scheme 15, we only need to prove that the following inequality is correct: namely,(16)i×E2i+k1-i×E2k11-ik1-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx(e-e-1<q<1), and according to Lemma 7, then, we have(17)gi+gc-i2<gc2⟹i×qi+k1-i×qk1-i2<k12×qk1/2⟹i×qi+k1-i×qk1-i<k1×qk1/2⟹i×1k1+1-qk1×1+1i-qi+k1-i×1k1+1-qk1×1+1k1-i-qk1-i>k11k1+1-qk1×1+2k2-qk1/2⟹i×E2i+k1-i×E2k11-ik1-k1×E2k1/2k1>0.
The proof is completed.Therefore, if every group hask1 (k1 is an even number and k1>1) objects in the 1st layer that need to be subdivided into two subgroup, Scheme 16 is more efficient than Scheme 15.The experiment results have verified the above conclusion in Table5. Let p=0.004 and k1=16. When every subgroup contains 8 objects in the 2nd layer, the expectation of classification times obtains minimum value for each object, where k21 is the number of the one subgroup in the 2nd layer, k22 is the number of the other subgroup, and E2 is the corresponding expectation of classification times for each object.Table 5
The changes of average expectation with different objects number in two groups.
( k 21 , k 22 ) ( 1,15 ) ( 2,14 ) ( 3,13 ) ( 4,12 ) ( 5,11 ) ( 6,10 ) ( 7,9 ) ( 8,8 )  E 2 0.07367 0.07329 0.07297 0.07270 0.07249 0.07234 0.07225 0.07222(b) Ifk1 is an even number, every group which contains k1 objects in 1st layer will be subdivided into three subgroups into 2nd layer.Scheme 17.
In the 2nd layer, if the first subgroup hasi  (1≤i<k1/2) objects, the average expectation of classification times for each object is E2(i). If the second subgroup has j(1≤j<k1/2) objects, the expectation of classification times for each object is E2(j). Then the third subgroup has (k1-i-j) objects, and the average expectation of classification times for each object is E2(k1-i-j). So the average expectation of classification times for each object in the 2nd is shown as follows:(18)i×E2i+j×E2j+k1-i-j×E2k1-i-jk1.Similarly, it is easy to be prove that Scheme16 is also more efficient than Scheme 17. In other words, we only need to prove the following inequality: namely,(19)i×E2i+j×E2j+k1-i-j×E2k1-i-jk1-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx  (e-e-1<q<1), and according to Lemma 7, then we have(20)gi+gc-i2<gc2⟹t×qi+k1-t×qk1-t2<k12×qk1/2⟹i×qi+j×qj+k1-i-j×qk1-i-j2<k12×qk1/2⟹i×qi+j×qj+k1-i-j×qk1-i-j<k1×qk1/2⟹i×1k1+1-qk1×1+1i-qi+j×1k1+1-qk1×1+1j-qj+k1-i-j×1k1+1-qk1×1+1k1-i-j-qk1-i-j>k1×1k1+1-qk1×1+2k2-qk1/2⟹i×E2i+j×E2j+k1-i-j×E2k1-i-jk1-k1×E2k1/2k1>0.
The proof is completed.Therefore, if every group which containsk1 (is an even number and k1>1) objects needs to be subdivided into three subgroups in the first layer, Scheme 16 is more efficient than Scheme 17.The experimental results have verified the above conclusion in Table6. Let p=0.004 and k1=16. When every subgroup contains 8 objects in the 2nd layer, the average expectation of classification times reaches minimum value for each object. In Table 6, the first line stands for the objects number of first group in the 2nd layer and the first row stands for the objects number of second group, and data stands for the corresponding average expectation of classification times. For example, 1,1,7.7143 expresses that the objects number of three groups, respectively, is 1, 1, and 14, and the average classification time for each object is E2=0.077143 in the 2nd layer.Table 6
The changes of average expectation with different objects number of three groups.
Objects Objects 1 2 3 4 5 Expectation (×10−2) 1 7.7143 7.6786 7.6488 7.6250 7.6072 2 7.6786 7.6458 7.6189 7.5980 7.5831 3 7.6488 7.6189 7.5950 7.5770 7.5651 4 7.6250 7.5980 7.5770 7.5620 7.5530 5 7.6072 7.5831 7.5651 7.5530 7.5470 6 7.5953 7.5742 7.5591 7.5500 7.5470 7 7.5894 7.5712 7.5591 7.5530 7.5530 8 7.5894 7.5742 7.5651 7.5620 7.5651 9 7.5953 7.5831 7.5770 7.5770 7.5980(c) When an abnormal group containsk1 (even) objects and it needs to be further granulated into the 2nd layer, Scheme 16 still has the best efficient.There are two granulation schemes. Scheme18 is that the abnormal groups are randomly subdivided into s(s<k1) subgroups in the 1st layer, and Scheme 16 is that the abnormal groups are averagely subdivided into two subgroups in the 1st layer.Scheme 18.
Supposing an abnormal group will be subdivided intos(s<k1) subgroups. The first group has x1(1≤x1<k1/2) objects and the average expectation of classification times for each object is E2(x1); the 2nd subgroup has x2(1≤x2<k1/2) objects and the average expectation of classification times for each object is E2x2,…; ith subgroup has xi(1≤xi<k1/2) objects and the average expectation of classification times for each object is E2xi,…; sth subgroup has xs(1≤xs<k1/2) objects and the average expectation of classification times for each object is E2(xs). Hence, the average expectation of classification times for each object in the 2nd layer is shown as follows:(21)1k1×∑j=1sxj×E2xj.Similarly, in order to prove that Scheme16 is more efficient than Scheme 18, we only need to prove the following inequality: namely,(22)1k1×∑j=1sxj×E2xj-k1×E2k1/2k1>0,e-e-1<q<1,k1>1.Proof.
Letg(x)=xqx(e-e-1<q<1), and according to Lemma 7. Then, we have(23)∑i=1sgxi2<gc2⟹∑i=1sxi×qxi2<k12×qk1/2⟹∑j=1sxj×1k1+1-qk1×1+1xj-qxj>k1×1k1+1-qk1×1+2k2-qk1/2⟹1k1×∑j=1sxj×E2xj-k1×E2k1/2k1>0.
The proof is completed.Therefore, when every abnormal group which containsk1 (which is an even number and k1>1) in the 1st layer objects needs to be granulated into many subgroups, Scheme 16 is more efficient than other schemes.(d) In a similar way, when every abnormal group which containsk1 (k1 is an odd number and k1>1) objects in the 1st layer will be granulated into many subgroups, the best scheme is that every abnormal group is uniformly subdivided into two subgroups: namely, each subgroup contains (k1-1)/2 or (k1+1)/2 objects in the 2nd layer.Case 2 (granulating abnormal groups from the 1st layer to ith layer)Theorem 19.
Inith layer, if the objects number of each abnormal group is more than 4, then the total of classification times can be reduced by keeping on subdividing the abnormal groups into two subgroups which contain equal objects as far as possible. Namely, if each group contains ki objects in ith layer, then each subgroup may contain ki/2 or (k1-1)/2 or (k1+1)/2 objects in (i+1)th layer.Proof.
In the multigranulation method, the objects number of each subgroup in the next layer is determined by the objects number of group in the current layer. In other words, the objects number of each subgroup in the(i+1)th layer is determined by the known objects number of each group in ith layer.
According to recursive idea, the process of granulating abnormal group fromith layer into (i+1)th layer is similar to that 1st layer into 2nd layer. It is known that the best efficient way is as far as possible uniformly subdividing an abnormal group in current layer into two subgroups in next layer when granulating abnormal group from 1st layer into 2nd layer. Therefore, the best efficient way is also as far as possible uniformly subdividing each abnormal group in ith layer into two subgroups in (i+1)th layer. The proof is completed.Based onk1 which is the optimum objects number of each group in 1th layer, then the optimum granulation levels and their corresponding objects number of each group could be obtained by Theorem 19. That is to say, ki+1=ki/2 (or ki+1=(ki-1)/2 or ki+1=(ki+1)/2), where ki(ki>4) is the objects number of each abnormal group in ith (1≤i≤s-1) layer, and s is the optimum granulation levels. Namely, in this multilevels granulation method, the final structure of granulating abnormal group from the 1st layer to last layer is similar to a binary tree, and the origin space can be granulated to the structure which contains many binary trees.According to Theorem19, multigranulation strategy can be used to solve the blood analysis case. When facing the different prevalence rates, such as p1=0.01, p2=0.001, p3=0.0001, p4=0.00001, and p5=0.000001, the best searching strategy is that the objects number of each group in the different layers is shown in Table 7 (ki stands for the objects number of each groups in ith layer and Ei stands for the average expectation of classification times for each object).Table 7
The best testing strategy in different layers with the different prevalence rates.
p E i ( k 1 , k 2 , … , k i ) 0.01 0.157649743271 (11, 5, 2) 0.001 0.034610328332 (32, 16, 8, 4) 0.0001 0.010508158027 (101, 50, 25, 12, 6, 3) 0.00001 0.003301655870 (317, 158, 79, 39, 19, 9, 4) 0.000001 0.001041044160 (1001, 500, 250, 125, 62, 31, 15, 7, 3)Theorem 20.
In the above multilevels granulation method,ifpwhich is the prevalence rate of a sickness (or the negative sample ratio in domain) tends to 0, the average classification times for each object tend to be 1/k1; in other words, the following equation always holds:(24)limp→0Ei=1k1.Proof.
According to Definition12, let q=1-p,  q→1; we have(25)Ei=1k1+1-qk1×1k2+1-qk2×1k3+1-qk3×1k4+1-qk4×⋯×1ki-1+1-qki-1×1ki+1-qki⋯.According to Lemma 6, k1=1/(p+p2/2) or k1=1/(p+p2/2)+1. And then let (26)T=1k2+1-qk2×1k3+1-qk3×1k4+1-qk4×⋯×1ki-1+1-qki-1×1ki+1-qki⋯,so limq→1⁡Ti=0 and limq→1⁡Ei=1/k1. The proof is completed.LetE=(1/k1)/Ei. The changing trend between T and E with the variable q is shown in Figure 3.Figure 3
The changing trend aboutT and E with q.


## 3.5. Binary Classification of Multigranulation Searching Algorithm

In this paper, a kind of efficient binary classification of multigranulation searching algorithm is proposed through discussing the best testing strategy of the blood analysis case. The algorithm is illuminated as follows.Algorithm 21.
Binary classification of multigranulation searching algorithm (BCMSA).Input. A probability quotient space Q=(U,2U,p).Output. The average classification times expectation of each object E.Step 1. k1 will be obtained based on Lemma 6. i=1,  j=0 and searching_numbers=0 will be initialized.Step 2. Randomly dividing Uij into si subgroups Ui1,Ui2,…,Uisi. (si=Nij/ki, where Nij stands for the number of objects in Uij,  U10=U1).Step 3. For i to log2Nij. (log2Nij stands for log2Nij and will round down to the nearest integer which is less than it ).Forj to si.IfTest(Uij)>0 and Nij>4. Then searching_numbers+1,  Ui+1=Uij,  i+1, go to Step 2 (Test function is a searching method).IfTest(Uij)=0. Then searching_numbers+1,  i+1.IfNij≤4. Go to Step 4.Step 4. searching_numbers+∑Uij,  E=(searching_numbers+UN)/N.Step 5. Return E.The algorithm flowchart is shown in Figure4.Figure 4
Flowchart of BCMSA.Complexity Analysis of Algorithm21. In this algorithm, the best case is p where the prevalence rate tends to be 0, and the classification time is N∗Ei≈N/k1≈N∗(p+(p2/2)), which tends to 1, so the time complexity of computing is O(1). But the worst case is p which tends to be 0.3, and the classification times tend to N, so the time complexity of computing is O(N).


## 4. Comparative Analysis on Experimental Results

In order to verify the efficiency of the proposed BCMSA, in this paper, suppose there are two large domainsN1=1×104,  N2=100×104 and five kinds of different prevalence rates which are p1=0.01,  p2=0.001,  p3=0.0001,  p4=0.00001, and p5=0.000001. In the experiment of blood analysis case, the number “0” stands for a sick sample (negative sample) and “1” stands for a healthy sample (positive sample), then randomly generating N numbers, in which the probability of generating “0” denoted as p and the probability of generating “1” denoted as 1-p stand for all the domain objects. The binary classifier is that, summing all numbers in a group (subgroup), if the sum is more than 1, it means this group is tested to be abnormal, and if the sum equals 0, it means this group has been tested to be normal.Experimental environment is 4 G RAM, 2.5 GHz CPU, and WIN 8 system, the program language is Python, and the experimental results are shown in Table8.Table 8
Comparative result of efficiency among 3 kinds of methods.
p Levels E ( X ) k 1 l N 1 N 2 Method9 Method10 0.01 Single-level 0.19557083665 11 46.48% 1944 195817 81.44% — 2 levels 0.15764974327 57.67% 1627 164235 83.58% 16.13%  0.001 Single-level 0.06275892424 32 49.79% 633 62674 94.72% — 4 levels 0.03461032833 90.29% 413 41184 96.82% 34.62%  0.0001 Single-level 0.01995065634 101 49.62% 201 19799 98.00% — 6 levels 0.01050815802 94.22% 113 11212 98.89% 47.33%  0.00001 Single-level 0.00631957079 318 49.76% 633 6325 99.37% — 7 levels 0.00330165587 95.26% 333 3324 99.67% 47.75%  0.000001 Single-level 0.00199950067 1001 49.96% 15 2001 99.80% — 9 levels 0.00104104416 95.96% 15 1022 99.89% 47.94%In Table8, item “p” stands for the prevalence rate, item “levels” stands for the granulation levels of different methods, and item “E(X)” stands for the average expectation of classification times for each object. Item “k1” stands for the objects number of each group in the 1st layer. Item “l” stands for the degree of E(X) close to 1/k1. N1=1×104 and N2=1×106, respectively, stand for the objects number of two original domains. Items “Method 9” and “Method 10,” respectively, stand for the improved efficiency where Method 11 compares with Method 9 and Method 10.Form Table8, diagnosing all objects needs to expend 10000 classification times by Method 9 (traditional method), 201 classification times in Method 10 (single-level grouping method), and only 113 classification times in Method 11 (multilevels grouping method) for confirming the testing results of all objects when N1=1×104 and p=0.0001. Obviously, the proposed algorithm is more efficient than Method 9 and Method 10, and the classification times can, respectively, be reduced to 98.89% and 47.33%. At the same time, when the probability p is gradually reduced, BCMSA has gradually become more efficient than Method 10, and l tends to 100%; that is to say, the average classification time for each object tends to 1/k1 in the BCMSA. In addition, the BCMSA can save 0%~50% of the classification times compared with Method 10. The efficiency of Method 10 (single-level granulation method) and Method 11 (multilevels granulation method) is shown in Figure 5; the x-axis stands for prevalence rate (or the negative sample rate) and the y-axis stands for the average expectation of classification times for each object.Figure 5
Comparative analysis between 2 kinds of methods.In this paper, BCMSA is proposed, and it can greatly improve searching efficiency when dealing with complex searching problems. If there is a binary classifier, which is not only valid to an object, but also valid to a group with many objects, the efficiency of searching all objects will be enhanced by BCMSA, such as blood analysis case. As the same time, it may play an important role for promoting the development of granular computing. Of course, this algorithm also has some limitations. For example, if the prevalence rate of a sickness (or the occurrence rate of eventA) p>0.3, it will have no advantage compared with traditional method. In other words, the original problem need not be subdivided into many subproblems when p>0.3. And when the prevalence rate of a sickness (or the negative sample rate in domain) is unknown, this algorithm needs to be further improved so that it can adapt to the new environment.


## 5. Conclusions

With the development of intelligence computation, multigranulation computing has gradually become an important tool to process the complex problems. Specially, in the process of knowledge cognition, granulating a huge problem into lots of small subproblems means to simplify the original complex problem and deal with these subproblems in different granularity spaces [64]. This hierarchical computing model is very effective for getting a complete solution or approximate solution of the original problem due to its idea of divide and conquer. Recently, many scholars pay their attention to efficient searching algorithms based on granular computing theory. For example, a kind of algorithm for dealing with complex network on the basis of quotient space model is proposed by L. Zhang and B. Zhang [65]. In this paper, combining hierarchical multigranulation computing model and principle of probability statistics, a new efficient binary classifier of multigranulation searching algorithm is established on the basis of mathematical expectation of probability statistics, and this searching algorithm is proposed according to recursive method in multigranulation spaces. Many experimental results have shown that the proposed method is effective and can save lots of classification times. These results may promote the development of intelligent computation and speed up the application of multigranulation computing. However, this method also causes some shortcomings. For example, on the one hand, this method has strict limitation for the probability value of p: namely, p<0.3. On the contrary, if p>0.3, the proposed searching algorithm probably is not the most effective method, and the improved methods need to be found. On the other hand, it needs a binary classifier, which is not only valid to an object, but also valid to a group with many objects. In the end, with the decrease of probability value of p (even it infinitely closes to zero), for every object, its mathematical expectation of searching time will gradually close to 1/k1. In our future research, we will focus on the issue on how to granulate the huge granule space without any probability value of each object and try our best to establish a kind of effective searching algorithm under which we do not know the probability of negative samples in domain. We hope these researches can promote the development of artificial intelligence.



---

*Source: 9329812-2016-11-15.xml*