We present our experience in creating a novel unsupervised clustering algorithm for situation-aware pattern extraction from usage logs. The algorithm automatically estimates nearoptimal number of clusters and cluster centroids. It models situation by taking advantage of sensors. 5-fold cross validations using real-world data show that the algorithm delivers higher accuracy than existing algorithms with much lower complexity. As a result it is the first clustering algorithm that can be practically deployed on mobile handheld devices in the real world. We also describe the research problems in situation-aware personalization that must be addressed before users can benefit from the learning algorithms and speculate on possible approaches to the solutions. Consumers are overwhelmed when trying to get what they want from the Web using their handheld devices. Personalization is recognized as a key to help the users, and understanding user interests is critical for personalization. Since users' interests are often situation dependent, we decided to pursue research on situation-aware user interest mining. With more sensors, such as GPS, camera, and gyroscope, embedded in mobile handhelds, we can capture the environmental contexts while recording a user usage. Increased usage of wearable sensors can enable us to capture users' physical and physiological state. If we use the captured sensor data to represent the situation of a usage event and extract patterns from the usage logs, we can then use the patterns to predict the user's situational interests for better personalization. The problem is that handheld devices have limited power and computation resources for complex analytics. To address this problem, the Maggitti project [16] suggested sending usage logs to a server for the analysis. This approach, however, resulted in immediate privacy concerns. To protect user privacy, we aimed for complete client solutions on mobile handheld devices. Currently there are many client-side solutions. Many of them target at media recommendations [1, 2] and Web information retrieval [3]. Most of them require profiles and situations defined by the users or by rules specified at design time; some even require the users to proactively train the system first. These requirements are unrealistic, since users are unlikely to specify situational preferences and keep them updated. Users are even less likely to train the system by entering their situations every time they use their phones. To alleviate users from these burdens, the author of [5] used unsupervised clustering algorithms to extract patterns from user usage data combined with context data from sensors. However, there is no substantial performance results reported and it is not generally applicable in real-life cases since it requires prior knowledge of K, the number of clusters, an important parameter for good performance, but K is typically unknown and varies from dataset to dataset. For a client-side solution to be practically deployable in the real world, we must eliminate all the impractical assumptions and requirements. In addition, the solution must be lightweight and able to perform well for the datasets with varying characteristics such as the density of valid data entries. In this paper, we will first describe our approach to solving the problem in Section 2. We will then present the results in Section 3. In Section 4, we will discuss the difficulties in situationaware pattern mining and in Section 5 we will conclude and speculate future research directions in this research area.
Our goal is to create a learning algorithm for usage pattern extraction that is practically
deployable on mobile handheld devices. We chose two use scenarios to drive algorithm
development: the situation-aware mobile task recommendation [
The raw log data is processed and encoded for clustering based on the requirements of the driving use scenarios. A data vector is semantically partitioned into two portions: a portion representing a situation and a portion representing user-need to be predicated. For example, for task recommendation, situation is represented by the context part only and the application usage part is used for predicting the applications that are likely to be used in a situation. In case of smart search, both the context and the application usage are used to represent situation and the interest part is used for predicting user needs in the situation.
At a prediction time, the sensor values are sampled to represent the current situation that is compared with the situation portion of each centroids. The centroid most similar to the current situation is selected for prediction. For example, in the case of application recommendation, we recommend applications that are most frequently used in a current situation. In the case of smart search, we use highly probable keywords plus current location to form queries and search for links and Ads for the user.
The input data densities of the two driving use cases are quite different. By data density, we mean the density of valid entries in the prediction portion of an input matrix. In the case of task recommender, it means the density of the valid entries in the application-usage portion of the matrix, where as in the smart search case, it means the density of the valid entries in the userinterest portion of the matrix. In the task recommender case, we assume the density is 100% since an application is either used or not used. In the smart search case, we assume that only the data entries that contain user implicit or explicit feedbacks are valid, and all the others are unknown – similar to the assumption used in collaborative filtering. Since a typical user would only give feedbacks to a very small number of items among all the items considered, the data density is usually very low.
feedback
Seeking for an algorithm that could deliver good performance for both scenarios, we need
datasets with various densities in our experiments. The first problem we faced is that there are no
real life data that can be used for algorithm development and we had to devise a cold-start
method to statistically generate synthetic data [
We chose to use unsupervised clustering approach to solving the problem because in the real
life, mobile device usage data will not come with labels. We started by using the LBG [
We created the One-Pass Clustering (OPC) algorithm [
After all the groups are classified, the number of basic groups becomes the estimated optimal number of clusters, K, and the situation state of each basic group becomes the initial situation centroid for the cluster. The OPC algorithm then assigns the data instances in the noisy groups into appropriate clusters by computing the similarity between the situation states between a noisy group and each of the centroids and assigns the data instances in the noisy groups to the cluster with highest similarity. It then updates the corresponding situation centroid. After all the data in noisy groups are assigned to the clusters, the algorithm then re-computes the prediction portion in every cluster.
We compared the performance of the algorithms for both task recommendation and smart
search using real-life data gathered from eight users including students, engineers, and managers
for 6 months. We recorded their application usages on BlackJackII phones together with the date,
time, location, battery level, device mode (e.g., “out door”, “automatic”, “vibrate”, etc.), and ring
status at each usage event. .Limited by space, we will only include the co-clustering in this paper.
We will also only describe the details of the result for the task recommendation here so as to
motivate our discussions on the difficulties of situation-aware pattern extraction. Interested
reader can find more details in [
We used a simple average method (AVG) as the base for algorithm comparison, where the unknown data fields are filled using the average of the valid values from the same column as predicated values; if there are no valid values in the column, the average of the valid values of entire matrix is used. For the co-clustering, we used the KL algorithm to estimate near-optimal number of clusters and used the LBG algorithm for initializing the centroids before running the co-clustering itself. The KL algorithm iteratively finds the k that gives the smallest difference in the overall distortions between kth and (k+1)th iterations. Its computation complexity is O{C2mnT)}, where C is the number of clusters, T is the number of iterations, m and n are the dimensions of the situation portion of the matrix. Obviously the complexity is too high to be used on mobile handhelds, especially considering the combined complexity of co-clustering and KL. In comparison, the computation complexity of OPC, including k estimation and clustering, is O{Cmn}. Although theoretically the number of clusters could be equal to the number of state combinations of the situation portion of the vector, in reality, it is much smaller since the number of patterns in a dataset is typically small. In our 8-user-6-month datasets, the number of clusters ranges from 1 to 280.
True Positiveness True Negativeness Overall Accuracy
User 1
User 2
User 3
User 4
User 5
User 6
User 7
User 8 CC OPC AVG CC OPC AVG CC OPC AVG
We used true positiveness (TP), true negativeness (TN), and overall accuracy defined in [
From the table, we can observe that co-clustering performs the worst although it is the most complex algorithm especially combined with the LBG and KL algorithms. Although it might be possible to further tune the KL algorithm and recommendation schemes, we expect the improvements to be small and not worth the high computation and memory costs. On the other hand, the simple AVG algorithm performs well, especially for datasets that do not contain clear situational patterns or for datasets with no statistically sufficient data for pattern extraction.
We observed that the real-life usage data vary widely from having no clear patterns to having strong patterns. Also for a single user, typically there are no clear patterns in the usage data at the beginning and patterns emerge and become clearer over time. In addition, over time some old patterns will gradually disappear and new ones will emerge. This means that a practically deployable algorithm should also be able to deliver good accuracy in most of these cases in addition to being able to estimate K. Our results show that the OPC algorithm performs the best over the datasets with these varying characteristics. For example, in Table 1, the TP performance of OPC and AVG differs from 6% to -1%, while TN performance differs from 2% to 0%. Overall, the OPC performs better than AVG, because it behaves like the AVG algorithm when there are no sufficient evidences for patterns, but it behaves like clustering when evidences increase.
We encountered problems in both data preprocessing and computation formulation. In this
section we will present our experiences so as to invite discussions from the research community.
The first problem is accuracy. As shown in the last section, even with good estimates of the
number of clusters and initial centroids, the prediction accuracy is only moderately higher than
the simple average method. This is mainly due to the difficulties in situation representation. For
example, user’s preferences often depend on her mood and who are around, but we are not able
to capture these parameters. Using fixed context states may introduce noises since what context
state should be used for representing a situation may vary from user to user and from time to
time. A naive solution could be to assign weights based on specific use scenarios, but such
solution may not be adaptive to different users. Furthermore a same context may be more
relevant for one situation than another. This means that the weighting for a context may not be
applicable to all situations. Since the features chosen by traditional feature selections [
The second problem is raw log data processing. For consumers to benefit from situationaware user modeling, the raw log data needs to be automatically transformed in order to be used by the learning algorithms. The transformation includes cleaning, quantization/grouping, and encoding. The quality of transformation significantly impacts the performance and how to transform typically depends on the use scenarios and user’s life style. A reasonable way might be to allow a use scenario to specify the requirements and the system automatically does the job. But we found several issues need to be addressed for this to happen.
One issue is the need to handle missing context data in raw log records. For example the location information may be missing because getting GPS data is very slow and the cell tower information is not available during phone calls. The battery status may be missing due to system limitations. We addressed this problem by sampling context values periodically in addition to sampling them at the time of use and by deriving a missing value from the valid value(s) in a time window around the usage event. But this interpolation can introduce significant noise into prediction and periodic sampling consumes power. Perhaps support from sensor and system designers to provide high quality context data can be a better solution to the problem.
Another issue is the difficulties of automatic cleaning, quantizing and encoding of raw data. For example many locations do not have statistically significant number of usage events and many applications occur infrequently in a log. We addressed this problem by retaining 9 frequently visited ZIP-code level locations, by combining the infrequently visited locations into a single group, and by grouping the applications by types, e.g. grouping SMS, MMS and IM as messaging. The issue gets more complicated if we consider that different use scenarios may require different treatments. Since there can be many types of data being logged, many applications available, and potentially a large number of items are to be predicated or recommended in the real world, how to model the log data fields in order to flexibly support the needs of various scenarios still need more research.
Situation-aware personalization is becoming more important in mobile and pervasive computing. Previous works in this area use assumptions that prevent them to be practically deployable in the real world. In this paper, we described the OPC algorithm that does not require the impractical assumptions and is able to perform well for datasets with broader characteristics. It delivers higher accuracy with much lower complexity than existing algorithms and runs completely on a mobile handheld device. However for end users to benefit from the results of user modeling, we need to address the following research issues: 1) a data model that supports automatic preprocessing (cleaning, quantization, and encoding) of usage data based on given requirements, 2) more accurate ways to approximate user's situations using sensors, 3) more semantically correct ways for computing similarity between context values. We also speculate that a client and server coordination solution could go a long way. Specifically a user's device could send predicted preferences to a server without revealing the user’s situation and the server offers recommendations based on the user’s preferences and the preferences from the people similar to the user. 21. H. Song, S. Jeong, D. Cheng, and S. Kalasapur, “Efficient situation-aware user preferences mining on mobile devices", to be submitted to RecSys 2009. 22. I. Katsavounidis, C.-C. J. Kuo, and Z. Zhang, “A New Initialization Technique for Generalized Lloyd Iteration”, IEEE Signal Processing Letters, Vol. 1, No. 10, Oct. 1994.