10.2.1 Motivating Applications

Discovering underlying similarities except keyword-based similarity allows for more meaningful and accurate things recommendation, classification and even context-aware activity recognition. We briefly discuss some of the areas where things contextual similarity can be applicable.

• Recommendation. Things recommendation is a crucial step for promoting and taking full advantage of the Web of Things (WoT), where it benefits the individuals, businesses, and society on a daily basis in terms of two main aspects. On the one hand, it can deliver relevant things to users based on users' preferences and interests. On the other hand, it serves to optimize the time and cost of using WoT in a particular situation [39]. The underlying correlations of things can enhance the performance of the generalized recommendation systems in the Web of Things in terms of two main points. Firstly, due to the sparsity of thing-user interactions, widely used collaborative filtering recommendation systems fail to find similar users or things, since these methods assume that two users have invoked at least some things in common. Moreover, users who have never used any things can not be fed good results in the first place (i.e., the cold start problem). Secondly, physical things have more distinctive structures and connections in terms of functionalities in real life (i.e., usefulness), as well as non-functionalities (i.e., availability), which are saliently highlighted in the contextual information of human-thing interactions.

• Searching. Developing efficient searching approaches is a crucial challenge with the rapid increase of a vast amount of things connected to the Web. Our approach adds one additional dimension to assist and reinforce current search techniques. For instance, existing semantic-based solutions do not make full use of the rich information contained in users' historical interactions with things (e.g., implicit relations of different things). Our approach can effectively capture such information, which can be integrated into existing search solutions, whereas the strength of latent connections between things/objects can be leveraged to predict which things will possibly co-occur. In this way, it would be complimentary to many semantic-based solutions for better performance, which usually require preparation of prior knowledge such as defining the descriptions of things and their corresponding characteristics and concepts. Our primary work on searching with entity graph for the Web of Things can be found at [38].

• Context-aware Activity Recognition. Recognizing human activities from sensor readings has recently attracted much research interest in pervasive computing due to its potential in many applications, such as assisted living of older people and healthcare. This task is particularly challenging because human activities are often performed in a not only simple (i.e., sequential) but also complex (i.e., interleaved or concurrent) manner in real life [34]. Our proposed approach provides a new useful means to infer human activities by taking advantages of reasoning relationships of globally unique object instances. For example, dense sensing-based activity monitoring learns human activities by detecting and analyzing human-object interactions. By discovering correlations of objects, we can cluster and organize things into differently structured groups based on their underlying relationships. In many cases, an activity could involve multiple relevant things including not only the things with similar functionalities but also things with complementary functionalities, which can be effectively uncovered by our proposed approach. Pairwise things with strong correlations indicate either they have similar functionalities (i.e., microwave and toaster) or them have a higher likelihood to be used together. For instance, a water tap and a chopping board are both in use when we prepare meals since most of the time we need to wash cooking ingredients (e.g., vegetables) before cutting them.

10.2.2 Problem Statement and Definitions

The only data source used in our work is human-thing interactions, namely things usage events. Each event happens when a person interacts with a particular thing, which carries three kinds of information: location, timestamp, and user. Each usage event record can be defined as a quadruplet ThingID, UserID, Timestamp, Location described as follows.

The problem targeted in this article can be therefore formulated as discovering the latent correlations among things by exploiting observable human-thing interactions with the goal of automatically distinguishing strong correlations of things from the weak ones. As illustrated in Fig. 10.2, each node denotes a thing (represented as a ball) in a three-dimensional space of identity, spatiality, and temporality. Things are discrete without distinctive and explicit correlations (Fig. 10.2(A)). However, our proposed approach can derive latent connections among these things and form a relational graph of things, where their implicit relatedness can be revealed (Fig. 10.2(B)). Therefore, our goal can be formulated as follows in Problem 10.1. The derived latent relations are a set of real-valued numbers between 0 and 1 in this work.

To complete this goal, there are two sequential subproblems we need to solve, which are defined as Subproblem 10.1.1 and Subproblem 10.1.2, respectively.

10.3.1 Spatio-Temporal Graph Construction

A spatiotemporal graph such as the one shown in Fig. 10.3(A) reflects the temporal pattern and spatial information hidden in the things usage events. In our approach, the spatial and temporal information of things usage events is treated as inseparable since they are mutually influential on detecting the correlations among things. Unlike virtual resources such as web pages, music or images, physical things such as restaurants and cookware usually provide more distinguished functionalists, and are more connected with people's daily lives. Some such distinctive features of physical things are their physical locations and functioning times. For example, kitchenware is more frequently used during dining times and they have higher likelihood to stay in a kitchen or similar locations (e.g., a dining room). We specifically explore the integrity of spatial and temporal information in the ubiquitous things environment via finding the periodical pattern between time and locations.

Generally, the timing of access to similar things may be similar. For example, restaurants are likely to be visited by people during lunch or dinner times. For the spatial information, we also argue in this paper that geographical influence to user activities cannot be ignored, i.e., a user tends to interact with the nearby things rather than the distant ones [41]. For example, if a user is at her office, she has a higher probability of using office facilities such as telephone, desktop computer, printer, and seminar rooms.

A spatiotemporal graph has three sets of nodes, namely locations, things, and timestamps. It contains one type of intra-relation (i.e., representing similarities between locations) and three types of inter-relations between locations, things, and timestamps. Edges between times and things can be obtained from usage events, say, the weight of edge $<loc,o>\in {\mathbf{E}}_{\mathbf{Y}}$ and $<ts,o>\in {\mathbf{E}}_{\mathbf{Z}}$ is proportional to the number of times objects o is used in a location loc and at timestamp ts. The inter-relation between location and time $<loc,ts>\in {\mathbf{E}}_{\mathbf{X}}$, indicates the periodical patterns. Formally, we define the spatio-temporal graph ${\mathbf{G}}_m$ as the following:

The corresponding weight matrix ${\mathbf{W}}_m$ of graph ${\mathbf{G}}_m$ can be formulated as:

${\mathbf{W}}_m=\left[\begin{array}{ccc}\hfill {\mathbf{W}}_{\mathbf{Loc}}\hfill & \hfill {\mathbf{W}}_{\mathbf{X}}\hfill & \hfill {\mathbf{W}}_{\mathbf{Y}}\hfill \\ \hfill {\mathbf{W}}_{\mathbf{X}}^{\mathbf{T}}\hfill & \hfill {\mathbf{W}}_{\mathbf{Ts}}\hfill & \hfill {\mathbf{W}}_{\mathbf{Z}}\hfill \\ \hfill {\mathbf{W}}_{\mathbf{Y}}^{\mathbf{T}}\hfill & \hfill {\mathbf{W}}_{\mathbf{Z}}^{\mathbf{T}}\hfill & \hfill {\mathbf{W}}_{\mathbf{O}}\hfill \end{array}\right]$

where each of the entries in Eq. (10.1) can be obtained as the following. ${\mathbf{W}}_{\mathbf{Loc}}$ indicates the similarity of each pair of locations. Given two locations, we measure their similarity using the Jaccard coefficient between the sets of things used at each location:

${\mathbf{W}}_{\mathbf{Loc}}(i,j)=\frac{|{\mathrm{\Gamma }}_i^o\cap {\mathrm{\Gamma }}_j^o|}{|{\mathrm{\Gamma }}_i^o\cup {\mathrm{\Gamma }}_j^o|}$

where ${\mathrm{\Gamma }}_i^o$ and ${\mathrm{\Gamma }}_j^o$ denote the set of used things at location i and location j respectively. ${\mathbf{W}}_{\mathbf{Ts}}$ and ${\mathbf{W}}_{\mathbf{O}}$ should be 0 since we do not consider the relationships between timestamps and the ones between things. ${\mathbf{W}}_{\mathbf{Y}}$ and its transpose ${\mathbf{W}}_{\mathbf{Y}}^{\mathbf{T}}$ are integers, indicating how often a thing is accessed at a location. Similarly, ${\mathbf{W}}_{\mathbf{Z}}$ and its transpose ${\mathbf{W}}_{\mathbf{Z}}^{\mathbf{T}}$ are integers, which indicate how often a thing is accessed at a particular time.

For defining relationship between time stamps and locations and their corresponding weight ${\mathbf{W}}_{\mathbf{X}}$ of graph ${\mathbf{G}}_m$, we propose periodic patterns between locations and timestamps. Given a sequence of locations $Loc=\{lo{c}_1,...,lo{c}_n\}$, our aim is to find their corresponding time period. To obtain relationship between time and location, we analyze the potential periods for each location and find the periodical pattern between locations and timestamps. A periodic pattern represents the repeat of certain usage event at a specific location with the certain time interval(s).

Periodic patterns can be extracted by analyzing things usage events. In particular, we build a time series dataset for each location where the elements of the time series data are the number of time slots (e.g., 0 for the period of 0:00–1:00; 1 for 1:00–2:00 and so on) that a thing at a location is invoked. We can clearly observe such periodic pattern from the example relating to a kettle in the kitchen from Fig. 10.4(A) and its periodogram in Fig. 10.4(B).

Given a sequence of locations, we adopt the Discrete Fourier Transform (DFT) method to detect the time periods in this discrete time-series sequence [31]. For each location, we define an integer sequence $A=\{a_1{a}_2...a_n\}$, where $a_i=1$ if the thing is used at this location at time i, and 0 otherwise. Essentially, this sequence can be transformed into a sequence of n complex numbers $X(f)$ from the time domain to the frequency domain:

$X(f_{k/N})=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}{a}_n{e}^{-\frac{j2\pi kn}{N}},k=0,...,N-1$

where $k/N$ denotes the frequency that each coefficient captures. As a result, DFT transforms the original sequences as a linear combination of the complex sinusoids $s_f(n)=\frac{e^{j2\pi fn/N}}{\sqrt{N}}$. The Fourier coefficients represent the amplitude of each of these sinusoids after sequences S is projected on them.

We aim at capturing the general shape of time-series data (e.g., thing usage over time) as “economically” as possible. To do so, we propose to use a spartan representation² from which one could reconstruct the signal using just its dominant frequencies (i.e., the ones that carry most of the signal energy). A popular way to identify the power content of each frequency is by calculating the power spectral density (PSD) of the sequence which indicates the signal power at each frequency in the spectrum. A well-known estimator of the PSD is the periodogram. The periodogram P is a vector comprised of the squared magnitude of the Fourier coefficients $X(f_{k/N})$:

$P(f_{k/N})={\Vert X(f_{k/N})\Vert }^2,k=0,1,...,\lceil \frac{N-1}{2}\rceil$

The k dominant frequencies appear as peaks in the periodogram (and correspond to the coefficients with the highest magnitude). In order to specify which frequencies are important, we need to set a threshold and identify those frequencies higher than this threshold. Each element of the periodogram provides the power at frequency $k/N$ or, equivalently, at period $N/k$. That is, coefficient $X(f_{k/N})$ corresponds to periods $[\frac{N}{k},...,\frac{N}{k-1})$. Interested readers are referred to [31].

When obtaining the periodogram of each location, we can decide their corresponding peak points based on preset threshold. From the periodogram, we can find the location and its corresponding time range. One benefit of using the periodogram is that we can visually identify the peaks as the k most dominant periods (period = 1/frequency). For automatically returning the important periods for a set of location sequences, we can simply set a threshold in the power spectrum to distinguish the dominant periods.

10.3.2 Social Graph Construction

Users' relations (e.g., friendships) can have a significant impact on things usage patterns. Personal tastes are correlated. Research in [10] shows that friendships and relations between users play a substantial role in human decision making in social networks. For instance, people usually turn to a friend's advice about a commodity (e.g., hair straighter) or a restaurant before they go for them. For exploring the impact social links between users on things' correlation discovery, we also construct a social graph, which is an augmented bipartite graph representing user interactions with things based on things usage events. As shown in Fig. 10.3(B), such a graph contains two sets of entities, users U and things O. There is one type of intra-relation between users (also called social connections) and one type of inter-relations: edges between users and things that can be obtained from usage events. Formally, the social graph is defined as the following:

The corresponding weight matrix ${\mathbf{W}}_u$ of graph ${\mathbf{G}}_u$ can be formulated as:

${\mathbf{W}}_u=\left[\begin{array}{cc}\hfill {\mathbf{W}}_U\hfill & \hfill {\mathbf{W}}_M\hfill \\ \hfill {\mathbf{W}}_M^T\hfill & \hfill {\mathbf{W}}_O\hfill \end{array}\right]$

The entries in Eq. (10.5) can be obtained as follows: ${\mathbf{W}}_M$ and its transpose ${\mathbf{W}}_M^T$ should be proportional to the number of times of a thing being used by the users. ${\mathbf{W}}_O$ should be zero since we do not consider relationships between things. The weight ${\mathbf{W}}_U$ of edges ${\mathbf{E}}_M$ indicates the user similarity influenced by the social links between users, reflecting the homophily meaning that similar users may have similar interests. We use the cosine similarity to calculate ${\mathbf{W}}_U$ as follows:

${\mathbf{W}}_{\mathbf{U}}(i,j)=\frac{e^{\alpha cos(b(i),b(j))}}{{\sum }_{k\in \mathrm{\Omega }(i)}{e}^{\alpha cos(b(i),(b(k))}}$

where $cos(b(i),b(j))=\frac{b(i)\cdot b(j)}{\Vert b(i)\Vert \Vert b(j)\Vert }$, $\mathrm{\Omega }(i)$ is the set of the user i's friends (i.e., $j\in \mathrm{\Omega }(i)$), $b(i)$ is the binary vector of things used by user i, $\Vert \cdot \Vert$ is the L-2 norm of vector $b(\cdot )$, and α is a parameter that reflects the preference for transitioning to a user who interacted with the same things.

10.3.3 Correlation Inference

After the two graphs ${\mathbf{G}}_m$ and ${\mathbf{G}}_u$ are constructed, we can perform the random walk with restart (RWR) [33] to derive the correlation between each pair of things. RWR provides a good relevance score between two nodes in a graph and has been successfully used in many applications such as automatic image captioning, recommendation systems, and link prediction. The goal of using RWR in our work is to find other things that have top-k highest relevance scores for a given thing. The values of the relevance scores imply the strength of the correlations among things. In the following, we focus on using RWR on the spatiotemporal graph ${\mathbf{G}}_m$ for discovering correlations between things.

We assume the random walker starts from a thing node $o_i$ on ${\mathbf{G}}_m$. The random walker iteratively transits to other nodes which have edges with $o_i$, with the probability proportional to the edge weight between them. At each step, $o_i$ also has a restart probability c to return to itself. We can obtain the steady-state probability of $o_i$ visiting another vertex ${\pi }_i$ when the RWR process is converged. The RWR process can be formulated as

${\pi }_i=(1-c)\mathbf{P}{\pi }_i+c{\mathbf{e}}_i$

where ${\pi }_i\in {\mathbb{R}}^{N\times 1}$, and weight matrix from graph ${\mathbf{G}}_m$ is ${\mathbf{W}}_m\in {\mathbb{R}}^{N\times N}$ (Section 10.3.1), ${\mathbf{e}}_i\in {\mathbb{R}}^{N\times 1}$ with i-th entry is 1, all other entries are 0. Eq. (10.7) can be further formulated as:

${\pi }_i=c{(\mathbf{I}-(1-c){\mathbf{P}}_m)}^{-1}{\mathbf{e}}_i=\mathbf{Q}{\mathbf{e}}_i$

where I is an identity matrix and ${\mathbf{P}}_m\in {\mathbb{R}}^{N\times N}$ is the transition matrix, which can be obtained based on weight matrix ${\mathbf{W}}_m$ of ${\mathbf{G}}_m$ by row normalization:

${\mathbf{P}}_m={\mathbf{W}}_m{\mathbf{D}}_m^{-1}$

where ${\mathbf{D}}_m$ is a diagonal matrix with ${\mathbf{D}}_m(i,i)={\sum }_j{\mathbf{W}}_m(i,j)$. The random walker on thing $o_i$ traverses randomly along its edges to the neighboring nodes based on the transition probability ${\mathbf{P}}_m(i,j),\forall j\in N(i)$, and the probability of taking a particular edge $<o_i$,$o_j>$ is proportional to the edge weight over all the outgoing edges from $o_i$ based on Eq. (10.9).

In Eq. (10.8), $\mathbf{Q}=c{(\mathbf{I}-(1-c){\mathbf{P}}_m)}^{-1}=c{\sum }_{t=0}^{\infty }{(1-c)}^t{\mathbf{P}}^t$ defines all the steady-state probabilities of random walk with restart. ${\mathbf{P}}^t$ is the t-th order transition matrix, whose elements $p_{ij}^t$ can be interpreted as the total probability for a random walker that begins at node i and ends at node j after t iterations, considering all possible paths between i and j. Since in our case we only consider relevance score between two things, if we vary the value of t, we can explicitly explore the relationship between two things at different scales. The steady-state probabilities for each pair of nodes can be obtained by recursively processing Random Walk and Restart until convergence. The converged probabilities give us the long-term visiting rates from any given node to any other node. This way, we can obtain the relevance scores of all pairs of thing nodes, denoted by $R_m(o_i,o_j)\in {\mathbf{R}}_m,\forall o_i,o_j\in \mathbf{O}$. It should be noted that the results can be calculated more efficiently by using the Fast Random Walk with Restart implementation [29] via low-rank approximation and graph partition.

Similarly, the transition probability matrix ${\mathbf{P}}_u$ for the social graph ${\mathbf{G}}_u$ can be obtained using:

${\mathbf{P}}_u={\mathbf{W}}_u{\mathbf{D}}_u^{-1}$

where ${\mathbf{D}}_u$ is a diagonal matrix with $D_u(i,i)={\sum }_j{\mathbf{W}}_u(i,j)$. Accordingly, we can obtain the relevance scores of things on this graph $R_u(o_i,o_j)\in {\mathbf{R}}_u,\forall o_i,o_j\in \mathbf{O}$.

The overall relevance score (i.e., the correlation value) of any pair of things can be calculated using

$R(o_i,o_j)=\alpha R_m(o_i,o_j)+\beta R_u(o_i,o_j)$

where $\alpha \in [0,1]$ and $\beta \in [0,1]$, which are regulatory factors affecting the weight on the social influence and the spatio-temporal influence.

With obtained correlation values, we could construct a top-k correlation graph of things by connecting each thing with the things that have top-k overall correlation values $R(o_i,o_j)$. Formally, the graph is defined as the following:

Extracting Feature ${\mathbf{F}}_{\mathbf{L}}$

This feature represents the label probabilities for unknown things, which can be computed using generative Bayesian rules from G, where each unknown thing $o^{⁎}$ is to be assigned one or multiple labels $l_k\in \mathbf{L}=\{l_1,...,l_k\}$. We propose to formulate our solution as posterior probability $Pr(l_k|o^{⁎})$. Once we know these probabilities, it is straightforward to assign $o_i$ the label having the top-K largest probabilities,

$Pr(l_k|o^{⁎})=\frac{Pr(o^{⁎}|l_k)Pr(l_k)}{{\sum }_{j=1}^{K}Pr(x|l_j)Pr(l_j)}\propto Pr(o^{⁎}|l_k)p(l_k)$

where the prior distribution probability $Pr(l_k)$ can be easily calculated from the training dataset. Let ${\mathbf{o}}^{l_k}=o_1^{l_k},...,o_{M_k}^{l_k}$ be the training dataset, having $M_k$ things with label k. Then $Pr(o^{⁎}|l_k)$ can be calculated using:

$\begin{array}{cc}\hfill Pr(o^{⁎}|l_k)& =\frac{1}{Z}\sum _{m=1}^{M_k}Pr(o^{⁎}|o_m^{l_k},l_k)Pr(o_m^{l_k}|l_k)\hfill \\ \hfill & =\frac{1}{Z\times M_k}\sum _{m=1}^{M_k}Pr(o^{⁎}|o_m^{l_k},l_k)\hfill \end{array}$

where Z is a normalizing constant and the conditional probability $Pr(o^{⁎}|o_m^{l_k},l_k)$ indicates the relevance score between testing thing $o^{⁎}$ and things in the training dataset $o_m^{l_k}$. $Pr(o^{⁎}|o_m^{l_k},l_k)\approx {\pi }_{o^{⁎}}$ denotes the steady state probability between $o^{⁎}$ and ${\mathbf{o}}^{l_k}=o_1^{l_k},...,o_{M_k}^{l_k}$, which can be obtained from Eq. (10.8) in our RWR process. The distribution $p(o_m^{l_k}|l_k)$ is set as a uniform distribution $1/M_k$. The probability $p(o^{⁎}|l_k)$ can be predicted in Eq. (10.13), and the labels with different posterior probabilities can be assigned to the testing thing. As a result, we can get the label probabilities for each testing object.

Extracting Latent Feature ${\mathbf{F}}_{\mathbf{S}}$

With RGT, we can easily extract features of things that indicate the things relationship with different communities on G. In reality, things usually hold multiple relations. For instance, a thing might be shared among its owner, owner's friends, co-workers, or family members. It might also be connected to other things based on functionality or non-functionality attributes. Detecting such relations from RGT, which can be used as a structural feature for things annotation, is naturally related to the task of modularity-based community detection [15]. Modularity is to evaluate the goodness of a partition of undirected graphs. The reason that we choose this method is that modularity has been shown to be an effective quantity to measure community structure in many complex networks [28].

Modularity $\mathcal{Q}$ is like a statistical test that the null model is a uniform random graph model, where one vertex connects to others with uniform probability. It is a measure of how far the interaction deviates from a uniform random graph with the same degree distribution. Modularity is defined as:

$\mathcal{Q}=\frac{1}{2m}\sum _{ij}[{\mathcal{A}}_{ij}-\frac{d_i{d}_j}{2m}]\delta (s_i,s_j)$

where ${\mathcal{A}}_{ij}$ is the adjacent matrix on the graph RGT, m is the number of edges of the matrix, $d_i$ and $d_j$ denote the in-degree of vertex i and out-degree of vertex j, and $\delta (s_{t_i},s_{t_j})$ are the Kronecker delta function that takes the value 1 if node $t_i$ and $t_j$ belong to the same community, 0 otherwise. A larger modularity $\mathcal{Q}$ indicates denser within-group interaction. So that, the modularity-based algorithm aims to find a community structure such that $\mathcal{Q}$ is maximized. In [20], Newman proposes an efficient solution by reformulating $\mathcal{Q}$ as:

$\mathcal{Q}=\frac{1}{2m}{\mathcal{S}}^{\mathcal{T}}\mathbf{B}\mathcal{S}$

where $\mathcal{S}$ is the binary matrix indicating which community each node belongs to. B is the modularity function, is defined as the following:

${\mathcal{B}}_{ij}={\mathcal{A}}_{ij}-\frac{d_i{d}_j}{2m}$

Since our relational graph of things (RGT) is a weighted and directed graph, we need to make some modifications on $\mathcal{Q}$ to solve the equation. This involves two steps.

In the first step, we extend $\mathcal{B}$ to directed graphs. Based on [15], we rewrite the modularity matrix $\mathcal{B}$ as the following:

${\mathcal{B}}_{ij}^{\prime }={\mathcal{A}}_{ij}-\frac{d_i^{in}{d}_j^{out}}{2m}$

where $d_i^{in}{d}_j^{out}$ are the in-degrees and out-degrees of all the nodes on the RGT graph. In the second step, we extend ${\mathcal{B}}^{\prime }$ to weighted graphs. To do so, we conduct further modification based on Eq. (10.17). It can be rewritten further as below:

${\mathcal{B}}_{ij}^{″}={\mathcal{W}}_{ij}-\frac{w_i^{in}{w}_j^{out}}{2m}$

where ${\mathcal{W}}_{ij}$ is the sum of weights of all edges in the RGT graph replacing the adjacency matrix $\mathcal{A}$, $w_i^{in}$ and $w_j^{out}$ are the sum of the weights of incoming edges adjacent to vertex $t_i$ and the outgoing edges adjacent to vertex $t_j$ on the RGT graph respectively. After these two steps, it should be noted that different from undirected situation, ${\mathcal{B}}^{″}$ is not symmetric. To use the spectral optimization method proposed by Newman in [20], we restore symmetry by adding ${\mathcal{B}}^{″}$ to its own transpose [15], thereby the new ${\mathcal{Q}}_{new}$ is:

${\mathcal{Q}}_{new}=\frac{1}{4m}{\mathcal{S}}^{\mathcal{T}}({\mathcal{B}}^{″}+{\mathcal{B}}^{″\mathcal{T}})\mathcal{S}$

We are then able to calculate all the eigenvectors corresponding to the top-k positive eigenvalue of ${\mathcal{B}}^{″}+{\mathcal{B}}^{″\mathcal{T}}$ and assign communities based on the elements of the eigenvector [21]. We take the obtained modularity vectors as the latent features, which indicate things relationships to communities (i.e., a larger value means a closer relationship with a community).

Extracting Feature ${\mathbf{F}}_{\mathbf{C}}$

It is the set of content-based features extracted from thing descriptions. We convert the keywords vectors into tf-idf format, which assigns each term x a weight in a thing's description d. $tf-idf(x,d)=tf(x,d)\times idf(x)$, where $tf(x,d)$, the number of times word x occurs in the corresponding thing's description d, and idf is the inverse text frequency which is defined as : $idf(x)=\log \frac{|N|}{df(x)}$, where $|N|$ is the number of texts in our dataset, and $df(x)$ is the number of texts where the word x occurs at least once.

Based on our experience in ontology bootstrapping for Web services [25], we exploit Term Frequency/Inverse Document Frequency (TF/IDF)—a common method in IR for generating a robust set of representative keywords from a corpus of documents—to analyze things' descriptions. It should be noted that the common implementation of TF/IDF gives equal weights to the term frequency and inverse document frequency (i.e., $w=tf\times idf$). We choose to give higher weight to the idf value (i.e., $w=tf\times id{f}^2$). The reason behind this modification is to normalize the inherent bias of the tf measure in short documents.

Finally, the set of feature vectors for the N things in the dataset $\tilde{\mathbf{v}}=[{\overrightarrow{v}}_1,...,{\overrightarrow{v}}_N]$ where ${\overrightarrow{v}}_i\in {\mathbb{R}}^m$ is the feature vector for each thing, m is the size of vocabulary we produced. For better performance, we perform a cosine normalization for tf-idf vectors: $\hat{\mathbf{v}}=\frac{\overrightarrow{\mathbf{v}}}{{\Vert \overrightarrow{\mathbf{v}}\Vert }_2}$ [24].

Building a Discriminative Classifier

After obtaining the features based on attributes of G and things, we combine the features (${\mathbf{F}}_{\mathbf{L}}+{\mathbf{F}}_{\mathbf{S}}+{\mathbf{F}}_{\mathbf{C}}$) together and feed them into a discriminative classifier.

Our method is a very flexible feature-based method, where the structural features can be put into any discriminative classifier for classification. In this paper, we evaluate our method based on SVM and Logistic regression. Specifically, we adopt LibSVM [4] for one-vs-rest classification.

Discussion

The high and real-time streams of interactions between human and ubiquitous things call for online processing techniques that are suitable to large-scale datasets and can be rapidly updated, adapted to reflect the constantly evolving the contextual similarities due to changing contextual information of things (e.g., social networks, status, locations etc). Our proposed model can be easily extended to deal with large-scale IoT data streams with online processing and incremental techniques due to the following characteristics of the model:

• We characterize each thing as a discriminative feature descriptor including static features (e.g., content-based features) and easily integrated dynamic features (e.g., locations, and instantaneous status of things). The feature vectors can be continuously updated with users' interactions with things in a real-time manner. It is noted that we only focus on training an offline model with the mixture of static and dynamic features, which provides the possibility of online learning, such as partaking in an incremental activity learning a framework that is able to continuously update and learn newly seen data.

• Our proposed model does not require any explicit input from users. All the contextual information is automatically obtained from users' social networks, localization techniques and sensor technologies in a non-obtrusive way.

• The process of contextual similarity calculation works based on the random walk techniques, which has been successfully used in large-scale online search engines. This type of techniques can be easily parallelized (e.g., using Hadoop framework for improving performance) and processed in real time.

Encoding User Friendships

User affinity can directly adopt the method in Section 10.3.2. We construct a directed weighted graph ${\mathbf{G}}_u=(V_u,E_v)$, whose vertex set $V_u$ corresponds to users set $\{u_1,...,u_m\}$, edges set $E_v$ represents the friendships between users and the range of their associated weight are in $[0,1]$. Bigger weights represent stronger ties between users. $W_u$ indicates the user similarity influenced by the social links between users, reflecting the homophily (i.e., similar users may have similar interests). We use the cosine similarity to calculated $s_{i{i}^{\prime }}$ as follows:

$s_{i{i}^{\prime }}=\frac{e^{\alpha \cos (b(i),b(i^{\prime }))}}{{\sum }_{k\in \mathrm{\Omega }(i)}{e}^{\alpha \cos (b(i),(b(k))}}$

where $\cos (b(i),b(i^{\prime }))=\frac{b(i)\cdot b(i^{\prime })}{\Vert b(i)\Vert \Vert b(i^{\prime })\Vert }$, $\mathrm{\Omega }(i)$ is the set of the user i's friends (i.e., $j\in \mathrm{\Omega }(i)$), $b(i)$ is the binary vector of things used by user i, $\Vert \cdot \Vert$ is the L-2 norm of vector $b(\cdot )$, and α is a parameter that reflects the preference for transitioning to a user who interacts with the same things.

After we obtain the users friendship matrix from ${\mathbf{G}}_u$, we factorize users' friendship matrix to derive a high-quality, low dimensional feature representation to user-based latent features vectors $u_i\in {\mathbb{R}}^{1\times m}$ and factor-based latent feature vectors $u_{i^{\prime }}^{\prime }\in {\mathbb{R}}^{1\times m}$ on analyzing the social network graph ${\mathbf{G}}_u$. The conditional probability of $s_{i{i}^{\prime }}$ over the observed social network is determined by:

$\begin{array}{cc}\hfill & s_{i{i}^{\prime }}\sim Pr(s_{i{i}^{\prime }}|u_i^T{u}_{i^{\prime }}^{\prime };{\sigma }_s)\hfill \\ \hfill & \text{where}{u}_i\sim \mathcal{N}(0,{\sigma }_u^2),u_{i^{\prime }}^{\prime }\sim \mathcal{N}(0,{\sigma }_{u^{\prime }}^2)\hfill \end{array}$

Similar to the Web link adjacency [43], if a user i has lots of links to other users, the trust value of $s_{i{i}^{\prime }}$ should be decreased. Whereas if a user i is trusted by many other users, the trust value of $s_{i{i}^{\prime }}$ should be increased, since the user can be considered as local authority. $s_{i{i}^{\prime }}$ should be adjusted as:

$s_{i{i}^{\prime }}^{⁎}=\sqrt{\frac{d^{in}(i^{\prime })}{d^{out}(i)+d^{in}(i^{\prime })}}\times S_{i{i}^{\prime }}$

where $d^{out}(i)$ represents the outdegree of node i, while $d^{in}(i^{\prime })$ indicates the indegree of $i^{\prime }$. Eq. (10.21) can be reformulated as:

$s_{i{i}^{\prime }}^{⁎}\sim Pr(s_{i{i}^{\prime }}^{⁎}|u^T{u}^{\prime };{\sigma }_s)$

Encoding User-Thing Interactions

User-thing interactions $y_{ij}$ are embodied by the usage frequency of thing i by user j in a certain time frame. We can map the usage frequency to interval $[0,1]$ by using function $f(x)=(x-y_{min})/(y_{max}-y_{min})$ without loss of generality, where $y_{max}$ and $y_{min}$ are the maximum and minimum usage values respectively. The dyadic relationship between a user and a thing does not only depend on their latent factor $U^{T}V$, whose vulnerability is that it makes use of past interactions and can not handle brand new things well, i.e., cold start problem. To tackle this issue, we use the explicit features directly by profiling users observable features $x_i\in {\mathbb{R}}^c$ (i.e., age, gender, location etc.) and things observable features $z_j\in {\mathbb{R}}^d$ (i.e., textual description of things functionalities). Here, c and d are the dimensionalities of users observable features and things observable features respectively. The dyadic relationship (thing usage value) depends on not only the inner product of latent factors of users and things, but also their observable features. Things usage value $y_{ij}$ can be defined as the following conditional probability:

$y_{ij}\sim Pr(y_{ij}|u_i,v_j,x_i,z_j,{\sigma }_y^2)$

We adopt the bilinear product to specify the similarity between user observable features and thing observable features [7]. The pairwise similarity between $x_i$ and $z_j$ can be denoted as:

$r_{ij}={\mathbf{w}}^T(x_i\otimes z_j)$

where w is a column vector of entries $\{w_{mn}\}$, $x_i\otimes z_j$ denotes the Kronecker product of $x_i$ and $z_j$. Eq. (10.25) can be rewritten as:

$r_{ij}=x_i^{T}W{z}_j$

where matrix $W\in {\mathbb{R}}^{m\times n}$ is a weight coefficients capturing pairwise associations between user i's explicit feature vector and thing j's explicit feature vector. The thing usage value depends on both the inner product of user and thing latent factors and the bilinear product of user observable features and thing observable features. Eq. (10.24) can be reformulated as:

$y_{ij}\sim Pr(y_{ij}|u_i^T{v}_j+r_{ij},{\sigma }_y^2)$

Model Learning

Given a training dataset for $\mathbb{O}=\{{\mathbb{O}}_y,{\mathbb{O}}_s,{\mathbb{O}}_t\}$, the joint posterior probability of model parameters Σ can be obtained through Bayes' theorem:

$Pr(\mathrm{\Sigma }|\mathbb{O})\propto Pr(\mathbb{O}|\mathrm{\Sigma })Pr(\mathrm{\Sigma })$

Maximizing Eq. (10.28) can be converted to minimizing the negative logarithm of $Pr(\mathbb{O}|\mathrm{\Sigma })Pr(\mathrm{\Sigma })$ via:

$\begin{array}{cc}\hfill \underset{\mathrm{\Sigma }}{\min }L(\mathrm{\Sigma })& =\min {\lambda }_y\sum _{ij\in {\mathbb{O}}_y}\ell (y_{ij},u_i^T{v}_j+r_{ij})\hfill \\ \hfill & +{\lambda }_s\sum _{i{i}^{\prime }\in {\mathbb{O}}_s}\ell (s_{i{i}^{\prime }}^{⁎},u_i^T{u}_{i^{\prime }}^{\prime })+{\lambda }_t\sum _{j{j}^{\prime }\in {\mathbb{O}}_t}\ell (t_{j{j}^{\prime }},v_j^T{v}_{j^{\prime }}^{\prime })\hfill \\ \hfill & +{\lambda }_{\mathbf{w}}{\Vert \mathbf{w}\Vert }^2+{\lambda }_u{\Vert u\Vert }^2+{\lambda }_{u^{\prime }}{\Vert u^{\prime }\Vert }^2+{\lambda }_v{\Vert v\Vert }^2+{\lambda }_{v^{\prime }}{\Vert v^{\prime }\Vert }^2\hfill \end{array}$

where ℓ⋅ is a loss function (we adopt the most widely used ${\ell }_2$ loss), and $\lambda =\{{\lambda }_y,{\lambda }_s,{\lambda }_t,{\lambda }_{\mathbf{w}},{\lambda }_u,{\lambda }_{u^{\prime }},{\lambda }_v,{\lambda }_{v^{\prime }}\}$ are trade-off parameters. A gradient descent process can be implemented to solve the parameters. Given a training dataset $\{y_{ij}\}$, the objective function in Eq. (10.29) can be found by performing gradient descent in $u_i$, $v_j$ and $w_{mn}$.

$\begin{array}{cc}\hfill & u_i\to u_i-\delta \times (\frac{\partial \ell }{\partial u_i}(y_{ij},u^{T}v+r_{ij})v_j+u_i^T{u}_i)\hfill \\ \hfill & v_j\to v_j-\delta \times (\frac{\partial \ell }{\partial v_j}(y_{ij},u^{T}v+r_{ij})u_i+v_j^T{v}_j)\hfill \\ \hfill & w\to w-\delta \times (\frac{\partial \ell }{\partial w}(y_{ij},u^{T}v+r_{ij})u_i{v}_j^T+w^{T}w)\hfill \\ \hfill & {u^{\prime }}_{i^{\prime }}\to {u^{\prime }}_{i^{\prime }}-\delta \times (\frac{\partial \ell }{\partial {u^{\prime }}_{i^{\prime }}}(s_{i{i}^{\prime }}^{⁎},u_i^T{u^{\prime }}_{i^{\prime }})u_i+{u^{\prime }}_{i^{\prime }}^T{u^{\prime }}_{i^{\prime }})\hfill \\ \hfill & {v^{\prime }}_{j^{\prime }}\to {v^{\prime }}_{j^{\prime }}-\delta \times (\frac{\partial \ell }{\partial {v^{\prime }}_{j^{\prime }}}(t_{j{j}^{\prime }},v_j^T{v^{\prime }}_{j^{\prime }})v_j+{v^{\prime }}_{j^{\prime }}^T{v^{\prime }}_{j^{\prime }})\hfill \end{array}$

where δ is the learning rate. After we obtain the optimal parameters ${\mathrm{\Sigma }}^{⁎}$, we can use them to predict the given testing data $\{\tilde{i},\tilde{j},y_{\tilde{i},\tilde{j}}\}$

$y_{\tilde{i}\tilde{j}}=u_{\tilde{i}}^T{v}_{\tilde{j}}+\sum _{mn}^{cd}{x}_{\tilde{i}n}{z}_{\tilde{j}m}{w}_{mn}^{⁎}$

10.6.1 Experiment Setup

Due to the lack of experimental public data sets, we set up a testbed that consists of several different places in the first author's home (e.g., bedroom, bathroom, garage, kitchen etc), where approximate 127 physical things (e.g., couch, laptop, microwave, fridge etc.) are monitored by attaching RFID and sensors. Table 10.1 presents the statistics of things used in this paper. The details in regards to this testbed can refer to [37]. To collect the records of things usage events, we need to figure out i) how to detect a usage event when it is happening; and ii) how to retrieve this thing's corresponding three contextual information. There are two ways to detect usage events of things with two identification technologies used, namely senor-based state changes and RFID-based mobility detection.

To conduct experimental studies, we manually labeled 127 things with 397 different labels. It should be noted that some things belong to multiple categories, therefore having multiple labels. For example, a Wii device belongs to category label Entertainment as well as Home Appliance. This dataset serves as the ground-truth dataset in our experiments for performance evaluation. Ten volunteers participated in the data collection phase by interacting with RFID tagged things for a period of four months, generating 20,179 records on the interactions of the things tagged in the experiments.

10.6.2 Evaluation on Thing Annotation

We randomly removed the category tags of a certain percentage, ranging from 10% to 50%, of things from each category of the ground-truth dataset. These things were used to test our approach while the rest were used as the training set. We iterated five times for each training percentage and took the averaged value as the final result. Our algorithm produces a vector of probabilities, representing the assignment probabilities of all labels for an unknown object. In our experiments, we ranked these probabilities and chose the top k labels to compare with the ground truth labels. The k value was set to the number of ground truth labels for each unknown object and it varies from object to object. The parameters α and β were set as 0.5 each.

We particularly compared the annotation performance by using i) the features obtained from G, ii) the features obtained from thing descriptions (i.e., content features ${\mathbf{F}}_{\mathbf{C}}$), and iii) the combination of the both. Each process was repeated 10 times and the average results were recorded. Similar observations were obtained for different testing percentages. Fig. 10.6 shows the result when we removed 30% of things from each category of the ground-truth dataset. Descriptions of things are normally short and noisy, it is therefore not surprising that the performance based on content features only is worse than the one based on implicit structural features (i.e., ${\mathbf{F}}_{\mathbf{L}}+{\mathbf{F}}_{\mathbf{S}}$) in most categories. The consistent good performance from the latent features also indicates that our top-k correlation graphs G is able to capture the correlations among things well. From the figure, we can see that by combining the two together, the performance of all six categories is increased and is the best consistently among the three.

10.6.3 Evaluation on Recommendation

We compare the prediction accuracy of our approach based on fusing social networks and things correlations (FST) with some state-of-the-art approaches based on probabilistic factor analysis: Probabilistic Matrix Factorization (PMF) [23], SoRec [16] and SVD++ [12]. This experiment evaluated our approach, in particular, its capability in handling the cold start problem, which refers to providing accurate prediction when some users only use few things or even have no usage historical records at all. In order to verify the capability of our approach to predicting the usage value of things that have not been used, we randomly selected and marked off $p\text{\%}$ of data ($p=10$, 20 and 50) from our dataset as training data and different number of latent factors (5 and 10) to test all the methods. The experimental results are shown in Table 10.2.

From the table, it is clear that our approach outperforms other methods on different training ratios and different number of factors, especially when the training data is small. PMF is a pure probabilistic factor model. Relying heavily on user-thing usage matrix, it can not deal with the circumstance where little interactions information is available. SoRec works better than PMF and SVD++ because of its aggregation of user-user internal information (social links). Our approach not only incorporates users and things internal information, but also defines the explicit features (i.e., content) for users (e.g., users profile) and things (e.g., description of things functionalities), which makes our approach performing better when there is a cold start problem. The experimental result further demonstrates the effectiveness on improving the recommendation accuracy by incorporating things correlations.