Augmented intuitive dissimilarity metric for clustering of Web user sessions

Abstract

Clustering is a very useful technique to categorise Web users with common browsing activities, access patterns and navigational behaviour. Web user clustering is used to build Web visitor profiles that make the core of a personalised information recommender system. These systems are used to comprehend Web users surfing activities by offering tailored content to Web users with similar interests. The principle objective of Web user sessions clustering is to maximise the intra-group while minimising the inter-group similarity. Efficient clustering of Web users’ sessions not only depend on the clustering algorithm’s nature but also depend on how well user concerns are captured and accommodated by the dissimilarity measure that are used. Determining the right dissimilarity measure to capture the access behaviour of the Web user is very significant for substantial clustering. In this paper, an intuitive dissimilarity measure is presented to estimate a Web user’s concern from augmented Web user sessions. The proposed usage dissimilarity measure between two Web user sessions is based on the accessing page relevance, the syntactic structure of page URL and hierarchical structure of the website. This proposed intuitive dissimilarity measure was used with K-Medoids Clustering algorithm for experimentation and results were compared with other independent dissimilarity measures. The worth of the generated clusters were evaluated by two unsupervised cluster validity indexes. The experimental results show that intuitive augmented session dissimilarity measure is more realistic and superior as compared to the other independent dissimilarity measures regarding cluster validity indexes.

Keywords

Augmented Web user sessions frequency of the page hierarchical structure intuitive dissimilarity metric page relevance page duration syntactic structure

1. Introduction

Due to exponential growth and continual popularity of the World Wide Web (www), most organisations now put their stipulated information on the Web to provide Web-based services to Web users. At present, masses are navigating Websites at a very large scale to acquire information and knowledge. This user navigation on the Web results in the enormous quantity of information about their surfing activities on the Web hosting servers in the form of Web server access logs [1]. These Web server logs are further analysed to deduce useful information and this analysis is known as Web usage mining. A challenging aspect of Web usage mining is to deduce useful information about Web users’ habits, interests and expectations. The information about the browsing behaviour of Web users may be revealed by applying different Web usage mining approaches on the Web server log repositories [2]. Clustering is one of the effective Web usage mining techniques to group Web users with common browsing activities, access patterns and navigational behaviours. The potential applications of Web user session clustering are in accessing personalised information, improvement in information delivery system, Website modification, business intelligence and Web user characterisation [3].

Clustering techniques are broadly classified into two major classes: one works with feature vector data and is known as object data clustering; the other works with relational data and is known as relational clustering. Relational clustering is preferred over feature vector based clustering for categorisation of Web user sessions because they are difficult to represent by numerical features [4]. But the essential requirement of any relational clustering algorithm is to encode a degree of resemblance between pairs of user sessions in the form of dissimilarity matrix. Determining the right dissimilarity measure to capture the access behaviour of the Web user is very significant for substantial clustering. One of the most challenging issues in clustering Web sessions is how to measure the similarity of two Web user sessions. Clustering results very much depend on how well user concerns are captured and accommodated by the used similarity metric between two Web user sessions [5]. Typically, the high precisions of dissimilarity metric leads to the enhanced quality clusters of Web user sessions and vice versa [6].

Therefore, a good similarity measure should be defined so that it does not ignore the syntactic and hierarchical organisation of page URLs of Web navigations in user sessions. This similarity measure should also consider the Web user’s habits, interests and expectations by considering the relevance of pages in every session because all of the URLs visited in a session are not equally important to the user [7]. The most popular measures used for Web sessions clustering are Euclidean distance, Cosine similarity measure and Jaccard Coefficient [8]. In the past, a variety of similar measures have been proposed to recognise accurate similarity among users based on their access behaviour, but these measures are used independently [9 –12].

This paper presents an intuitive augmented session dissimilarity measure to estimate a Web user’s concern from augmented Web user sessions. This similarity measure is based on accessing page relevance, the syntactic and hierarchical structure of a page URL.

The rest of this paper is organised as follows: Section 2 briefly reviews the existing literature on different (dis)similarity measures for web user sessions. In section 3, the methodology adopted for the computation of page relevance based augmented session similarity is described in detail. Section 4 describes the computation of a page relevance based augmented session similarity matrix in brief. Section 5 presents the URL based syntactic similarity computation method in brief. Section 6 presents a description of a hierarchy based syntactic similarity technique. In section 7, an intuitive augmented session similarity metric is proposed with an illustrative example. In section 8, a Web user clustering and various cluster validity indexes were discussed in detail to test the effectiveness of different dissimilarity measures. In section 9, experiments have been set to demonstrate the performance of the intuitive similarity metric with various other individual measures presented and results were discussed in details. Finally, section 10 concluded this work with some suggested future studies.

2. Related work

In the literature, diversity of similarity measures has been discussed for measuring Web user’s session similarity/dissimilarity to categorize the Web users who exhibit the analogous browsing behaviour. Web user sessions are represented by a vector of the dimension of page URLs on any Website. Different values are assigned to these dimensions (page URLs) for different user access behaviour analysis. The extensively used technique is to assign binary values to these dimensions based on their user access (1-for access) or not access (0-for not access) of a Web page (URL) in a particular session [2, 9]. Nasraoui et al. [9], used this method of Webpage access representation in any Web user session vector. They use a cosine similarity measure to compute the similarity between any two user sessions using this binary representation for clustering of user sessions. Yan et al. [13] and Forsati et al. [14], proposed access duration and access frequency of the page based weights to page URLs, in particular, sessions as an alternative of binary weights. Chan [10] and Xiao et al. [11] the concept of implicit measure of user interest of a page was introduced and further extended by Liu and Kešelj [12] and proposed page stay time (duration) and page access frequency to measure the user concern for a Web page. Banerjee and Ghosh [15], used relative time spent on longest common subsequence and abstract similarity graph. Wang and Zaïane [16], proposed the concept of sequence alignment using the hierarchical structure of URLs on the Website. The precise page viewing time of visiting pages and URL of the pages are presented in Liu and Lu [17]. Bose et al. [18], introduced a Website concept hierarchy based similarity scoring system that further integrated with other similarity measures like browsing order and time spent on a page.

3. Methodology

This section presents a detailed description of the adopted methodology under following subsections.

3.1. Web server logs pre-processing

The Web server access logs keep a record of all files/pages explicitly or implicitly accessed by the Web users. Each log entry consists of different fields like remote host address, remote log name, username, timestamp and time zone of the request, request method, path on the server, protocol version, service status code, the size of the returned data and referrer user agent [19].

First, the Weblog entries that are not germane to our purpose were removed. These are mostly implicit requests made for embedding objects within Web pages, requests made by automated software agents [20], unsuccessful requests of users and requests with access methods other than GET.

Second, the Web server log entries are grouped into user sessions, where session refers to the unit of interaction between a Web user and a Web server. This work considered a broadly accepted and practically implemented timeout based session identification method [21]; other session identification techniques are also available in the literature [22, 23]. A session is created when a new IP address is found in the Weblog entries, and subsequently, a request from the same IP address is added to the session as long as the lapsed time between two consecutive requests does not exceed a predefined threshold value, set for 30 min in our work. Otherwise, the current session closes and new session starts. A Web user’s historical access pattern may have more than one session because he or she may visit a Website from time to time and spend an arbitrary amount of time between consecutive visits [24].

3.2. Vector space representation of Web user sessions

Suppose, for a given website, there is m usage sessions extracted from the Web server log $S_{i} = {S_{1}, S_{2}, \dots . S_{m}}$ accessing n number of different URLs (pages) $P_{i} = {P_{1}, P_{2}, \dots . P_{n}}$ on a Website in some time interval. We represent each user session $S_{i}$ by following the equation $S_{i} = {S_{i}^{1}, S_{i}^{2}, \dots S_{i}^{n}}, \forall i = 1, 2, \dots, m .$ where each $S_{k}^{i}$ represents a harmonic mean of the number of visits to the page $P_{k}$ within the session $S_{i}$ , and the duration of the page (in seconds) $P_{k}$ in session $S_{i}$ , and represented by Eq. (1) and Eq. (2).

S_{k}^{i} \leftarrow {\begin{matrix} Number of visits to the page . \\ Time spent on page (in seconds) . \\ Size of the page (in bytes) . \end{matrix}

(1)

R [m, n] = (\begin{matrix} S_{1}^{1} & S_{1}^{2} & \dots & S_{1}^{n} . \\ S_{2}^{1} & S_{2}^{2} & \dots & S_{2}^{n} . \\ ⋮ & ⋮ & ⋱ & ⋮ \\ S_{m}^{1} & S_{m}^{2} & \dots & S_{m .}^{n} \end{matrix})

(2)

3.3. Computation of a page relevance in any Web user session

Web users’ interests for any page are computed by implicit measures [10, 11]. These implicit measures are page stay time (duration) and page access frequency of a Web page in a Web user session [12]. The following measures are computed to find the relevance of a Web page in any user session to measure the Web user concern for a Web page.

3.3.1. Duration of page $(D o P) :$

Duration of page is defined as the time spent on a page by a Web user and is the difference between the exact time of the request for page $P_{i}$ and the time of the request for the next Webpage in the session from the access log file. Eq. (3) is used to compute the duration of a Web page ( $P_{i}$ ) in a user session ( $S_{k}$ ) and is represented as ${(D o P)}_{P_{i}}$

{(D o P)}_{P_{i}} = \frac{\frac{Σ Time Spent on (P_{i})}{Size of (_{P_{i}})}}{Max (\forall_{j \in S_{k}} \frac{Σ Time Spent on (P_{j})}{Size of (P_{j})})}

(3)

where 0≤ ${(D o P)}_{P_{i}}$ ≤1.

3.3.2. Frequency of page $(F o P) :$

Frequency of a page is the number of times the Web page $P_{i}$ has been visited in the session. It seems natural to assume that Web pages with a higher frequency are of more concern to users, which is normalised by the total number of visits of Web pages in the session. Eq. (4) is used to compute the frequency of the web page ( $P_{i}$ ) in user session ( $S_{k}$ ) and represented as $({(F o P)}_{P_{i}})$

{(F o P)}_{P_{i}} = \frac{Σ # of visits to (P_{i})}{Max (\forall_{j \in S_{k}} Σ # of visits to (P_{j}))}

(4)

where 0≤ ${(F o P)}_{P_{i}}$ ≤ 1.

3.3.3. Relevance of the page $(R o P) :$

The relevance of the page in any user session is computed by giving equal importance to the duration of page and frequency of page because this harmonic mean will moderate the impact of large and small outliers [6]. Eq. (5) is used to measure the relevance of a Web page ( $P_{i}$ ) in user session ( $S_{k}$ ) and represented as ${(R o P)}_{P_{i}}$

{(R o P)}_{P_{i}} = \frac{2 \times {(D o P)}_{P_{i}} \times {(F o P)}_{P_{i}}}{{(D o P)}_{P_{i}} + {(F o P)}_{P_{i}}}

(5)

where 0 ≤ ${(R o P)}_{P_{i}}$ ≤ 1.

3.4. Augmented Web user sessions

Now, by applying Eqs. (3) to (5) the page relevance matrix ( $R M_{m \times n}$ ) is computed. This relevance matrix will define the relevance of each page in every session. If the page has high relevance means the user has more concern in this page. This relevance matrix is given by Eq. (6). By incorporating page relevance in the Web user session access behaviour matrix, simple Web user sessions are converted to augmented Web user sessions.

R M_{m \times n} = (\begin{matrix} {(R o P)}_{11} & {(R o P)}_{12} & \dots & {(R o P)}_{1 n} \\ {(R o P)}_{21} & {(R o P)}_{22} & \dots & {(R o P)}_{12} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ {(R o P)}_{m 1} & {(R o P)}_{m 2} & \dots & {(R o P)}_{mn} \end{matrix})

(6)

The augmented Web session is represented as $A S_{a} = {(P 1, {(R o P)}_{P 1}, (P 2, {(R o P)}_{P 2}) \dots (P n, {(R o P)}_{P n})}$ . Where $P i$ , and ${(R o P)}_{P i}$ are the visiting page and its relevance, respectively.

4. Page relevance based augmented session similarity

Here, relevance of pages accessed in user sessions is incorporated in simple cosine similarity measure in Eq. (7). Augmented session similarity between any two augmented Web user sessions $A S_{a}$ and $A S_{b}$ is represented as $A S S_{(A S_{a}, A S_{b})}$ and given by Eq. (7) where $A S_{a} {(R o P)}_{i}$ represents the relevance of any visiting page $P_{i}$ in augmented sessions $A S_{a}$ .

A S S_{(A S_{a}, A S_{b})} = \frac{Σ_{i = 1}^{n} A S_{a} {(R o P)}_{i} \times A S_{b} {(R o P)}_{j}}{\sqrt{Σ_{i = 1}^{n} A S_{a} {(R o P)}_{i}^{2}} \sqrt{Σ_{i = 1}^{n} A S_{b} {(R o P)}_{j}^{2}}}

(7)

This augmented session similarity measure may be more realistic and may represents session similarities based on the Web user’s habits, interests and expectations as compared to a simple binary session (dis)similarity measure. But a key constraint of this measure is also the same as of a simple binary session (dis)similarity measure [9], that it completely abandons the hierarchical grouping of Web URLs which are placed in the same directory if Web pages are related.

5. A URL syntactic similarity between $i^{th}$ and $j^{th}$ page URL

In [9], the authors also defined an alternative URL based syntactic similarity measure to compute the syntactic similarity between any pair of Web page URLs $(P_{i}, P_{j})$ . The URL syntactic similarity is defined as $U S S_{(U S_{a}^{p_{i}}, U S_{b}^{p_{j}})}$ and given by Eq. (8).

U S S_{(U S_{a}^{p_{i}}, U S_{b}^{p_{j}})} = M in (1, \frac{| L o P (P_{(a, i)}) \cap L o P (P_{(b, j)}) |}{M ax (1, M ax (L o P (P_{(a, i)}), L o P (P_{(b, j)})) - 1)})

(8)

Where $L o P (P_{(a, i)})$ is length of URL (or number of edges) of path traversed from root node to respective node of $P_{i}$ in user session $U S_{a}$ .

By applying URLs syntactic similarity of Eq. (8), the augmented URL syntactic similarity measure between two augmented Web user sessions $(A S_{a}^{p_{i}}, A S_{b}^{p_{j}})$ is computed by Eq. (9) and represented as $A U S S_{(A S_{a}^{p_{i}}, A S_{b}^{p_{j}})}$ .

A U S S_{(A S_{a}^{p_{i}}, A S_{b}^{p_{j}})} = \frac{Σ_{i = 1}^{n} Σ_{j = 1}^{n} A S_{a} {(R o P)}_{i} \times A S_{b} {(R o P)}_{j} \times U S S_{(U S_{a}^{pi}, U S_{b}^{p_{j}})}}{Σ_{i = 1}^{n} A S_{a} {(R o P)}_{i} \times Σ_{j = 1}^{n} A S_{b} {(R o P)}_{j}}

(9)

However, this similarity measure assumes a uniform URL based syntactic similarity of one for any node, its parent and all sibling nodes of any parent. This assumption is not very intuitive because in a hierarchy based syntactic model of a Website tree, lower level nodes represent more conceptually related information than the higher level nodes. Therefore, their syntactic similarity can provide arbitrarily low values between identical sessions.

6. A hierarchical syntactic similarity between $i^{th}$ and $j^{th}$ page URL

Consider a hypothetical hierarchical organisation of Web page URLs of a Website (Figure 1). In a hierarchy based syntactic model of the site, Web page URLs are placed at different levels of the tree and represented by nodes. The root of the tree is the highest level URL and represents the home page of a Website. Here, it is assumed that any node, its parent, and all sibling node pairs of any parent at lower levels in URL hierarchy, should be more similar than higher level pairs. The correlated subject URLs are put together (as siblings) in the same subdirectory.

For the root node page URL, level one is assumed when the level of lowest common ancestor ( $L C A$ ) [25, 26] for any pair of URLs of web pages ( $P_{i}$ , $P_{j}$ ) is found. As we are assuming that when we traverse at lower levels in URL hierarchy, we get more particular information or siblings/children at a lower level has more similarity than at higher levels. The hierarchical syntactic similarity $H S S_{sim (i, j)}$ between any pair of Web page URLs ( $P_{i}$ , $P_{j}$ ) is defined by considering the position of URLs in a given Website and Eq. (10) is used to compute hierarchical syntactic similarity $H S S_{sim (i, j)}$ for any pair of Web page URLs.

H S S_{sim (i, j)} = \frac{Level of (L C A (P_{i} \cap P_{j}))}{Max (Level of (P_{i}), Level of (P_{j}))}

(10)

Where $H S S_{sim (i, j)} = H S S_{sim (i, j)}$ and 0< $H S S_{sim (i, j)}$ ≤ 1

Now the session level similarities are computed by incorporating hierarchical syntactic similarity from Eq. (10) with cosine measure of the page relevance based augmented session similarity in Eq. (7). Eq. (11) is used to define a hierarchy based augmented URL syntactic similarity $A H S S_{(A S_{a}^{p_{i}}, A S_{b}^{p_{j}})}$ .

A H S S_{(A S_{a}^{p_{i}}, A S_{b}^{p_{j}})} = \frac{Σ_{i = 1}^{n} Σ_{j = 1}^{n} A S_{a} {(R o P)}_{i} \times A S_{b} {(R o P)}_{j} \times H S S_{sim (i, j)}}{Σ_{i = 1}^{n} A S_{a} {(R o P)}_{i} \times Σ_{j = 1}^{n} A S_{b} {(R o P)}_{j}}

(11)

7. Intuitive augmented session similarity

In the previous section, several existing measures have been described, and their limitations have been discussed. In order to overcome these limitations, an intuitive augmented Web user session similarity measure (IASS) has been proposed in this article. This similarity measure is based on page relevance; URL and hierarchy based syntactic similarity of two Web user sessions.

Illustrative Example: Consider any two random hypothetical augmented sessions $A S_{a}$ = {( $P_{5}$ , $0.67$ ), ( $P_{8}$ , 0.50)}, and $A S_{b}$ = {( $P_{9}$ , $0.75$ ), ( $P_{12}$ , 0.25)}. The page relevance based augmented session similarity between these two sessions $A S S_{(A S_{a}, A S_{b})}$ will be zero because accessing pages are not common. Similarly, consider the URLs of pages $P_{5}, P_{8}, P_{9}, and P_{12}$ from Figure 1 if URL based syntactic similarity $U S S_{(U S_{a}^{p_{i}}, U S_{b}^{pj})}$ between page URLs $(P_{5}, P_{12}), (P_{8}, P_{12}), and (P_{9}, P_{12})$ is computed using Eq. (8) then all considered page URLs assigns the same similarity value of 0.75. However, if we have a closer look at the URLs of pages $P_{5}, P_{8}, P_{9}, and P_{12}$ in Figure 1 then we found that the URLs of pages $(P_{8}, P_{12})$ are more similar than $(P_{9}, P_{12})$ and similarly URLs of $(P_{9}, P_{12})$ are more similar than $(P_{5}, P_{12})$ . Therefore, the assignment of same similarity values to all pair of page URLs is not very intuitive. Now, a hierarchy based syntactic similarity $H S S_{sim (i, j)}$ between $(P_{5}, P_{12}), (P_{8}, P_{12}), and (P_{9}, P_{12})$ is computed using Eq. (10) when different similarity values $(P_{8}, P_{12})$ = 0.80, $(P_{9}, P_{12})$ = 0.60, and $(P_{5}, P_{12})$ = 0.40 are obtained for all pairs of pages.

If any pair of Web pages has a small value of hierarchical syntactic similarity and a URL based syntactic similarity, the page relevance based augmented session similarity will produce good results. For large values of augmented URL and hierarchy based URL syntactic similarity they will produce better results. Intuitive augmented session similarity utilises the properties of all three measures and considers the maximum optimistic aggregation of these measures to give superior similarities between Web user sessions. Intuitive augmented session similarity is computed using Eq. (12).

I A S S_{(A S_{a}, A S_{b})} = Max {A S S_{(A S_{a}, A S_{b})}, A U S S_{(A S_{a}^{pi}, A S_{b}^{pj}),}, A H S S_{(A S_{a}^{pi}, A S_{b}^{p_{j}})}}

(12)

As a requirement of relational clustering, this intuitive augmented session similarity is converted to the dissimilarity/distance measure. This distance measure satisfies the necessary conditions of a metric [27]. The intuitive augmented session dissimilarity is computed using Eq. (13).

D_{(A S_{a}, A S_{b})}^{2} = {(1 - I A S S_{(A S_{a}, A S_{b})})}^{2}

(13)

Where 0 < $D_{(A S_{a}, A S_{b})}^{2}$ ≤ 1, for $A S_{a}$ , $A S_{b}$ =1, 2.….m.

The distance between any two sessions must be non-negative.

The distance between two sessions must be zero if and only if the two sessions are identical.

The distance must be symmetric, that is, the distance from $A S_{a} to A S_{b}$ is the same as the distance from $A S_{a} to A S_{b}$ .

The pseudo code for proposed intuitive augmented session dissimilarity metric is presented as Algorithm 1. This algorithm summarised the above-described procedure and is used to compute essential dissimilarity matrix for relational clustering of Web user sessions.

Algorithm 1: Pseudo code for computation of intuitive augmented sessions dissimilarity metric.
Input: {Web server log file: $L of n records where L \leftarrow {r_{1}, r_{2} \dots r_{n}}, where n ⋙ 1$ , $H S S_{sim (i, j)}$ – Hierarchy based URL similarity matrix $U S S_{(U S_{a}^{pi}, U S_{b}^{pj})} - URL based Syntactic Similarity matrix$ } Output: { $D_{m \times m}$ \| Page relevance matrix (dis)similarity matrix } 1: Removing of extraneous information: $L^{c} \leftarrow {r_{1}, r_{2} \dots r_{n}}$ is a cleaned Web log file 2: Identification of Web users $U_{i} = {U_{1}, U_{2}, \dots . U_{n}} for i = 1, 2, \dots n .$ 3: Identification of Web user sessions $S_{i} = {S_{1}, S_{2}, \dots . S_{m}} for i = 1, 2, \dots m$ where m≥n 4: Vector representation of Web user sessions $S_{i} = {S_{i}^{1}, S_{i}^{2}, \dots S_{i}^{n}}, \forall i = 1, 2, \dots, m .$ 5: Computation of relevance of any Web page in user sessions for each pair of ( $S_{k}, P_{i})$ in session $S_{k}$ and page $P_{i}$ where, $i = 1, 2, \dots m .$ and $k = 1, 2, \dots, m .$ 6: Compute the duration of a Web page ( $P_{i}$ ) in user session ( $S_{k}$ ) using Eq. (3). 7: Compute the frequency of the Web page ( $P_{i}$ ) in user session ( $S_{k}$ ) using Eq. (4). 8: Compute the relevance of a Web page ( $P_{i}$ ) in user session ( $S_{k}$ ) using Eq. (5). 9: Computation of page relevance based augmented session similarity matrix by using Eq. (9). 10: Compute the page relevance and URL syntactic similarity based augmented session similarity matrix by using Eq. (10). 11: Compute the page relevance and hierarchical URL similarity based augmented session similarity matrix by using Eq. (11). 12: Compute the intuitive augmented session similarity by using Eq. (12). 13: Compute the intuitive augmented session dissimilarity matrix by using Eq.(13).

Algorithm 1: Pseudo code for computation of intuitive augmented sessions dissimilarity metric.

Input: {Web server log file:

L of n records where L \leftarrow {r_{1}, r_{2} \dots r_{n}}, where n ⋙ 1

H S S_{sim (i, j)}

– Hierarchy based URL similarity matrix

U S S_{(U S_{a}^{pi}, U S_{b}^{pj})} - URL based Syntactic Similarity matrix

}
Output: {

D_{m \times m}

| Page relevance matrix (dis)similarity matrix }
1: Removing of extraneous information:

L^{c} \leftarrow {r_{1}, r_{2} \dots r_{n}}

is a cleaned Web log file
2: Identification of Web users

U_{i} = {U_{1}, U_{2}, \dots . U_{n}} for i = 1, 2, \dots n .

3: Identification of Web user sessions

S_{i} = {S_{1}, S_{2}, \dots . S_{m}} for i = 1, 2, \dots m

where m≥n
4: Vector representation of Web user sessions

S_{i} = {S_{i}^{1}, S_{i}^{2}, \dots S_{i}^{n}}, \forall i = 1, 2, \dots, m .

5: Computation of relevance of any Web page in user sessions for each pair of (

S_{k}, P_{i})

in session

S_{k}

and page

P_{i}

where,

i = 1, 2, \dots m .

and

k = 1, 2, \dots, m .

6: Compute the duration of a Web page (

P_{i}

) in user session (

S_{k}

) using Eq. (3).
7: Compute the frequency of the Web page (

P_{i}

) in user session (

S_{k}

) using Eq. (4).
8: Compute the relevance of a Web page (

P_{i}

) in user session (

S_{k}

) using Eq. (5).
9: Computation of page relevance based augmented session similarity matrix by using Eq. (9).
10: Compute the page relevance and URL syntactic similarity based augmented session similarity matrix by using Eq. (10).
11: Compute the page relevance and hierarchical URL similarity based augmented session similarity matrix by using Eq. (11).
12: Compute the intuitive augmented session similarity by using Eq. (12).
13: Compute the intuitive augmented session dissimilarity matrix by using Eq.(13).

8. Web user session clustering and validity measures

To evaluate the performance of a proposed intuitive augmented session dissimilarity measure, K-Medoids Clustering [28] was preferred over K-means [29]. This is because it chooses one of the real sessions from the data set as a centre of the cluster, which is used to represent the cluster, while in K-means [29] this centre of a cluster (centroid) is computed as the mean of sessions belonging to that cluster. This fundamental difference makes the K-Medoids approach more suitable for user session (dis)similarity metrics (relational data) [30]. Given a set of user sessions $S_{i} = {S_{1}, S_{2}, \dots . S_{m}} for i = 1, 2, \dots m$ , where each session is represented by a vector of n -dimensions $S_{I} = {S_{I}^{1}, S_{I}^{2}, \dots S_{I}^{n}}, \forall i = 1, 2, \dots, m$ , the objective of K-Medoids is to find K representative sessions called medoids, such that the total dissimilarity of other sessions to their closest medoid is minimised.

Let $C \leftarrow {c_{1}, c_{2}, \dots c_{k}}$ be the set of medoids. The objective function and membership function of K-Medoids clustering algorithms are defined by Eq. (14) and Eq. (15).

F_{k - medoids} = \sum_{i = 1}^{m} (\sum_{c = 1}^{k} μ_{ci} d_{ci}^{2} (S_{i}, δ_{c}))

(14)

μ_{ci} = {\begin{matrix} 1, if S_{i} \in c_{1} \\ 0 otherwise \end{matrix}

(15)

Where, $d_{ci}^{2} (S_{i}, δ_{c})$ is the dissimilarity between session $S_{i}$ and medoid of cluster $c_{c}$ is represented as $δ_{c}$ . The pseudo code for K-Medoids clustering is presented as algorithm 2, which describes the working of K-Medoids clustering in detail.

Algorithm 2: Pseudo code for K-Medoids clustering algorithm [28].
Input: { $D_{m \times m}$ \|Dissimilarity matrix, $C$ \|no. of clusters, $T_{\max}$ \|max. no of iterations} Output: { $V \leftarrow {v_{1}, v_{2}, \dots v_{k}}$ \| set of k-medoids respective to the clusters $C \leftarrow {c_{1}, c_{2}, \dots c_{k}}$ } 1: Initialise: $T$ = 1; Randomly chosen set of initial medoids: $V \leftarrow {v_{1}, v_{2}, \dots v_{k}}$ 2: While $(T \leq T_{\max})$ 3: Compute memberships $μ_{ci}$ : 4: For $c = 1, 2, \dots k do$ 5: For $i = 1, 2, \dots m$ 6: The membership function $μ_{ci}$ that minimises $F_{k - medoids}$ can be computed as follows: $q = \underset{1 \leq c \leq k}{argmin} d_{ci}^{2} (S_{i}, δ_{c}); μ_{ci} = {\begin{matrix} 1; if c = q \\ 0; otherwise \end{matrix} δ_{c} \leftarrow S_{i}$ ; 7: End for 8: End for 9: Store the current medoid: $V_{old} = V$ Compute the new medoids: 10: For $c = 1, 2, \dots k do$ 11: The new cluster medoid $δ_{c}$ that minimises $F_{k - medoids}$ can be computed as follows: $δ_{c} = \underset{S_{i} \in C_{c}}{argmin} \sum_{S_{j} \in C_{c}} d_{ij}^{2} (S_{i}, S_{j})$ ; $V_{c} = δ_{c}$ ; 12: End for 13: $T = T + 1$ 14: End While

Algorithm 2: Pseudo code for K-Medoids clustering algorithm [28].

Input: {

D_{m \times m}

|Dissimilarity matrix,

C

|no. of clusters,

T_{\max}

|max. no of iterations}
Output: {

V \leftarrow {v_{1}, v_{2}, \dots v_{k}}

| set of k-medoids respective to the clusters

C \leftarrow {c_{1}, c_{2}, \dots c_{k}}

}
1: Initialise:

T

= 1; Randomly chosen set of initial medoids:

V \leftarrow {v_{1}, v_{2}, \dots v_{k}}

2: While

(T \leq T_{\max})

3: Compute memberships

μ_{ci}

:
4: For

c = 1, 2, \dots k do

5: For

i = 1, 2, \dots m

6: The membership function

μ_{ci}

that minimises

F_{k - medoids}

can be computed as follows:

q = \underset{1 \leq c \leq k}{argmin} d_{ci}^{2} (S_{i}, δ_{c}); μ_{ci} = {\begin{matrix} 1; if c = q \\ 0; otherwise \end{matrix} δ_{c} \leftarrow S_{i}

;
7: End for
8: End for
9: Store the current medoid:

V_{old} = V

Compute the new medoids:
10: For

c = 1, 2, \dots k do

11: The new cluster medoid

δ_{c}

that minimises

F_{k - medoids}

can be computed as follows:

δ_{c} = \underset{S_{i} \in C_{c}}{argmin} \sum_{S_{j} \in C_{c}} d_{ij}^{2} (S_{i}, S_{j})

;

V_{c} = δ_{c}

;
12: End for
13:

T = T + 1

14: End While

To assess the quality of generated clusters we used Dunn’s validity (DV) Index [31] and Davies-Bouldin (DB) Index [32]. These two unsupervised validity measures are based on compactness and separation and are measured by intra-cluster and inter-cluster distances.

The Dunn’s Index seeks to find out most compact and well-separated clusters. Therefore, the number of clusters for which the value of Dunn’s Index maximised is considered as an optimal value. The DV Index is given by Eq. (16).

D V_{index} = min_{i = 1, 2 . . k} {min_{j = i + 1, . . k} (\frac{d (c_{i}, c_{j})}{max_{ℓ = 1, 2, . . k} diam (c_{ℓ})})}

(16)

Where, $d (c_{i}, c_{j}) = min_{S_{i \in C_{i ’} S_{j \in C_{j},}}} d (A S_{i}, A S_{j})$ and $diam (c_{ℓ}) = max_{S_{i,} S_{j} \in c_{ℓ}} d (A S_{i}, A S_{j})$

The DB Index measures the average of similarity between each cluster and its most similar one. The number of clusters for which the value of DB Index is minimised is considered as an optimal value. The DB Index is given by Eq. (17).

D B_{index} = \frac{1}{k} \sum_{i = 1}^{k} {max}_{j = 1, 2, \dots . k, j \neq i} (\frac{diam (c_{i}) + diam (c_{j})}{d (c_{i}, c_{j})})

(17)

Where $d (A S_{i}, A S_{j})$ is the distance between two sessions in cluster $C_{i}$ and $C_{j}$ , $d (c_{i}, c_{j})$ is the dissimilarity function between two cluster $C_{i}$ and $C_{j}$ and $diam (c_{ℓ})$ diameter of cluster $C_{ℓ}$ .

9. Experimental results and discussion

To evaluate the performance of the proposed intuitive augmented session dissimilarity measure, a number of experiments have been performed. All experiments were performed with an Intel Core¹ i3 (CPU M370 2.40 GHz) with 4.00 GB RAM. In the experiments, the Web access logs of a Web server of an academic institution² were used because the concept hierarchy of this Website is known to us. The proposed measure was implemented and tested using MATLAB³ [33]. For our experiments, K-Medoids Clustering code available at MATLAB Central file exchange [34] has been modified and used, with different dissimilarity measures and computed the value of the Dunn’s Index and DB Index [35] with varying number of user sessions clusters. Table 1 gives a brief summary original server log file.

Table 1.

Summary original server log file

Web access logs duration	7 April 2013 to 30 April 2013
Size of log file	45.5 MB
No. of log entries (total hits)	108,024
No. of sessions	4906
No. of unique page URLs	385

First, the necessary preprocessing step was applied on these Weblogs and generated 4906 sessions using a 30-min threshold time. After that 184 Web robot sessions are filtered out from the generated user sessions because they are generated by automated software agents and their access behaviour is monotonous. Subsequently, 1920 minuscule sessions of length 1, 2 or 3 were also removed from the total generated sessions as they did not contribute any significant information for user session clustering.

Finally, after performing the session filtering, 2802 Web user sessions are left for experimentation. These 2802 Web user sessions accessed more than 385 unique pages in total. Further, by removing very less frequent and very short duration visited pages the number of unique pages is reduced to 167. Table 2 presents a summary of the cleaned and pre-processed server log file.

Table 2.

Summary of cleaned and pre-processed server log file

Web access logs duration	7 April 2013 to 30 April 2013
Size of log file	20.1 MB
No. of log entries (total hits)	79,026
No. of sessions	2802
No. of unique page URLs	167

Now, by applying Eq. (7) an augmented web user session dissimilarity metric of size 2802 × 2802 is computed. Then a 167 × 167 URL similarity metric is computed for all referred unique pages (URLs) by using Eq. (8) and by using this a URL based syntactic dissimilarity of 2802 × 2802 is computed by Eq. (9).

Again, the same procedure is adopted to compute augmented hierarchy based URL syntactic similarity metric $D_{2802 \times 2802}$ using Eq. (11) and the results are summarised in Table 3.

Table 3.

Summary of Dunn’s validity (DV) Index and Davies-Bouldin (DB) Index for different dissimilarity measures and varying numbers of clusters by K-Medoids clustering

K-Medoids clustering with different dissimilarity measures	No. of clusters	DV Index	DB Index
Page relevance based augmented session dissimilarity matrix	5	0.032	2.955
	10	0.024	3.067
	15	0.022	3.198
	20	0.021	3.476
URL syntactic based augmented session dissimilarity matrix	5	0.041	1.94
	10	0.039	2.035
	15	0.037	2.655
	20	0.041	2.661
URL hierarchy based augmented session dissimilarity matrix	5	0.036	2.481
	10	0.028	2.582
	15	0.033	2.998
	20	0.028	2.987
Intuitive augmented session dissimilarity matrix	5	0.043	2.155
	10	0.036	1.987
	15	0.041	2.448
	20	0.032	2.854

After that, an intuitive augmented dissimilarity metric is computed by using Eq. (12) and Eq. (13). This dissimilarity metric takes the maximum value of dissimilarities from the aforementioned dissimilarity matrices.

After computation of different dissimilarity metrics, the K-Medoids clustering algorithm was used with the different number of clusters (i.e. $C = 5, 10, 20, 25 etc .)$ .This algorithm assigns 2802 sessions to a diverse number of generating clusters, respectively.

The validity of generating clusters is evaluated by computing the DV Index and DB Index, respectively. The results are summarised in Table 3.

The main argument of the proposed work is that only binary consideration (accessed or not accessed) of accessing pages in any Web user session is not sufficient to categorise user browsing behaviour. However, the web user’s habits, interests and expectations should also be considered by measuring the relevance of pages in every session because all of the URLs visited in a session are not equally important to the user. At the same time, one cannot ignore the syntactic structure of the accessing page URL and hierarchical position of this URL in Website organisation.

By considering the above-stated facts, an intuitive dissimilarity measure was proposed to capture the resemblance between two user sessions. Finally, to evaluate the effect of this measure, the performance of proposed measure was compared with other independent measures using K-Medoids clustering algorithm with varying number of clusters (i.e. $C$ =5, 10, 20, 25 etc.). To validate generated clusters with different measures the value of the DV Index and DB Index are computed. The major validity threat to this work is prior knowledge of the hierarchical organisation of page URLs on a website that may be learned from a Web developer or Web masters.

The experiment results are shown in Figures 2 and 3, and it has been observed that intuitive dissimilarity metric performed better regarding the DV Index and the DB Index.

The DV and DB validity index suggest five numbers of optimal clusters in considered Weblog data. The experimental results suggest that the maximum aggregation of page relevance, URL syntactic and URL hierarchy based augmented session dissimilarity in proposed intuitive dissimilarity metric is proved better most of the time and represent session dissimilarities in the more significant way.

10. Conclusion and future work

In this paper, the concept of augmented sessions was used and an intuitive augmented user sessions dissimilarity metric is proposed for web user sessions. The proposed metric was based on URL syntactic dissimilarity, hierarchical URL syntactic dissimilarity and page relevance based augmented session dissimilarity. This metric take the advantage of all the aforementioned (dis)similarity measures. The dissimilarity metrics generated by different measures were provided as input to K-Medoids clustering to generate a different number of clusters. DV Index and DB Index were used to assess the quality of generated clusters. Experiments have been performed with varying number clusters to get optimised and stable results. Experimental results show (Figures 2 and 3) that intuitive augmented session dissimilarity measure outperformed the individual page relevance based augmented session, URL based syntactic and augmented hierarchy based URL syntactic dissimilarity measures on both DV and DB index evaluation parameters. It has been observed that optimised and stable results were found for five numbers of clusters. However, in this experiment a small size server log was considered to avoid pre-processing overhead. Therefore in the future the same experiment may be extended for larger web log data. The same hypothesis may be tested with other clustering algorithms with a different set of cluster validation measures to generalise the results.

Footnotes

Acknowledgements

The authors are very thankful to the editors and anonymous referees whose valuable suggestions and comments helped to improve the paper.

Funding

This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

Notes

References

Ryu

KH.

MapReduce-based web mining for prediction of web-user navigation. Journal of Information Science 2014; 40: 557–567.

Alkan

Karagoz

WaPUPS: Web access pattern extraction under user-defined pattern scoring. Journal of Information Science. 2015. DOI: 0165551515593495.

Chiu

CM.

Towards a hypermedia-enabled and web-based data analysis framework. Journal of Information Science 2004; 30(1): 60–72.

Krishnapuram

Joshi

. A fuzzy relative of the k-medoids algorithm with application to web document and snippet clustering. In: IEEE International Fuzzy Systems Conference Proceedings (FUZZ-IEEE’99), 1999, pp. 1281–1286.

Xiao

Zhang

Jia

Measuring similarity of interests for clustering web-users. In: Proceedings of the 12th Australasian database conference. IEEE Computer Society, 2001, pp. 107–114.

Strehl

Ghosh

Mooney

. Impact of similarity measures on webpage clustering. In: Workshop on Artificial Intelligence for Web Search (AAAI 2000), 2000, pp. 58–64.

Srivastava

Bhosale

Sural

. Speeding up web access using weighted association rules. In: Pattern Recognition and Machine Intelligence. Berlin: Springer, 2005, pp. 660–665.

Yaslan

Cataltepe

. A comparison framework of similarity metrics used for web access log analysis. In: MLDM Posters, 2007, pp. 144–152.

Nasraoui

Soliman

Saka

Badia

Germain

A web usage mining framework for mining evolving user profiles in dynamic websites. IEEE Transactions on Knowledge and Data Engineering 2008; 20(2): 202–215.

10.

Chan

PK.

A non-invasive learning approach to building web user profiles. In: Proceedings of the WEBKDD’99 Workshop on Web Usage Analysis and User Profiling, 1999, pp. 7–12.

11.

Xiao

Zhang

Jia

Measuring similarity of interests for clustering web-users. In: Proceedings of the 12th Australasian database conference. IEEE Computer Society, 2001, pp. 107–114.

12.

Liu

Kešelj

Combined mining of Web server logs and web contents for classifying user navigation patterns and predicting users’ future requests. Data & Knowledge Engineering 2007; 61(2): 304–330.

13.

Yan

Jacobsen

Garcia-Molina

Dayal

From user access patterns to dynamic hypertext linking. Computer Networks and ISDN Systems 1996; 28(7): 1007–1014.

14.

Forsati

Meybodi

Rahbar

. An efficient algorithm for web recommendation systems. In: IEEE/ACS International Conference on Computer Systems and Applications, (AICCSA 2009), IEEE, 2009, pp. 579–586.

15.

Banerjee

Ghosh

Clickstream clustering using weighted longest common subsequences. In: Proceedings of the web mining workshop at the 1st SIAM conference on data mining, 2001, p. 144.

16.

Wang

Zaïane

OR.

Clustering web sessions by sequence alignment. In: Proceedings 13th International Workshop on Database and Expert Systems Applications, 2002, pp. 394–398.

17.

. Similarity measurement of web sessions by sequence alignment. In: IFIP International Conference on Network and Parallel Computing Workshops, IEEE, 2007, pp. 716–720.

18.

Bose

Beemanapalli

Srivastava

Sahar

Incorporating concept hierarchies into usage mining based recommendations. In: Nasraoui

Spiliopoulou

Srivastava

Mobasher

Masand

(eds) Advances in Web Mining and Web Usage Analysis. Berlin: Springer, 2007, pp. 110–126.

19.

Sisodia

Verma

Web usage pattern analysis through weblogs: A review. In: International Joint Conference on Computer Science and Software Engineering (JCSSE), IEEE, 2012, pp. 49–53.

20.

Sisodia

Verma

Vyas

OP.

Agglomerative approach for identification and elimination of web robots from web server logs to extract knowledge about actual visitors. Journal of Data Analysis and Information Processing 2015; 3(1): 1–10.

21.

Cooley

Mobasher

Srivastava

Data preparation for mining World Wide Web browsing patterns. Knowledge and Information Systems 1999; 1(1): 5–32.

22.

Huang

Peng

Schuurmans

Dynamic weblog session identification with statistical language models. Journal of the American Society for Information Science and Technology 2004; 55(14): 1290–1303.

23.

Arce

Román

Velásquez

Parada

Identifying web sessions with simulated annealing. Expert Systems with Applications 2014; 41(4): 1593–1600.

24.

Sisodia

Verma

Vyas

OP.

A Comparative analysis of browsing behavior of human visitors and automatic software agents. American Journal of Systems and Software 2015; 3(2): 31–35.

25.

Bender

Farach-Colton

Pemmasani

Skiena

Sumazin

Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms 2005; 57(2): 75–94.

26.

Nichele

Becker

Clustering web sessions by levels of page similarity. In: Ng

W-K

Kitsuregawa

Chang

(eds) Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2006, pp. 346–350.

27.

Huang

. Similarity measures for text document clustering. In: Proceedings of the sixth New Zealand computer science research student conference (NZCSRSC2008), Christchurch, New Zealand, 2008, pp. 49–56.

28.

Park

Jun

CH.

A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications 2009; 36(2): 3336–3341.

29.

Jain

AK.

Data clustering: 50 years beyond K-means. Pattern Recognition Letters 2010; 31(8): 651–666.

30.

Mei

Chen

Fuzzy clustering with weighted medoids for relational data. Pattern Recognition 2010; 43(5): 1964–1974.

31.

Dunn

JC.

Well separated clusters and optimal fuzzy partitions. Journal of Cybernetics 1974; 4(1): 95–104.

32.

Davies

Bouldin

DW.

Cluster Separation Measure. IEEE Transactions on Pattern Analysis and Machine Intelligence 1979; 1(2): 224–227.

33.

MATLAB (R2012a) Software. http://www.mathworks.com.

34.

MATLAB Central file exchange K-Medoids Clustering. http://in.mathworks.com/matlabcentral/fileexchange/28860-kmedioids/content/kmedioids.m (accessed September 2015).

35.

MATLAB Central file exchange Dunn’s and Davies-Bouldin validity indexes. http://in.mathworks.com/matlabcentral/fileexchange/14620-cvap–cluster-validity-analysis-platform–cluster-analysis-and-validation-tool-/content/valid_DbDunn.m (accessed September 2015).

Augmented intuitive dissimilarity metric for clustering of Web user sessions

Abstract

Keywords

1. Introduction

2. Related work

3. Methodology

3.1. Web server logs pre-processing

3.2. Vector space representation of Web user sessions

3.3. Computation of a page relevance in any Web user session

3.3.1. Duration of page ( D o P ) :

3.3.2. Frequency of page ( F o P ) :

3.3.3. Relevance of the page ( R o P ) :

3.4. Augmented Web user sessions

4. Page relevance based augmented session similarity

5. A URL syntactic similarity between i th and j th page URL

6. A hierarchical syntactic similarity between i th and j th page URL

7. Intuitive augmented session similarity

8. Web user session clustering and validity measures

9. Experimental results and discussion

10. Conclusion and future work

Footnotes

Acknowledgements

Funding

Notes

References

3.3.1. Duration of page $(D o P) :$

3.3.2. Frequency of page $(F o P) :$

3.3.3. Relevance of the page $(R o P) :$

5. A URL syntactic similarity between $i^{th}$ and $j^{th}$ page URL

6. A hierarchical syntactic similarity between $i^{th}$ and $j^{th}$ page URL