.Net « Ali Tarhini

The data mining tutorial is designed to walk you through the process of creating data mining models in Microsoft Sql server 2008. The data mining algorithms and tools in Sql server 2008 make it easy to build a comprehensive solution for a variety of projects, including market basket analysis, forecasting analysis, and targeted mailing analysis. The scenarios for these solutions are explained in greater detail later in the tutorial.

The most visible components in Sql server 2008 are the workspaces that you use to create and work with data mining models. The online analytical processing (OLAP) and data mining tools are consolidated into two working environments: Business Intelligence Development Studio and SQL Server Management Studio. Using Business Intelligence Development Studio, you can develop an Analysis Services project disconnected from the server. When the project is ready, you can deploy it to the server. You can also work directly against the server. The main function of SQL Server Management Studio is to manage the server. Each environment is described in more detail later in this introduction. For more information on choosing between the two environments, see “Choosing Between SQL Server Management Studio and Business Intelligence Development Studio” in SQL Server Books Online.

All of the data mining tools exist in the data mining editor. Using the editor you can manage mining models, create new models, view models, compare models, and create predictions based on existing models.

After you build a mining model, you will want to explore it, looking for interesting patterns and rules. Each mining model viewer in the editor is customized to explore models built with a specific algorithm. For more information about the viewers, see “Viewing a Data Mining Model” in SQL Server Books Online.

Often your project will contain several mining models, so before you can use a model to create predictions, you need to be able to determine which model is the most accurate. For this reason, the editor contains a model comparison tool called the Mining Accuracy Chart tab. Using this tool you can compare the predictive accuracy of your models and determine the best model.

To create predictions, you will use the Data Mining Extensions (DMX) language. DMX extends SQL, containing commands to create, modify, and predict against mining models. For more information about DMX, see “Data Mining Extensions (DMX) Reference” in SQL Server Books Online. Because creating a prediction can be complicated, the data mining editor contains a tool called Prediction Query Builder, which allows you to build queries using a graphical interface. You can also view the DMX code that is generated by the query builder.

ou use to work with and create data mining models are the mechanics by which they are created. The key to creating a mining model is the data mining algorithm. The algorithm finds patterns in the data that you pass it, and it translates them into a mining model — it is the engine behind the process. Sql server 2008 includes nine algorithms:

Microsoft Decision Trees

Microsoft Clustering
Microsoft Naïve Bayes
Microsoft Sequence Clustering
Microsoft Time Series
Microsoft Association
Microsoft Neural Network
Microsoft Linear Regression
Microsoft Logistic Regression

Using a combination of these nine algorithms, you can create solutions to common business problems. These algorithms are described in more detail later in this tutorial.

Some of the most important steps in creating a data mining solution are consolidating, cleaning, and preparing the data to be used to create the mining models. Sql server 2008 includes the Data Transformation Services (DTS) working environment, which contains tools that you can use to clean, validate, and prepare your data. For more information on using DTS in conjunction with a data mining solution, see “DTS Data Mining Tasks and Transformations” in SQL Server Books Online.

In order to demonstrate the SQL Server data mining features, this tutorial uses a new sample database called AdventureWorksDW. The database is included with Sql server 2008, and it supports OLAP and data mining functionality. In order to make the sample database available, you need to select the sample database at the installation time in the “Advanced” dialog for component selection.

If you are new to data mining, download “Preparing and Mining Data with Microsoft SQL Server 2000 and Analysis Services” (msdn.microsoft.com/library/default.asp?url=/servers/books/sqlserver/mining.asp).

AdventureWorksDW is based on a fictional bicycle manufacturing company named Adventure Works Cycles. Adventure Works produces and distributes metal and composite bicycles to North American, European, and Asian commercial markets. The base of operations is located in Bothell, Washington with 500 employees, and several regional sales teams are located throughout their market base.

Adventure Works sells products wholesale to specialty shops and to individuals through the Internet. For the data mining exercises, you will work with the AdventureWorksDW Internet sales tables, which contain realistic patterns that work well for data mining exercises.

For more information on Adventure Works Cycles see “Sample Databases and Business Scenarios” in SQL Server Books Online.

Database Details

The Internet sales schema contains information about 9,242 customers. These customers live in six countries, which are combined into three regions:

North America (83%)
Europe (12%)
Australia (7%)

The database contains data for three fiscal years: 2002, 2003, and 2004.

The products in the database are broken down by subcategory, model, and product.

Business Intelligence Development Studio

Business Intelligence Development Studio is a set of tools designed for creating business intelligence projects. Because Business Intelligence Development Studio was created as an IDE environment in which you can create a complete solution, you work disconnected from the server. You can change your data mining objects as much as you want, but the changes are not reflected on the server until after you deploy the project.

Working in an IDE is beneficial for the following reasons:

You have powerful customization tools available to configure Business Intelligence Development Studio to suit your needs.
You can integrate your Analysis Services project with a variety of other business intelligence projects encapsulating your entire solution into a single view.
Full source control integration enables your entire team to collaborate in creating a complete business intelligence solution.

The Analysis Services project is the entry point for a business intelligence solution. An Analysis Services project encapsulates mining models and OLAP cubes, along with supplemental objects that make up the Analysis Services database. From Business Intelligence Development Studio, you can create and edit Analysis Services objects within a project and deploy the project to the appropriate Analysis Services server or servers.

If you are working with an existing Analysis Services project, you can also use Business Intelligence Development Studio to work connected the server. In this way, changes are reflected directly on the server without having to deploy the solution.

SQL Server Management Studio

SQL Server Management Studio is a collection of administrative and scripting tools for working with Microsoft SQL Server components. This workspace differs from Business Intelligence Development Studio in that you are working in a connected environment where actions are propagated to the server as soon as you save your work.

After the data has been cleaned and prepared for data mining, most of the tasks associated with creating a data mining solution are performed within Business Intelligence Development Studio. Using the Business Intelligence Development Studio tools, you develop and test the data mining solution, using an iterative process to determine which models work best for a given situation. When the developer is satisfied with the solution, it is deployed to an Analysis Services server. From this point, the focus shifts from development to maintenance and use, and thus SQL Server Management Studio. Using SQL Server Management Studio, you can administer your database and perform some of the same functions as in Business Intelligence Development Studio, such as viewing, and creating predictions from mining models.

Data Transformation Services

Data Transformation Services (DTS) comprises the Extract, Transform, and Load (ETL) tools in Sql server 2008. These tools can be used to perform some of the most important tasks in data mining: cleaning and preparing the data for model creation. In data mining, you typically perform repetitive data transformations to clean the data before using the data to train a mining model. Using the tasks and transformations in DTS, you can combine data preparation and model creation into a single DTS package.

DTS also provides DTS Designer to help you easily build and run packages containing all of the tasks and transformations. Using DTS Designer, you can deploy the packages to a server and run them on a regularly scheduled basis. This is useful if, for example, you collect data weekly data and want to perform the same cleaning transformations each time in an automated fashion.

You can work with a Data Transformation project and an Analysis Services project together as part of a business intelligence solution, by adding each project to a solution in Business Intelligence Development Studio.

Data mining algorithms are the foundation from which mining models are created. The variety of algorithms included in Sql server 2008 allows you to perform many types of analysis. For more specific information about the algorithms and how they can be adjusted using parameters, see “Data Mining Algorithms” in SQL Server Books Online.

Microsoft Decision Trees

The Microsoft Decision Trees algorithm supports both classification and regression and it works well for predictive modeling. Using the algorithm, you can predict both discrete and continuous attributes.

In building a model, the algorithm examines how each input attribute in the dataset affects the result of the predicted attribute, and then it uses the input attributes with the strongest relationship to create a series of splits, called nodes. As new nodes are added to the model, a tree structure begins to form. The top node of the tree describes the breakdown of the predicted attribute over the overall population. Each additional node is created based on the distribution of states of the predicted attribute as compared to the input attributes. If an input attribute is seen to cause the predicted attribute to favor one state over another, a new node is added to the model. The model continues to grow until none of the remaining attributes create a split that provides an improved prediction over the existing node. The model seeks to find a combination of attributes and their states that creates a disproportionate distribution of states in the predicted attribute, therefore allowing you to predict the outcome of the predicted attribute.

Microsoft Clustering

The Microsoft Clustering algorithm uses iterative techniques to group records from a dataset into clusters containing similar characteristics. Using these clusters, you can explore the data, learning more about the relationships that exist, which may not be easy to derive logically through casual observation. Additionally, you can create predictions from the clustering model created by the algorithm. For example, consider a group of people who live in the same neighborhood, drive the same kind of car, eat the same kind of food, and buy a similar version of a product. This is a cluster of data. Another cluster may include people who go to the same restaurants, have similar salaries, and vacation twice a year outside the country. Observing how these clusters are distributed, you can better understand how the records in a dataset interact, as well as how that interaction affects the outcome of a predicted attribute.

rosoft Naïve Bayes

The Microsoft Naïve Bayes algorithm quickly builds mining models that can be used for classification and prediction. It calculates probabilities for each possible state of the input attribute, given each state of the predictable attribute, which can later be used to predict an outcome of the predicted attribute based on the known input attributes. The probabilities used to generate the model are calculated and stored during the processing of the cube. The algorithm supports only discrete or discretized attributes, and it considers all input attributes to be independent. The Microsoft Naïve Bayes algorithm produces a simple mining model that can be considered a starting point in the data mining process. Because most of the calculations used in creating the model are generated during cube processing, results are returned quickly. This makes the model a good option for exploring the data and for discovering how various input attributes are distributed in the different states of the predicted attribute.

Microsoft Time Series

The Microsoft Time Series algorithm creates models that can be used to predict continuous variables over time from both OLAP and relational data sources. For example, you can use the Microsoft Time Series algorithm to predict sales and profits based on the historical data in a cube.

Using the algorithm, you can choose one or more variables to predict, but they must be continuous. You can have only one case series for each model. The case series identifies the location in a series, such as the date when looking at sales over a length of several months or years.

A case may contain a set of variables (for example, sales at different stores). The Microsoft Time Series algorithm can use cross-variable correlations in its predictions. For example, prior sales at one store may be useful in predicting current sales at another store.

Microsoft Association

The Microsoft Association algorithm is specifically designed for use in market basket analyses. The algorithm considers each attribute/value pair (such as product/bicycle) as an item. An itemset is a combination of items in a single transaction. The algorithm scans through the dataset trying to find itemsets that tend to appear in many transactions. The SUPPORT parameter defines how many transactions the itemset must appear in before it is considered significant. For example, a frequent itemset may contain {Gender=”Male”, Marital Status = “Married”, Age=”30-35″}. Each itemset has a size, which is number of items it contains. In this case, the size is 3.

Often association models work against datasets containing nested tables, such as a customer list followed by a nested purchases table. If a nested table exists in the dataset, each nested key (such as a product in the purchases table) is considered an item.

that C is predicted by A and B. The probability threshold is a parameter that determines the minimum probability before a rule can be considered. The probability is also called “confidence” in data mining literature.

Association models are also useful for cross sell or collaborative filtering. For example, you can use an association model to predict items a user may want to purchase based on other items in their basket.

Microsoft Sequence Clustering

The Microsoft Sequence Clustering algorithm analyzes sequence-oriented data that contains discrete-valued series. Usually the sequence attribute in the series holds a set of events with a specific order (such as a click path). By analyzing the transition between states of the sequence, the algorithm can predict future states in related sequences.

The Microsoft Sequence Clustering algorithm is a hybrid of sequence and clustering algorithms. The algorithm groups multiple cases with sequence attributes into segments based on similarities of these sequences. A typical usage scenario for this algorithm is Web customer analysis for a portal site. A portal Web site has a set of affiliated domains such as News, Weather, Money, Mail, and Sport. Each Web customer is associated with a sequence of Web clicks on these domains. The Microsoft Sequence Clustering algorithm can group these Web customers into more-or-less homogenous groups based on their navigations patterns. These groups can then be visualized, providing a detailed understanding of how customers are using the site.

Microsoft Neural Network

In Microsoft Sql server 2008 Analysis Services, the Microsoft Neural Network algorithm creates classification and regression mining models by constructing a multilayer perceptron network of neurons. Similar to the Microsoft Decision Trees algorithm provider, given each state of the predictable attribute, the algorithm calculates probabilities for each possible state of the input attribute. The algorithm provider processes the entire set of cases , iteratively comparing the predicted classification of the cases with the known actual classification of the cases. The errors from the initial classification of the first iteration of the entire set of cases is fed back into the network, and used to modify the network’s performance for the next iteration, and so on. You can later use these probabilities to predict an outcome of the predicted attribute, based on the input attributes. One of the primary differences between this algorithm and the Microsoft Decision Trees algorithm, however, is that its learning process is to optimize network parameters toward minimizing the error while the Microsoft Decision Trees algorithm splits rules in order to maximize information gain. The algorithm supports the prediction of both discrete and continuous attributes.

Microsoft Linear Regression

The Microsoft Linear Regression algorithm is a particular configuration of the Microsoft Decision Trees algorithm, obtained by disabling splits (the whole regression formula is built in a single root node). The algorithm supports the prediction of continuous attributes.

Microsoft Logistic Regression

The Microsoft Logistic Regression algorithm is a particular configuration of the Microsoft Neural Network algorithm, obtained by eliminating the hidden layer. The algorithm supports the prediction of both discrete and continuous attributes.

Throughout this tutorial you will work in Business Intelligence Development Studio (as depicted in Figure 1). For more information about working in Business Intelligence Development Studio, see “Using SQL Server Management Studio” in SQL Server Books Online.

Figure 1 Business Intelligence Studio

The tutorial is broken up into three sections: Preparing the SQL Server Database, Preparing the Analysis Services Database, and Building and Working with the Mining Models.

Preparing the SQL Server Database

The AdventureWorksDW database, which is the basis for this tutorial, is installed with SQL Server (not by default, but as an option at installation time) and already contains views that will be used to create the mining models. If it was not installed at the installation time, you can add it by selecting Change button from Control Panel à Add/Remove Programs à Microsoft Sql server 2008. Look for AdventureWorksDW Sample Data Warehouse under Books online and Samples of Workstation Components.

Preparing the Analysis Services Database

Before you begin to create and work with mining models, you must perform the following tasks:

Create a new Analysis Services project
Create a data source.
Create a data source view.

Creating an Analysis Services Project

Each Analysis Services project defines the schema for the objects in a single Analysis Services database. The Analysis Services database is defined by the mining models, OLAP cubes, and supplemental objects that it contains. For more information about Analysis Services projects, see “Creating an Analysis Services Project in Business Intelligence Development Studio” in SQL Server Books Online.

To create an Analysis Services project

Open Business Intelligence Development Studio.
Select New and Project from the File menu.
Select Analysis Services Project as the type for the new project and name it AdventureWorks.
Click Ok.

The new project opens in Business Intelligence Development Studio.

Creating a Data Source

A data source is a data connection that is saved and managed within your project and deployed to your Analysis Services database. It contains the server name and database where your source data resides, as well as any other required connection properties.

To create a data source

Right-click the Data Source project item in Solution Explorer and select New Data Source.
On the Welcome page, click Next.
Click New to add a connection to the AdventureWorksDW database.
The Connection Manager dialog box opens. In the Server name drop-down box, select the server where AdventureWorksDW is hosted (for example, localhost), enter your credentials, and then in the Select the database on the server drop-down box select the AdventureWorksDW database.
Click OK to close the Connection Manager dialog box.
Click Next.
By default the data source is named Adventure Works DW. Click Finish

The new data source, Adventure Works DW, appears in the Data Sources folder in Solution Explorer.

ating a Data Source View

A data source view provides an abstraction of the data source, enabling you to modify the structure of the data to make it more relevant to your project. Using data source views, you can select only the tables that relate to your particular project, establish relationships between tables, and add calculated columns and named views without modifying the original data source.

For more information, see “Working with Data Source Views” in SQL Server Books Online.

To create a data source view

In Solution Explorer, right-click Data Source
View, and then click New Data Source View.
On the Welcome page, click Next.
The Adventure Works DW data source you created in the last step is selected by default in the Relational data sources window. Click Next.
If you want to create a new data source, click New Data Source to launch the Data Source Wizard.
Select the tables in the following list and click the right arrow button to include them in the new data source view:
vAssocSeqLineItems
vAssocSeqOrders
vTargetMail
vTimeSeries
Click Next.
By default the data source view is named Adventure Works DW. Click Finish.

Data Source View Editor opens to display the Adventure Works DW data source view, as shown in Figure 2. Solution Explorer is also updated to include the new data source view. You can now modify the data source view to better work with the data.

Figure 2 Adventure Works DW data source view

Using Data Source View Editor, you can make changes to the way you see the data in the data source. For example, you can change the name of any object to something that may be more relevant to the project. The name in the original data source is not modified, but you can refer to the object by this friendly name in your project.

In order to create the market basket and sequence clustering scenarios, you need to create a new many-to-one relationship between vAssocSeqOrders and vAssocSeqLineItems. Using this relationship you can make vAssocSeqLineItems a nested table of vAssocSeqOrders for creating the models.

To create a new relationship

In the data source view, select OrderNumber from the vAssocSeqLineItems table.
Drag the selected column into the vAssocSeqOrders table, and place it on the OrderNumber column.

A new many-to-one relationship exists between vAssocSeqOrders and vAssocSeqLineItems.

The data mining editor (shown in Figure 4) contains all of the tools and viewers that you will use to build and work with the mining models. For more information about the data mining editor, see “Using the Data Mining Tools” in SQL Server Books Online.

Figure 4 Data mining editor

Throughout this tutorial you will work through the following scenarios:

Targeted mailing
Forecasting
Market basket
Sequence clustering

In the targeted mailing scenario, you will build the models, compare their predictive capabilities using the Mining Accuracy Chart view, and create predictions using Prediction Query Builder. In the other scenarios, you will build and explore the models.

The marketing department of Adventure Works is interested in increasing sales by targeting specific customers for a mailing campaign. By investigating the attributes of known customers, they want to discover some kind of pattern that can be applied to potential customers, which can then be used to predict who is more likely to purchase a product from Adventure Works.

Additionally, the marketing department wants to find any logical groupings of customers already in their database. For example, a grouping may contain customers with similar buying patterns and demographics.

Adventure Works contains a list of past customers and a list of potential customers.

Upon completion of this task, the marketing department will have the following:

A set of mining models that will be able to suggest the most likely customers from a list of potential customers
A clustering of their current customers

In order to complete the scenario, you will use the Microsoft Naïve Bayes, Microsoft Decision Trees, and Microsoft Clustering algorithms. The scenario consists of five tasks:

Create the mining model structure.
Create the mining models.
Explore the mining models.
Test the accuracy of the mining models.
Create predictions from the mining models.

The first step is to use the Mining Model Wizard to create a new mining structure. The Mining Model Wizard also creates an initial mining model based on the Microsoft Decision Trees algorithm.

To create the targeted mailing mining structure

In Solution Explorer, right-click Mining Structures, and then click New Mining Structure.

The Mining Model Wizard opens.
On the Welcome page, click Next.
Click From existing relational database or data warehouse, and then click Next.
Under Which data mining technique do you want to use?, click Microsoft Decision Trees.

You will create several models based on this initial structure, but the initial model is based on the Microsoft Decision Trees algorithm.
Click Next.

By default the Adventure Works DW is selected in the Select Data Source View window. You may click Browse to view the tables in the data source view inside of the wizard.
Click Next.
Select the Case check box next to the vTargetMail table, and then click Next.
Select the Key check box next to the CustomerKey column.

If the source table from the data source view indicates a key, the Mining Model Wizard automatically chooses that column as a key for the model.
Select the Input and Predictable check boxes next to the BikeBuyer column.

This action enables the column for prediction in new datasets. When you indicate that a column is predictable, the Suggest button is enabled. Clicking Suggest opens the Suggest Related Column dialog box, which lists the columns that are most closely related to the predictable column.

The Suggest
Related Columns dialog box orders the attributes by their correlation with the predictable attribute. Columns with a value higher than 0.05 are automatically selected to be included in the model. If you agree with the suggestion, click OK, which marks the selected columns as inputs in the wizard. If you don’t agree, you can either modify the suggestion or click Cancel.
Input check boxes next to the columns listed in the following table.

Age	YearlyIncome	Region
CommuteDistance	HouseOwnerFlag	TotalChildren
EnglishEducation	LastName
EnglishOccupation	MaritalStatus
FirstName	NumberCarsOwned
Gender	NumberChildrenAtHome

You can select multiple columns by using the SHIFT key. Selecting a check box within the selected area specifies the same selection for each column.

Click Next.
In Specify Columns’ Content and Data Type, click Detect.

An algorithm runs that samples numeric data and determines whether the numeric columns contain continuous or discrete values. For example, a column can contain salary information as the actual salary values, which is continuous, or it can contain integers representing encoded salary ranges (1 = < $25,000; 2 = from $25,000 to $50,000, and so on) which is discrete.
Click Next.
In both Mining Structure Name and Mining Model Name, type Targeted Mailing.
Click Finish.

The data mining editor opens, displaying the mining structure named Targeted Mailing that you just created, as shown in Figure 5.

Figure 5 Targeted Mailing mining structure tab

Edit the Mining Models

The initial mining structure only contains a model based on the Microsoft Decision Trees model. In this section, you will define two additional models using the Mining Models tab of the data mining editor: a Microsoft Naïve Bayes model and a Microsoft Clustering model.

To create a Microsoft Clustering model

Click the Mining Models tab.
Right-click Targeted Mailing and then click New Mining Model.
In Model Name, type TM_Clustering.
In Algorithm Name, select Microsoft Clustering.
Click OK.

A new model appears in the Mining Models tab. A Microsoft Clustering model can cluster and predict continuous and discrete attributes. You can modify the column usage and properties for the new model.

Predict has no effect on the model training; it allows you to select that column in a PREDICTION JOIN query. However, the algorithm ignores columns set to PredictOnly when it creates clusters. The statistics for PredictOnly columns in a clustering model are determined as a final pass after the clustering operation is complete. This is beneficial if you want to see how an attribute is distributed across clusters created from other attributes, and it can expose deeper correlations.

To create a Microsoft Naïve Bayes model

Right-click Targeted Mailing, and then click New Mining Model.
In Model Name, type TM_NaiveBayes.
In Algorithm Name, click Microsoft Naïve Bayes.
Click OK.

A dialog box appears with the text explaining that the Microsoft Naïve Bayes algorithm does not support working with the Age, Yearly Income columns, which are continuous, and will be ignored
Click Yes.

A new model appears in the Mining Models tab. Although you can modify the column usage and properties for all of the models in this tab, in this case you can leave them as they are.

Process the Mining Models

Now that the structure and parameters for the mining models are complete, you can deploy and process the models.

To deploy the project and process the mining models

Click F5.

Depending on what account Analysis Services is running under, you may need to change impersonation information of the data source. To change it, open Adventure Works DW.ds from your solution explorer and go to the Impersonation Information tab.

The Analysis Services database is deployed to the server and the mining models are processed. If the database has already been deployed to the server, you can just process the mining models using the following process.

To process the mining models

On the Mining Model menu, select Process.

The Process Mining Structure dialog box opens showing Targeted Mailing in Object list.
Click Run.

The Process Progress dialog box opens, displaying information about model processing. This may take some time, depending on your computer.
After processing is complete, click Close in both dialog boxes.

Note that processing the mining models may take several minutes depending on your computer configuration.

After the models are processed, you can view them using the Mining Model Viewer tab in the data mining editor. Using the Mining Model combo box at the top of the tab, you can examine the models in the mining structure.

Microsoft Decision Trees Model

The Mining Model Viewer tab defaults to opening the Targeted Mailing mining model, the first model in the structure. The Tree viewer contains two tabs, Decision Tree and Dependency Network.

Decision Tree

On the Decision Tree tab, you can examine all of the tree models that make up the Targeted_Mailing model. There is one tree model for each predictable attribute in the model, unless feature selection is invoked. Because your model only contains a single predictable attribute, Bike Buyer, there is only one tree to view. If there were more trees, you could use the Tree box to choose another tree.

The Tree viewer defaults to only showing the first three levels of the tree. If the tree contains less than three levels, the Tree viewer only shows the existing levels. You can view more levels using the Show Level slider or the Default Expansion box. For more information about configuring the Tree viewer, see “Viewing with Tree Viewer” in SQL Server Books Online.

To create the tree shown in Figure 6

Slide Show Level to 5.
In the Background list, click 1.

By changing this setting, you can quickly tell the number of cases for bike buyer equal to 1 that exist in each node. The darker the node, the more cases that exist.

Figure 6 Decision Tree tab of the Targeted Mailing model

Each node in the decision tree displays three pieces of information:

The condition required to reach that node from the node preceding it. You can see the full node path in either the legend or a ToolTip.
A histogram that describes the distribution of states for the predictable column in order of popularity. You can control how many states appear in the histogram using the Histogram control.
The concentration of cases, if the state of the predictable attribute specified in the Background control.

If drillthrough is enabled, you can see the training cases each node supports by right-clicking the node and then clicking Drillthrough.

The Dependency Network tab displays the relationships between the attributes that contribute to the predictive ability of the mining model. The dependency network for the Targeted Mailing model is displayed in Figure 7.

Figure 7 Dependency Network tab of the Targeted Mailing model

The center node in Figure 7, Bike Buyer, represents the predictable attribute in the mining model. Each surrounding node represents an attribute that affects the outcome of the predictable attribute. You can use the slider on the left side of the tab to control the strength of the links that are shown. Moving the slider down means that only the strongest links are shown.

Using the color legend at the bottom of the chart, you can see the nodes that a selected node predicts, or the nodes that the selected node is predicted by.

Use the Mining Model combo box at the top of the node to switch to the TM_Clustering model. The viewer for this model, the Cluster viewer, contains four tabs: Cluster Diagram, Cluster Profiles, Cluster
Characteristics, and Cluster Discrimination. By default, the viewer displays the Cluster
Diagram tab when it first opens.

For more information about using the Cluster viewer, see “Viewing with Cluster Viewer” in SQL Server Books Online.

Using the Cluster Diagram tab, you can explore the relationships between the clusters discovered by the algorithm. The lines between the clusters represent “closeness” and are shaded based on how similar the clusters are. The actual color of the cluster represents the frequency of the variable and state (selected in the Shading Variable and State boxes at the top of the node) in each cluster. The default variable is population, but you can change this to any attribute in the model to find which clusters contain members with the attributes you want quickly. Using the slider on the left, you can filter out the weaker links and find the clusters that are the closest.

For example, set Shading Variable to Bike Buyer and State to 1. As shown in Figure 8, Cluster 5 contains the highest density of bike buyers. The strongest relationship exists between Cluster 4 and Cluster 7.

Figure 8 Cluster Diagram tab of the TM_Clustering model

The Cluster Profiles tab provides an overall view of the TM_Clustering model. As Figure 9 shows, the Cluster Profiles tab contains a column for each cluster in the model. The first column lists the attributes that are associated with at least one cluster. The distribution of an attribute’s states for each cluster fills out the rest of the viewer. The distribution of a discrete variable is shown as a colored bar with the maximum number of bars displayed in the Bars per histogram box. Continuous attributes are displayed using a diamond chart, which represents the mean and standard deviation in each cluster.

Figure 9 Cluster Profiles tab of the TM_Clustering model

ter Characteristics

Using the Cluster Characteristics tab, you can examine the characteristics that make up a cluster in more detail. For example, in Figure 10, you can see that people in Cluster 5 (the bike buyers) tend to have such characteristics as: they commute short distances (0-1 mile), they do not own a car, and they are married.

Figure 10 Cluster Characteristics tab of the TM_Clustering model

Using the Cluster Discrimination tab, you can explore the characteristics that distinguish one cluster from another. After you select two clusters from the First cluster and Second cluster boxes, the viewer determines the differences and displays them ordered by the attributes that distinguish the clusters the most.

Figure 11 compares Cluster 5 and Cluster 10 from the TM_Clustering model. Cluster 5 contains the highest density of bike buyers, and Cluster 10 contains the lowest density of bike buyers. For example, people in Cluster 10 tend to be from North America and younger (23-31) and people in Cluster 5 tend to be from Europe with a short commute distance (0-1 mile).

Figure 11 Cluster Discrimination tab of the TM_Clustering model

Use the Mining Model combo box to switch to the TM_NaiveBayes model. The viewer for this model, the Naïve Bayes viewer, contains four tabs: Dependency Network, Attribute Profiles, Attribute Characteristics, and Attribute Discrimination.

For more information about using the Naïve Bayes viewer, see “Viewing with Naïve Bayes Viewer” in SQL Server Books Online.

Dependency Network

The Dependency Network tab works the same way as the Dependency Network tab for the Tree viewer. Each node in the viewer represents an attribute, and the lines between nodes represent relationships. Figure 12 displays all of the attributes that affect the state of the predictable attribute, Bike Buyer.

Figure 12 Dependency Network tab for the TM_NaïveBayes model

As you lower the slider, only the attributes that have the greatest effect on the Bike Buyer column remain. Using this technique, you find that the number of cars owned is the greatest factor in determining whether someone is a bike buyer.

The Attribute Profiles tab describes how different states of the input attributes affect the outcome of the predictable attribute.

In the Predictable box, click Bike Buyer. The attributes that affect the state of the predictable attribute are listed along with values of each state of the input attributes, and their distributions in each state of the predictable attribute.

Figure 13 shows the Attribute Profiles tab for the Bike Buyer column in the TM_NaiveBayes model.

Figure 13 Attribute Profiles tab for an attribute in the TM_NaïveBayes model

Using the Attribute Characteristics tab, you can select an attribute and value to see how frequently values for other attributes appear in the selected value cases.

In Attribute, click Bike Buyer, and in Value, click 1.

For example, Figure 14 shows that people who have no children at home tend to buy the most bicycles.

Figure 14 Attribute Characteristics tab for an attribute in the TM_NaïveBayes model

Using the Attribute Discrimination tab, you can investigate the relationship between two discrete values of the selected predictable attribute and other attribute values. Because the TM_NaiveBayes model only has two states, 1 and 0, you do not have to make any changes to the viewer.

For example, Figure 15 shows that people who do not own cars tend to buy bicycles, and people who own two cars tend not to buy bicycles.

Figure 15 Attribute Characteristics tab for an attribute value in the TM_NaïveBayes model

You have now processed and explored the mining models. But how well do they perform predictions? Does one of the targeted mailing models perform better than the others?

Using the Mining Accuracy Chart tab, you can calculate how well each of the models predicts and compare their results directly against each other. This method of comparison is also sometimes called a lift chart. The Mining Accuracy Chart tab uses test data, which is data separated from the original training dataset, to compare predictions against a known result. The results are then sorted and plotted on a graph, along with an ideal model to show how well the model performs at predictions. An ideal model represents a plot for a theoretical model that predicts the result correctly 100 percent of the time.

The lift chart is important because it helps to distinguish between nearly identical models in a structure, determining which provides the best predictions. Similarly, it shows which algorithm types perform the best predictions for a given situation. For more information about using the Mining Accuracy Chart tab, see “Comparing Data Mining Models with the Lift Chart” in SQL Server Books Online.

Open the tab, which is shown in Figure 16, by clicking Mining Accuracy Chart.

Figure 16 Mining Accuracy Chart tab

racy chart, you must perform the following tasks:

Map the columns of the model to the columns in the input dataset.

Filter the input data.

Select the models to compare and the predictable columns and values.

Note Before you can use the mining accuracy chart, you must deploy and process the mining models.

Mapping the Input Columns

The first step is to map the columns in the model to the columns in the test data. If the column names map directly, the tool automatically creates relationships.

To map the input columns to the mining structure

In the Select Input Table(s) box, click Select case table.

The Select Table dialog box opens, where you choose an input table that contains the test data that you want to use in the prediction queries to determine the accuracy of the models. For example, if you held out some TargetMail rows independent from vTargetMail that was used to process the models, you might select that table. However, in this tutorial we use the same data used to process the models as the input table.
In the Select Table dialog box, select Adventure Works DW from data source list.
Select vTargetMail.from Table/View list and click OK.

The columns the mining structure are automatically mapped to the columns with the same name in the input table, as shown in Figure 17.

Figure 17 Mapped columns in the Mining Accuracy Chart tab

A prediction query is generated for each model in the structure based on the column mappings. You can delete a mapping by selecting the line that links the columns in Mining Structure and Select Input Table(s) and then pressing DELETE. You can also manually create mappings by clicking a column in Select Input Table(s) and dragging it onto the corresponding column in Mining Structure.

Filtering Input Rows

You can use the grid under Filter the input data used to generate the lift chart to filter the input data. You can drag columns from Select Input Table(s) to the grid, or you can select the values from combo boxes. For example, if you want to limit the input rows to those where the YearlyIncome column is greater than x, in the Field column, select YearlyIncome, and then in the Criteria/Argument column, type >x.

You will not filter the data in this tutorial.

The next step is to select the models that you want to include in the lift chart and the predictable column that they will be compared against. By default, all of the models in the mining structure are selected. You can choose not to include a model, but for this tutorial, leave them as they are.

You can create two types of accuracy charts. If you select a predictable value, you will see a chart like the one in Figure 18, which shows how much lift the model provides. If you do not include a Predict Value, as shown in Figure 19, the chart will show how accurate the model is.

To show the lift of the models

For each remaining model, in Predictable Column Name, click Bike Buyer.
For each remaining model, in the Predict Value column, click 1.

To show the accuracy of the models

In Predictable Column Name, click Bike Buyer.

Leave the Predict Value column empty.

If the Synchronize Prediction Columns and Values check box is selected, the predictable column is synchronized for each mining model in the mining structure.

Note The mining model columns listed in the Predictable Column Name box are restricted to columns that have the usage type set to Predict or Predict
Only, and where the mining structure column on which this mining column is based has a content type of Discrete or Discretized.

In some advanced scenarios, you may want to generate a lift chart that includes a predictable column in two mining models that are not based on the same structure column but contain the same data. If you clear the Synchronize Prediction Columns and Values check box, you can select any valid predictable column and value. The results are plotted together, regardless of whether they make sense.

Click the Lift Chart tab to view the lift chart. When you click the tab, a prediction query runs against the server and database for the mining structure and input table. The predicted results are compared to the actual values that is known and sorted by probability, and the results are plotted on the graph. For more information about using the chart, see “Lift Chart” in SQL Server Books Online.

If you specified a predictable value, the lift chart is plotted as shown in Figure 18.

Figure 18 Lift provided by each model plotted against the ideal model

value, the lift chart shows the accuracy of the mining model predictions as shown in Figure 19.

Figure 19 Accuracy of each model plotted against the ideal model

Now that you are satisfied with the mining models, you can begin to create DMX prediction queries using Prediction Query Builder. Prediction Query Builder is similar to Access Query Builder, in which you use drag-and-drop operations to build the queries. The tool contains three different views:

Design

Query

Result

Figure 20 Default view of Prediction Query Builder

Using the Design and Query views, you can build and look at your query. You can then execute and view the results of the query in the Result view.

For more information about using Prediction Query Builder, see “Creating Prediction Queries Against Data mining Models” in SQL Server Books Online.

The first step in creating the query is to select a mining model and input table.

To select a model and input table

In Mining Model, click Select model.

The Select Mining Model dialog box opens. By default, the first mining model in the mining structure is selected.
Navigate through the tree to Targeted Mailing, and then click Targeted Mailing.
In the Select Input Table(s) box, click Select case table.

The Select Table dialog box opens.
Navigate through the tree and select the vTargetMail table in the AdventureWorksDW data source view.

Note that typically you would have a separate table that contains your prospect customers and you would want to predict whether each customer would buy a bike or not (i.e., Bike Buyer column) based on other known information (i.e., other columns). However, for the sake of simplicity of the tutorial, we are using the same training data, vTargetMail as the prospect customers.

After you select the input table, Prediction Query Builder creates a default mapping between the mining model and input table based on the names of the columns, as shown in Figure 21.

Figure 21 Mapped columns in the Mining Model Prediction tab

To build the prediction query

In the Source column, click the cell in the first empty row, and then click vTargetMail table.
In the Field column, next to the entry you created in step 1, click CustomerKey.

This adds the unique identifier to the prediction query so that you can identify who is and who is not likely to buy a bicycle.
Click the next cell in the Source column, and then click Targeted Mailing mining model.
In the Field cell, click Bike Buyer.

This specifies that the Microsoft Clustering model in the Targeted Mailing structure will be used to create the predictions.
Click the next cell under the Source column, and then click Prediction Function.
Next to Prediction Function, in the Field column, click PredictProbability.

Prediction functions provide information about how the model predicts. The PredictProbability function provides information about the probability of the prediction being correct. You can specify parameters for the prediction function in the Criteria/Argument column.
In the Criteria/Argument column, type [Targeted Mailing].[Bike Buyer].

This specifies the target column for the PredictProbability function. For more information on functions, see “DMX Function Reference” in SQL Server Books Online.

Figure 22 Prediction Query Builder in the Mining Model Prediction tab

By clicking the icon in the upper-left corner of the view, you can switch to the Query view and look at the DMX code that Prediction Query Builder created. You can also run the query, modify the query, and run the modified query, but the modified query is not persisted if you switch back to the Design view.

You can run the query by clicking the arrow next to the icon in the top left corner of the tab, and then clicking Result. Figure 23 displays the query results.

Figure 23 Mining Model Prediction Result tab

The CustomerKey, BikeBuyer, and Expression columns identify potential customers, whether they are bike buyers, and the probability of the prediction being correct. You can use these results to determine who should be sent an advertisement.

A sales analyst for Adventure Works has been asked to forecast the sale of bike models for the next year. In particular, he has been asked to find peak times for bike sales and how sales lead or lag with respect to region. Additionally, he will look to see whether sales of different models vary depending on the time of the year.

The analyst will investigate the data at the monthly level. Sales will be divided into three regions: Europe, North America, and Australia.

Upon completion of this task, the analyst will be able to answer the following questions:

What time of year do sales peak?
How do the different bike models interact over time?
Is there a pattern to sales with respect to the three regions?

In order to complete the task, the analyst will use the Microsoft Time Series algorithm. The scenario consists of three tasks:

Create the mining model structure.
Edit the mining model.
Explore the mining model.

reate a Forecasting Mining Model Structure Using the Wizard

The first step is to use Mining Model Wizard to create a new mining structure. The Mining Model Wizard also creates an initial mining model based on the Microsoft Time Series algorithm.

To create the forecasting mining structure

In Solution Explorer, right-click Mining Structures, and then click New Mining Structure.

The Mining Model Wizard opens.
On the Welcome page, click Next.
Click From existing relational database or data warehouse, and then click Next.
Under What data mining technique do you want to use?, click Microsoft Time Series.
Click Next.

By default Adventure Works DW is selected in the Select data source view window.
Select the Case check box next to the vTimeSeries table.
Select the Key check boxes next to the TimeIndex and ModelRegion columns.
Select the Input and Predictable check boxes next to the Quantity columns.

This indicates that you want to forecast these columns.
Click Next.
Select Key Time in the drop box of TimeIndex column

The TimeIndex column is designated as a key time column and the ModelRegion column is designated as a key column. This means that a separate time series will be built for each unique entry in the ModelRegion column. The values in TimeIndex must be unique only across individual values in ModelRegion.
Click Next.
In both Mining structure name and Model Name box, type Forecasting, and then click Finish.

The data mining editor opens, displaying the Forecasting mining structure you created.

Figure 24 Mining model structure for the forecasting scenario

The mining structure shown in Figure 24 contains a single forecasting model that you defined in the Mining Model Wizard. Before you process and explore the model, you need to change its structure slightly and modify one property.

Modify the Mining Structure

You can change the mining structure using the Mining Structure tab of the data mining editor. You only used three columns to create the model: TimeIndex, ModelRegion, and Quantity. The Forecasting table also contains an Amount column that you can use to forecast the amount of sales. Using the Mining Structure tab, you can add this column from the data source view to the mining structure.

To add the Amount column to the Forecasting mining structure

Select the Amount column in the vTimeSeries table in the Data Source View window.
Drag the Amount column from the Data Source View window into the list of columns for the Forecasting structure.

The Amount column now exists as part of the Forecasting mining structure.

Because you added a new column to the structure, you must define how it will be used in the Mining Model tab. Figure 24 shows what the tab for this mining structure looks like.

The Mining Models tab lists the columns contained in the mining structure, under Structure, and those contained in the model, under the name of the model (in Figure 25, Forecasting). Click the names of the columns or the name of the model to make modifications.

Figure 25 Mining Models tab of the Forecasting structure

Note In this tab you can also create new models based on the same structure, and you can adjust the algorithm and column properties for each model. You must process the model before these changes take effect.

he Forecasting mining model, the Amount column is used as an input and to forecast future sales. Therefore, you must set the properties of the column so that it can be used as both an input column and a predictable column.

To define how the Amount column will be used

Under the Mining Models tab, click the Amount row of Forecasting model.

A list box containing Ignore, Input, Predict, and PredictOnly appears.
Click Predict.

The Amount column is now both an input and a predictable column.

You can also change the properties of individual columns by selecting the column and opening the properties window (right-click the column name, and then click Properties). By selecting the column under the model (in this case, under Forecasting), you can change the properties just for that model. By selecting the column under Structure, you can change properties of the column for the structure, which affects every model associated with the structure.

If you select Forecasting, you can change properties and parameters associated with the model. The Microsoft Time Series algorithm contains several parameters that affect how a model is created. For more information about these parameters, see “Time Series Algorithm Parameters” in SQL Server Books Online.

For this model you will adjust the value of the PERIODICITY_HINT parameter, which gives the algorithm information about often the data is repeated. The data in AdventureWorksDW is patterned on a monthly basis, and the periodicity is at the yearly level. Therefore, you will set the PERIODICITY_HINT parameter to 12, indicating that a pattern repeats itself every year.

To change the PERIODICITY_HINT parameter

Right-click Forecasting, and select Set Algorithm Parameters.

The Algorithm Parameters dialog box opens.
Set PERIODICITY_HINT to {12}.

Process the Mining Model

Now that the structure and parameters for the mining model are set, you can process the model. The method for processing the Forecasting mining model is the same as that for the Targeted Mailing models. For more information, see “Targeted Mailing” earlier in this document.

Now that the model is built and processed, you can explore the results using the Time Series viewer in the Mining Model Viewer tab. The Time Series viewer contains two tabs: Decision Tree and Charts. For more information about these tabs, see “Viewing with Time Series Viewer” in SQL Server Books Online.

The Microsoft Time Series algorithm builds a model for each distinct series that exists in the dataset. For example, each model for each region in the dataset contains information about sales over the time period. Therefore, a separate time series exists for each model in each region for both quantity and amount.

In this section, you will explore the time series for the amount of sales for Europe, North America, and the Pacific.

Decision Tree Tab

The Decision Tree tab (Figure 26) enables you to look at the decision tree that was created when the model was processed. In Tree, select the M200 Pacific: Amount model.

Figure 26 Decision Tree tab of the Forecasting model

The concentration of cases for the state of the predictable attribute specified in the Background control. The Node Legend window and ToolTip give the exact number of cases.
The regression formula for the node.
A diamond chart that represents the range of the range of the attribute. The diamond is located at the mean for the node, and the width of the diamond represents the variance of the attribute at that node. A thinner diamond indicates that the node can create a higher quality prediction.

Charts Tab

Using the Charts tab, you can investigate the time series that are created by the algorithm.

To select a time series

Select the following time series from the
drop-down list.

R750 Europe:Amount
R750 North America:Amount
R750 Pacific:Amount

Click OK.

The legend on the right side of the viewer lists the series selected from the drop-down list along with check boxes. By selecting and clearing check boxes in the legend, you can control which time series are displayed in the viewer.

Figure 27 Charts tab of the Forecasting model

The chart displays both historical and future data. Future data is shaded to differentiate it from historical data. Use Prediction Steps to control how many future steps of data are displayed. Use Show Deviations to add error bars to the predictions.

As you can see in Figure 27, sales are generally increasing with a peak every 12 months (in December). The predictions continue this trend.

The marketing department of Adventure Works is interested in improving their Web site so that they can promote cross-selling.

Before they can update the site, they need to create a data mining model that can predict which products customers might want based on what customers already have in their baskets. These predictions will also assist the marketing department in placing items that tend to be bought together in close proximity on the Web site.

Upon completion of the task, the marketing department will have a model that can predict additional items that can appear in a shopping basket, or that a customer would like to add to a basket. In addition, they will have a complete mining model that shows groups of items from historical customer transactions.

In order to complete the task, the analyst will use the Microsoft Association algorithm. The scenario consists of three tasks:

Create the mining model structure.
Edit the mining model.
Explore the mining model.

sket Mining Model Structure Using the Wizard

The first step is to use Mining Model Wizard to create a new mining structure. The Mining Model Wizard also creates an initial mining model. For the market basket scenario, you will use the wizard to create a mining structure and an associated mining model based on the Microsoft Association algorithm.

To create the Association mining structure

In Solution Explorer, right-click Mining Structures, and then click New Mining Structure.

The Mining Model Wizard opens.
On the Welcome page, click Next
Click From existing relational database or data warehouse, and then click Next.
Under What data mining technique do you want to use?, click Microsoft Association Rules.
Click Next.

By default, Adventure Works DW is selected in the Select data source view window.
Select the Case check box next to the vAssocSeqOrders table and the Nested check box next to the vAssocSeqLineItems table, and then click Next.
Clear the Key check box next to CustomerKey and the Key and Input check boxes next to LineNumber.

By default, CustomerKey, OrderNumber, and LineNumber are listed as Key types. OrderNumber will only be used as a key for Microsoft Association Rules model, so you must change the default setting.
Select the Key, Input and Predictable check boxes next to the Model column. Make sure that the final selection is the same as shown in figure 28a.

Figure 28a Attribute specification for the Association mining structure.

Click Next.
Click Next.
In Both Mining Structure Name and Mining Model Name box, type Association, and then click Finish.

. Figure 28b shows the mining structure and mining model you created.

Figure 28b Mining Structure tab of the Association mining structure

Before you process the model, you must change the default values of two of the parameters: Support and Probability. Support defines the percentage of cases in which a rule must exist before it is considered to be a valid rule. Probability defines how likely an association must be before it can be considered valid.

To adjust Association model parameters

Select the Mining Models tab.
Right-click Association, and select Set Algorithm Parameters.

The Algorithm Parameters dialog box opens.
Set the following parameters:

Parameter	Value
MINIMUM_PROBABILITY	0.1
MINIMUM_SUPPORT	0.01

Process the Mining Model

Now that the structure and parameters for the mining model are set, you can process the model. The method for processing the Market Basket mining model is the same as with the Targeted Mailing models. For more information, see “Targeted Mailing” earlier in this document.

Explore Mining Models in the Editor

To open the Association viewer, select the Mining Model Viewer tab. The Association viewer contains three tabs: Itemsets, Rules, and Dependency Net. For more information about the Association viewer, see “Viewing with Association Viewer” in SQL Server Books Online.

The Itemsets tab displays three important pieces of information that relate to the itemsets found by the Microsoft Association algorithm: the support (the number of transactions that the itemset shows up in), the size (how many items are in the itemset), and the actual makeup of the itemset. Depending on how the algorithm parameters are set, the algorithm can generate a large number of itemsets. Using the controls at the top of the tab, you can filter the viewer to show only itemsets containing a specified minimum support and itemset size.

You can also use the Filter itemset box to filter the itemsets shown in the viewer. For example, to see only the itemsets that contain information about the Mountain-200 bicycle, type Mountain-200.

Figure 29 Itemsets tab of the Microsoft Association algorithm

As you can see in Figure 29, only itemsets that contain the words “Mountain-200″ are displayed. Each itemset returned contains information about transactions in which a Mountain-200 bicycle was sold. For example, the itemset that contains the value 710 under Support tells you that out of all of the transactions, 710 people who bought the Mountain-200 bicycle also bought the Sport-100 bicycle.

The Rules tab displays three pieces of information relating to the rules that the algorithm found.

Probability

The likelihood of a rule occurring.

Importance

A measure of the usefulness of a rule, with a higher value meaning a better rule. Simply looking at the probability can be misleading. For example, if every transaction contains an item x, the rule y predicts x has a probability of 1 — it will always occur. Even though the accuracy of the rule is very good, it does not relay very much information, because every transaction contains x regardless of y.

Rule

The definition of the rule.

As with the Itemsets tab, the rules can be filtered so that only the most interesting rules are shown. For example, suppose you only want to see the rules that include the Mountain-200 bicycle. If you type Mountain-200 in the Filter Rule box, you receive the results shown in Figure 30.

Figure 30 Rules tab of the Microsoft Association algorithm

ce of other items. For example, the first rule tells you that if someone buys a Mountain-200 bicycle and a 30-ounce water bottle, there is a probability of 1 that the person will also buy a Mountain bottle cage.

Dependency Net

Using the Dependency Net tab, you can investigate the interaction of the different items in the model. Each node in the viewer represents an item; for example, Mountain-200 = Existing (meaning that Mountain 200 exists in a transaction). By selecting a node, you can use the color legend at the bottom of the tab to determine which other items either determine, or are determined by, other items in the model.

The slider is associated with the probability of a rule. By sliding up or down, you can filter out weak associations.

For example, in the Show box, click Show attribute name only, and then click Mountain bottle cage. Zooming in, you see the Association viewer pictured in Figure 30. The viewer shows that Mountain bottle cage both predicts and is predicted by 30-ounce water bottle and Mountain-200, meaning that these items are likely to show up in a transaction together. This makes sense — if someone buys a bike, he or she is likely to buy a water bottle holder and water bottle.

Figure 31 Dependency Net tab of the Microsoft Association algorithm

Sequence Clustering

The marketing department of Adventure Works is interested seeing how customers move through the Adventure Works Web site. They suspect that there is a pattern to the order in which customers put products into their shopping cart. Using the Microsoft Sequence Clustering algorithm, they can find the sequences by which customers add items to their carts. They can then use this information to streamline the flow of the Web site so that it leads customers to purchase additional products.

Upon completion of this task, the marketing department will have a model capable of predicting what a customer will put in his or her shopping basket next.

In order to complete the task, the analyst will use the Microsoft Sequence Clustering algorithm. The scenario consists of two tasks:

Create the mining model structure.
Explore the mining model.

The first step is to use Mining Model Wizard to create a new mining structure. The Mining Model Wizard also creates an initial mining model based on the Microsoft Sequence Clustering algorithm.

To create the Sequence Clustering mining structure

In Solution Explorer, right-click Mining Structures, and then click New Mining Structure.

The Mining Model Wizard opens.
On the Welcome page, click Next.
Click From existing relational database or data warehouse, and then click Next.
Under What data mining technique do you want to use?, click Microsoft Sequence Clustering.
Click Next.

By default, Adventure Works DW is selected in the Select data source view window. Click Browse to view the tables in the data source view inside of the wizard.
Select the Case check box next to the vAssocSeqOrders table and the Nested check box next to the vAssocSeqLineItems table.
Click Next.
Clear the Key check box next to CustomerKey.

By default, OrderNumber and LineNumber are listed as Key types, which is correct.
Select the Input and Predictable check boxes next to the Model columns. Make sure that the final selection is the same as shown in figure 32a.

Figure 32a Attribute specification for the sequence clustering mining structure.

Click Next.
In both Mining Structure Name and Mining Model Name box, type Sequence Clustering, and then click Finish.

The data mining editor opens, displaying the new Sequence Clustering mining structure.

Figure 32b Sequence Clustering mining structure

You do not need to make any changes to the mining model structure or mining model in the data mining editor, so you can just process the model.

Process the Mining Model

The method for processing the Sequence Clustering mining model is the same as that for the Targeted Mailing models. For more information, see “Targeted Mailing” earlier in this document.

Explore Mining Models in the Editor

Use the Sequence Clustering viewer to explore the mining model you created for the sequence clustering scenario. To open the Sequence Clustering viewer, click Mining Model Viewer. Like the Cluster viewer, the Sequence Clustering viewer contains five tabs: Cluster Diagram, Cluster Profiles, Cluster Characteristics, Cluster Discrimination, and State Transitions. For more information about using the Sequence Clustering viewer, see
“Viewing with Sequence Clustering Series Viewer” in SQL Server Books Online.

The Cluster Diagram tab graphically displays the clusters the algorithm discovered in the database. The layout represents the cluster relationships where similar clusters are grouped close together. By default, the node color represents the density of all cases in the cluster — the darker the node, the more cases it contains. You can also change the meaning of node color-coding so that it represents an attribute and state. For example, to generate the diagram shown in Figure 33, in the Shading Variable list, click Model, and in the State list, click Cycling Cap.

Figure 33 Cluster Diagram tab of the Microsoft Sequence Clustering model

You can see that Cluster 9 contains the highest density of cycling caps.

The Cluster Profiles tab displays the sequences that exist in each cluster. The clusters are listed in individual columns to the right of the States column, and the rows listed in the Variables column show the variable distributions for a cluster.

In Figure 34, the Model.samples row represents sequence data, and the Model row describes the overall distribution of items in a cluster. Each line of the color sequences displayed in each cell of the Model.samples row represents the behavior of a randomly selected user in the cluster. Each color in the sequence histogram represents a product model.

Figure 34 Cluster Profiles tab of the Microsoft Sequence Clustering model

For example, the aqua color in cluster 3 represents the Mountain-200 bicycle. Its presence as the first color in most of the sequences means that a customer is very likely to place the Mountain-200 bike in the shopping basket first.

The Cluster Characteristics tab summarizes the transitions between states in a cluster, with bars describing the importance of the attribute value for the selected cluster. For example, in Cluster 10, on of the most important profiles is that customers tend to place a ML Mountain tire and in the shopping cart first.

Figure 35 Cluster Characteristics tab of the Microsoft Sequence Clustering model

Cluster Discrimination

Using the Cluster Discrimination tab, you can compare two clusters, determining which models favor which clusters. The tab contains four columns: Variables, Values, Favors Cluster (i), Favors Cluster (i). If the cluster favors a specific model, a blue bar appears in one of the Favors Cluster(i) columns, in the row of the model listed in the Variables column. The longer the blue bar, the more the model favors the cluster.

Figure 36 compares Cluster 2 with Cluster 5. A customer who purchases a bottle cage for a mountain bike (indicated by Mountain Bottle Cage in the Values column) is more likely to be in Cluster 5, and a customer who purchases a Touring tire (indicated by Touring Tire in the Values column) is more likely to be grouped into Cluster 2.

Figure 36 Cluster Discrimination tab of the Microsoft Sequence Clustering model

State Transitions

On the State Transitions tab, you can select a cluster and browse through its state transitions. Each node represents a state of the model (such as Mountain-200). A line represents the transition between states, and each node is based on the probability of a transition. The background color represents the frequency of the node in the cluster.

For example, select Cluster 3 from Cluster, select the Touring-3000 node, and lower the All Links slider a couple of notches. As you can see in Figure 37, if users put a Touring Tire into his shopping cart, there is a probability of 0.63 (indicated by the blue arrow) that he will next put a Touring Tire Tube into the cart, and a probability of 0.26 that he will end his shopping by placing a Sport 100 bike into his shopping cart.

Figure 37 Cluster Transitions tab of the Microsoft Sequence Clustering model

Filed under .Net

Motion Mining & Detection in Video Streams

February 27, 2012 Leave a comment

Motion Mining & Detection in Video Streams

Ali Tarhini, Fatima Hamdan, Hazem Hajj

Department of Electrical and Computer Engineering

American University of Beirut

Beirut, Lebanon

{fsh08, hh63}@aub.edu.lb

Abstract–Motion detection is the process of finding and extracting motion in continuous media. There are many approaches for motion detection in continuous video streams. All of them are based on comparing the current video frame with one from the previous frames or with something known as the “background”. This method is useful in video compression when estimating changes in the frame is the only requirement, not the whole frame. Although this algorithm is simple, it suffers from disadvantages. If the object is moving smoothly, only small changes from frame to frame is detected. Another problem is when the object is moving slowly, the algorithms will not give any useful result at all. Another approach is to compares the current frame to the first frame in the video sequence rather than comparing with the previous one. But, this approach fails in practice because it will always have motion detected on the same region since the initial frame is static. In this paper, we propose a new method which overcomes the problems of previous methods by creating a moving frame over a time interval and comparing against this frame. Our tests show that the proposed algorithm outperforms the previous ones with speed and accuracy.

Keywords: Motion Mining, Video Stream, Detection.

INTRODUCTION

Motion detection is the process of finding and extracting motion in continuous media. There are many approaches for motion detection in continuous video streams. All of them are based on comparing the current video frame with one from the previous frames or with something known as the “background”. One of the most common approaches is to compare the current frame with the previous one. This method is useful in video compression when estimating changes in the frame is the only requirement, not the whole frame. Although this algorithm is straightforward in motion mining, it suffers from disadvantages. If the object is moving smoothly, only small changes from frame to frame is detected. So it’s impossible to get the whole moving object. Another problem is when the object is moving slowly, the algorithms will not give any useful result at all. There is another approach that compares the current frame the first frame in the video sequence rather than comparing with the previous one. So, if there were no objects in the initial frame, comparison of the current frame with the first one will give us the whole moving object independently of its motion speed. But, this approach fails in practice because if there was, for example, a car on the first frame, but then it is gone then this method will always have motion detected on the same place where the car was. Although one workaround over this problem is to renew the initial frame at regular intervals, but still it will not yield good results in the cases where the probability of guaranteeing that the first frame will contain only static background. But there can be an inverse situation. For example, if we add a picture on the wall in the room we will get motion detected continuously until the initial frame is renewed.

The most efficient motion mining algorithms are based on building a “background”, also known as the “scene” and comparing each current frame with that scene. There are many approaches to build the scene, but most of them are too complex and require significant computation time which consumes excessive processing power and introduce latency which is not accepted in real time systems. In this paper, we introduce a new approach for motion mining using the scene building method while improving performance over the current algorithms.

BACKGROUND & PREVIOUS WORK

One of the widely known algorithms in motion detection is the Mask Motion Object Detection(MMOD) algorithm. This algorithm works in steps that involve background subtraction, frame difference, frame difference mask and background difference mask are generated and utilized to detect moving objects. First, a threshold value is calculated under the assumption that camera noise obeys Gaussian distribution and background change is caused mainly by camera noise. The frame difference is found by subtracting the current frame from the previous frame. The background difference is found by subtracting the current frame from the background frame. Then the frame difference mask and the background difference mask are found by comparing the obtained frame difference and background difference with the threshold. N(x, y, t) denotes the total frame number that pixel (x,y) may belong to background region. If N(x, y, t) >= f_threshold which shows that the probability which pixel belong to background region is high, then the background difference mask is used to detect moving objects otherwise the frame difference mask is used. To detect moving objects, the current frame is anded with the chosen mask.

Motion Region Estimation Technique(MRET) is another algorithm which also uses image subtraction for motion detection. It starts by processing the output image obtained from image subtraction after thresholding and noise removal. Thresholding determine the areas of output image (from subtraction) consists of pixels whose values lie within the threshold value range. Threshold value also indicates the sensitivity of motion to
detect. After thresholding, the image may still contain a small amount of noise. Noise is removed by using median filtering method. Median filtering is more effective than convolution when the goal is to simultaneously reduce noise and preserve edges. The gray level of each pixel is replaced by the median of the gray levels in a neighborhood of that pixel. Motion region information can be obtained by using AND and OR double difference image IO during different time t and frame n from video frames.

PROPOSED METHOD

Given a background frame representing the initial frame, a current frame representing the latest frame captured from the video source. As a preprocessing approach, both the background frame and the current frame are converted to grayscale. These grayscale images will be used throughout the rest of the algorithm. The algorithm then proceeds to compare the current frame with the background frame. But this would give the results we discussed earlier that suffer from many problems. The tweak here is to “move” the background frame in time at regular intervals to approach the current frame, but not reach it because if the two frames match, the difference becomes zero and therefore motion will not be determined. In order to approach the current frame from the background frame, the color value of the pixels in the background frame is changed by one level per frame.

The algorithm takes two parameters as input, the background frame and the current frame then it works as follows:

Create a grayscale version of the background frame
Create a grayscale version of the current frame
Subtract the current frame from the background frame to yield the difference frame
Render the difference on screen
Check whether X frame count have passed(X=threshold)
If step5 evaluates to true then merge background frame with the current frame. Otherwise go back to step 3 and repeat.

EXPERIMENTS& RESULTS

The goal of this experiment was to study the performance of the proposed algorithm. A camera is setup in a room and its video streams is fed into 3 motion detection algorithms. The first one uses the background for comparison, the 2^nd one used the previous frame for comparison and the 3^rd one is our proposed algorithm that uses a moving background for comparison with the current frame.

Figure1: Comparison with background

Figure2: Comparison with previous frame

Figure3: Comparison with moving background

In figure1, the comparison with the background frame detects the entire person in the picture. This looks good for the first sight but it’s obvious that the approach is not feasible in practice because the background happened to be static, were it dynamic(i.e clock on the wall)…

In figure2, the person was walking slowly and with minimum movement. As we can see, the detected region of motion appears to be cluttered and disconnected.

In figure3, the person was also moving slowly and with minimum movement. We can see the great improvement in the detected region as all the body was detected as one object. The reason for the improvement from the algorithm used in figure2 is that the comparison was done with a combination of previous frames in order to approximate the state of the background frame a little while ago. This approach is better because if the comparison was with the previous frame, only a small difference will be detected. This shows that our algorithm outperforms the previous algorithms.

CONCLUSION

In this paper, a motion detection algorithm was implemented by applying a new approach to improve the accuracy of existing motion detection algorithms. The implementation this technique increased the efficiency of the detected region when the object is subject to slow and/or smooths movement.

Filed under .Net

Mining Association Rules in Wireless Sensor Network

February 27, 2012 Leave a comment

Mining Association Rules in Wireless Sensor Network

Ali Tarhini, Fatima Hamdan

Department of Electrical and Computer Engineering

American University of Beirut

Beirut, Lebanon

{aat16, fsh08}@aub.edu.lb

Abstract – Wireless Sensor Networks produce large amounts of data during their lifetime operation and the data must be transferred to the base station. Transferring large scale data consumes energy because of the long transmission time. Recently, frequent pattern mining received attention in extracting knowledge from WSNs data. In particular, mining for association rules on the sensor data provides useful information for different applications. In this paper, we study one of the most widely used association rules mining algorithms, the Apriori, and show the effects of implementing this algorithm in a WSN in order to predict the source of future events and to identify sets of temporally correlated sensors therefore thereby improving the Quality of Service of WSANs in various ways.

INTRODUCTION

Wireless Sensor Networks produce large amounts of data during their lifetime operation and the data must be transferred to the base station. Transferring large scale data consumes energy because of the long transmission time. Recently, frequent pattern mining received attention in extracting knowledge from WSNs data. In particular, mining for association rules on the sensor data provides useful information for applications that require predicting the source of future events or faulty nodes. For example, we are expecting to receive an event from a certain node, and it does not occur. It may also be used to identify the source of the next event in the case of the emergency preparedness class of applications. Identifying correlated sensors can also be helpful in compensating for the undesirable effects of unreliable wireless communication such as missed reading and in the resource management process such as deciding which nodes can be switched safely to a sleep mode without affecting the coverage of the network. In this paper, we study the possibility of extracting association rules between sensors using one of the most widely used data mining algorithms for frequent patterns, The Apriori algorithm. The sensors’ association rules will capture the set of sensors that report events within the same time interval. An example of such rules could be (s1s2 ⇒ s3) which can be interpreted as follows: if we received events from sensor s1 and sensor s2, then we may receive events from sensor s3 with λ units of time. Generating these rules requires a redefinition of the association rule mining problem, as the definition originally was proposed for business data, in order to fit with WSN terminologies. Also, an efficient extraction methodology is needed to extract the required data for the mining algorithms.

RELATED WORK

The mining association rules problem was first introduced in [1], where it was originally proposed in terms of transactional databases. These rules were able to predict the items that can be purchased within the same transaction. Such rules have a great impact on making decisions about which item should be put on sale or which items should be placed near to each other.

Mining association rules is a costly process and the complexity grows exponentially with the number of the items presented in the database. Many algorithms have been developed to generate association rules, each of them adopting a different optimization technique that applies either to the structure of the data or to the algorithm that traverses the search space. Among these algorithms are Apriori [1], FP-growth [4], and DHP (Directed Hashing and Pruning) [5]. A comprehensive survey of the recent algorithms for mining association rules is presented in [6]. In [7], a framework for extracting association rules from sensor networks is proposed. The association involves the sensors’ values as the main objects in the rule. In their methodology, the time is divided into intervals, and the sensors’ values at that interval formulate the transaction to be stored in the database. Each different value of a sensor is regarded as single element and it is assumed that sensors take on a finite number of discrete states. Each transaction is associated with a weight value indicating the validity of the transaction. The support of the pattern is then defined to be the total length of all non overlapping intervals in which the pattern occurs. The main differences between this methodology and the one presented in this paper, is that we assume objects in the same context are the sensors themselves, not their values, and the support of the pattern is the number of epochs in which the pattern occurs as a subset. This makes the formulation presented in this paper a more general one.

Most of the data mining techniques applied to sensor data are based on centralized data extraction, where the data is collected at a single site and then the mining technique is applied. However, there are still some techniques that use the distributed nature of sensors and try to apply distributed mining algorithms. In [8] they propose a distributed framework for building a classifier. In their framework, most of the work is pushed to the sensors themselves to build local models.

APRIORI IN WSNs

Apriori is a frequent pattern mining algorithm for discovering association rules originally developed by Rakesh Agrawal and Ramakrishnan Srikant[4]. It operates on a list of transactions containing items (for example, products in a supermarket). Frequent occurrences of items with each other are mined by Apriori to discover relationship among different items. A single transaction is called an Itemset. Apriori uses a minimum support value as the main constraint to determine whether a set of items is frequent. In the first pass of the algorithm, it constructs the candidate 1-itemsets. The algorithm then generates the frequent 1-itemsets by pruning some candidate 1-itemsets if their support values are lower than the minimum support. After the algorithm finds all the frequent 1-itemsets, it joins the frequent 1-itemsets with each other to construct the candidate 2-itemsets and prune some infrequent itemsets from the candidate 2-itemsets to create the frequent 2-itemsets. This process is repeated until no more candidate itemsets can be created.

In order to allow Apriori to be used in WSN, we will need to map the sensors to objects so that each sensor in the WSN domain will represent an item in the apriori domain and hence a transmission of multiple sensors within the same time interval T in the WSN domain will represent an item set in the Apriori domain. Formally, Let S = {s1, s2, . . . , sm} be a set of sensors in a particular sensor network. We assume that the time is divided into equal sized slots {t1, t2, . . . , tn} such that ti+1 – ti = λ, for all 1 < i < n. λ is the size of each time slot. A transaction T = {s1, s2, . . . , sk} ⊆ S is called an itemset, or simply, a pattern of sensors sharing common transmission behavior.

PROPOSED METHOD

Our algorithm runs on the base station, where transmissions are received from sensors every time interval. Upon receiving of each message, the system will record the sensors participating in the message which represents an itemset. The itemset is them stored for later processing when the Apriori runs. This process of logging sensors participating in the transmission is a continuous process and it is up to the system administrator to determine the proper number of itemsets to store. Off course, the more itemsets stores, there will be more likely to detect additional patterns but this will require more memory and energy consumption. On the other hand, if only a small number of itemsets are stored, the mining accuracy of Apriori will decrease and the resultant patterns will not be necessarily useful or meaningful in the WSN.

Once the determined number of itemsets has been stored, the database is now ready for association rule mining and Apriori algorithm is triggered to start processing. The algorithm works as follows:

First, the set of frequent 1-itemsets is found by scanning the database to accumulate the count for each item, and collecting those items that satisfy minimum support. The resulting set is denoted L1.Next, L1 is used to find L2, the set of frequent 2-itemsets, which is used to find L3, and so on, until no more frequent k-itemsets can be found. The finding of each Lk requires one full scan of the database. To improve the efficiency of the level-wise generation of frequent itemsets, an important property called the Apriori property, presented below, is used to reduce the search space. We will first describe this property, and then show an example illustrating its use.

Apriori property: All nonempty subsets of a frequent itemset must also be frequent.

Note that a two-step process is followed to compute Lk from Lk-1 for k > 2; these consist of join and prune actions:

The join step: To find Lk, a set of candidate k-itemsets is generated by joining Lk-1 with itself.
The prune step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset. Hence, if any (k-1)-subset of a candidate k-itemset is not in Lk-1, then the candidate cannot be frequent either and so can be removed from Ck. This subset testing can be done quickly by maintaining a hash tree of all frequent itemsets.

EXPERIMRNTS & RESULTS

Will be available in the full paper.

REFERENCES

[1] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proceedings of ACM SIGMOD Conference. Management of Data, Washington, D.C., United States May 1993.

[2] Intel Lab Data, http://berkeley.intel-research.net/labdata/.

[3] G. Mathur, P. Desnoyers, D. Ganesan, and P Shenoy. Ultra-Low Power Data Storage for Sensor Networks.In proceedinig of the Fifth IEEE/ACM Conference on Information Processing in Sensor Networks (IPSNSPOTS), Nashville TN, April 19 -21, 2006 [4] J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. In ACM SIGMOD, 2000.

[5] J.S. Park, M. Chen, P.S. Yu. An Effective Hash-Based Algorithm for Mining Association Rules. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, pages 175-186, May

1995.

Filed under .Net

Parallel Sudoku Solver Algorithm

February 27, 2012 Leave a comment

Parallel Sudoku Solver Algorithm

Ali Tarhini, Hazem Hajj

Department of Electrical and Computer Engineering

American University of Beirut

Beirut, Lebanon

{aat16, hh63}@aub.edu.lb

Abstract—Sudoku is a complex yet exciting game. It is a 9 by 9 matrix divided to sub grids of size 3. The goal of the game is to fill in all the cells with numbers from 1 to 9 such that no two cells on the same row, column or minigrid have the same number. This problem can be generalized for larger size and the computational complexity to find a solution for Sudoku is high. In this paper, we propose a new parallel algorithm solver for the generalized NxN Sudoku grid that exploits the manycore architecture. Our test results show that the algorithm scales well as the number of cores grow.

INTRODUCTION

Sudoku is a complex yet exciting game. It is a 9 by 9 matrix divided to sub grids of size 3. The goal of the game is to fill in all the cells with numbers from 1 to 9 such that no two cells on the same row, column or minigrid have the same number. This problem can be generalized for larger size and the computational complexity to find a solution for Sudoku is high. A Sudoku puzzle usually comes with a partially filled grid. The aim is to complete the grid in the shortest amount of time.

From a mathematical perspective, it has been proven that the total number of valid Sudoku puzzles is equal to 6, 670, 903, 752, 021,072,936,960 or
approximately 6.671×10²¹[1].

Trying to populate all these grids is itself a difficult problem because of the huge number of possibilities and combinations of puzzles, Assuming each solution takes 1 micro second to be found, then with a simple calculation we can determine that it takes 211,532,970,320.3 years to find all possible solutions. If that number was small, say 1000, it would be very easy to write a Soduku solver application that can solve a given puzzle in short amount of time. The program would simply enumerate all the 1000 puzzles and compares the given puzzle with the enumerated ones and we don’t have to design a parallel algorithm for finding Sudoku solutions. Unfortunately, this is not the case since the actual number of possible valid grids is extremely large so it’s not possible to enumerate all the possible solutions. This large number also directly eliminates the possibility of solving the puzzle with brute force technique in a reasonable amount of time. Therefore, a method for solving the puzzle quickly will be derived that takes advantage of manycore architecture on modern and future computer systems which will bring down the time cost of solving an NxN Sudoku to a reasonable amount? Our goal is to allow for the algorithm to take advantage of the manycore architecture to further reduce its running time. This is very important and is at the heart of our work because for large N, the number of cells per row and column in the Sudoku grid, finding a solution becomes an extremely difficult and computationally intensive problem. Hence, the parallel algorithm must also scale as the grid size increases.

RELATED WORK

Many algorithms have been developed to solve the Sudoku problem. One of these developed algorithms is the simulated annealing algorithm [1]. The Simulated annealing algorithm works by first randomly filling all the blank cells then it checks if the same number is repeated twice in the same row or same column. If there’s a repeated number then it swaps this value with another and repeats checking for repeated values. The simulated annealing algorithm consumes much time to solve the puzzle and it is only applicable to easy Sudoku problems. Another proposed algorithm to solve the Sudoku puzzle follows the linear system approach [6]. The algorithm converts the puzzle into a number of liner equations and tries to solve them. There are many rules that we should keep in mind while transforming the Sudoku puzzle into a system of linear equations. These constraints are:

There shouldn’t be any repeated value in the same row of a Sudoku puzzle.
There shouldn’t be any repeated value in the same column of a Sudoku puzzle.
There shouldn’t be any repeated value in the same 3*3 square of a Sudoku puzzle.
All the numbers should be from 1 to 9.
We must fill all the blank cells.

It is hard to solve the system for hard puzzles. This algorithm is only applicable for relatively easy Sudoku puzzles.

Artificial Bee Colony algorithm was invented recently to solve the Sudoku problem [3]. This algorithm has this name because it imitates the work done by the bees. The bees are divided into two sets, one set performs the real work while the other set supervises their work and receive information from them and based on that information they make decisions. In a similar way this algorithm tries to solve the Sudoku puzzle by following a parallel search approach where multiple blank cells can be filled while other cells would wait to receive information if those chosen cells values fit in that cells, and based on that they fill their values accordingly. Another approach for solving the Sudoku problem is by implementing the SAC algorithm [4]. This algorithm works by first assigning a set of potential values for every blank cell. Each cell has 9 optional values to choose from. The algorithm starts by choosing one of these potential values and assigning them to the cell and proceeds to other cells. If any rule is broken, the algorithm rolls back deletes this value from the set of potential values of the cell and chooses another value from the cell’s optional values. This algorithm follows a parallel approach to speed up solving the Sudoku problem, by allowing two cells to work in parallel for finding their correct values.

PROPOSED METHOD

Our algorithm follows a depth first search approach with backtracking. However, backtracking on manycore is not an easy task since each core is processing a path independent of the other cores so it’s hard to determine what was the previous step and backtrack to it. We also need to determine the granularity of a task or a work item, that is, the smallest unit of work done by any core because each core will be handling a work item at any point during the running time of the algorithm. Defining the granularity clearly shows whether each work item is dependent on other work items or that it is totally independent. In this case, the work item is not dependant of previous inputs and does not require any kind of inputs from other cores in order to be processed.

Consider a work item to be the operation of setting a value of one cell in an NxN grid. Therefore, the problem space is N²work items if the cells that initially have values already set are excluded. We will also define the operation LOCK which denotes a locking mechanism for the cell whose value is about to be changed. However, a problem arises when two cores attempt to update two different cells on the same row, on the same column or within the same minigrid. For example, if these two cells had only two possible values, when both cores take a lock over the cells, there is a probability that both cores assign the same value to the cells. Hence, the locking operation is not capable of resolving this issue and needs to be modified. The proposed algorithm works around this problem by defining LOCK as an operation that takes a lock over the entire row, column and minigrid so no other core could lock any cell within the same area. This area is referred to as the conflict boundary of a cell. The shaded area in Figure1 shows the conflict boundary (locked area) for the cell C(2,3) or C(2^nd row, 3^rd column).

The algorithm starts by splitting the work items equally among available cores. Given N cores and n²work items, where N is the number of core and n is the width of the square grid, and to distribute the loads equally across the cores, each core is assigned n²/N work items. Each core will determine the set of possible values for each of its cells and store these possible values. Then, each core will sort the work items in ascending order according to the smallest set of possible values for each cell so that the cells that have least possible values will be processed first. This is a good heuristic because most likely there will be cells that have only one possible value and that can be directly set thus reducing the problem space and eliminating unneeded computations. It is also important even if the cell had two possible options because the algorithm will randomly pick one of the two values by random and assign it to the cell. The probability of choosing the wrong value here is 0.5 which is much better than if there were, for example, 4 possible values left for a cell that the algorithm had to choose from. In that case, the probability of choosing a wrong value is ¾ assuming the cell has only one correct answer.

Figure 1 The shaded area represents the locked region which is the conflict boundary required to be locked in order to update cell C(2,3).

Once the work items are assigned, the cores are ready to start processing their work items. A core P will pull a work item from its local queue, check its set of possible value and randomly pick one value and assign it to the cell after taking a lock on the cell’s conflict boundary. If P is unable to take a lock due to another core already locking another cell on the same conflict boundary, the work item is not processed and the work item is enqueued again while another work item is dequeued and processed. This process reduces the idle time for P since it eliminates the need for waiting until the other core releases its lock on the conflict boundary and allows P to process another work item hence maximizing the overall efficiency of the algorithm.

One problem remains when a core tries to set a value for a cell but does not find a value because the cell has no more possible values, meaning that the current values in all the cells in the grid yielded an invalid Sudoku puzzle. The core has to backtrack to a previous state and take another branch. Here, the state of the puzzle is defined as a stable instance of it, that is, a puzzle that could be solved and is not yet determined as unsolvable. In that case, a message is sent to the N-1 cores to stop processing any work items while P retrieves the previous puzzle from its local stack and distributes the new work items of that puzzle to the N-1 cores. Once, all cores receive their work items, P will try to set a value for the cell that previously had no solution. When it sets a value, P sends another message to the N-1 core indicating they may proceed in processing more work items if they are waiting. The algorithm terminates when there are no more work items to be processed.

TESTING AND RESULTS

The proposed algorithm is tested on an 8 core machine with 4 GB of physical memory on a windows based operating system. First the sequential version of the algorithm is run and it utilized, as expected, only one of the available cores. The sequential algorithm was given a partially filled Sudoku grid and the running time took 0.78 seconds for the 9 by 9 Sudoku. Then the parallel version of the proposed algorithm is run on the same puzzle. Monitoring the Task Manager in windows, we noticed the full utilization of all the cores as in the figure shown below. The overall running time of the algorithm took an average of 0.11 seconds of five repeated executions.

Figure 2 Utilization of all available cores by the parallel algorithm.

CONCLUSION

In this paper, we proposed a new parallel algorithm for solving an NxN Sudoku grid. The algorithm is designed to maximize the utilization of all cores available on the system. Testing and results section that show the efficiency of the algorithm and that it utilized all the available cores on the system. Future work for this algorithm will be testing it for manycore architecture and verifying if it will scale on manycore as it did on multicore.

REFERENCES

[1]
“An FPGA-Based Sudoku Solver based on Simulated Annealing Methods”. Pavlos Malakonakis, Miltiadis Smerdis, Euripides Sotiriades, Apostolos Dollas International Conference on Field-Programmable Technology, 2009. FPT 2009.

[2] “Linear Systems, Sparse Solutions, and Sudoku”. Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, Fellow, IEEE, and Jian Li, Fellow, IEEE. Signal Processing Letters, IEEE.

[3] “Artificial Bee Colony (ABC), Harmony Search and Bees Algorithms on Numerical Optimization” .D. Karaboga, B. Akay. Erciyes University, The Dept. of Computer Engineering, 38039, Melikgazi, Kayseri, Turkiye.

[4] “Coordinating Data Parallel SAC Programs with S-Net”. Clemens Grelck, Sven-Bodo Scholz, and Alex Shafarenko. Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International

[5] Bertram Felgenhauer, “Enumerating possible Sudoku grids”.

[6] S.F.Bammel, J.Rothstein, The number of 9×9 Latin squares, Discrete Mathematics 11 (1975) 93–95.

Filed under .Net

Genetic Algorithm for Conference Schedule Mining

February 27, 2012 Leave a comment

Genetic Algorithm for Conference Schedule Mining

Ali Tarhini

Problem Definition:

Scheduling sessions, also known as “time tabling” at a large conference is a persistent challenge. The problem states that given a large number of sessions, rooms, time slots and a set of constraints, it is required to mine for the best schedule that covers all sessions within the given time slots while satisfying the required set of constraints. Allocating sessions to specific “time slots” requires advanced computational techniques for finding the best schedule that satisfies most of the constraints. The problem with large conferences is that many sessions will be scheduled to run concurrently; therefore an attendant may run into a problem if two or more of his/her favorite sessions are scheduled to run at the same time. Although there have been efforts to tackle the problem by using “tracks” to categorize sessions, which basically assumes that an attendant will stick to one track where the sessions of a track are scheduled sequentially in time. It turned out that this solution is not efficient in practice because attendants tend to hop from one track to the other rather than following a strict schedule for one track. More advanced approaches reduce the problem to the Job Shop Scheduling problem (JSSP) with multiple precedence constraints which is an optimization problem composed of resources, operations, and constraints. A job consists of a sequence of operations with each operation is part of exactly one job. Each operation is executed on a resource with starting time during a processing time with precedence constraints. A job has a release date, completion time and due date. A resource can execute only one operation at a time. We assume that any successive operations of the same job are going to be processed on different machines. It is desired to find a feasible schedule, which optimizes a set of given performance measures. However, JSSP problems tend to be theoretical and are not feasible to be applied in practice for international conferences because the algorithm does not take into account human interest in a particular set of sessions. For example, JSSP cannot handle attendant’s favorite sessions because this is not a constraint, it’s a training set. In this paper, a genetic algorithm is presented to provide a solution for the conference scheduling problem. In the context of genetic algorithms, a class of approximation algorithms, our “solution” means one among a set of all possible “best” solutions. It may not be the “best possible solution” but is certainly among the best.

Proposed algorithm:

Input: Sessions, Rooms, Timeslots, set of preference sessions.

As any genetic algorithm, this approach utilizes the genetic property “survival of the fittest” which means that as solutions are getting generated, bad solutions are eliminated and good solutions are carried over to the next step. In order to determine what’s good and what’s bad, a Fitness function is used. This function validates a given solution with the set of constraints and list of preference sessions and returns a value indicating how relevant the solution is. The fitness function also takes into consideration the training set of favorite sessions recommended by attendants and tries to optimize the fitness according to how well each solution is close to any of the favorite choices.

A solution is simply a set of associations of a session to room and a timeslot.

The algorithm starts by generating solutions at random, that is, by randomly picking a session and assigning it to a room and a timeslot. The session is then removed from the input and the selected room/timeslot is also removed from the list of remaining rooms/timeslots. This is to eliminate the possibility of assigning the same session twice. Hence, the probability of coming up with solutions that are at least worth considering is optimized. We will denote the set of generated solutions as generation 0; the first generation. Next, each solution in generation 0 is applied to the Fitness function which compares the solution against the set of constraints and returns a value indicating relevance. Once all solutions are evaluated, they are sorted in descending order(assuming lower value indicates better solution) and the top X percentage of the solutions is chosen to be carried on to the next generation. Kill all the remaining solutions. The surviving solutions will undergo two operations in order to compute the next generation. Mutation and Crossover. In mutating a solution, one association of a session to a room/timeslot is selected and the session is changed to a different session that is not already listed in the solution. In crossover, two solutions are picked at random and sessions are exchanged in between. This procedure is repeated over many generations until a solution that meets most of the constraints is met.

References:

[1] Wayne Smith, Applying Data Mining To Scheduling Courses at a University, School of Information Systems and Technology Claremont Graduate University

This study demonstrates the feasibility of applying the principles of data mining. Specifically it uses association rules to evaluate a nonstandard (“aberrant”) timetabling pilot study undertaken in one College at a University. The results indicate that inductive methods are indeed applicable, and that both summary and detailed results can be understood by key decision-makers, and, straightforward, repeatable SQL queries can be used as the chief analytical technique on a recurring basis. In addition, this study was one of the first empirical studies to provide an accurate measure of the discernable, but negligible, scheduling exclusionary effects that may impact course availability and diversity negatively.

[2] Atif Shahzad Nasser Mebarki Discovering Dispatching Rules For Job Shop Scheduling Problem Through Data Mining

A data mining based approach to discover previously unknown priority dispatching rules for job shop scheduling problem is presented. This approach is based upon seeking the knowledge that is assumed to be embedded in the efficient solutions provided by the optimization module built using tabu search. The objective is to discover the scheduling concepts using data mining and to obtain a rule-set capable of approximating the efficient solutions in a dynamic job shop scheduling environment. A data mining based scheduling framework is presented which consists of 3 phases: Search for a set of solutions, Apply data cleaning and for the resulting solutions including aggregation and attribute construction and the finally to model induction and interpretation by applying decision tree induction algorithm.

[3] Ahmed Hamdi Abu Absa, Sana’a Wafa Al-Sayegh, E-Learning Timetale Generator Using Genetic Algorithms

In this paper, the authors explain the details of the implementation of a computer program which employs Genetic Algorithms (GAs) in the quest for an optimal lecture timetable generator. GA theory is covered with emphasis on less fully encoded systems employing nongenetic operators. The field of Automated Timetabling is also explored. A timetable is explained as, essentially, a schedule with constraints placed upon it. The program, written in java, has the special libraries to deal with genetic algorithm which are used for the implementation. In a simplified university timetable problem it consistently evolves constraint violation free timetables. The effects of altered mutation rate and population size are tested. It is seen that the GA could be improved by the further incorporation of repair strategies, and is readily scalable to the complete timetabling problem.

[4] Branimir Sigl, Marin Golub, Vedran Mornar, Solving Timetable Scheduling Problem

Using Genetic Algorithms

In this paper a genetic algorithm for solving timetable scheduling problem is described. The algorithm was tested on small and large instances of the problem. Algorithm performance was significantly enhanced with modification of basic genetic operators. Intelligent operators restrain the creation of new conflicts in the individual and improve overall algorithm ‘s behavior.
The program uses eliminating selection, which chooses and eliminates bad individuals from the current population, making room for new children that will be born from the remaining individuals. The probability of elimination increases proportionally with the fitness value of the individual. As the remaining individuals are better than the average of the population, it is expected that their children will be better as well. There is some probability (though very small) that eliminating selection deletes the best individual. That would ruin the algorithm efforts and put its work back for some number of generations. Therefore, protection mechanism for best individuals has to be made, so the good genetic material is sustained in population. It is called the elitism. The authors’ choice was to keep just the top one individual. The reproduction operators constitute

Filed under .Net

Exception Handling Guidelines

April 8, 2011 Leave a comment

Forums and Minerals, the new Internet tools

Image via Wikipedia

Follow class naming conventions, but add Exception to the end of the name.
Some rules listed below are to be followed in Exceptions blocks or classes:

Never do a “catch” exception and do nothing. If you hide an exception, you will never know if the exception happened or not.
In case of exceptions, give a friendly message to the user, but log the actual error with all possible details about the error, including the time it occurred, method and class name etc.
Always catch only the specific exception, not generic exception as well as system exceptions.
You can have an application level (thread level) error handler where you can handle all general exceptions. In case of an ‘unexpected general error’, this error handler should catch the exception and should log the error in addition to
giving a friendly message to the user before closing the application, or allowing the user to ‘ignore and proceed’.
Do not write try-catch in all your methods. Use it only if there is a possibility that a specific exception may occur. For example, if you are writing into a file, handle only FileIOException.
Do not write very large try-catch blocks. If required, write separate try-catch for each task you perform and enclose only the specific piece of code inside the try-catch. This will help you find which piece of code generated the exception and you can give specific error message to the user.
You may write your own custom exception classes, if required in your application. Do not derive your custom exceptions from the base class SystemException. Instead, inherit from ApplicationException.
To guarantee resources are cleaned up when an exception occurs, use a try/finally block. Close the resources in the finally clause. Using a try/finally block ensures that resources are disposed even if an exception occurs.
Error messages should help the user to solve the problem. Never give error messages like “Error in Application”, “There is an error” etc. Instead give specific messages like “Failed to update database. Make sure the login id and password are correct.”
When displaying error messages, in addition to telling what is wrong, the message should also tell what the user should do to solve the problem. Instead of message like “Failed to update database.” suggest what should the user do: “Failed to update database. Make sure the login id and password are correct.”
Show short and friendly message to the user. But log the actual error with all possible information. This will help a lot in diagnosing problems.
Define a global error handler in Global.asax to catch any exceptions that are not handled in code. You should log all exceptions in the event log to record them for tracking and later analysis.

Filed under .Net, Errors! Tagged with Application programming interface, C++, Error message, Event (computing), Exception handling, Languages, Programming, Stack trace

Adding IntelliSense for JQuery in Visual Studio 2008

April 6, 2011 Leave a comment

To set up IntelliSense for JQuery you will need to download the JQuery Documentation File
from the JQuery site.

At the top of the JavaScript file in which you would like to have jQuery IntelliSense enabled, you will need to add a line to reference
the documentation file:

                                        /// <reference path="jquery-1.3.2-vsdoc2.js" />

If you downloaded jQuery and saved it to your project Visual Studio will look for the vsdoc.js file automatically if
the following conditions are met.

You downloaded and installed the hotfix for Visual Studio.
jQuery and the documentation file need to be named the same with the exception that the documentation file end with -vsdoc.js.
So when you add jQuery to your project make sure to rename them similarly. For instance, jquery-1.3.2.js is your jQuery library,
Visual Studio will look for the documentation file at jquery-1.3.2-vsdoc.js and load it.

(Note: the jQuery 1.3.2 documentation file is named jquery-1.3.2-vsdoc2.js on the Download page so make sure you take out
the 2 so that the file will be found by Visual Studio).
To test to make sure the documentation file loaded correctly, you can type $( and you should be presented with some documentation.

Filed under .Net, Technology Tagged with .NET Framework, Computer file, IntelliSense, JavaScript, JQuery, Microsoft Visual Studio, Programming, Visual Studio

The network BIOS command limit has been reached

April 6, 2011 Leave a comment

Image via Wikipedia

When you are building an asp.net deployment project, you may often recieve an ASPNETCOMPILER error “The network BIOS command limit has been reached” . As describes by Microsoft, the error occurs because of the following reasons:

This issue may occur if the client computer submits simultaneous, long-term requests against a file server that uses the Server Message Block (SMB) protocol. An example of a long-term request is when a client computer uses the FindFirstChangeNotification function to monitor a server share for changes.
This issue may occur if the MaxCmds registry value setting on the client is less than 50, or the MaxMpxCt registry value setting on the server is less than 50.

To resolve this issue, verify that the MaxCmds and MaxMpxCt registry values are set to 50 or more. To do this, follow these steps:

Click Start -> Run – > “regedit”
Navigate to the following registry key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanworkstation\parameters
Open the MaxCmds entry in the right listview.
In the Value data, enter a value of 50 or more.
Navigate to the following registry key:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanserver\parameters
Open the MaxMpxCt entry in the right listview.
In the Value data, enter a value of 50 or more.
Restart your computer for the changes to take effect.

Note The MaxCmds and MaxMpxCt registry entries are REG_DWORD decimal entries. If they do not exist on your computer, you can create them as new REG_DWORD values. The range of values for these registry entries is between 0 and 65535.

Filed under .Net, Errors! Tagged with File server, Microsoft, Microsoft Windows, Programming, Server Message Block, Windows Registry, Windows XP, Word (computing)

Collection was modified; enumeration operation may not execute

April 6, 2011 3 Comments

Image via Wikipedia

The error occurs when you are performing a for each loop over a generic list or a collection and there is a line of code inside the loop that is trying to modify the contents of the list. Take a look at the code below :

                                        Dim myList As New List(Of Integer)
                                        myList.Add(1)
                                        myList.Add(2)
                                        myList.Add(3)
                                        myList.Add(4)
                                        myList.Add(5)
                                        For Each i As Integer In myList
                                            myList.Remove(i)
                                        Next

the above code will throw an InvalidOperationException because we are removing items from the list while we are still iterating over its items using the for each loop.

a simple fix to the above code would be replacing the for each loop with the standard index loop as follows :

                                      For i As Integer = 0 To myList.Count - 1
                                            myList.Remove(i)
                                        Next

Filed under .Net, Errors! Tagged with Add-Ins, C++, Compiler, Foreach, Languages, Programming, String (computer science), Visual Basic

Cross-thread operation not valid: Control ‘ControlName’ accessed from a thread other than the thread it was created on

April 6, 2011 Leave a comment

Image via Wikipedia

This is a common error when you are developing a multithreading application you often recieve an InvalidOperationException
indicating that a thread is trying to access an object that was created on another thread. A typical code block that generates this
error is shown below :

Dim th As New Threading.Thread(AddressOf test)
 

Private Sub test()
    TextBox1.Text = "using textbox from another thread"
End Sub


Private Sub Form1_Load(ByVal sender As System.Object, _ 
 ByVal e As System.EventArgs) Handles MyBase.Load
     th.Start()
End Sub

In the code above, TextBox1 is a normal textbox placed in the form. As we predicted, the error is thrown because TextBox1 belongs to main thread
, which is the single thread that runs the form and th is another thread accessing the textbox from the test function. To resolve
this problem, each control must be exclusively accessed from it belonging thread. What we are talking about here is to apply
context switching whenever we need to access controls on different threads. This is easy to do in .net framework. In face, we can
also add a small functionality to check whether a cross threading operation is required before we actually go on and swtich the context
because context switching has its performance penalties.

Using the Invoke method of the form, we can pass in a MethodInvoker object, which is a delegate specifying the address of the
function that we would like to invoke in case if an invokation is required by the form’s thread. To do the actual testing if an invokation
is needed, we use the form’s InvokeRequired property. Below is the working version of the code:

Dim th As New Threading.Thread(AddressOf test)
 

Private Sub test()
      If Me.InvokeRequired Then
             Me.Invoke(New MethodInvoker(AddressOf test))
       Else
                TextBox1.Text = "using textbox from another thread"
        End If
End Sub

Private Sub Form1_Load(ByVal sender As System.Object, _ 
 ByVal e As System.EventArgs) Handles MyBase.Load
     th.Start()
End Sub

Filed under .Net, Errors! Tagged with .NET Framework, C++, Java, Languages, Method (computer science), Programming, Single threading, thread

← Older posts

	Understanding Heap S… on Exploit the buffer – Buf…
	Ali Tarhini on About
	cscturkey on About
	Matic Cankar on Parallel Naïve Bayesian C…
	Abdelmalik Dreidi on Face Recognition: An Intr…

References

Contents

Introduction

Microsoft Decision Trees

Microsoft Clustering

rosoft Naïve Bayes

Microsoft Time Series

Microsoft Association

Microsoft Sequence Clustering

Microsoft Neural Network

Microsoft Linear Regression

Microsoft Logistic Regression

Preparing the SQL Server Database

Preparing the Analysis Services Database

Creating an Analysis Services Project

Creating a Data Source

ating a Data Source View

Edit the Mining Models

Microsoft Decision Trees Model

reate a Forecasting Mining Model Structure Using the Wizard

sket Mining Model Structure Using the Wizard

Explore Mining Models in the Editor

Sequence Clustering

Explore Mining Models in the Editor

Welcome to Ali Tarhini’s blog

Check these out!

Email Subscription

Categories

Top Posts

Recent Posts

Recent Comments

Tags

Archive

Follow “Ali Tarhini”