ICACT20220156 Slide.39
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Thank you
|
|
ICACT20220156 Slide.38
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Our proposed method avoids the computation of dominance relation for each object which consequently reduce the time require to update approximations. Extensive experiments are conducted on UCI datasets. As results already discussed, our proposed algorithm proves efficient with an average reduction of 98% without compromising accuracy. The computational complexity also reduced to quadratic as compared to cubic complexity of the traditional method. In future, we want to explore the variation in the value set of attributes (conditional and decision attribute) along with object set variations.
|
|
ICACT20220156 Slide.37
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Similarly, we computed Big-O for proposed algorithm and for worst case scenario, complexity reduced to quadratic (O(U2)) as compared to the cubic (O(U3)) complexity of conventional algorithm of dominance based rough set theory.
|
|
ICACT20220156 Slide.36
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
We compared proposed approach with conventional method in terms of complexity. We measure the complexity of an algorithm using Big-O notation. Big-O classifies an algorithm based on the execution time, inputs and number of steps required to get the output. We analyse the calculations required for each approximation of the conventional algorithm to find its complexity. Big-O in the case of conventional algorithm is (O(U3)).
|
|
ICACT20220156 Slide.35
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Graphs show that our proposed approach performs considerable faster for all four datasets as compared to incremental method.
|
|
ICACT20220156 Slide.34
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
We also compare our proposed approach with another incremental method proposed for dynamic datasets. We implemented both approaches on four UCI datasets with more instances and computed the percentage reduction in execution time. Results showed that our proposed algorithm performed faster in terms of execution time, both for insertion and deletion of objects with time.
|
|
ICACT20220156 Slide.33
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Graphical description of comparison of execution time is given here. Considerable reduction in terms of computation time has been achieved for both insertion and deletion of objects from the system.
|
|
ICACT20220156 Slide.32
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Similarly, we compared execution time of conventional algorithm and proposed algorithm, upon deletion of 5% objects from each dataset and achieved average reduction of 97% as shown in Table.
|
|
ICACT20220156 Slide.31
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To make comparison, we implemented proposed approach for updating approximation upon insertion of new objects and conventional method on ten UCI datasets with variation ratio of 5% of each dataset size. We compared the computational time of both algorithms by calculating the percentage decrease in execution time. As it can be observed from the table, our proposed approach update approximation sets in reduce time as compared to conventional method, with an average reduction of 98%.
|
|
ICACT20220156 Slide.30
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To evaluate the performance of our proposed approach, we have compared proposed approach with the traditional approach of dominance based rough set theory and another recently proposed incremental method for dynamic datasets, in terms of computation time and complexity. The brief description of ten UCI datasets is given here. We have selected those datasets which can be used for multi-criteria classification problems. These datasets have numerical values for conditional attributes and decision class.
|
|
ICACT20220156 Slide.29
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Then we update approximations using pre-defined four rules upon deletion of object ′𝒙𝟑’ from the system. As decision class of 𝑥3 is ‘t=2’ ,we check 𝑥3 belongs to lower approximation for downward union of classes of class ‘2’ and delete it from approximation set. We delete 𝑥3 from upper approximation for downward union of classes of class ‘2’ and upper approximation from upward union of classes of class ‘2’, as per rule 2 & 4 ( for 𝒕≥𝟐 ), without any computation. Simultaneously, we check whether 𝑥3 belongs to upper approximation for downward union of classes of class ‘3’then delete 𝑥3 from this approximation set. Compare 𝑥3with objects of less preferred class than class ‘2’,𝑥3 appears more preferred than all objects, delete it from lower approximation for upward union of classes of class ‘2’.When we Compare 𝑥3 with objects of more preferred class than class ‘2’,𝑥3 appears less preferred than all objects, so no action performs here. Similarly repeat step 1 and step 2 to update approximation sets for object 𝒙𝟕.
|
|
ICACT20220156 Slide.28
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To understand the working of algorithm proposed for updating approximation sets when one or more old objects leave the system , we consider a same sample information system used in previous example. We assume that two objects leave the system , {𝒙𝟑,𝒙𝟕}. In the first step, we update decision classes and other relevant higher/lower preference ordered classes upon deletion of an object ‘𝒙𝟑’ from the system.
|
|
ICACT20220156 Slide.27
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In the second step, algorithm updates approximations using defined pseudocode in the previous slides.As per defined rule 1, decision class of 𝑥_11 is lowest class in preference, so it becomes part of upper approximation for downward union of classes for class ‘1’.Simultaneously our proposed algorithm updates upper approximation for downward union of classes of class ‘2’,an object 𝑥_11 also selects for it without any computation. Now we compare an object 𝑥_11, with objects of more preferred class than class ‘1’.Here 𝑥_11 is more preferred than object 𝑥_6and new object 𝑥_14 , therefore, 𝑥_11 does not select for lower approximation for downward union of classes of class ‘1’ but as defined in pseudocode, 𝑥_11 selects for lower approximation for downward union of classes of class ‘2’. In the same step,𝑥_11 also becomes part of upper approximation for upward union of classes of class ‘2’. As mentioned earlier, objects of more preferred class than ‘1’,〖 𝑥〗_6and 𝑥_14 are less preferred than object 𝑥_11, so these objects become part of upper approximation for downward union of classes of class ‘1’, if already does not exist. So only 𝑥_14 selects for updated set.In proposed rule for upper approximation for downward union of classes of class ‘t’, all objects of less preferred class than ‘t’ become part of it. As new object 𝑥_11 belongs to class ‘t=1’, a less preferred class than class ‘t=2’, therefore, we select it for upper approximation for downward union of classes of class ‘2’, without performing any calculation. Similarly update approximations for remaining three objects.
|
|
ICACT20220156 Slide.26
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
We start with an assumption that four new objects enter the information system at time t+1. Detail of their conditional and decision attribute is given in table (we arbitrarily assign values to criteria with an assumption that value set for criteria remains same). In the first step, we update decision classes and all respective higher/lower preference ordered classes for all new objects.
|
|
ICACT20220156 Slide.25
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To understand the working of proposed approach, here we consider a sample decision table with ten objects, q1,q2 and q3 are conditional attributes and d is decision attribute. We also have the previous information about the decision classes and approximation sets.
|
|
ICACT20220156 Slide.24
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Pseudocode to update approximations using pre-defined four rules, is given here. We assume that we have previous information about the decision classes and approximation sets. We have already updated decision classes in step 1. When we compare single object, our proposed algorithm deletes it from all relevant approximations sets simultaneously. We start from the first object which leaves the information system. We check all four proposed rules and delete object from all relevant lower and upper approximation sets. Similarly, we check all objects which leave the system, one by one and update approximations.
|
|
ICACT20220156 Slide.23
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In rule 3, we proposed to compare new object ‘x’ with objects of less preferred classes than class t and if ‘x’ is more preferred than delete ‘x’ from lower approximation for upward union of classes of class ‘t’ (if t ≥ 2). To compute upper approximation for upward union of classes of class ‘t’, it has been proposed in rule 4, if t ≥ 2, delete ‘x’ from upper approximation for upward union of classes. Then compare object ‘x’ with object ‘y’ of less preferred class than ‘t’ and if ‘x’ is less preferred than ‘y’, delete ‘y’ from upper approximation for upward union of classes of class ‘t’, simultaneously delete ‘y’ from lower approximation for downward union of classes of class ‘t’ and from upper approximation for downward union of classes of more preferred class than ‘t’ (if t ≥ 2). Delete ‘x’ from upper approximation for upward union of classes of more preferred class than ‘t’,if 𝒕<𝟐.
|
|
ICACT20220156 Slide.22
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In the second step, our proposed method update approximation sets using four heuristic rules. In rule 1, it has been given that to update lower approximation for downward union of classes of class ‘t’, check if object ‘x’ exists in it, delete it from this approximation set and simultaneously delete ‘x’ from lower approximation for downward union of classes of more preferred class than class ‘t’. To update upper approximation for downward union of classes of class ‘t’, delete object ‘x’ from upper approximation for downward union of classes of class ‘t’, without any computation. Simultaneously, delete ‘x’ from upper approximation for downward union of classes of more preferred class than class ‘t’ if t ≤ 2. We compare object ‘x’ with object ‘y’ of more preferred class than ‘t’, if ‘x’ is more preferred than object ‘y’, delete ‘y’ from upper approximation for downward union of classes of class ‘t’.
|
|
ICACT20220156 Slide.21
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Now we discuss the methodology to update approximations of DRSA when one or more objects leave the system at time t+1. First, we update decision classes to exclude object one at a time. Pseudocode is given here. As an input, we have old dataset, previous information of decision classes, set of objects delete from the system, total number of decision classes (with an assumption that any change in object set does not affect the decision classes). This step generates updated decision classes and respective higher and lower preference ordered classes upon deletion of single object from the system.
|
|
ICACT20220156 Slide.20
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Here is the pseudocode to update approximations using rules, defined earlier. As an input we have old approximation sets, new object set and updated dataset. We start with the first object of new object set, if class of new object is lowest class (𝒕<𝟐), object selects for upper approximation for downward union of classes of class ‘t’ without computation. Simultaneously, object selects for upper approximation for downward union of classes of more preferred class than class ‘t’ (t+1). Then we compare new object with objects of more preferred class than ‘t’ for all its conditional attributes, if new object is more preferred, select new object for upper approximation for downward union of classes of class ‘t’ and simultaneously for lower approximation for downward union of classes of class ‘t’ and upper approximation for upward union of classes of class ‘t’. If new object is less preferred, then object selects for lower approximation for downward union of classes of class ‘t’. If new object does not belong to lowest class, then algorithm update approximations using defined rules for ‘𝒕≥𝟐’ and avoid redundant computations.
|
|
ICACT20220156 Slide.19
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To update lower approximation for upward union of classes of class ‘t’, we check each new object whether it belongs to upper approximation for downward union of classes of less preferred class than ‘t’ or not, if not, object selects for lower approximation for upward union of classes of class ‘t’. To update upper approximation for upward union of classes of class ‘t’, all new object of class ‘t’ or less preferred class than ‘t’ becomes part of this approximation set. In case ‘t’ is not lowest class, if new object ‘x’ belongs to less preferred class than ‘t’, we compare ‘x’ with object ‘y’ of class ‘t’. If ‘x’ is more preferred than ‘y’, ‘x’ selects for under discussion approximation set.
|
|
ICACT20220156 Slide.18
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In this algorithm, we update approximations without computing dominance relation and checking subset and intersect properties. We proposed rules, based on the conventional definition and properties of approximations. To update lower approximation for downward union of classes of class ‘t’, we check if new object belongs to updated decision class ‘t’ and is less preferred than all objects of more preferred decision classes than class ‘t’. If ‘t’ is not lowest class, we check if new object belongs to lower preference ordered class than class ‘t’ and we check whether new object is more preferred than objects of updated decision class ‘t’. If ‘t’ is not lowest class, all objects of lower approximation for downward union of classes of lower preference ordered class than ‘t’, select for lower approximation for downward union of classes of class ‘t’ without any computation. To update upper approximation for downward union of classes of class ‘t’, all new objects of class ‘t’ and lower preference ordered class than ‘t’, selects for it without any comparison. We compare new object ‘x’ of decision class ‘t’ with object ‘y’ of more preferred classes than ‘t’. If object ‘y’ is less preferred than new object ‘x’, object ‘y’ selects for under discussion approximation set.
|
|
ICACT20220156 Slide.17
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Research aims to improve the efficiency of the algorithm by not compromising the accuracy. Now we discuss the methodology to update approximations of DRSA when new objects enter the system at time t+1. In first step, we update decision classes to include new objects. Pseudocode is given here. As an input, we have old dataset, previous information of decision classes, set of new objects, total number of decision classes (with an assumption that any change in object set does not affect the decision classes). This step generates updated decision classes and respective higher and lower preference ordered classes.
|
|
ICACT20220156 Slide.16
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In this paper, we have presented a novel approach to efficiently update approximations of dominance based rough set theory when data evolve at time t+1, new objects enter the system and old objects leave the system. Two algorithms have been proposed, update approximations when new objects enter the system at time t+1 and update approximations when old objects leave the system at time t+1. To evaluate the performance of proposed approach, experiments performed on UCI publicly available datasets with variation ratio of 5% of original dataset size.
|
|
ICACT20220156 Slide.15
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
It is computational expensive to compute approximations using conventional dominance based rough set theory in terms of time and complexity. In case of real time applications where data changes over time, approximations need to be updated periodically. If we use traditional DRSA algorithm, it poses significant performance bottleneck for large size datasets.
|
|
ICACT20220156 Slide.14
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
As we discussed earlier, to compute approximations using conventional algorithm of dominance based rough set theory, high computational cost incurred in terms of time and complexity. To compute approximations, it is required to perform three computationally expensive steps. In first step, it requires to compute upward and downward union of classes for each decision class. Then to compute dominance relation, each object repeatedly compared with whole dataset for all its conditional attributes. In the third step, to compute approximation, once again comparison need to be made to check subset and intersect properties. This whole process impose heavy computational cost and affect the performance of algorithm using dominance based rough set theory.
|
|
ICACT20220156 Slide.13
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Here we present the brief introduction of different approaches used to handle dynamic datasets for updating approximations of dominance based rough set theory. Dynamic dominance based rough set approaches occurs less computational cost, but with complex algorithm architecture. Incremental approach to update approximations is less computationally cost but suitable for small datasets only. However, most of these approaches result in complex algorithm architectures and repeat various computations against addition or deletion of each object.
|
|
ICACT20220156 Slide.12
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In this paper, authors have used dominance based rough set theory, to predict the number of students likely to drop out from the Massive Open Online Course (MOOCS) course next week using the historic data of the previous week. The traditional algorithm of dominance based rough set theory has been implemented in this paper in incremental way which considerably slows the performance.
|
|
ICACT20220156 Slide.11
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In this paper, authors have applied dominance based rough set approach on dynamic datasets. In dynamic datasets, information keeps on adding with the passage of time. So, once approximation is calculated, author proposed to update it regularly as new information is added in the dataset by considering new object as new dataset. Therefore, the computational cost of re-calculation of approximations of dominance based rough set theory when change occurs in dataset, affect the performance of the application.
|
|
ICACT20220156 Slide.10
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Our research topic related to dominance based rough set theory. Many researchers work on different dimensions of dynamic dataset and presented solutions to update approximations of dominance based rough set theory, we will review some related work here.
|
|
ICACT20220156 Slide.09
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In dominance based rough set theory, calculation of approximations is a core step, but their computations prove expensive, particularly when we are dealing with larger databases. In the 1st step, a complete dataset needs to be traversed to compute upward and downward union of classes for each decision class. In the second step, a conventional algorithm must compare every single object and its characteristics with the whole dataset for multiple times belonging to the upward or downward union of classes. One object can belong to more than one equivalence class, so computation of the dominance relation is also repeated against each respected class. After computation of dominance relations, subset or intersection property need to be checked for computation of lower or upper approximation. We repeat the whole lengthy process for updating approximations in case of some variation in dataset.
|
|
ICACT20220156 Slide.08
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Instead of simple approximations, in dominance based rough set theory, lower and upper approximations are calculated for upward and downward union of classes. Lower approximations group the objects which certainly belong to upward and downward class union and upper approximations group the objects which could belong to upward and downward class union.
|
|
ICACT20220156 Slide.07
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In dominance based rough set theory, we have a finite number of classes in a decision system, but decision classes are preference ordered, an upward union of classes and downward union of classes. Mathematically, the upward union of class t contains all objects of class t and more preferred than class t and downward union of class t contains all objects of class t and less preferred than class t.
|
|
ICACT20220156 Slide.06
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
As I defined earlier, dominance based rough set theory replaces the indescernibility relation with dominance relation to handle inconsistencies. Dominance is a key concept of dominance based rough set theory; it defines the preference order. Mathematically, we define that, for criteria P which is a subset of conditional attribute set, if an object x dominates object y for every criterion from P, it is called dominance-negative relation of object x. Similarly, if object y dominates object x for every criterion from P, it is called dominance-positive relation of object x.
|
|
ICACT20220156 Slide.05
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In the context of dominance based rough set theory, a decision table is a four tuple where
U is a finite set of objects. In given dataset, U comprises objects: { x1, x2, x3, x4, x5, x6, x7 }
Q is a finite set of criteria (The attributes with preference-ordered domains are called criteria).It contains conditional and decision attribute. In dataset, Physics and Chemistry are conditional attributes and Final-Grade is decision attribute.
𝑉 is the value set of criteria q. Value set of criteria ‘Physics’ is { A, B, C}
f: assigns a particular value to an object x for attribute q.
|
|
ICACT20220156 Slide.04
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Greco presented dominance based rough set theory in 2001. The main change compared to the classical rough set theory is the substitution for the indiscernibility relation by a dominance relation, which permits one to deal with inconsistencies typical to consideration of criteria and preference-ordered decision classes. As dominance based rough set theory considered the priority order of criteria/attributes, it has been predominantly used for multicriteria classification problems.
|
|
ICACT20220156 Slide.03
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Traditional classification tasks have a certain number of attributes with a certain range of values and a decision attribute that is a known outcome for each object. However, when there is a need to classify a dataset which also has a preferred order of attributes, classical rough set theory fails to consider the dominance relation. Dominance based rough set theory is an extension of rough set theory. Dominance based rough set theory performs classification tasks by considering the dominance relation of attributes instead of indiscernibility relations.
|
|
ICACT20220156 Slide.02
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Polish computer scientist Pawlak in 1982 presented a tool for knowledge discovery, named as, Rough Set Theory. It is one of the first non-statistical approaches in data analysis. Rough set theory is based on set theory of mathematics. It can be used for feature selection, feature extraction, data reduction, decision rule generation, and pattern extraction (templates, association rules) etc.
The concept of the rough set theory can be applied in various fields such as:
Data Mining: Rough set theory can be applied to the field of data mining in different phases of knowledge discovery such as selection of core attribute, attribute extraction, reducing the datasets, generate the decision rule and pattern recognition.
Economic and financial prediction: It requires the accurate prediction of the future states based on the identification of patterns in the historical data
Medical Imaging: Such as medical image segmentation and object extraction, feature extraction/reduction, and image classification
Bio Informatics: Rough set-based rule induction allows easily interpretable descriptions of complex biological systems
|
|
ICACT20220156 Slide.01
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Hi everybody, my name is Faryal Nosheen. For ICACT 2022, I have cooperated with two partners, Mr. Usman Qamar from National University of Sciences and Technology, Pakistan and Mr. Summair Raza from Virtual University, Pakistan. This presentation is about the computational cost of calculation of approximations of dominance based rough set theory, in case of dynamic datasets. We presented a solution called, A Heuristic Approach to Dynamically Update Approximations of Dominance Based Rough set Theory.
|
