## 3 Methodology
### System Analysis and Design
This method is a bottom-up approach that initially considers all data points to be their own cluster. The clusters that are closest together are merged recursively until a certain number of clusters or a distance threshold is met, after which the final clusters are formed, as illustrated in Figure 5. There are different linkage criteria that can be used to determine the distance between sets of observations; average linkage was selected, a middle ground between the tendency of small linkage to produce loose clusters and the tendency of complete linkage to produce tight clusters. However, agglomerative clustering is not fully unsupervised, in the sense that the model requires the number of clusters to be specified like in k-means clustering, or alternatively, a distance threshold can be specified to avoid explicitly setting the number of clusters. The second option was more applicable for this study since we wanted to make sure items that were physically close together were clustered, thus the distance threshold was set to a value that corresponded to the decision-making time and the traveling time set in the simulator. Although this approach nearly fulfilled all our requirements, there was still a major issue that the model did not fully address. The two aforementioned clustering algorithms work well with high-density graphs, but not so well with sparse ones. Both algorithms would require a connection between all 307,740 pairs to function properly, and it would take the simulator a very long time to accomplish that task. An imperfect but effective way to solve this is by setting distances for items with no connection to a very large number such as 10,000, thereby telling the model that those two items are dissimilar. Of course, this means that the algorithm cannot accurately discern the proximity of two items if data are insufficient, i.e., it will not cluster items that are supposed to be close together but do not have a connection stored yet. Thus, the DProSA algorithm is expected to have higher efficiency for larger datasets. A third algorithm was used to solve the issue of requiring denser graphs to work well. Affinity propagation is a clustering technique that is best fit for sparse graphs. As depicted in Figure 6, it works by calculating the \"responsibility\" and \"availability\" of each data point, and a high value for both makes that data point an exemplar. Responsibility measures the similarity of that data point to other data points, while availability measures how much support it receives from other data points. This machine learning model calculates the two criteria through multiple message exchanges that eventually converge to a set of exemplars which are \"representatives\" of clusters. Other data points then conform to the exemplars which best represent them. Exemplars are often located in dense regions of the data, but the model does not require a strongly connected graph. The model achieves this by using a  
Figure 5: Illustration of Agglomerative clustering model. similarity matrix instead of a distance matrix or dissimilarity matrix. The input matrices were converted accordingly for this algorithm. The machine learning models were used to cluster the items so they were grouped according to closest proximity. These clusters are essentially'sections' of the supermarket where item acquisition activity for those sets of items is higher than in other areas, and the timestamps represent the items. In order to reduce the time complexity of the sorting process and save memory space, clustering helped us by treating the clusters as one group of items. During the sorting process, the distance between each item no longer had to be referenced, as in the brute force method; instead, only the clusters were sorted. Dynamic sorting  
As mentioned earlier, this approach to sorting the shopping list is expected to be much faster than brute force since the sorting occurs for groups of items rather than individual items.