The classification process, data generalisation, attribute relevance, class comparison and statistical measures.
10.1 Definition of classification
Classification assigns each record to one of a set of predefined classes, using a model that has been learned from labelled examples.
As the figure shows, the model is learned once from labelled training data, checked on separate test data, and then used to classify every new record.
ExampleA bank has 1,000 past loan applications, each labelled either "repaid" or "defaulted". It trains a model on 700 of them and tests it on the remaining 300, and the model classifies 258 of the 300 test applications correctly, which is an accuracy of 86 per cent. The bank then uses the model on a new applicant who is 29 years old, earns ₹6 lakh a year and has one existing loan, and the model classifies this applicant as "repaid".
ExplanationTesting on data the model has never seen shows how it will behave on future applicants. If accuracy were measured on the training data instead, the result would be too optimistic, because the model has already seen those records.
10.2 Data generalisation
Data generalisation replaces low-level data with higher-level concepts, so that a large set of records can be summarised in a few general descriptions. It can be done with a data cube (the OLAP approach) or with attribute-oriented induction (AOI).
ExampleStudent records hold each student's name, date of birth, city and exact grade point average (GPA). After generalisation, the date of birth becomes an age range such as 21 to 25, the city becomes a state such as Uttar Pradesh, the GPA becomes a grade such as "very good", and the name is removed altogether.
ExplanationThousands of unique records collapse into a handful of general descriptions that a person can read and understand at a glance.
10.3 Attribute-oriented induction and analytical characterisation
Attribute-oriented induction generalises a set of task-relevant records step by step, as the following example shows.
ExampleThe goal is to characterise graduate students. The first table shows part of the initial relation.
| Name | Gender | Major | Birthplace | Birth date | GPA |
|---|---|---|---|---|---|
| Asha Rao | F | Physics | Pune, India | 12-08-2001 | 3.67 |
| Karan Mehta | M | CSE | Lucknow, India | 02-03-2000 | 3.70 |
| Li Wei | M | Chemistry | Beijing, China | 21-11-1999 | 3.83 |
The second table shows the generalised relation that attribute-oriented induction produces from it.
| Gender | Major | Birthplace | Age range | GPA | Count |
|---|---|---|---|---|---|
| F | Science | India | 21–25 | Very good | 16 |
| M | Engineering | India | 21–25 | Very good | 22 |
| M | Science | Foreign | 26–30 | Excellent | 18 |
ExplanationThe name attribute has a different value for almost every student and no higher concept to climb to, so it is removed. The major, birthplace, birth date and GPA attributes are generalised up their concept hierarchies: Physics becomes Science, "Pune, India" becomes India, the birth date becomes an age range, and a GPA of 3.67 becomes "very good". Rows that become identical are then merged, and a count records how many students each merged row stands for. A generalisation threshold, such as "keep at most three values for each attribute", decides how far up each hierarchy the process climbs.
10.4 Analysis of attribute relevance
Attribute relevance analysis measures how well each attribute separates the classes, so that weak attributes can be dropped before the data is described or compared.
ExampleA university has 1,000 students, of whom 300 are graduates and 700 are undergraduates. The entropy of the whole set is −0.3 log₂ 0.3 − 0.7 log₂ 0.7 = 0.521 + 0.360 = 0.881. The table below shows how the students divide by GPA grade and by gender.
| Attribute value | Graduates | Undergraduates | Total | Entropy of this group |
|---|---|---|---|---|
| GPA excellent | 200 | 50 | 250 | 0.722 |
| GPA good | 80 | 250 | 330 | 0.799 |
| GPA fair | 20 | 400 | 420 | 0.276 |
| Gender male | 140 | 360 | 500 | 0.855 |
| Gender female | 160 | 340 | 500 | 0.904 |
For GPA, the expected entropy after the split is (250 ÷ 1,000) × 0.722 + (330 ÷ 1,000) × 0.799 + (420 ÷ 1,000) × 0.276 = 0.181 + 0.264 + 0.116 ≈ 0.560 (adding the unrounded values), so the information gain is 0.881 − 0.560 = 0.321. For gender, the expected entropy is 0.5 × 0.855 + 0.5 × 0.904 = 0.880, so the gain is only 0.881 − 0.880 = 0.001. Calculated in the same way, the gain is 0.21 for major, 0.18 for age and 0.02 for birthplace. With a relevance threshold of 0.1, gender and birthplace are dropped.
ExplanationGPA splits the students into groups that are mostly graduates or mostly undergraduates, so it gives a large gain. Gender splits them into two groups with almost the same mix as the whole set, so it tells the classes apart hardly at all. Attributes with low relevance would only clutter the description, so relevance analysis is carried out before characterisation or comparison.
10.5 Mining class comparisons (discrimination)
Class comparison, also called discrimination, compares a target class with one or more contrasting classes. Both classes are first generalised to the same level so that they can be compared fairly.
ExampleA university has 300 graduate students and 700 undergraduate students. After generalisation, the group "Science, aged 21 to 25, GPA good" contains 90 graduates and 210 undergraduates. The t-weight of this group, which measures how typical it is of the target class, is 90 ÷ 300 = 30 per cent, so 30 per cent of all graduates belong to it. The d-weight of this group, which measures how well it discriminates, is 90 ÷ (90 + 210) = 30 per cent, so only 30 per cent of the students in the group are graduates.
ExplanationA group with a high t-weight is typical of the target class, while a group with a high d-weight separates the target class well from the contrasting class. Because this group's d-weight is only 30 per cent, it consists mostly of undergraduates, so it does not distinguish graduates well.
10.6 Statistical measures in large databases
Statistical measures summarise the centre and the spread of a set of values.
ExampleThe salaries of 12 employees, in thousands of rupees and sorted in order, are 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70 and 110. The table below shows the main measures for this data.
| Measure | Value | How it is calculated |
|---|---|---|
| Mean | 58 | 696 ÷ 12 |
| Median | 54 | The average of the 6th and 7th values: (52 + 56) ÷ 2 |
| Mode | 52 and 70 | Each value occurs twice, so the data is bimodal |
| Midrange | 70 | (30 + 110) ÷ 2 |
| Q1 and Q3 | 47 and 63 | Q1 is the value at position 0.25 × 12 = 3 (the 3rd value), and Q3 is at position 0.75 × 12 = 9 (the 9th value) |
| Interquartile range (IQR) | 16 | Q3 − Q1 = 63 − 47 |
| Five-number summary | 30, 47, 54, 63, 110 | Minimum, Q1, median, Q3 and maximum |
| Variance (σ²) | 379.17 | The sum of squared deviations from the mean, 4,550, divided by 12 |
| Standard deviation (σ) | 19.47 | √379.17 |
The sum 696 comes from 30 + 36 + 47 + 50 + 52 + 52 + 56 + 60 + 63 + 70 + 70 + 110. The squared deviations from the mean of 58 are 784, 484, 121, 64, 36, 36, 4, 4, 25, 144, 144 and 2,704, and these add up to 4,550.
ExplanationThe mean of 58 is pulled above the median of 54 by the single high salary of 110, and that one salary alone contributes 2,704 of the 4,550 in the variance. Under the 1.5 × IQR rule, the upper fence is Q3 + 1.5 × IQR = 63 + 1.5 × 16 = 63 + 24 = 87, so any value above 87 is treated as an outlier, and the salary of 110 is flagged. The lower fence is 47 − 24 = 23, and no salary falls below it. A box plot draws exactly this information: a box from Q1 to Q3, a line at the median, whiskers that reach the most extreme values that are not outliers, and a separate dot for the outlier of 110.
Exam points
- Classification learns a model from labelled training data and checks its accuracy on separate test data.
- Attribute-oriented induction removes attributes with no higher concept and generalises the rest up their hierarchies.
- Attribute relevance is measured with information gain, gain ratio or the Gini index.
- t-weight shows how typical a group is of the target class; d-weight shows how well it separates the target class from the contrasting class.
- The five-number summary is minimum, Q1, median, Q3 and maximum; IQR = Q3 − Q1.
- A value more than 1.5 × IQR beyond the quartiles is usually treated as an outlier.
Independent study notes for learning purposes. Not affiliated with or endorsed by any university, publisher or course provider. Product and company names are trademarks of their respective owners.