# Using Product Network Analysis to Optimize Product-to-Shelf Assignment Problems
## 3 Research Method
### Product Relationship Networks  
Let \(I=\{i_{1},\,i_{2},\,\ldots,\,i_{p}\}\) be the set of product items sold in a store where \(P\) is the total number of product items. A purchase database stores a set of purchase records in which a record consists of a purchase timestamp, a transaction identifier (T_ID), a customer identifier (C_ID), and a product item. Depending on how the product relationship is constructed, product items in the purchase database can be aggregated according to unique T_ID or C_ID. If records are aggregated using T_ID, the dataset is called a transaction-based dataset (TBD). If records are aggregated using C_ID, the dataset is called a customer-based dataset (CBD). Figure 2 shows a simple aggregation example. Figure 2a indicates 14 purchase records in a purchase database. After aggregating by T_ID, 6 transaction-based records are generated as shown in Figure 2b. Similarly, as shown in Figure 2c, 4 customer-based records are generated if C_ID is used to aggregate the purchase database.  
Based on different datasets, two types of Product Relationship Networks (PRNs) are constructed. If the network is constructed using the transaction-based dataset (TBD), the network is called a transaction-based network (TBN). If the network is constructed using the customer-based dataset (CBD), the network is called a customer-based network (CBN). The construction process for both types of PRNs includes the following two phases. The first phase derives all frequent 2-itemsets from an aggregated dataset using the Apriori algorithm under a minimum support count. The second phase builds the product association matrix according to the support values of frequent 2-itemsets.  
The Apriori algorithm proposed by [PERSON] and [PERSON] [7] is a popular method for identifying frequent itemsets. Let \(L_{k}\) represent the set of all frequent \(k\)-itemsets and \(C_{k}\) represents the set of candidate \(k\)-itemsets. \(k\)-itemsets may or may not be frequent, but all of the frequent \(k\)-itemsets are included in \(C_{k}\). The Apriori algorithm scans the dataset and calculates the count of each candidate in \(C_{k}\) to determine which \(k\)-itemsets are frequent. All candidates with a count exceeding the minimum support count are frequent and belong to \(L_{k}\). Otherwise, the candidates are removed. \((k+1)\)-itemsets of \(C_{k+1}\), which include frequent \(k\)-itemsets, can be repeatedly generated by \(L_{k}\). The algorithm will stop  
Figure 2: (a) Purchase database, (b) transaction based dataset, (c) customer based dataset.  
when \(L_{k}=\O\). Note that this algorithm will stop when \(k=2\) since only frequent 2-itemsets are required in this study.  
After obtaining frequent 2-itemsets, the product association matrix of a PRN can be determined. Let M = [\(m_{i,j}\)] be the product association matrix of size \(y\times y\) where \(y\) is the number of individual items which have ever appeared in the frequent 2-itemsets, and \(m_{i,j}\) is defined as:  
\[m_{i,j}=SupCount\big{(}\big{\{}t_{i},t_{j}\big{\}}\big{)} \tag{1}\]  
where \(SupCount\) is the function returning the support count of itemset \(\{i_{i},i_{j}\}\). If \(m_{ij}\) is high, the association between items \(i_{i}\) and \(i_{j}\) is strong. Note that if itemset \(\{i_{i},i_{j}\}\) cannot be found in the frequent 2-itemsets, the support count \(m_{i,j}\) will be marked as \"x\" in the matrix.  
In TBN, records with the same transaction ID are aggregated so that the association value between two items indicates the co-purchase relationship from the viewpoint of transactions. In CBN, records with the same customer ID are aggregated so that the association between items in CBN indicates the co-purchasing relationship from the viewpoint of customers. That is, CBN treats each customer in the store as equally important, while TBN might favor frequent buyers.