Been trying my best to stick to the well-known UNIX Philosophy – “Do one thing and do it well”, so I have been breaking down my projects into numerous pieces of small tasks and rely on existing tools whenever possible. One of the existing tool that I use a lot is the GNU sort tool. Generally sort utility is really doing fine and dandy without having to configure anything, at least not until I realize the problem that leads to this post.

Considering I am having input in this form

http://flickr.com/photos/tags/スラム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/スラム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/46857830@N03/5651576112 0

I am expecting result in this order

http://flickr.com/photos/tags/スラム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/スラム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/99996011@N00/5396566822 0

but I am getting this instead

http://flickr.com/photos/tags/スラム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/13980928@N03/6001200971 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/21207178@N07/5441742937 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/25845846@N06/3033371575 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/30366924@N08/5772100510 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/31343451@N00/5957189406 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/36662563@N00/4815218552 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/38583880@N00/5686968462 1
http://flickr.com/photos/tags/スラム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/43335486@N00/5794673203 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/46857830@N03/5651576112 0
http://flickr.com/photos/tags/スラム http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ホーム http://flickr.com/photos/99996011@N00/5396566822 0
http://flickr.com/photos/tags/ブラジル http://flickr.com/photos/99996011@N00/5396566822 0

After a quick search, it turns out that GNU sort actually rely on LC_COLLATE to do the sorting. I don’t really care about the character sequence order as long as I get consistent output, therefore the easiest way to fix this problem is obviously changing either LC_COLLATE, LC_ALL or LANG environment variable to “C”. However, to ensure the utility works the same elsewhere without interfering other scripts/programs relying on those environment variables, it would be easier to do this instead

$ <whatever command that produce output to stdOut> | LC_COLLATE="C" sort

Just a quick update to the previous post, the virtuoso storage engine works with redland provided the required packages are properly installed (yes, yes, yes, I know I haven’t release my PHP OO wrapper for Redland). Now that the package is installed, we need to do some configuration so that Redland can use it.

Installing Virtuoso

Just a quick update to the previous post, the virtuoso storage engine works with redland provided the required packages are properly installed (yes, yes, yes, I know I haven’t release my PHP OO wrapper for Redland). Now that the package is installed, we need to do some configuration so that Redland can use it.

Running Virtuoso

virtuoso-opensource and unixodbc-dev would have to be installed before virtuoso database can be started. After installing the required packages, make a copy of virtuoso.ini from /etc/virtuoso-opensource-6.1/virtuoso.ini to the directory where you want virtuoso to store the database.

$ mkdir foo
$ cp /etc/virtuoso-opensource-6.1/virtuoso.ini foo

Edit the ini file as desired, just make sure the configured ports aren’t being used by other processes (by default, virtuoso runs at port 1111 with web interface at port 8890, so if you are running another instance of it, change the port settings). If you are not interested in running another instance of virtuoso database, you can actually skip this part.

After everything is configured, just run this command at the directory.

$ cd foo
$ virtuoso-t -fd

For more information, please refer to this quick start guide.

Setting Up ODBC

By referring to this tutorial, add these lines to /etc/odbc.ini (assuming the database name is SENSEIDB)

[SENSEIDB]
Driver = /usr/lib/odbc/virtodbc.so
Description = Sensei DB
Address = localhost:11111

Making Redland to Work With Virtuoso

Just make sure the ODBC configuration is done correctly, then follow the guide for further instructions.

I wanted to try using virtuoso as the storage engine for Redland but unfortunately there is no librdf-storage-virtuoso package for Ubuntu. After getting some help from @dajobe, I attempted to build the packages myself. Although it takes quite some time to build packages, but not too difficult it seems.

The version of Redland that I am attempting to build is 1.0.13, and unfortunately this means I would have to build librasqal3 too as the version provided by Ubuntu Natty is not up to date. Installing the packages may cause some breakage, so… YMMV.

Pre-requisites

By following the instructions here, add this source repository to /etc/apt/sources.list

deb-src http://download.librdf.org/binaries/debian/unstable ./

And then run an apt-get update

$ sudo apt-get update

Building Rasqal

To build Rasqal, first grab the source package

$ sudo apt-get source librasqal

Grab the source packages

$ sudo apt-get source librasqal3

.. install the dependencies

$ sudo apt-get build-dep librasqal3 librasqal3-dev

Then build them

$ sudo apt-get -b source librasqal3

Then install librasqal3, librasqal3-dev, rasqal-utils

Build Redland

First we will need to grab the packages

$ sudo apt-get -b source librdf0

You may get an error saying some packages can’t be downloaded, in particular the source package. Just download this into the same directory as the other downloaded tarballs and rename it as redland_1.0.13.orig.tar.gz (Note: as of writing, source packages for 1.0.14 is not out yet, you may want to adjust when package for 1.0.14 is out).

There are some other dependencies besides the listed ones that needs to be installed, to install all of them, issue these commands

$ sudo apt-get install virtuoso-opensource unixodbc-dev
$ sudo apt-get build-dep librdf0

Now we can proceed to build Redland

$ sudo apt-get -b source librdf0

To build librdf-storage-virtuoso, Navigate to $REDLAND_SRC/redland-1.0.13/debian and edit a file named ‘control’ (without the quotes). Append this to the end of the file.

Package: librdf-storage-virtuoso
Section: libs
Architecture: any
Depends: ${shlibs:Depends}, ${misc:Depends}
Replaces: librdf0 (<< 1.0.9-3)
Description: RDF library, Virtuoso backend
 Redland is a library that provides a high-level interface for RDF
 (Resource Description Framework) implemented in an object-based API.
 It is modular and supports different RDF/XML parsers, storage
 mechanisms and other elements. Redland is designed for applications
 developers to provide RDF support in their applications as well as
 for RDF developers to experiment with the technology.
 .
 This package contains the Virtuoso storage backend.

Edit a file named 'files' (without the quotes) and append this line

librdf-storage-virtuoso_1.0.13-2_i386.deb libs optional

Add a new file named librdf-storage-virtuoso.install with the following content

debian/tmp/usr/lib/redland/librdf_storage_virtuoso.so

Add another file named librdf-storage-virtuoso.substvars

shlibs:Depends=libc6 (>= 2.3.6-6~), libc6 (>= 2.4), libdb4.8, librdf0 (>= 1.0.13), unixodbc (>= 2.2.11)
misc:Depends=

Not sure what happens, but that was the edited version after building the packages, my original version is shown below (will update once I find out why)

shlibs:Depends=libc6 (>= 2.3.6-6~), libc6 (>= 2.4), libdb4.8, librdf0 (>= 1.0.13), unixodbc-dev (>= 2.2.14p2-2ubuntu1), virtuoso-opensource (>= 6.1.2+dfsg1-1ubuntu4)
misc:Depends=

Lastly, create a new file named librdf-storage-virtuoso.debhelper.log from librdf-storage-mysql.debhelper.log Apparently this file is generated automatically, thanks @dajobe for the tip again.

Lastly, navigate back to $REDLAND_SRC and build the packages again

# apt-get -b source librdf0

Building Redland-bindings

Same thing again, first grab the source packages

$ sudo apt-get source redland-bindings

Since I am just interested in the php5-librdf package, I issue this to fetch the dependencies

$ sudo apt-get build-dep php5-librdf

Proceed with building

$ sudo apt-get -b source php5-librdf

Everything looks fine as of now, but I am seeing some random conflicts. Will try to work with the virtuoso storage engine and post a follow up later today.

This post is purely based on my own speculation as there’s no experiment on real-life data to actually back the arguments. I am currently trying to document down a plan for my experiment(s) on recommender system (this reminds me that I have not release the Flickr data collection tool :/) and my supervisor advised to write a paragraph or two on some of the key things. Since he is not going to read it, so I might as well just post it here as a note.

The idea of using tag clusters is based on the papers published by Gemmell et al. during year 2008-2009 in which they used tag clusters to find out relevance between user and resources in their recommender system. The reason of using tag clusters instead of using tags alone is mainly to address two problems that are commonly found in folksonomies – tag ambiguity (polysemy) and tag redundancy (synonym) problems.

Fuzzy C-Means Clustering (FCM) is one of the fuzzy clustering methods where each node do not necessary belong to only one cluster. Instead, they may be a member of one or more clusters with different degree of membership. For example, if one model tags as points in a vector space, each tag may belong to one or more clusters, which is theoretically useful because some tags may carry different meanings (polysemy) depending on the context (user interest).

While the diagram in my previous post (my attempt to implement FCM clustering algorithm using clojure, not of production quality though) only shows each point belong to one cluster, the fact is each of the point may belong to more than one cluster. The line connecting each point to the cluster centroid is showing the most prominent relationship between a point with all the available clusters.

Similar to the approach used by Gemma et al., we are modeling users and resources using vector of tags. The weighting scheme to produce each tag entry would be most probably an adaptation of tf*idf used by most of the tag-based recommender systems. Now that each cluster is also a vector of tags, the degree of membership values are also treated as weights.

To calculate similarity between resources and tag clusters (which are all in vectors), there are some approaches that may be used (just discovered this after a quick search at Google, will read after publishing this). Adapting collaborative filtering into the original design published by Gemmell at el. is not too difficult, at least theoretically (yes, as mentioned, this post is full of crap speculation). All we need to do is just to find out a list of n similar user using the similarity measure, and then compare this group of users with the tag cluster to find out the degree of relationship between them.

Information extracted by traversing social graph, community/group membership as well as ratings (mark as favorite, +1, like) may be also applied somewhere in between, but I still can’t find where can it be used for now, will post followup whenever there is an update.

I was asked to evaluate fuzzy c-means to find out whether it is a good clustering algorithm for my MPhil project. So I spent the whole afternoon reading through some tutorial to get some basic understanding. Then I thought why not implement it in Clojure because it doesn’t look too complicated (I was so wrong…).

I based my implementation on the tutorial posted here. However I still don’t understand how the terminate condition is met so I am setting the function to loop only like 10 times for now (until I understand it better). Added the objective function, loop will stop when the next result is higher than the current result.

My current code for fuzzy c-means:

(ns sensei.clustering.fcm)

(use 'clojure.set
     '[incanter core stats])

(defn fcm[data cluster-count fuzziness-index]
    (let [random-points (take
                          cluster-count
                          (repeatedly
                            #(matrix (take
                               (count (first data))
                               (repeatedly rand)))))
          degree-of-membership (fn [point centroids cluster-index]
                                   (let [power #(pow % (/ 2 (- fuzziness-index 1)))]
                                     (/ 1 (apply
                                            +
                                            (map
                                              #(power (/ (euclidean-distance point (nth centroids cluster-index))
                                                         (euclidean-distance point %)))
                                              centroids)))))
          fuzzy-membership (fn [centroids]
                               (map
                                 (fn [point]
                                     (map
                                       #(degree-of-membership point centroids %)
                                       (range cluster-count)))
                                 data))
          cluster-membership (fn [cluster-index membership]
                                 (map #(nth % cluster-index) membership))
          new-centroid (fn [members]
                           (div (apply
                             plus
                             (map
                               #(mult (pow (nth members %) fuzziness-index) (nth data %))
                               (range (count members))))
                           (apply
                             +
                             (map
                               #(pow (nth members %) fuzziness-index)
                               (range (count members))))))
          new-centroids (fn [membership]
                            (map
                              #(new-centroid (cluster-membership % membership))
                              (range cluster-count)))
          objective (fn [membership centroids]
                        (apply
                          +
                          (map
                            (fn [point-index]
                                (apply
                                  +
                                  (map
                                    #(* (pow (nth (nth membership point-index) %) fuzziness-index)
                                        (pow (euclidean-distance (nth data point-index) (nth centroids %)) 2))
                                    (range cluster-count))))
                            (range (count membership)))))
          cluster (fn re-cluster
                      ([membership centroids] (re-cluster membership centroids (objective membership centroids)))
                      ([membership centroids objective-value]
                       (let [next-membership (fuzzy-membership centroids)
                             next-centroids (new-centroids next-membership)
                             next-objective (objective next-membership next-centroids)]
                         (if (>= next-objective objective-value)
                           (cons centroids membership)
                           (recur next-membership next-centroids next-objective)))))]
      (cluster (fuzzy-membership random-points) random-points)))

My attempt to plot a graph showing the relationship between each point and clusters. Only lines that shows the most degree of membership are shown in this example

(ns sensei.core)

(use 'sensei.clustering.fcm
     '[incanter core charts stats])

(let [data (take
             500
             (repeatedly
               #(matrix (take
                          2
                          (repeatedly rand)))))
      [centroids & membership] (fcm data 5 5)
      chart (scatter-plot
              (map #(nth % 0) data)
              (map #(nth % 1) data))]
  (view (reduce
    (fn [chart point-index]
        (let [point-membership (nth membership point-index)
              max-membership (apply max point-membership)]
          (reduce
            (fn [chart cluster-index]
                (if (= max-membership (nth point-membership cluster-index))
                  (add-lines
                    chart
                    (vector (nth (nth centroids cluster-index) 0) (nth (nth data point-index) 0))
                    (vector (nth (nth centroids cluster-index) 1) (nth (nth data point-index) 1)))
                  chart))
            chart
            (range (count centroids)))))
    chart
    (range (count data)))))

Example output:

I was trying to learn scala and clojure to find one that I may want to use in my postgraduate project. After trying to learn scala for a couple of days, I gave up because I really don’t like the syntax (too OO for my liking). Then I continued with clojure and found myself liking the syntax better.

I briefly tried haskell through this interactive tutorial before starting scala, so I first started with this clojure equivalent web-app. It is a great tutorial, but not quite enough to get myself started to code, so I went on with this Labrepl tutorial guide. The first few sessions was great but it became a bit difficult to follow due to the lack of instruction. Probably I am just being impatient.

A guy nicknamed raek at #clojure irc then suggested a couple of other resources that I may be interested in. One of them is a web-app called 4clojure. Basically it is an app that creates a series of puzzles that let u fill in the blanks so that the statement becomes valid.

After about a week (started last Thursday, and finished on 1st June!), I have solved all posted puzzles (99 in total, and new puzzles are frequently added). The first few puzzles are kinda straight forward, but the later ones took me like hours to half a day to actually came out with a rough idea. Implementing it also took quite some time as I am still not used to programming in functional way.

Some of the puzzles that I kinda like, although the code count is on the high side of the histogram (most people solves the same problem with less code). Besides, I don’t really care about computation complexity because I have not learned it in proper manner (lol, that means I don’t really understand Big-O notation)

Game of Life (Problem 94)

Assuming everyone knows about the game, I guess I would just post the solution straight away.

(fn [i-board]
     (let [
           c-count (count (first i-board))
           r-count (count i-board)
           in-board (fn [i-coor]
                            (let [[i-row i-col] i-coor]
                              (and
                                (>= i-row 0)
                                (< i-row r-count)
                                (>= i-col 0)
                                (< i-col c-count))))
           has-life (fn [i-coor]
                        (= \# (nth (nth i-board (first i-coor)) (last i-coor))))
           board-coor (reduce
                        concat
                        '()
                        (map
                          (fn [my-row]
                              (map #(vector my-row %) (range c-count)))
                          (range r-count)))
           live-list (filter has-life board-coor)
           dead-list (filter #(not (has-life %)) board-coor)
           neighbour (fn [i-coor]
                         (let [[i-row i-col] i-coor]
                           (filter
                             #(let [[my-row my-col] %] (not (and (= my-row i-row) (= my-col i-col))))
                             (reduce
                               concat
                               '()
                               (map
                                 (fn [i-coors]
                                     (filter in-board i-coors))
                                 (map
                                   (fn [my-row]
                                       (map
                                         (fn [my-col]
                                             (vector my-row my-col))
                                         (range (dec i-col) (+ i-col 2))))
                                   (range (dec i-row) (+ i-row 2))))))))
           living-neighbour (fn [i-coor] (filter has-life (neighbour i-coor)))
           lives-on (fn [i-coor]
                        (let [n-count (count (living-neighbour i-coor))]
                          (or (= 2 n-count) (= 3 n-count))))
           reproducible (fn [i-coor]
                            (= 3 (count (living-neighbour i-coor))))
           new-lives (group-by
                       #(first %)
                       (concat
                         (filter lives-on live-list)
                         (filter reproducible dead-list)))
           draw-row (fn plot-lives
                        ([i-row] (plot-lives [] 0 (sort (map last (get new-lives i-row)))))
                        ([result i-pos i-lives]
                         (if (= c-count i-pos)
                           (apply str result)
                           (let [c-life (first i-lives) n-pos (inc i-pos)]
                             (if (= i-pos c-life)
                               (plot-lives (conj result \#) n-pos (rest i-lives))
                               (plot-lives (conj result \space) n-pos i-lives))))))
           ]
       (map draw-row (range r-count))))

OK, I know this is one of the longest solution one can write (and perhaps not the most efficient way).

Roman Numbers (Problem 92)

Completing this also mean I need to be able to read the numbers properly too.

(fn roman
     ([i-literal] (roman 0 i-literal))
     ([i-result i-literal]
      (if (zero? (count i-literal))
        i-result
        (let [
              v-map {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500 \M 1000}
              head (first i-literal)
              tail (rest i-literal)
              t-head (first tail)
              ]
          (if (and (not (nil? t-head)) (> (get v-map t-head) (get v-map head)))
            (roman (+ i-result (- (get v-map t-head) (get v-map head))) (rest tail))
            (roman (+ i-result (get v-map head)) tail))))))

I really hate graphs/trees related puzzles, like this following puzzle.

Graph Connectivity (Problem 91)

Given a set of edges, find if the graph is connected.

(fn [i-set]
     (let [
           nodes (reduce
                   #(conj (conj %1 (first %2)) (last %2))
                   #{}
                   i-set)

           n-count (count nodes)
           n-range (range n-count)
           n-map (apply hash-map (interleave nodes n-range))
           n-index (fn [i-node] (get n-map i-node))

           edges (concat i-set (map #(apply vector (reverse %)) i-set))
           grouped-edges (group-by #(n-index (first %)) edges)

           n-dest (fn [i-node]
                      (map last (get grouped-edges (n-index i-node))))
           walk-graph (fn discover
            ([i-node] (discover #{} (hash-set i-node)))
            ([result discovered]
             (if (zero? (count discovered))
               result
               (let [
                     current (first discovered)
                     n-result (conj result current)
                     new-nodes (filter #(not (contains? n-result %)) (n-dest current))
                     ]
                 (discover n-result (reduce conj (apply hash-set (rest discovered)) new-nodes))))))
           ]
       (= nodes (walk-graph (first (first i-set))))))

This answer sort of gave me idea on how to solve the following 2 very similar questions (although most people don't agree). Note how I start not to care about the code length.

Word ChainWord Ladder (Problem 82)

According to Wikipedia, the game is actually called Word Ladder instead of Word Chain.

(fn [i-words]
     (let [
           n-count (count i-words)
           n-range (range n-count)
           n-map (apply hash-map (interleave i-words n-range))
           n-index (fn [i-word] (get n-map i-word))

           edit-distance (fn diff ([a-word b-word] (diff 0 a-word b-word))
                             ([distance a-word b-word]
                              (let [
                                    a-head (first a-word)
                                    b-head (first b-word)

                                    a-tail (rest a-word)
                                    b-tail (rest b-word)

                                    a-next (first a-tail)
                                    b-next (first b-tail)
                                    ]
                                (if (and (nil? a-head) (nil? b-head))
                                  distance
                                  (if (= a-head b-head)
                                    (diff distance a-tail b-tail)
                                    (if (= a-next b-head)
                                      (diff (inc distance) a-tail b-word)
                                      (if (= a-head b-next)
                                        (diff (inc distance) a-word b-tail)
                                        (diff (inc distance) a-tail b-tail))))))))
           edges (reduce
                   (fn [result i-word]
                       (reduce
                         #(conj %1 (vector i-word %2))
                         result
                         (filter #(= 1 (edit-distance i-word %)) i-words)))
                   #{}
                   i-words)
           grouped-edges (group-by #(n-index (first %)) edges)

           n-dest (fn [i-word]
                      (map last (get grouped-edges (n-index i-word))))

           build-chains (fn chain
                            ([i-word] (chain (dec n-count) (vector (vector i-word))))
                            ([i result]
                             (if (zero? i)
                               result
                               (chain
                                 (dec i)
                                 (reduce
                                   concat
                                   []
                                   (map
                                     (fn [i-chain]
                                         (map
                                           #(conj (apply vector i-chain) %)
                                           (filter #(not (contains? (apply hash-set i-chain) %)) (n-dest (last i-chain)))))
                                     result))))))
           ]
       (reduce
         (fn [result i-word]
             (if (false? result)
               (boolean (some #(= (count %) n-count) (build-chains i-word)))
               result))
         false
         i-words)))

Graph Tour (Problem 89)

(fn [i-edges]
     (let [
           nodes (reduce #(conj (conj %1 (first %2)) (last %2)) #{} i-edges)

           n-count (count nodes)
           n-range (range n-count)
           n-map (apply hash-map (interleave nodes n-range))
           n-index (fn [i-node] (get n-map i-node))

           e-count (count i-edges)

           edges-count (fn [my-edges]
                           (reduce
                             (fn [result i-edge]
                                 (let [[edge occurences] i-edge]
                                   (conj result (hash-map edge (count occurences)))))
                             {}
                             (group-by #(apply vector %) (map sort my-edges))))
           edge-count (fn [i-edge]
                          (let [e-count (edges-count i-edges)]
                            (get e-count i-edge 0)))

           edges (concat i-edges (map #(apply vector (reverse %)) i-edges))
           grouped-edges (group-by #(n-index (first %)) edges)

           n-dest (fn [i-node]
                      (reduce #(conj %1 (last %2)) #{} (get grouped-edges (n-index i-node))))

           build-chains (fn chain
                            ([i-edge] (chain (dec e-count) (vector (vector i-edge))))
                            ([i result]
                             (if (zero? i)
                               result
                               (chain
                                 (dec i)
                                 (reduce
                                   concat
                                   []
                                   (map
                                     (fn [i-chain]
                                         (let [
                                               t-node (last (last i-chain))
                                               n-edges (map #(vector t-node %) (n-dest t-node))
                                               ]
                                           (filter
                                             (fn [my-chain]
                                                 (reduce
                                                   (fn [result i-edge]
                                                       (let [[edge o-count] i-edge]
                                                         (and result (>= (edge-count edge) o-count))))
                                                   true
                                                   (edges-count my-chain)))
                                             (map #(conj i-chain %) n-edges))))
                                     result))))))
           ]
       (reduce
         (fn [result i-edge]
             (if (false? result)
               (boolean (some #(= (count %) e-count) (build-chains i-edge)))
               result))
         false
         i-edges)))

I guess that's all for now lol. Oh, my supervisor's reaction (his primary language is probably JAVA) to scala and clojure was - try not to learn strange (weird) language. Then he mentioned about bad employment opportunity or something I don't really care to remember (I am actually trying very hard to avoid learning JAVA because I don't like it). So I guess this is it.

There may be some other interesting questions that I may have missed. Hopefully I will have the time to revisit on this and post more solutions.

Although my supervisor strongly recommend using JENA for RDF related work, but as I really don’t like Java (just personal preference), and wouldn’t want to install JRE/JVM (whatever it is called) at my shared server account, so I went to look for an alternative. After spending some time searching, I found this library called Redland and it provides binding for my current favorite language — PHP, so I decided to use this for my RDF work.

I used pure relational database approach (postgresql to be exact) to store information collected via flickr initially, but it wouldn’t really scale (or I just simply suck at designing/maintaining database tables) and my queries got killed numerously by the web host. Besides that, as the table grow larger, the amount of resource consumed to serve a query also grow, hence I needed to find another way to store the data. At first I thought of using some popular noSQL solutions, but my supervisor told me to turn the data into RDF format instead. So I went on with Redland and use postgresql (again) as storage.

However, for some reason, postgresql doesn’t seem to work efficiently and a simple query can take tens of minutes to run when it holds more than 100k RDF statements. For some reason, the hash storage doesn’t work on my Ubuntu development VM, so I switched the storage engine to MySQL after @dajobe’s suggestion.

However, as PHP binding apparently not that popular, so there aren’t much information / tutorial posted. I actually wanted to write a collection of scripts to collect data from flickr for my research project, so I began with finding an existing script for that task. However, I didn’t find good ones in PHP, so I ported this from Perl to PHP and use Redland. Then after knowing how it really works, I rewrote everything again from scratch (will put them up to bitbucket when I have time to clean up). I even wrapped the library with class methods, which I hope to release later (I only knew about another OO wrapper in PHP for Redland after almost done writing my scripts).

To use Redland’s PHP functions without OO wrapper, we always start with a statement to build a world. I am not very sure what this means (yes, I didn’t really read the documentation that thoroughly), but it seems that almost all constructor functions depend on it to create new object (yes, Redland has this OO feel although all the function calls are in procedural style). So, in PHP, the statement would look like:

$world = librdf_new_world();

Then you would want to decide where to store your RDF statements. For this piece of note, I will just use non-persistent memory store. So the function call to build a storage object is

$storage = librdf_new_storage($world, 'memory', $name, $options);

where $name stores the name of the storage object, and $options often carries the DSN, but in our case it is NULL. Now that we have storage defined, then we proceed with building a model to actually store RDF statements into the storage (it would be easy to think model as a database library, and storage as an abstraction layer).

$model = librdf_new_model($world, $storage, NULL);

Statements are consists of nodes, so let’s create some. To create a URI node, it is just as easy as

$foo = librdf_new_node_from_uri_string($world, 'urn:foo');
$bar = librdf_new_node_from_uri_string($world, 'urn:bar');

Creating a literal node would be just as simple as

$baz = librdf_new_node_from_literal($world, 'baz', NULL, FALSE);

Putting them into a statement

$statement = librdf_new_statement_from_nodes($world, $foo, $bar, $baz);

which is the equivalent to this

<urn:foo> <urn:bar> 'baz' .

To run a query to the model, just simply send a SPARQL statement as follows

$query = librdf_new_query(
    $world,
    'sparql',
    NULL,
<< ?object .
        }
SPARQL
);

Running the query and get result

$result = librdf_model_query_execute($model, $query);
var_dump(librdf_query_results_to_string2($result, 'json', 'application/json', NULL, NULL));

Enjoy!

Had a discussion with my secondary supervisor and it turned out pretty bad because I wasn’t fully prepared and he was rushing to somewhere else for a meeting. So I am jotting down a brief summary (read: highly based on personal/subjective feelings/opinions) of my readings here to help organize things before the followup meeting that is taking place next week.

For some reason, my secondary supervisor seems very skeptical with everything and keeps having argument with my primary supervisor in a lot of things. It is probably a good idea to ensure everyone is on the same page before I begin.

Folksonomy / Collaborative Tagging

Folksonomy is becoming the primary way web users organize their content. While rigid category may still being offered by some web-applications, the flexibility of folksonomy continue to attact more users to tag their resources using keywords^[1]. Besides that, a particular content may be represented with different sets of keywords over time, and folksonomy works great in capturing this change of semantics.

While we cannot deny the fact that the flexibility may cause abuse to the system, but this is not a new problem and there are people working on it. Besides that, considering tags are just a list of keywords describing a resource, they can be considered as a document and can be modeled in a number of ways like how IR people model documents. If the IR people face problems like polysem, synonyms etc, the same problems are also applied to the tags. One of the solutions to the problem is the usage of dimensionality reduction techniques such as LSI, pLSI or LDA ^[2], or clustering tags to avoid ambiguity ^[4].

Encouraging people to tag their resources properly is not actually within the scope of my project, although it is known that collaborative tagging system typically suffered from ramp-up problem (arises when new user/item is added to the system or ratings/tags for an item is sparsely populated). I actually have no idea why is this raised in the previous discussion. However, my secondary supervisor is kind enough to point me to a project called ESP Game which is a game to help tagging of pictures ^[3].

Conclusion: Tagging is a mean of organizing information that is gaining popularity, although it may be subjected to various problems, but it can be (to a certain extend) fixed.

Web 2.0 Applications

Again, both of my supervisors don’t seem to agree on the usefulness of web 2.0 applications. But as web 2.0 applications is gaining popularity, the amount of information generated is drastically increased and there may be a need to offer an alternative approach to enable users to discover them. It is not logical to say Web 2.0 application is built on flawed principles, and then the users deserve no more further innovation from the applications.

Recommender System

A recommender system is a system that recommend content to user to assist in discovery of new content and predict the degree of interest a user may have to an unrated item ^[5]. Depending on different classification methods, they can be generally categorized into 2 major types.

Content-based Recommender

Content-based recommender works by comparing user’s profile to unseen content to predict whether he/she would like that content. In short, it is a system that recommend content based on this statement – ‘you liked A, B and C in the past, then you should like D which is similar to A, B and C’ ^{[5, 7]}.

Collaborative-filtering

Unlike content-based recommender, collaborative-filtering system compares an unseen content with profiles of other users with similar interests, then recommend it if others expressed their interest in the past. In short, it is a system that exercises – ‘Alice, Bob, and Charlie liked A, therefore you should also like A‘ (assuming Alice, Bob and Charlie share the same interest with the current user) ^[5].

Collaborative-filtering system can be further categorized into 2 types – memory-based and model-based ^[6].

Memory-based

To me, this is what a recommender should do ideally. Everything about content and users are stored in the storage and used in the recommender algorithm. However, this means it is heavily depending on content that may not necessarily annotated, or tagged appropriately.

Model-based

Model-based is implementing collaborative filtering in another way where a set of training data is usually fed to a learning algorithm to produce a mathematical model ^[6]. Depending on implementation, an intermediate layer (probably lower dimension, depending on the model) is created to complement the incompleteness of annotated data.

Most of the current model consider all users are distributed independently and identically without considering relationships between them ^[6]. However, in reality, we often turn to people having same interests for recommendations ^[7]. Therefore, some people start utilizing social relationship and trust network into the modeling of recommendation algorithm ^[8].

Besides studying user’s social network, other relationships that may be observed are user-tag, user-content, and content-tag relationships. My research project will be more or less based on the research done by Ma et al ^[6]. So as I am going this route, my first problem will be identifying which relationship(s) should be incorporated into the model.

Data Sources and Domain

I wanted to work on something that would help in travel itinerary planning. But as I may not have enough time (with only roughly 7 months left) to do that, I am scaling down the scope to build a system that recommend images. Data will most probably come from flickr through their API as suggested by fellow stackoverflowers.

What do I do next?

As told by my primary supervisor, I am going to start drafting the initial design while keep reading more about this area.

Further Readings

1. Shadbolt, Nigel, Tim Berners-Lee, and Wendy Hall. 2006. The Semantic Web Revisited. IEEE Intelligent Systems 21, no. 3 (May): 96-101. doi:10.1109/MIS.2006.62. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1637364.
2. Siersdorfer, Stefan, and Sergej Sizov. 2009. Social recommender systems for web 2.0 folksonomies. Proceedings of the 20th ACM conference on Hypertext and hypermedia – HT ’09. New York, New York, USA: ACM Press. doi:10.1145/1557914.1557959. http://portal.acm.org/citation.cfm?doid=1557914.1557959.
3. Von Ahn, Luis, and Laura Dabbish. 2004. Labeling images with a computer game. Proceedings of the 2004 conference on Human factors in computing systems CHI 04 6, no. 1: 319-326. doi:10.1145/985692.985733. http://portal.acm.org/citation.cfm?doid=985692.985733.
4. Shepitsen, Andriy, Jonathan Gemmell, Bamshad Mobasher, and Robin Burke. 2008. Personalized recommendation in social tagging systems using hierarchical clustering. Proceedings of the 2008 ACM conference on Recommender systems RecSys 08: 259. doi:10.1145/1454008.1454048. http://portal.acm.org/citation.cfm?doid=1454008.1454048.
5. Szomszor, Martin, Ciro Cattuto, Harith Alani, Kieron O’Hara, Andrea Baldassarri, Vittorio Loreto, and Vito D P Servedio. 2007. Folksonomies, the Semantic Web, and Movie Recommendation. eprintsecssotonacuk: 71-84. http://eprints.ecs.soton.ac.uk/14007/.
6. Ma, Hao, Haixuan Yang, Michael R Lyu, and Irwin King. 2008. Sorec: social recommendation using probabilistic matrix factorization. In Proceeding of the 17th ACM conference on Information and knowledge management, 931-940. ACM. doi:10.1145/1458082.1458205. http://portal.acm.org/citation.cfm?id=1458205.
7. Shardanand, Upendra, and Pattie Maes. 1995. Social information filtering: algorithms for automating “word of mouth. In Proceedings of the ACM Conference on Human Factors in Computing Systems, ed. I R Katz, R Mack, L Marks, M B Rosson, and J Nielsen, 1:210-217. ACM Press/Addison-Wesley Publishing Co. doi:10.1145/223904.223931. http://portal.acm.org/citation.cfm?id=223931&coll=portal&d…N=53154003&ret=1.
8. Andersen, Reid, Christian Borgs, Jennifer Chayes, Uriel Feige, Abraham Flaxman, Adam Kalai, Vahab Mirrokni, and Moshe Tennenholtz. 2008. Trust-based recommendation systems: an axiomatic approach. Industrial Engineering 08pages: 199-208. doi:10.1145/1367497.1367525. http://portal.acm.org/citation.cfm?doid=1367497.1367525.

Folksonomy is a neologism of two words, ’folk’ and ’taxonomy’ which describes conceptual structures created by users ^{[4, 5]}. A folksonomy is a set of unstructured collaborative usage of tags for content classification and knowledge representation that is popularized by Web 2.0 and social applications ^{[1, 5]}. Unlike taxonomy that is commonly used to organize resources to form a category hierarchy, folksonomy is non-hierarchical and non-exclusive ^[3]. Both content hierarchy and folksonomy can be used together to better content classification.

Users of Web 2.0 applications typically organize their created content with a set of terms or keywords, also commonly known as tags ^{[3, 4, 6, 7]}. Spending additional time and effort to provide annotation such as tags to a resource usually implicitly implies the relevance and/or importance of the resource to a user ^[1]. Therefore, besides being used for content classification, tags assignment can also be analyze to find the implicit relationship between users and the tagged content.

It is also observed that the frequency of term usage is proportional to the level of importance or connection to user, i.e. the more a tag is used, the more it is important to the user ^{[1, 8]}. The choice of tags when annotating a resource often express the user interest and perceptions ^[8]. Users usually have different ideas and interests when tagging a resource especially when the application allow the same resource tagged by multiple users ^[2]. Therefore tagging activity pattern can be studied to find a user’s domain of interest.
Users with common interests tend to use similar set of tags in tagging re- sources of interest ^[2]. The similarity of users can then be calculated through the tagging pattern for recommending purpose as it provides social relationships between users ^{[4, 7]}. This may allow more collaboration between users sharing similar interest.

Although the variety selection of tag helps in better representation of the resource, but this may cause some problems as users don’t tend to agree to each other ^[2]. Observations also shows tagging behaviour follows power law distribution where tags are mostly assigned to a small subset of more
popular resources ^{[2, 7]}. Hence, when a resource gets popular, users having different interests will attempt to assign tags with keywords from all different domains. However, when different tags that are semantically related from each other are assigned to related resources (vocabulary mismatch problem), it may drastically decrease the level of relevance although the tags may actually share similar meaning ^{[3, 7]}.

Correlation between resources is often established when they are assigned with common tags ^[8]. The level of relevance can then be observed by studying the similarity in their set of assigned tags ^[8]. The correlation and similarity between the tags assigned to resources may also help users to find unseen resources by browsing the tags.

The assigned tags can be used as a tool to enable discovery, sharing and collaboration of web resources ^{[1, 2, 3, 8]}. Some applications even allow sharing of tagging information ^{[2, 8]}. Hence, besides using tags as a tool for content classification and user interest study, they can be used to make collaboration easier.

A resource may be described by its assigned tags depending on the tagging behaviour ^[1]. When an tagging system follows the bag-model, i.e. system that allows multiple users to tag a resource, the frequency of a tag is assigned also indirectly shows the increased relevance between the tag and the resource ^{[1, 2, 8]}. Weights can be also calculated for each tag to rank the relevance with the resource.
On the other hand, systems that implements the set-model do not provide enough data to deduce the level of importance or popularity of an assigned tag to the resource ^[8]. Due to the unstructured nature of collabo- rative tagging, the system can be easily abused if users assign tags that do not describe the content ^{[1, 8]}. The problem is more apparent for system implementing the set-model as there is no way to rank the assigned tags.

References

1. I. Cantador, A. Bellog ́ın, and D. Vallet. Content-based Recommendation in Social Tagging Systems. Methodology, pages 237–240, 2010.
2. Y. Guo and J. B. Joshi. Topic-based personalized recommendation for collaborative tagging system. Number 10. ACM Press, New York, New York, USA, 2010.
3. R. Lambiotte and M. Ausloos. Collaborative tagging as a tripartite network, 2005.
4. P. Mika. Ontologies are us: A unified model of social networks and semantics. Web Semantics Science Services and Agents on the World Wide Web, 5(1):5–15, 2007.
5. C. Schmitz, A. Hotho, R. J ̈aschke, and G. Stumme. Mining Association Rules in Folksonomies, pages 261–270. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, 2006.
6. N. Shadbolt, T. Berners-Lee, and W. Hall. The Semantic Web Revisited. IEEE Intelligent Systems, 21(3):96–101, May 2006.
7. S. Siersdorfer and S. Sizov. Social recommender systems for web 2.0 folksonomies. ACM Press, New York, New York, USA, 2009.
8. M. Szomszor, C. Cattuto, H. Alani, K. OHara, A. Baldassarri, V. Loreto, and V. D. P. Servedio. Folksonomies, the Semantic Web, and Movie Recommendation. eprintsecssotonacuk, pages 71–84, 2007.

Just managed to migrate all my blog sites to one centralized multi-site, so no more half-baked solution and hopefully this brings better plugin compatibility. I have not check with other related services (like Google Webmaster Tools) whether this cause any breakage though. Well, the main purpose of this blog post is actually a draft of what I did for the past two months for my postgraduate programme. Yea, I should have posted more stuff to this blog (just realized that my last post here is already like half a year ago).

Long story short, I have been working on my research project two months ago. Throughout the mentioned time period, I basically spent a lot of time trying to read and understand some of the related topics in semantic web, information retrieval as well as machine learning as suggested by my supervisor.

I first started with revisiting RDF by putting more emphasis on how it is usually implemented. Yea, I know I did some when I was preparing my research proposal, but I didn’t go to the detail and skipped the section describing RDF/XML all together.

Recently there have been some debates on whether JSON should be used as another data serialization format. I personally like JSON for its simplicity (especially comparing it to XML), but I find RDF/XML actually makes sense (read: good enough) because I find RDF is very URI dependent and it would probably be a bit awkward to see a lot of URI popping up in JSON. However, I am still very interested to see how this is sorted out, as W3C initiated a group to work on it. (Some thought-provoking read on this by nathan@webr3)

I have also read on RDFS for the first time and the more I read it, the more I find it related to my classes on AI (especially Prolog) in my Bachelor Degree. However, I am also slightly surprised to see how tolerant it is (leaving too much room for error?). Besides RDFS, I also read on OWL and find more similarity with Prolog (I really should post the summary of the readings here, yeah, too much to blog about, but lack of time and motivation).

What really surprised me was that with the combination of these (RDF, RDFS and OWL) technologies, I actually tried re-inventing the same thing for my last task in my previous job (over and over again). Although usage of RDF may not exactly fit the problem, but I feel it is close enough to solve the problem.

While looking for some articles on Linked Data Principle, I came across this TED talk by Sir Tim-Berners-Lee. Yeah, I do feel sorry for not publishing enough semantic data online after watching that, the talk was very motivating indeed (but is posting personal info that is machine readable without limit actually a good idea, I don’t feel like injecting a great portion of my life into social networking site, but that’s a different story).

I also read the beginner’s guide to SPARQL, and this is the real wow-factor to me. Although I don’t really like the SQL-like syntax, but the similarity to Prolog makes everything looks cool now. Yeah, I am pretty new in this, so I keep referring everything to Prolog XD.

Then I started to read on information retrieval, this is when everything suddenly seems not cool anymore. However, it did force me to do a lot of revision on statistics and some basic maths stuff (you will be surprised to see how much I forget after working for 2 years). And it wasn’t encouraging when I began to watch a video lecture on machine learning hoping to pick up in shorter time span because I find myself not understanding most of the lectures XD.

Yeah, that’s basically wraps up my progress for the past 2 months, getting myself excited with new stuff for the first month, and getting frustrated in the second month not able to understand the material.