Download In PDF Document file (Last Page)
1)What is Data Warehouse? Explain it with Key Feature.
Ans. Data warehousing provides architectures and tools for business executives to systematically organize, understand, and use their data to make strategic decisions.
A data warehouse refers to a database that is maintained separately from an organization’s operational databases.
Data warehouse systems allow for the integration of a variety of application systems.
They support information processing by providing a solid platform of consolidated historical data for analysis.
According to William H. Inmon, a leading architect in the construction of data warehouse systems, “A data warehouse is a subject-oriented, integrated, time-variant, and nonvolatile collection of data in support of management’s decision making process”
The four keywords, subject-oriented, integrated, time-variant, and nonvolatile, distinguish data warehouses from other data repository systems, such as relational database systems, transaction processing systems, and file systems.
Subject-oriented:
▪ A data warehouse is organized around major subjects, such as customer, supplier, product, and sales.
▪ Rather than concentrating on the day-to-day operations and transaction processing of an organization, a data warehouse focuses on the modeling and analysis of data for decision makers.
▪ Data warehouses typically provide a simple and concise view around particular subject issues by excluding data that are not useful in the decision support process.
Integrated:
▪ A data warehouse is usually constructed by integrating multiple heterogeneous sources, such as relational databases, flat files, and on-line transaction records.
▪ Data cleaning and data integration techniques are applied to ensure consistency in naming conventions, encoding structures, attribute measures, and so on.
Time-variant:
▪ Data are stored to provide information from a historical perspective (e.g., the past 5–10 years).
▪ Every key structure in the data warehouse contains, either implicitly or explicitly, an element of time.
Nonvolatile:
▪ A data warehouse is always a physically separate store of data transformed from the application data found in the operational environment.
▪ Due to this separation, a data warehouse does not require transaction processing, recovery, and concurrency control mechanisms.
▪ It usually requires only two operations in data accessing: initial loading of data and access of data.
2) Explain Data Warehouse Design Process in Detail.
Ans. A data warehouse can be built using a top-down approach, a bottom-up approach, or a combination of both.
Top Down Approach:
▪ The top-down approach starts with the overall design and planning.
▪ It is useful in cases where the technology is mature and well known, and where the business problems that must be solved are clear and well understood.
Bottom up Approach:
▪ The bottom-up approach starts with experiments and prototypes.
▪ This is useful in the early stage of business modeling and technology development.
▪ It allows an organization to move forward at considerably less expense and to evaluate the benefits of the technology before making significant commitments.
Combined Approach:
▪ In the combined approach, an organization can exploit the planned and strategic nature of the top-down approach while retaining the rapid implementation and opportunistic application of the bottom-up approach.
The warehouse design process consists of the following steps:
• Choose a business process to model, for example, orders, invoices, shipments, inventory, account administration, sales, or the general ledger.
• If the business process is organizational and involves multiple complex object collections, a data warehouse model should be followed. However, if the process is departmental and focuses on the analysis of one kind of business process, a data mart model should be chosen.
• Choose the grain of the business process. The grain is the fundamental, atomic level of data to be represented in the fact table for this process, for example, individual transactions, individual daily snapshots, and so on.
• Choose the dimensions that will apply to each fact table record. Typical dimensions are time, item, customer, supplier, warehouse, transaction type, and status.
• Choose the measures that will populate each fact table record. Typical measures are numeric additive quantities like dollars sold and units sold.
3) What is Business Intelligence? Explain Business Intelligence in today’s perspective.
Ans. While there are varying definitions for BI, Forrester defines it broadly as a “set of methodologies, processes, architectures, and technologies that transform raw data into meaningful and useful information that allows business users to make informed business decisions with real-time data that can put a company ahead of its competitors”.
In other words, the high-level goal of BI is to help a business user turn business related data into actionable knowledge.
BI traditionally focused on reports, dashboards, and answering predefined questions.
Today BI also includes a focus on deeper, exploratory, and interactive analyses of the data using Business Analytics such as data mining, predictive analytics, statistical analysis, and natural language processing solutions.
BI systems evolved by adding layers of data staging to increase the accessibility of the business data to business users.
Data from the operational systems and ERP were extracted, transformed into a more consumable form (e.g., column names labeled for human rather than computer consumption, errors corrected, duplication eliminated).
Data from a warehouse were then loaded into OLAP cubes, as well as data marts stored in data warehouses.
OLAP cubes facilitated the analysis of data over several dimensions.
Data marts present a subset of the data in the warehouse, tailored to a specific line of business.
Using Business Intelligence, the business user, with the help of an IT specialist who had set up the system for her, could now more easily access and analyze the data through a BI system.
4) What do you mean by data mart? What are the different types of data mart?
Ans. Data marts contain a subset of organization-wide data that is valuable to specific groups of people in an organization.
A data mart contains only those data that is specific to a particular group.
Data marts improve end-user response time by allowing users to have access to the specific type of data they need to view most often by providing the data in a way that supports the collective view of a group of users.
A data mart is basically a condensed and more focused version of a data warehouse that reflects the regulations and process specifications of each business unit within an organization.
Each data mart is dedicated to a specific business function or region.
For example, the marketing data mart may contain only data related to items, customers, and sales. Data marts are confined to subjects.
Listed below are the reasons to create a data mart:
▪ To speed up the queries by reducing the volume of data to be scanned.
▪ To partition data in order to impose access control strategies.
▪ To segment data into different hardware platforms.
▪ Easy access to frequently needed data
▪ Creates collective view by a group of users
▪ Improves end-user response time
▪ Lower cost than implementing a full data warehouse
▪ Contains only business essential data and is less cluttered.
Three basic types of data marts are dependent, independent, and hybrid.
The categorization is based primarily on the data source that feeds the data mart.
Dependent data marts draw data from a central data warehouse that has already been created.
Independent data marts, in contrast, are standalone systems built by drawing data directly from operational or external sources of data or both.
Hybrid data marts can draw data from operational systems or data warehouses
1. Dependent Data Marts:
A dependent data mart allows you to unite your organization's data in one data warehouse.
This gives you the usual advantages of centralization.
Figure illustrates a dependent data mart.
2. Independent Data Marts:
An independent data mart is created without the use of a central data warehouse.
This could be desirable for smaller groups within an organization.
Figure illustrates an independent data mart.
3. Hybrid Data Marts:
A hybrid data mart allows you to combine input from sources other than a data warehouse.
This could be useful for many situations, especially when you need ad hoc integration, such as after a new group or product is added to the organization.
Figure illustrates a hybrid data mart.
5) Explain usage of Data warehousing for information processing, analytical processing, and data Mining.
Ans. Data warehouses are used in a wide range of applications for Business executives to perform data analysis and make strategic decisions.
In many firms, data warehouses are used as an integral part of a plan-execute-assess “closed-loop” feedback system for enterprise management.
Data warehouses are used extensively in banking and financial services, consumer goods and retail distribution sectors, and controlled manufacturing, such as demand based production.
Business users need to have the means to know what exists in the data warehouse (through metadata), how to access the contents of the data warehouse, how to examine the contents using analysis tools, and how to present the results of such analysis.
There are three kinds of data warehouse applications:
1. Information processing:
It supports querying, basic statistical analysis, and reporting using crosstabs, tables, charts, or graphs.
A current trend in data warehouse information processing is to construct low-cost Web-based accessing tools that are then integrated with Web browsers.
Information processing, based on queries, can find useful information. However, answers to such queries reflect the information directly stored in databases or computable by aggregate functions.
They do not reflect sophisticated patterns or regularities buried in the database. Therefore, information processing is not data mining.
2. Analytical processing:
It supports basic OLAP operations, including slice-and-dice, drill-down, roll-up, and pivoting.
It generally operates on historical data in both summarized and detailed forms.
The major strength of on-line analytical processing over information processing is the multidimensional data analysis of data warehouse data.
It can derive information summarized at multiple granularities from user-specified subsets of a data warehouse.
3. Data mining:
It supports knowledge discovery by finding hidden patterns and associations, constructing analytical models, performing classification and prediction, and presenting the mining results using visualization tools.
It may analyze data existing at more detailed granularities than the summarized data provided in a data warehouse.
It may also analyze transactional, spatial, textual, and multimedia data that are difficult to model with current multidimensional database technology.
6) Explain three tier data warehouse architecture in brief.
Bottom tier:
• The bottom tier is a warehouse database server that is almost always a relational database system.
• Back-end tools and utilities are used to feed data into the bottom tier from operational databases or other external sources.
• These tools and utilities perform data extraction, cleaning, and transformation, as well as load and refresh functions to update the data warehouse.
• The data are extracted using application program interfaces known as gateways.
• A gateway is supported by the underlying DBMS and allows client programs to generate SQL code to be executed at a server.
• Examples of gateways include ODBC (Open Database Connection) and OLEDB (Open Linking and Embedding for Databases) by Microsoft and JDBC (Java Database Connection).
• This tier also contains a metadata repository, which stores information about the data warehouse and its contents.
Middle tier:
• The middle tier is an OLAP server that is typically implemented using either.
• A relational OLAP (ROLAP) model, that is, an extended relational DBMS that maps operations on multidimensional data to standard relational operations or,
• A multidimensional OLAP (MOLAP) model, that is, a special-purpose server that directly implements multidimensional data and operations.
Top tier:
• The top tier is a front-end client layer, which contains query and reporting tools, analysis tools, and/or data mining tools.
From the architecture point of view, there are three data warehouse models:
1. Enterprise warehouse:
• An enterprise warehouse collects all of the information about subjects spanning the entire organization.
• It provides corporate-wide data integration, usually from one or more operational systems or external information providers, and is cross-functional in scope.
• It typically contains detailed data as well as summarized data,
• It can range in size from a few gigabytes to hundreds of gigabytes, terabytes, or beyond.
2. Data mart:
• A data mart contains a subset of corporate-wide data that is of value to a specific group of users.
3. Virtual warehouse:
• A virtual warehouse is a set of views over operational databases.
For efficient query processing, only some of the possible summary views may be materialized.
7) Differentiate between OLTP and OLAP systems.
Ans.
Feature | OLTP | OLAP |
|---|---|---|
Characteristic | operational processing | informational processing |
Orientation | transaction | analysis |
User | clerk, DBA, database professional | knowledge worker (e.g., manager, executive, analyst) |
Function | day-to-day operations | long-term informational requirements, decision support |
DB design | ER based, application-oriented | star/snowflake, subject-oriented |
Data | current; guaranteed up-to-date | historical; accuracy maintained over time |
Summarization | primitive, highly detailed | summarized, consolidated |
View | detailed, flat relational | summarized, multidimensional |
Access | ead/write | mostly read |
Focus | data in | information out |
Operations | index/hash on primary key | lots of scans |
Number of users | thousands | hundreds |
DB size | 100 MB to GB | 100 GB to TB |
Metric | transaction throughput | query throughput, response time |
8) What is application of concept hierarchy? Draw concept hierarchy for location (country, state, city, and street) and time (year, quarter, month, week, day). OR
What do you mean by concept hierarchy? Show its application with suitable example.
Ans.
• A concept hierarchy defines a sequence of mappings from a set of low-level concepts to higher-level, more general concepts.
• Consider a concept hierarchy for the dimension location. City values for location include Vancouver, Toronto, New York, and Chicago.
• Each city, however, can be mapped to the province or state to which it belongs.
• For example, Vancouver can be mapped to British Columbia, and Chicago to Illinois.
• The provinces and states can in turn be mapped to the country to which they belong, such as Canada or the USA.
• These mappings form a concept hierarchy for the dimension location, mapping a set of low-level concepts (i.e., cities) to higher-level, more general concepts (i.e., countries).
• The concept hierarchy described above is illustrated in following Figure.
• Concept hierarchies may be provided manually by system users, domain experts, or knowledge engineers, or may be automatically generated based on statistical analysis of the data distribution.
• Many concept hierarchies are implicit within the database schema.
• For example, suppose that the dimension location is described by the attributes number, street, city, province or state, zipcode, and country.
• These attributes are related by a total order, forming a concept hierarchy such as “street < city < province or state < country”. This hierarchy is shown in following Figure (a).
• Alternatively, the attributes of a dimension may be organized in a partial order, forming a lattice.
An example of a partial order for the time dimension based on the attributes day, week, month, quarter,
and year is “day <{ month <quarter; week} < year”. This lattice structure is shown in Figure (b).
• A concept hierarchy that is a total or partial order among attributes in a database schema is called a schema hierarchy.
• Concept hierarchies may also be defined by discretizing or grouping values for a given dimension or attribute, resulting in a set-grouping hierarchy.
• A total or partial order can be defined among groups of values.
• There may be more than one concept hierarchy for a given attribute or dimension, based on different user viewpoints.
9) List out the different schema of data warehouse and explain each in detail. OR Explain following design methods for multidimensional database: Star schema, Snowflake schema, Fact constellation schema. Also compare them with illustration.
Ans.
• The entity-relationship data model is commonly used in the design of relational databases, where a database schema consists of a set of entities and the relationships between them.
• Such a data model is appropriate for on-line transaction processing.
• A data warehouse, however, requires a concise, subject-oriented schema that facilitates on-line data analysis.
• The most popular data model for a data warehouse is a multidimensional model.
• Such a model can exist in the form of a star schema, a snowflake schema, or a fact constellation schema.
Let’s look at each of these schema types.
Star schema:
The most common modeling paradigm is the star schema, in which the data warehouse contains,
(1) a large central table (fact table) containing the bulk of the data, with no redundancy, and
(2) a set of smaller attendant tables (dimension tables), one for each dimension.
• The schema graph resembles a starburst, with the dimension tables displayed in a radial pattern around the central fact table.
• DMQL code for star schema can be written as follows:
define cube sales star [time, item, branch, location]:
dollars sold = sum(sales in dollars), units sold = count(*)
define dimension time as (time key, day, day of week, month, quarter, year) define dimension item as (item key, item name, brand, type, supplier type) define dimension branch as (branch key, branch name, branch type)
define dimension location as (location key, street, city, province or state, country)
Snowflake Shema:
The major difference between the snowflake and star schema models is that the dimension tables of the snowflake model may be kept in normalized form to reduce redundancies. Such a table is easy to maintain and saves storage space.
• However, this saving of space is negligible in comparison to the typical magnitude of the fact table. Furthermore, the snowflake structure can reduce the effectiveness of browsing, since more joins will be needed to execute a query.
• Hence, although the snowflake schema reduces redundancy, it is not as popular as the star schema in data warehouse design.
• DMQL code for star schema can be written as follows:
define cube sales snowflake [time, item, branch, location]: dollars sold = sum(sales in dollars), units sold = count(*)
define dimension time as (time key, day, day of week, month, quarter, year) define dimension item as (item key, item name, brand, type, supplier (supplier key, supplier type))
define dimension branch as (branch key, branch name, branch type) define dimension location as (location key, street, city
(city key, city, province or state, country))
Fact constellation: Sophisticated applications may require multiple fact tables to share dimension tables.
• This kind of schema can be viewed as a collection of stars, and hence is called a galaxy schema or a fact constellation.
• A fact constellation schema allows dimension tables to be shared between fact tables.
• For example, the dimensions tables for time, item, and location are shared between both the sales and shipping fact tables.
• DMQL code for star schema can be written as follows:
define cube sales [time, item, branch, location]:
dollars sold = sum(sales in dollars), units sold = count(*)
define dimension time as (time key, day, day of week, month, quarter, year) define dimension item as (item key, item name, brand, type, supplier type) define dimension branch as (branch key, branch name, branch type)
define dimension location as (location key, street, city, province or state, country)
define cube shipping [time, item, shipper, from location, to location]: dollars cost = sum(cost in dollars), units shipped = count(*)
define dimension time as time in cube sales define dimension item as item in cube sales
define dimension shipper as (shipper key, shipper name, location as location in cube sales, shipper type)
define dimension from location as location in cube
sales define dimension to location as location in
cube sales
10)Explain OLAP Operations in the Multidimensional Data Model?
Ans. 1. Roll-up:
• Roll-up performs aggregation on a data cube in any of the following ways:
▪ By climbing up a concept hierarchy for a dimension
▪ By dimension reduction
• The following diagram illustrates how roll-up works.
• Roll-up is performed by climbing up a concept hierarchy for the dimension location.
• Initially the concept hierarchy was "street < city < province < country".
• On rolling up, the data is aggregated by ascending the location hierarchy from the level of city to the level of country.
• The data is grouped into cities rather than countries.
• When roll-up is performed, one or more dimensions from the data cube are removed.
2. Drill-down:
• Drill-down is the reverse operation of roll-up. It is performed by either of the following ways:
▪ By stepping down a concept hierarchy for a dimension
▪ By introducing a new dimension.
• The following diagram illustrates how drill-down works:
• Drill-down is performed by stepping down a concept hierarchy for the dimension time.
• Initially the concept hierarchy was "day < month < quarter < year."
• On drilling down, the time dimension is descended from the level of quarter to the level of month.
• When drill-down is performed, one or more dimensions from the data cube are added.
• It navigates the data from less detailed data to highly detailed data.
3. Slice:
• The slice operation selects one particular dimension from a given cube and provides a new sub cube.
• Consider the following diagram that shows how slice works.
• Here Slice is performed for the dimension "time" using the criterion time = "Q1".
• It will form a new sub-cube by selecting one or more dimensions.
4. Dice:
• Dice selects two or more dimensions from a given cube and provides a new sub-cube.
• Consider the following diagram that shows the dice operation.
• The dice operation on the cube based on the following selection criteria involves three dimensions.
▪ (location = "Toronto" or "Vancouver")
▪ (time = "Q1" or "Q2")
▪ (item =" Mobile" or "Modem")
5. Pivot:
• The pivot operation is also known as rotation.
• It rotates the data axes in view in order to provide an alternative presentation of data.
• Consider the following diagram that shows the pivot operation.
• In this the item and location axes in 2-D slice are rotated.
11) Explain Types of OLAP Servers.
Ans.
We have four types of OLAP servers:
1. Relational OLAP:
• ROLAP servers are placed between relational back-end server and client front-end tools.
• To store and manage warehouse data, ROLAP uses relational or extended-relational DBMS.
• ROLAP includes the following:
▪ Implementation of aggregation navigation logic.
▪ Optimization for each DBMS back end.
▪ Additional tools and services.
2. Multidimensional OLAP:
• MOLAP uses array-based multidimensional storage engines for multidimensional views of data.
• With multidimensional data stores, the storage utilization may be low if the data set is sparse.
• Many MOLAP server use two levels of data storage representation to handle dense and sparse data sets.
3. Hybrid OLAP (HOLAP):
• Hybrid OLAP is a combination of both ROLAP and MOLAP.
• It offers higher scalability of ROLAP and faster computation of MOLAP.
• HOLAP servers allows to store the large data volumes of detailed information.
• The aggregations are stored separately in MOLAP store.
4. Specialized SQL Servers:
• Specialized SQL servers provide advanced query language and query processing support for SQL queries over star and snowflake schemas in a read-only environment.
12) the term “Data Mining”. With the help of a suitable diagram explain the process of knowledge discovery from databases. OR What is Data mining? Explain Data mining as one step of Knowledge Discovery Process.
Ans. Data Mining: “It refers to extracting or “mining” knowledge from large amounts of data.”
Also refers as Knowledge mining from data.
Many people treat data mining as a synonym for another popularly used term, Knowledge Discovery from Data, or KDD.
Data mining can be viewed as a result of the natural evolution of information technology.
The abundance of data, coupled with the need for powerful data analysis tools, has been described as data rich but information poor situation.
Knowledge base: This is the domain knowledge that is used to guide the search or evaluate the interestingness of resulting patterns. Such knowledge can include concept hierarchies, used to organize attributes or attribute values into different levels of abstraction.
Data warehouses typically provide a simple and concise view around particular subject issues by excluding data that are not useful in the decision support process.
Knowledge such as user beliefs, which can be used to assess a pattern’s interestingness based on its unexpectedness, may also be included. Other examples of domain knowledge are additional interestingness constraints or thresholds, and metadata (e.g., describing data from multiple heterogeneous sources).
Data mining engine: This is essential to the data mining system and ideally consists of a set of functional modules for tasks such as characterization, association and correlation analysis, classification, prediction, cluster analysis, outlier analysis, and evolution analysis.
Pattern evaluation module: This component typically employs interestingness measures and interacts with the data mining modules so as to focus the search toward interesting patterns.
It may use interestingness thresholds to filter out discovered patterns. Alternatively, the pattern evaluation module may be integrated with the mining module, depending on the implementation of the data mining method used.
For efficient data mining, it is highly recommended to push the evaluation of pattern interestingness as deep as possible into the mining process so as to confine the search to only the interesting patterns.
KDD (Knowledge Discovery from Data) Process:
KDD stands for knowledge discoveries from database. There are some pre-processing operations which are required to make pure data in data warehouse before use that data for Data Mining processes.
A view data mining as simply an essential step in the process of knowledge discovery. Knowledge discovery as a process is depicted in Figure 2 and consists of an iterative sequence of the following steps:
✓ Data cleaning: To remove noise and inconsistent data.
✓ Data integration: where multiple data sources may be combined.
✓ Data selection: where data relevant to the analysis task are retrieved from the database.
✓ Data transformation: where data are transformed or consolidated into forms appropriate for mining by performing summary or aggregation operations, for instance.
✓ Data mining: An essential process where intelligent methods are applied in order to extract data patterns.
✓ Pattern evaluation: To identify the truly interesting patterns representing knowledge based on some interestingness measures.
✓ Knowledge presentation: where visualization and knowledge representation techniques are used to present the mined knowledge to the user.
KDD refers to the overall process of discovering useful knowledge from data. It involves the evaluation and possibly interpretation of the patterns to make the decision of what qualifies as knowledge. It also includes the choice of encoding schemes, preprocessing, sampling, and projections of the data prior to the data mining step.
Data mining refers to the application of algorithms for extracting patterns from data without the additional steps of the KDD process.
Objective of Pre-processing on data is to remove noise from data or to remove redundant data.
There are mainly 4 types of Pre-processing Activities included in KDD Process that is shown in fig. as Data cleaning, Data integration, Data transformation, Data reduction.
12)List and describe major issues in data mining. OR List Challenges to data mining regarding data mining methodology and user-interactions issues.
Ans. Data Mining is a dynamic and fast-expanding field with great strengths. Major issues in data mining research, partitioning them into five groups: Mining methodology, User interaction, Efficiency and scalability, Diversity of data types, and Data mining & Society.
Many of these issues have been addressed in recent data mining research and development to a certain extent and are now considered data mining requirements; others are still at the research stage. The issues continue to stimulate further investigation and improvement in data mining.
Mining Methodology: This involves the investigation of new kinds of knowledge, mining in multidimensional space, integrating methods from other disciplines, and the consideration of semantic ties among data objects.
In addition, mining methodologies should consider issues such as data uncertainty, noise, and incompleteness.
Mining various and new kinds of knowledge: Data mining covers a wide spectrum of data analysis and knowledge discovery tasks, from data characterization and discrimination to association and correlation analysis, classification, regression, clustering, outlier analysis, sequence analysis, and trend and evolution analysis.
These tasks may use the same database in different ways and require the development of numerous data mining techniques. Due to the diversity of applications, new mining tasks continue to emerge, making data mining a dynamic and fast-growing field.
For example, for effective knowledge discovery in information networks, integrated clustering and ranking may lead to the discovery of high-quality clusters and object ranks in large networks.
Mining knowledge in multidimensional space: When searching for knowledge in large data sets, we can explore the data in multidimensional space. That is, we can search for interesting patterns among combinations of dimensions (attributes) at varying levels of abstraction. Such mining is known as (exploratory) multidimensional data mining.
In many cases, data can be aggregated or viewed as a multidimensional data cube. Mining
knowledge in cube space can substantially enhance the power and flexibility of data mining.
Data mining—an interdisciplinary effort: The power of data mining can be
substantially enhanced by integrating new methods from multiple disciplines. For example, to mine data with natural language text, it makes sense to fuse data mining methods with methods of information retrieval and natural language processing.
As another example, consider the mining of software bugs in large programs. This form of mining, known as bug mining, benefits from the incorporation of software engineering knowledge into the data mining process.
Handling uncertainty, noise, or incompleteness of data: Data often contain noise, errors, exceptions, or uncertainty, or are incomplete. Errors and noise may confuse the data mining process, leading to the derivation of erroneous patterns.
Data cleaning, data preprocessing, outlier detection and removal, and uncertainty reasoning are examples of techniques that need to be integrated with the data mining process.
User Interaction: The user plays an important role in the data mining process. Interesting areas of research include how to interact with a data mining system, how to incorporate a user’s background knowledge in mining, and how to visualize and comprehend data mining results.
▪ Interactive mining: The data mining process should be highly interactive. Thus, it is important to build flexible user interfaces and an exploratory mining environment, facilitating the user’s interaction with the system.
▪ A user may like to first sample a set of data, explore general characteristics of the data, and estimate potential mining results. Interactive mining should allow users to dynamically change the focus of a search, to refine mining requests based on returned results, and to drill, dice, and pivot through the data and knowledge space interactively, dynamically exploring “cube space” while mining.
▪ Incorporation of background knowledge: Background knowledge, constraints, rules, and other information regarding the domain under study should be incorporated into the knowledge discovery process. Such knowledge can be used for pattern evaluation as well as to guide the search toward interesting patterns.
▪ Presentation and visualization of data mining results: How can a data mining system present data mining results, vividly and flexibly, so that the discovered knowledge can be easily understood and directly usable by humans? This is especially crucial if the data mining process is interactive.
▪ It requires the system to adopt expressive knowledge representations, user-friendly interfaces, and visualization techniques.
Efficiency and Scalability: Efficiency and scalability are always considered when comparing data mining algorithms. As data amounts continue to multiply, these two factors are especially critical.
▪ Efficiency and scalability of data mining algorithms: Data mining algorithms must be efficient and scalable in order to effectively extract information from huge amounts of data in many data repositories or in dynamic data streams.
▪ In other words, the running time of a data mining algorithm must be predictable, short, and acceptable by applications. Efficiency, scalability, performance, optimization, and the ability to execute in real time are key criteria that drive the development of many new data mining algorithms.
▪ Parallel, distributed, and incremental mining algorithms: The humongous size of many data sets, the wide distribution of data, and the computational complexity of some data mining methods are factors that motivate the development of parallel and distributed data- intensive mining algorithms. Such algorithms first partition the data into “pieces.”
▪ Each piece is processed, in parallel, by searching for patterns. The parallel processes may interact with one another. The patterns from each partition are eventually merged. Diversity of Database Types: The wide diversity of database types brings about challenges to data mining. These includes are as below.
▪ Handling complex types of data: Diverse applications generate a wide spectrum of new data types, from structured data such as relational and data warehouse data to semi- structured and unstructured data; from stable data repositories to dynamic data streams; from simple data objects to temporal data, biological sequences, sensor data, spatial data, hypertext data, multimedia data, software program code, Web data, and social network data.
▪ It is unrealistic to expect one data mining system to mine all kinds of data, given the diversity of data types and the different goals of data mining. Domain- or application-dedicated data mining systems are being constructed for in depth mining of specific kinds of data.
▪ The construction of effective and efficient data mining tools for diverse applications remains a challenging and active area of research.
▪ Mining dynamic, networked, and global data repositories: Multiple sources of data are connected by the Internet and various kinds of networks, forming gigantic, distributed, and heterogeneous global information systems and networks.
▪ The discovery of knowledge from different sources of structured, semi-structured, or unstructured yet interconnected data with diverse data semantics poses great challenges to data mining.
Data Mining and Society: How does data mining impact society? What steps can data mining take to preserve the privacy of individuals? Do we use data mining in our daily lives without even knowing that we do? These questions raise the following issues:
▪ Social impacts of data mining: With data mining penetrating our everyday lives, it is important to study the impact of data mining on society. How can we used at a mining technology to benefit society? How can we guard against its misuse?
▪ The improper disclosure or use of data and the potential violation of individual privacy and data protection rights are areas of concern that need to be addressed.
▪ Privacy-preserving data mining: Data mining will help scientific discovery, business management, economy recovery, and security protection (e.g., the real-time discovery of intruders and cyberattacks).
▪ However, it poses the risk of disclosing an individual’s personal information. Studies on privacy-preserving data publishing and data mining are ongoing. The philosophy is to observe data sensitivity and preserve people’s privacy while performing successful data mining.
▪ Invisible data mining: We cannot expect everyone in society to learn and master data mining techniques. More and more systems should have data mining functions built within so that people can perform data mining or use data mining results simply by mouse clicking, without any knowledge of data mining algorithms.
▪ Intelligent search engines and Internet-based stores perform such invisible data mining by incorporating data mining into their components to improve their functionality and performance. This is done often unbeknownst to the user.
▪ For example, when purchasing items online, users may be unaware that the store is likely collecting data on the buying patterns of its customers, which may be used to recommend other items for purchase in the future.
13) Explain different types of data on which mining can be performed.
Ans. Data mining can be applied to any kind of data as long as the data are meaningful for a target application. The most basic forms of data for mining applications are database data, data warehouse data, and transactional data.
Data mining can also be applied to other forms of data (e.g., data streams, ordered/sequence data, graph or networked data, spatial data, text data, multimedia data, and the WWW).
Database Data: A database system, also called a database management system (DBMS), consists of a collection of interrelated data, known as a database, and a set of software programs to manage and access the data.
The software programs provide mechanisms for defining database structures and data storage; for specifying and managing concurrent, shared, or distributed data access; and for ensuring consistency and security of the information stored despite system crashes or attempts at unauthorized access.
A relational database is a collection of tables, each of which is assigned a unique name. Each table consists of a set of attributes (columns or fields) and usually stores a large set of tuples (records or rows).
Each tuple in a relational table represents an object identified by a unique key and described by a set of attribute values. A semantic data model, such as an entity-relationship (ER) data model, is often constructed for relational databases.
Example:
▪ A relational database for All Electronics. The company is described by the following relation tables: customer, item, employee, and branch.
▪ The relation customer consists of a set of attributes describing the customer information, including a unique customer identity number (cust_ID), customer name, address, age, occupation, annual income, credit information, and category.
▪ Similarly, each of the relations item, employee, and branch consists of a set of attributes describing the properties of these entities. Tables can also be used to represent the relationships between or among multiple entities.
▪ In our example, these include purchases (customer purchases items, creating a sales transaction handled by an employee), items sold (lists items sold in a given transaction), and works at (employee works at a branch of AllElectronics).
o Customer (cust_ID, name, address, age, occupation, annual income, credit information, category, ...)
o Item (item ID, brand, category, type, price, place made, supplier, cost, ...)
o employee (empl_ID, name, category, group, salary, commission, ...)
o Branch (branch ID, name, address, ...)
o Purchases (trans ID, cust_ID, empl_ID, date, time, method paid, amount)
o Items sold (trans ID, item ID, Qty)
o Works at (empl_ID, branch_ID)
Relational data can be accessed by database queries written in a relational query language (e.g., SQL) or with the assistance of graphical user interfaces.
A given query is transformed into a set of relational operations, such as join, selection, and projection, and is then optimized for efficient processing. A query allows retrieval of specified subsets of the data. Suppose that your job is to analyze the All Electronics data.
Through the use of relational queries, you can ask things like, “Show me a list of all items that were sold in the last quarter.” Relational languages also use aggregate functions such as sum, avg (average), count, max (maximum), and min (minimum). Using aggregates allows you to ask: “Show me the total sales of the last month, grouped by branch,” or “How many sales transactions occurred in the month of December?” or “Which salesperson had the highest sales?”
Data Warehouse Data: Suppose that All Electronics is a successful international company with branches around the world. Each branch has its own set of databases. The president of All Electronics has asked you to provide an analysis of the company’s sales per item type per branch for the third quarter.
This is a difficult task, particularly since the relevant data are spread out over several databases physically located at numerous sites.
If All Electronics had a data warehouse, this task would be easy. “A data warehouse is a repository of information collected from multiple sources, stored under a unified schema, and usually residing at a single site.”
Data warehouses are constructed via a process of data cleaning, data integration, data transformation, data loading, and periodic data refreshing.
To facilitate decision making, the data in a data warehouse are organized around major subjects (e.g., customer, item, supplier, and activity). The data are stored to provide information from a historical perspective, such as in the past 6 to 12 months, and are typically summarized.
For example, rather than storing the details of each sales transaction, the data warehouse may store a summary of the transactions per item type for each store or, summarized to a higher level, for each sales region.
A data warehouse is usually modeled by a multidimensional data structure, called a data cube, in which each dimension corresponds to an attribute or a set of attributes in the schema, and each cell stores the value of some aggregate measure such as count or sum (sales amount). A data cube provides a multidimensional view of data and allows the precomputation and fast access of summarized data.
Although data warehouse tools help support data analysis, additional tools for data mining are often needed for in-depth analysis. Multidimensional data mining (also called exploratory multidimensional data mining) performs data mining in multidimensional space in an OLAP style.
That is, it allows the exploration of multiple combinations of dimensions at varying levels of granularity in data mining, and thus has greater potential for discovering interesting patterns representing knowledge.
Transactional Data: In general, each record in a transactional database captures a transaction, such as a customer’s purchase, a flight booking, or a user’s clicks on a web page. A transaction typically includes a unique transaction identity number (trans_ID) and a list of the items making up the transaction, such as the items purchased in the transaction.
A transactional database may have additional tables, which contain other information related to the transactions, such as item description, information about the salesperson or the branch, and so on.
Example:
▪ A transactional database for AllElectronics.
▪ Transactions can be stored in a table, with one record per transaction. A fragment of a transactional database for AllElectronics is shown in Figure 4. From the relational database point of view, the sales table in the figure is a nested relation because the attribute list of item IDs contains a set of items.
▪ Because most relational database systems do not support nested relational structures, the transactional database is usually either stored in a flat file in a format similar to the table in Figure 4.
▪ As an analyst of AllElectronics, you may ask, “Which items sold well together?” This kind of market basket data analysis would enable you to bundle groups of items together as a strategy for boosting sales.
▪ For example, given the knowledge that printers are commonly purchased together with computers, you could offer certain printers at a steep discount (or even for free) to customers buying selected computers, in the hopes of selling more computers (which are often more expensive than printers).
▪ A traditional database system is not able to perform market basket data analysis. Fortunately, data mining on transactional data can do so by mining frequent item sets, that is, sets of items that are frequently sold together.
Trans_ID | List of item IDs |
T100 | I1, I3, I8, I16 |
T200 | I2, I8 |
… | … |
Fig.4 Fragment of a transactional database for sales at AllElectronics
15) Why Data Preprocessing is needed and which are the techniques used for data Preprocessing?
Ans. Today’s real-world databases are highly susceptible to noisy, missing, and inconsistent data due to their typically huge size (often several gigabytes or more) and their likely origin from multiple, heterogeneous sources.
Low-quality data will lead to low-quality mining results. How can the data be preprocessed in order to help improve the quality of the data and, consequently, of the mining results? How can the data be preprocessed so as to improve the efficiency and ease of the mining process?
Data have quality if they satisfy the requirements of the intended use. There are many factors comprising data quality, including accuracy, completeness, consistency, timeliness, believability, and interpretability.
Example :
Imagine that you are a manager at AllElectronics and have been charged with analyzing the company’s data with respect to your branch’s sales.
You immediately set out to perform this task. You carefully inspect the company’s database and data warehouse, identifying and selecting the attributes or dimensions (e.g., item, price, and units sold) to be included in your analysis.
Alas! You notice that several of the attributes for various tuples have no recorded value. For your analysis, you would like to include information as to whether each item purchased was advertised as on sale, yet you discover that this information has not been recorded.
Furthermore, users of your database system have reported errors, unusual values, and inconsistencies in the data recorded for some transactions.
In other words, the data you wish to analyze by data mining techniques are incomplete (lacking attribute values or certain attributes of interest, or containing only aggregate data); inaccurate or noisy (containing errors, or values that deviate from the expected); and inconsistent (e.g., containing discrepancies in the department codes used to categorize items).
Above example illustrates three of the elements defining data quality: accuracy, completeness, and consistency.
Inaccurate, incomplete, and inconsistent data are commonplace properties of large real-world databases and data warehouses.
There are many possible reasons for inaccurate data (i.e., having incorrect attribute values). The data collection instruments used may be faulty.
There may have been human or computer errors occurring at data entry. Users may purposely submit incorrect data values for mandatory fields when they do not wish to submit personal information (e.g., by choosing the default value “January 1” displayed for birthday). This is known as disguised missing data. Errors in data transmission can also occur.
There may be technology limitations such as limited buffer size for coordinating synchronized data transfer and consumption. Incorrect data may also result from inconsistencies in naming conventions or data codes, or inconsistent formats for input fields (e.g., date).
Incomplete data can occur for a number of reasons. Attributes of interest may not always be available, such as customer information for sales transaction data.
Other data may not be included simply because they were not considered important at the time of entry. Relevant data may not be recorded due to a misunderstanding or because of equipment malfunctions. Data that were inconsistent with other recorded data may have been deleted.
Furthermore, the recording of the data history or modifications may have been overlooked. Missing data, particularly for tuples with missing values for some attributes, may need to be inferred.
Data Preprocessing Methods/Techniques:
Data Cleaning routines work to “clean” the data by filling in missing values, smoothing noisy data, identifying or removing outliers, and resolving inconsistencies.
Data Integration which combines data from multiple sources into a coherent data store, as in data warehousing.
Data Transformation, the data are transformed or consolidated into forms appropriate for mining
Data Reduction obtains a reduced representation of the data set that is much smaller in volume, yet produces the same (or almost the same) analytical results.
15) Explain Mean, Median, Mode, Variance & Standard Deviation in brief.
Ans. Mean: The sample mean is the average and is computed as the sum of all the observed outcomes from the sample divided by the total number of events. We use x as the symbol for the sample mean. In math terms,
where n is the sample size and the x correspond to the observed valued.
Let’s look to Find out Mean.
Suppose you randomly sampled six acres in the Desolation Wilderness for a non-indigenous weed and came up with the following counts of this weed in this region: 34, 43, 81, 106, 106 and 115
We compute the sample mean by adding and dividing by the number of
samples,
6. 34 + 43 + 81 + 106 + 106 + 115
6
We can say that the sample mean of non-indigenous weed is 80.83.
The mode of a set of data is the number with the highest frequency. In the above example 106 is the mode, since it occurs twice and the rest of the outcomes occur only once.
The population mean is the average of the entire population and is usually impossible to compute. We use the Greek letter μ for the population mean.
Median: One problem with using the mean, is that it often does not depict the typical outcome. If there is one outcome that is very far from the rest of the data, then the mean will be strongly affected by this outcome. Such an outcome is called and outlier.
An alternative measure is the median; the median is the middle score. If we have an even number of events, we take the average of the two middles. The median is better for describing the typical value. It is often used for income and home prices.
Let’s Look to Find out Median.
Suppose you randomly selected 10 house prices in the South Lake area. You are interested in the typical house price. In $100,000 the prices were: 2.7, 2.9, 3.1, 3.4, 3.7, 4.1, 4.3, 4.7, 4.7, 40.8.
If we computed the mean, we would say that the average house price is 744,000. Although this number is true, it does not reflect the price for available housing in South Lake Tahoe.
A closer look at the data shows that the house valued at 40.8 x $100,000 = $4.08 million skews the data. Instead, we use the median. Since there is an even number of outcomes, we take the average of the middle two is 3.9.
3.7 + 4.1
2 = 3.9
The median house price is $390,000. This better reflects what house shoppers should expect to spend.
Mode: The mode is another measure of central tendency. The mode for a set of data is the value that occurs most frequently in the set.
Therefore, it can be determined for qualitative and quantitative attributes. It is possible for the greatest frequency to correspond to several different values, which results in more than one mode. Data sets with one, two, or three modes are respectively called unimodal, bimodal, and trimodal.
In general, a dataset with two or more modes is multimodal. At the other extreme, if each data value occurs only once, then there is no mode.
Let’s Look for find Mode.
In Above Example We Consider 4.7 As Mode.
Variance & Standard Deviation: The mean, mode and median do a nice job in telling where the center of the data set is, but often we are interested in more.
For example, a pharmaceutical engineer develops a new drug that regulates iron in the blood. Suppose she finds out that the average sugar content after taking the medication is the optimal level. This does not mean that the drug is effective. There is a possibility that half of the patients have dangerously low sugar content while the other half have dangerously high content.
Instead of the drug being an effective regulator, it is a deadly poison. What the pharmacist needs is a measure of how far the data is spread apart. This is what the variance and standard deviation do. First we show the formulas for these measurements. Then we will go through the steps on how to use the formulas.
We define the variance to be
and the standard deviation to be
Variance and Standard Deviation: Step by Step
Calculate the mean, x.
Write a table that subtracts the mean from each observed value.
Square each of the differences.
Add this column.
Divide by n -1 where n is the number of items in the sample this is the variance.
To get the standard deviation we take the square root of the variance.
Let’s Look to Find out variance & standard deviation
The owner of the Indian restaurant is interested in how much people spend at the restaurant. He examines 10 randomly selected receipts for parties of four and writes down the following data.
44, 50, 38, 96, 42, 47, 40, 39, 46, 50
He calculated the mean by adding and dividing by 10 to get Average(Mean) = 49.2.
Below is the table for getting the standard deviation:
x | x - 49.2 | (x - 49.2 )2 |
44 | -5.2 | 27.04 |
50 | 0.8 | 0.64 |
38 | 11.2 | 125.44 |
96 | 46.8 | 2190.24 |
42 | -7.2 | 51.84 |
47 | -2.2 | 4.84 |
40 | -9.2 | 84.64 |
39 | -10.2 | 104.04 |
46 | -3.2 | 10.24 |
50 | 0.8 | 0.64 |
Total | | 2600.4 |
Now 2600.4/10 – 1 = 288.7
Hence the variance is 289 and the standard deviation is the square root of 289 = 17.
Since the standard deviation can be thought of measuring how far the data values lie from the mean, we take the mean and move one standard deviation in either direction. The mean for this example was about 49.2 and the standard deviation was 17.
We have: 49.2 - 17 = 32.2 and 49.2 + 17 = 66.2
What this means is that most of the patrons probably spend between $32.20 and $66.20.
The sample standard deviation will be denoted by s and the population standard deviation will be denoted by the Greek letter σ.
The sample variance will be denoted by s2 and the population variance will be denoted by σ2.
The variance and standard deviation describe how spread out the data is. If the data all lies close to the mean, then the standard deviation will be small, while if the data is spread out over a large range of values, s will be large. Having outliers will increase the standard deviation.
17) What is Data Cleaning? Discuss various ways of handling missing values during data cleaning.
OR Explain Data Cleaning process for missing values & Noisy data.
OR Explain the data pre- processing required to handle missing data and noisy data during the process of data mining.
OR List and describe methods for handling missing values in data cleaning.
Ans. Real-world data tend to be incomplete, noisy, and inconsistent. Data cleaning (or data cleansing) routines attempt to fill in missing values, smooth out noise while identifying outliers, and correct inconsistencies in the data.
Missing Values: Imagine that you need to analyze AllElectronics sales and customer data. You note that many tuples have no recorded value for several attributes such as customer income. How can you go about filling in the missing values for this attribute? Let’s look at the following methods.
Ignore the tuple: This is usually done when the class label is missing (assuming the mining task involves classification). This method is not very effective, unless the tuple contains several attributes with missing values. It is especially poor when the percentage of missing values per attribute varies considerably.
By ignoring the tuple, we do not make use of the remaining attributes values in the tuple. Such data could have been useful to the task at hand.
Fill in the missing value manually: In general, this approach is time consuming and may not be feasible given a large data set with many missing values.
Use a global constant to fill in the missing value: Replace all missing attribute values by the same constant such as a label like “Unknown” or 1. If missing values are replaced by, say, “Unknown,” then the mining program may mistakenly think that they form an interesting concept, since they all have a value in common—that of “Unknown.” Hence, although this method is simple, it is not foolproof.
Use a measure of central tendency for the attribute (e.g., the mean or median) to fill in the missing value: For normal (symmetric) data distributions, the mean can be used, while skewed data distribution should employ the median.
For example, suppose that the data distribution regarding the income of AllElectronics customers is symmetric and that the mean income is $56,000. Use this value to replace the missing value for income.
Use the attribute mean or median for all samples belonging to the same class as the given tuple: For example, if classifying customers according to credit risk, we may replace the missing value with the mean income value for customers in the same credit risk category as that of the given tuple. If the data distribution for a given class is skewed, the median value is a better choice.
Use the most probable value to fill in the missing value: This may be determined with regression, inference-based tools using a Bayesian formalism, or decision tree induction. For example, using the other customer attributes in your data set, you may construct a decision tree to predict the missing values for income.
Noisy Data: Noise is a random error or variance in a measured variable. Given a numeric attribute such as say, price, how can we “smooth” out the data to remove the noise? Let’s look at the following data smoothing techniques.
Binning: Binning methods smooth a sorted data value by consulting its “neighborhood,” that is, the values around it. The sorted values are distributed into a number of “buckets,” or bins. Because binning methods consult the neighborhood of values, they perform local smoothing.
Figure 1 illustrates some binning techniques. In this example, the data for price are first sorted and then partitioned into equal-frequency bins of size 3 (i.e., each bin contains three values).
In smoothing by bin means, each value in a bin is replaced by the mean value of the bin.
For example, the mean of the values 4, 8, and 15 in Bin 1 is 9. Therefore, each original value in this bin is replaced by the value 9. Similarly, smoothing by bin medians can be employed, in which each bin value is replaced by the bin median. In smoothing by bin boundaries, the minimum and maximum values in a given bin are identified as the bin boundaries. Each bin value is then replaced by the closest boundary value. In general, the larger the width, the greater the effect of the smoothing. Alternatively, bins may be equal width, where the interval range of values in each bin is constant.
Sorted data for price (in dollars): 4, 8, 15, 21, 21, 24, 25, 28, 34
Regression: Data smoothing can also be done by regression, a technique that conforms data values to a function. Linear regression involves finding the “best” line to fit two attributes (or variables) so that one attribute can be used to predict the other.
Multiple linear regression is an extension of linear regression, where more than two attributes are involved and the data are fit to a multidimensional surface.
Outlier analysis: Outliers may be detected by clustering, for example, where similar values are organized into groups, or “clusters.” Intuitively, values that fall outside of the set of clusters may be considered outliers.
18) Explain Data Transformation Strategies in data mining.
Ans. In data transformation, the data are transformed or consolidation to forms appropriate for mining. Strategies for data transformation include the following:
Smoothing, which works to remove noise from the data. Techniques include binning, regression, and clustering.
Attribute construction (or feature construction), where new attributes are constructed and added from the given set of attributes to help the mining process.
Aggregation, where summary or aggregation operations are applied to the data. For example, the daily sales data may be aggregated so as to compute monthly and annual total amounts. This step is typically used in constructing a data cube for data analysis at multiple abstraction levels.
Normalization, where the attribute data are scaled so as to fall within a smaller range, such as−1.0
to 1.0, or 0.0 to 1.0.
Example: Data Transformation -2, 32, 100, 59, 48
Discretization, where the raw values of a numeric attribute (e.g. Age) are replaced by interval labels (e.g., 0–10, 11–20, etc.) or conceptual labels (e.g., youth, adult, senior). The labels, in turn, can be recursively organized into higher-level concepts, resulting in a concept hierarchy for the numeric attribute. Figure 2 shows a concept hierarchy for the attribute price. More than one concept hierarchy can be defined for the same attribute to accommodate the needs of various users.
Fig. 2 A concept hierarchy for the attribute price, where an interval ($X... $Y] denotes the range from $X (exclusive) to $Y (inclusive).
Concept hierarchy generation for nominal data, where attributes such as street can be generalized to higher-level concepts, like city or country. Many hierarchies for nominal attributes are implicit within the database schema and can be automatically defined at the schema definition level.
19)What is Data Reduction & Explain Techniques used in data reduction.
Ans. Data reduction techniques can be applied to obtain a reduced representation of the data set that is much smaller in volume, yet closely maintains the integrity of the original data. That is, mining on the reduced data set should be more efficient yet produce the analytical results.
Strategies for data reduction include the following:
Data cube aggregation, where aggregation operations are applied to the data in the construction of a data cube.
Attribute subset selection: where irrelevant, weakly relevant, or redundant attributes or dimensions may be detected and removed.
Dimensionality reduction: where encoding mechanisms are used to reduce the data set size.
Numerosity reduction: where the data are replaced or estimated by alternative, smaller data representations such as parametric models (which need store only the model parameters instead of the actual data) or nonparametric methods such as clustering, sampling, and the use of histograms.
Discretization and concept hierarchy generation: where raw data values for attributes are replaced by ranges or higher conceptual levels. Data discretization is a form of numerosity reduction that is very useful for the automatic generation of concept hierarchies. Discretization and concept hierarchy generation are powerful tools for data mining, in that they allow the mining of data at multiple levels of abstraction.
20) Explain Apriori Algorithm with an example and also explain methods to Improve Apriori’s Efficiency.
Ans. Purpose: The Apriori Algorithm is an influential algorithm for mining frequent itemsets for boolean association rules. Key Concepts:
• Frequent Itemsets: The sets of item which has minimum support (denoted by Li for ith-Itemset).
• Apriority Property: Any subset of frequent itemset must be frequent.
• Join Operation: To find Lk, a set of candidate k-itemset is generated by joining Lk-1 itself.
o Find the frequent item sets: the sets of items that have minimum support – A subset of a frequent itemset must also be a frequent itemset (Apriori Property)
o i.e., if {AB} is a frequent itemset, both {A} and {B} should be a frequent itemset – Iteratively find frequent itemsets with cardinality from 1 to k (k-itemset)
o Use the frequent itemsets to generate association rules.
The Apriori Algorithm : Pseudo code
o Join Step: C k is generated by joining Lk-1with itself
o Prune Step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset
• Pseudo-code:
Ck: Candidate itemset of
size k Lk: frequent itemset
of size k L1= {frequent
items};
for (k = 1; Lk != ∅; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
Increment the count of all candidates in
Ck+1 That are contained in t
Lk+1 = candidates in Ck+1 with min_support
End-
return 𝖴k Lk;
Example :
o Consider a database, D, consisting of 9 transactions.
o Suppose min. support count required is 2
(i.e. min_sup = 2/9 = 22 %)
o Let minimum confidence required is 70%.
o We have to first find out the frequent itemset using Apriori algorithm.
o Then, Association rules will be generated using min. support & min. confidence.
Step 1: Generating 1-itemset Frequent Pattern:
o The set of frequent 1-itemsets, L1, consists of the candidate 1- itemsets satisfying minimum support.
o In the first iteration of the algorithm, each item is a member of the set of candidate.
Step 2: Generating 2-itemset Frequent Pattern:
o To discover the set of frequent 2-itemsets, L2, the algorithm uses L1 Join L1 to generate a candidate set of 2-itemsets, C2.
o Next, the transactions in D are scanned and the support count for each candidate itemset in C2 is accumulated (as shown in the middle table).
o The set of frequent 2-itemsets, L2, is then determined, consisting of those candidate 2-itemsets in C2 having minimum support.
o Note: We haven’t used Apriori Property yet.
Step 3: Generating 3-itemset Frequent Pattern:
o The generation of the set of candidate 3-itemsets, C3 , involves use of the Apriori Property.
o In order to find C3, we compute L2 Join L2.
o C3 = L2 join L2 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, {I2, I4, I5}}.
o Now, Join step is complete and Prune step will be used to reduce the size of C3. Prune step helps to avoid heavy computation due to large Ck.
o Based on the Apriori property that all subsets of a frequent itemset must also be frequent, we can determine that four latter candidates cannot possibly be frequent. How ?
o For example, lets take {I1, I2, I3}. The 2-item subsets of it are {I1, I2}, {I1, I3} & {I2, I3}. Since all 2- item subsets of {I1, I2, I3} are members of L2, We will keep {I1, I2, I3} in C3.
o Lets take another example of {I2, I3, I5} which shows how the pruning is performed. The 2-item subsets are {I2, I3}, {I2, I5} & {I3,I5}.
o But, {I3, I5} is not a member of L2 and hence it is not frequent violating Apriori Property. Thus We will have to remove {I2, I3, I5} from C3.
o Therefore, C3 = {{I1, I2, I3}, {I1, I2, I5}} after checking for all members of result of Join operation for Pruning.
o Now, the transactions in D are scanned in order to determine L3, consisting of those candidates 3- itemsets in C3 having minimum support.
Step 4: Generating 4-itemset Frequent Pattern:
o The algorithm uses L3 Join L3 to generate a candidate set of 4-itemsets, C4. Although the join results in {{I1, I2, I3, I5}}, this itemset is pruned since its subset {{I2, I3, I5}} is not frequent.
o Thus, C4 = φ, and algorithm terminates, having found all of the frequent items. This completes our Apriori Algorithm. What’s Next?
o These frequent itemsets will be used to generate strong association rules (where strong association rules satisfy both minimum support & minimum confidence).
Step 5: Generating Association Rules from Frequent Itemsets
Procedure:
o For each frequent itemset “l”, generate all nonempty subsets of l.
o For every nonempty subset s of l, output the rule “s -> (l-s)” if support_count(l) /
support_count(s) >= min_conf where min_conf is minimum confidence threshold.
Back to Example:
o We had L = {{I1}, {I2}, {I3}, {I4}, {I5}, {I1, I2}, {I1, I3}, {I1, I5}, {I2, I3}, {I2, I4}, {I2, I5}, {I1, I2, I3}, {I1, I2, I5}}.
o Let’s take l = {I1, I2, I5}. – It’s all nonempty subsets are {I1, I2}, {I1, I5}, {I2, I5}, {I1}, {I2}, {I5}.
o Let minimum confidence threshold is, say 70%.
o The resulting association rules are shown below, each listed with its confidence.
o R1: I1 ^ I2 -> I5 Confidence = sc{I1, I2, I5}/sc{I1,I2} = 2/4 = 50% (R1 is Rejected)
o R2: I1 ^ I5 -> I2 Confidence = sc{I1, I2, I5}/sc{I1,I5} = 2/2 = 100% (R2 is Selected)
o R3: I2 ^ I5 -> I1 Confidence = sc{I1, I2, I5}/sc{I2,I5} = 2/2 = 100% (R3 is Selected)
o R4: I1 -> I2 ^ I5 Confidence = sc{I1, I2, I5}/sc{I1} = 2/6 = 33% (R4 is Rejected)
o R5: I2 -> I1 ^ I5 Confidence = sc{I1, I2, I5}/{I2} = 2/7 = 29% (R5 is Rejected)
o R6: I5 -> I1 ^ I2 Confidence = sc{I1, I2, I5}/ {I5} = 2/2 = 100% (R6 is Selected)
o In this way, we have found three strong association rules.
Methods to Improve Apriori’s Efficiency
o Hash-based itemset counting: A k-itemset whose corresponding hashing bucket count is below the threshold cannot be frequent.
o Transaction reduction: A transaction that does not contain any frequent k-itemset is useless in subsequent scans.
o Partitioning: Any itemset that is potentially frequent in DB must be frequent in at least one of the partitions of DB.
o Sampling: mining on a subset of given data, lower support threshold + a method to determine the completeness.
o Dynamic itemset counting: add new candidate itemsets only when all of their subsets are estimated to be frequent.
20) Explain Concept of Market Basket Analysis.
Ans. Market Basket Analysis is a modelling technique based upon the theory that if you buy a certain group of items, you are more (or less) likely to buy another group of items.
For example, if you are in a store and you buy a milk and don't buy a bread, you are more likely to buy eggs at the same time than somebody who didn't buy bread.
The set of items a customer buys is referred to as an itemset, and market basket analysis seeks to find relationships between purchases.
Typically, the relationship will be in the form of a rule:
e.g IF {milk, eggs} THEN {bread}.
The probability that a customer will buy milk without an eggs (i.e. that the antecedent is true) is referred to as the support for the rule. The conditional probability that a customer will purchase bread is referred to as the confidence.
The algorithms for performing market basket analysis are fairly straightforward. The complexities mainly arise in exploiting taxonomies, avoiding combinatorial explosions (a supermarket may stock 10,000 or more line items), and dealing with the large amounts of transaction data that may be available.
A major difficulty is that a large number of the rules found may be trivial for anyone familiar with the business. Although the volume of data has been reduced, we are still asking the user to find a needle in a haystack.
Requiring rules to have a high minimum support level and a high confidence level risks missing any exploitable result we might have found. One partial solution to this problem is differential market basket analysis, as described below.
❖ How is it used?
o In retailing, most purchases are bought on impulse. Market basket analysis gives clues as to what a customer might have bought if the idea had occurred to them.
o As a first step, therefore, market basket analysis can be used in deciding the location and promotion of goods inside a store. If, as has been observed, purchasers of Barbie dolls have are more likely to buy candy, then high-margin candy can be placed near to the Barbie doll display. Customers who would have bought candy with their Barbie dolls had they thought of it will now be suitably tempted.
o But this is only the first level of analysis. Differential market basket analysis can find interesting results and can also eliminate the problem of a potentially high volume of trivial results.
o In differential analysis, we compare results between different stores, between customers in different demographic groups, between different days of the week, different seasons of the year, etc.
o If we observe that a rule holds in one store, but not in any other (or does not hold in one store, but holds in all others), then we know that there is something interesting about that store. Perhaps its clientele is different, or
perhaps it has organized its displays in a novel and more lucrative way. Investigating such differences may yield useful insights which will improve company sales.
❖ Application Areas:
o Although Market Basket Analysis conjures up pictures of shopping carts and supermarket shoppers, it is important to realize that there are many other areas in which it can be applied. These include:
• Analysis of credit card purchases.
• Analysis of telephone calling patterns.
• Identification of fraudulent medical insurance claims. (Consider cases where common rules are broken).
• Analysis of telecom service purchases.
Best of Luck
Comments