Geo Word Clouds

背景:

有许多文本数据含有重要的地理信息,而现有的词云方法无法显示空间信息。
Geo word clouds:不但可以显示词频还可以显示词之间的空间关联。

输入:n个点(带有地理位置);
M:需要填充的地理区域;
M':填充完后的地理区域;

2.1 Requirements

Paste_Image.png
  • R1. 所有单词不相交;
  • R2. 每个词都有少量的shapes;(一个点代表一个单词,如果相同的词的点相互关联,则将其连成一个词。一个簇是一个单词,根据簇大小决定文本大小,一个簇可视后是一个shape)
  • R3/M1. 词的shapes要和它的点很好的吻合;(为了强调词云的空间性,shapes和点需要吻合。一个词覆盖的点越多,这个词和没有被覆盖的点的距离越小,这个词所代表的空间数据越好。)
  • R4/M2. 有k个点的词的区域接近于(M'是可视化后的区域,M是原始区域)
Paste_Image.png
  • R5/M3. M'需要将M完美覆盖(不要越界,不要留太多空白)
  • R6. 同一单词的shapes需要有相同的颜色(保证一致性)
  • R7. 不要让着色影响单词的重要性。

2.2 Measures:

A.

Paste_Image.png

( p:点;Cp:p所属的簇;Word(Cp):矩形限位框。)
在边框上或者内部的霍斯多夫距离为0。
为了测量词的shapes是否和它的点很好的吻合,需要用到Hausdorff距离。
Coverage error:
The sum of the error for all points measures how well all shapes in M' cover the whole data set.(可视化后的shapes结果与数据的吻合度,可以理解为聚类后的框与其可视化后的shapes的吻合度)

B.

Paste_Image.png

为了给词定义合适的位置,有时候需要进行词的缩放,因此M2表示的就是词的大小能够代表其点数的程度。比如对于有k个点的词,缩放比例为x,则not represented的点数为|k-k*x| (Rep(c):簇c中not represented 的点数。C:所有簇。),因此缩小词会使得该值变大。

C.

Paste_Image.png

How well does M' resemble M.
M'与M的差值。

3.布局算法

k-means算法将同一标签的点聚成簇,每一个簇放一个单词。单词的大小取决于簇中点的数量。
clustering之后对每一个簇确定一个旋转角度。对簇中的点确定特征向量,利用特征向量中的principal component。确定这些点的特征向量并使用向量中的主成分。角度的选取要与特征向量保持相近。旋转角度:正交、45度、10度。

Paste_Image.png

词的位置:贪心算法。根据簇的大小(簇中包含的点数)进行排序,位置由大到小放置避免对于更大的簇会有大的误差。按像素进行词的位置的计算,没有被占据的像素可以利用。
如果词无法放置在准确的位置,我们需要按比例缩减它,这样词的中心距离簇的中心就会更小。则需要对其进行重新的大小排序。

Paste_Image.png

Optimal size的设定(R4):(AM 为由像素计算的M)

Paste_Image.png

4.着色:

为了满足R6和R7.

Paste_Image.png

根据Hue光谱,颜色的排布随词的大小排。
相似大小的单词颜色要隔c个,以防相似大小的词颜色相似。因此c需要大于1,图中为c=3的情况。这样两个相邻的单词得到相同颜色的概率大大缩减。

5.实验

数据:
1.法国:125个不同的标签,关于奶酪品种
2.英国和爱尔兰:126个来自网络相册的不同的照片标签,545140个图像。
实现:Sage Math Cloud(基于Python的软件包)

5.1Allowed rotations(是否需要更多的角度选择?)

Paste_Image.png

90度的coverage error(所有点距离限位框的距离和,与其原定位置的差值)最小,因为90度时空间整齐,选择性强,使得shapes与其原定位置相差小。
Words not represented 变大,因为在45度和10度时,把所有词放在原定位置有困难,因此需要缩小一些词,因此words not represented会更多。
Symmetric difference在90度时最小,因为90度时更紧密,使得M'与M差值最小。

5.2 Initial font size

Paste_Image.png

100%到90% coverage error(所有点距离限位框的距离和,与其原定位置的差值)变大,因为所有字都变小,聚类的覆盖的点就变少了。90%到80%变小,因为可视化后的词比预定位置更接近。
随着字体变小,words not represented 就变小了。
随着字体变小,symmetric difference变大。(可以理解为:所有词都变小,地图上的总覆盖变小,因此M'与M相差较大)

5.3 Clustering

Paste_Image.png
  • a.一个点放一个词,则无法区分词频。
  • b.是a和b这两个极端的中间值。标签应用的多个区域都可以观察到,并且词的数量不会太大。
  • c.每一个词用一个簇,则无法看出地区差别。
Paste_Image.png
  • 1.点被聚类的时候coverage error(所有点距离限位框的距离和)会变大,因为点距离它的原本位置的误差变大。
  • 2.如果不聚类的话,许多词的位置会重叠,这样许多词不能放在原本的位置,因此这些词需要缩小以放置在适合的位置,所以words not represented会变大。
  • 3.(c)比(b)差的原因:簇变大,词也会变大,使得相似大小的词难以整齐排布填满地图。

5.4 Word placement

Paste_Image.png
  • 1.第一个被放置的词是Tomme,因为它的词频最大,根据聚类算法,将其分为两个簇,词放置在最佳的位置以覆盖尽可能多的点;
  • 2.第二个词Faisselle,因为Tomme占据了Faisselle的右下角最佳位置,因此需要调整Faisselle的位置,保证覆盖尽可能多的点;
  • 3.第三个是Crottin,放置方法与之前相同。

5.5 Running time

法国:30分钟(90度)
英国和爱尔兰:60分钟(90度)
如果把角度变为10度,时间增加了60%。
数据的预处理(聚类和归一化)仅分别花费了几秒和几分钟。

Conclusions

  • 1.旋转角度为90度时,结果最紧凑;
  • 2.实现方法:贪心算法;
  • 3.所选择的聚类算法也会影响地图的覆盖,我们发现k-means算法是最好的。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容