Please wait a minute...
Data Analysis and Knowledge Discovery  2018, Vol. 2 Issue (12): 77-88    DOI: 10.11925/infotech.2096-3467.2018.0358
Current Issue | Archive | Adv Search |
Clustering Social Tags with Improved DBSCAN Algorithm
Xiong Huixiang(), Ye Jiaxin, Jiang Wuxuan
School of Information Management, Central China Normal University, Wuhan 430079, China
Download: PDF (631 KB)   HTML ( 4
Export: BibTeX | EndNote (RIS)      
Abstract  

[Objective] This paper tries to improve the DBSCAN algorithm and verify its feasibility and effectiveness in social tagging. [Methods] First, we analyzed the frequency of social tags for resources and their total appearances. Then, we examined the relationship between tags and resources to improve the DBSCAN clustering algorithm. Finally, we applied the new algorithm to cluster tags, and users. [Results] We ran our experiment with data from Douban Movies. The modified DBSCAN algorithm improved the inter-object and inter-cluster correlations of social taggings. [Limitations] The sample datasets need more in-depth mining. [Conclusions] The improved DBSCAN algorithm could effectively cluster social tags.

Key wordsDBSCAN      Tag Clustering      User Clustering      Tag Expansion     
Received: 30 March 2018      Published: 16 January 2019
ZTFLH:  G202  

Cite this article:

Xiong Huixiang,Ye Jiaxin,Jiang Wuxuan. Clustering Social Tags with Improved DBSCAN Algorithm. Data Analysis and Knowledge Discovery, 2018, 2(12): 77-88.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2018.0358     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2018/V2/I12/77

用户名称 用户标签 用户标注电影
烦烦电影 美剧; 神盾局特工; 漫威; 电影; 欧美电影; 国产电影;
日韩电影; 电影周边; 电影资讯; 电影剪辑
X战警: 黑凤凰; 复仇者联盟3: 无限战争; 心理罪之城市之光; 这就是命; 鲨海
电影阻击手 高清电影; 在线电影; 电影; 种子; 情感段子; 电影阻击手 美国队长; 变相怪杰; 蝙蝠侠: 黑暗骑士; 死寂; 白夜追凶
大电影院 电影; 电影迷; 电影控; 电影博主 X战警; 你好旧时光; 闪灵; 破坏之王; 巨额来电
深度电影圈 影讯; 影评; 电影; 美剧; LGBT; 欧美; KatyPerry;
MattBomer; 英剧; 好莱坞
复仇者联盟3: 无限战争; 引爆者; 神奇动物在哪里2; 花木兰; 心理罪之城市之光
电影 标签
X战警: 黑凤凰 动作; 科幻; 冒险
复仇者联盟3: 无限战争 动作; 科幻
心理罪之城市之光 动作; 悬疑; 犯罪
神奇动物在哪里2 剧情; 奇幻; 冒险
花木兰 剧情; 动画; 家庭; 冒险
心理罪之城市之光 动作; 悬疑; 犯罪
标签
动作; 科幻; 冒险; 悬疑; 犯罪; 喜剧; 惊悚; 爱情; 奇幻; 剧情; 恐怖; 动画; 家庭
类目 电影 标签
动作 这个杀手不太冷; 让子弹飞; …; V字仇杀队 剧情; 动作; …; 惊悚
科幻 盗梦空间; 阿凡达; …; 源代码 剧情; 动作; …; 冒险
悬疑 无间道; 盗梦空间; …; 恐怖游轮 剧情; 犯罪; …; 惊悚
喜剧 美丽人生; 三傻大闹宝莱坞; …; 天使爱美丽 剧情; 爱情; …; 科幻
音乐 海上钢琴师; 放牛班的春天; …; 音乐之声 剧情; 音乐; …; 冒险
爱情 这个杀手不太冷; 放牛班的春天; …; 曾经 剧情; 动作; …; 奇幻
战争 辛德勒的名单; 红海行动; …; 风声 动作; 科幻; …; 战争
标签
剧情; 动作; 犯罪; 科幻; 悬疑; 冒险; 喜剧; 西部; 奇幻; 动画; 古装; 惊悚; 爱情; 歌舞; 音乐; 家庭; 传记; 同性; 战争; 灾难; 历史; 情色
类目
标签
动作 科幻 悬疑 喜剧 音乐 爱情 战争 剧情 犯罪 恐怖 出现次数
动作 10 4 0 1 0 0 2 2 2 2 23
科幻 5 10 3 0 0 1 0 1 1 4 25
冒险 5 5 1 3 1 2 0 1 0 0 18
悬疑 0 3 10 0 0 0 0 1 3 5 22
犯罪 2 1 3 0 0 0 1 2 10 0 19
喜剧 2 1 0 10 2 5 1 2 1 0 24
惊悚 2 4 8 0 0 0 1 0 4 4 23
奇幻 2 0 0 1 1 2 0 1 0 0 7
爱情 0 1 0 7 4 10 2 3 0 0 27
动画 1 2 0 2 2 1 0 1 0 0 9
歌舞 0 0 0 1 0 1 0 1 0 0 3
剧情 5 6 9 7 9 7 9 10 10 4 76
灾难 0 0 0 0 0 1 0 1 0 1 3
音乐 0 0 0 0 10 0 0 1 0 0 11
同性 0 0 0 0 0 1 1 0 0 0 2
恐怖 0 0 0 0 0 0 0 0 0 10 10
战争 1 1 0 1 1 0 10 0 0 0 14
历史 0 0 0 0 1 0 6 0 0 0 7
情色 0 0 0 0 0 0 1 0 0 0 1
传记 0 0 0 0 1 0 2 0 0 0 3
家庭 0 0 0 0 1 0 0 0 0 0 1
西部 1 0 0 1 0 0 0 1 0 0 3
标签
标签
动作 科幻 冒险 悬疑 ··· 传记 家庭 西部
动作 0 9.055 7.000 14.731 ··· 11.402 11.576 10.488
科幻 9.055 0 7.550 11.358 ··· 12.570 12.410 12.000
冒险 7.000 7.550 0 12.570 ··· 8.307 8.062 7.141
悬疑 14.731 11.358 12.570 0 ··· 12.207 12.042 12.042
犯罪 12.329 13.784 12.042 11.533 ··· 10.954 10.954 10.677
喜剧 13.748 15.395 9.381 16.371 ··· 11.705 11.705 10.724
惊悚 11.916 9.055 10.344 3.606 ··· 10.863 10.863 10.770
序号 1 ··· 12 13 14 15 ··· 21 22
1 ··· 4 4.359 5.385 6.708 ··· 9.487 19.468
聚类簇 标签 数量
1 战争; 历史; 歌舞··· 11
2 惊悚; 悬疑 2
-1 剧情; 传记; 音乐··· 9
类目
标签
动作 科幻 悬疑 喜剧 ··· 剧情 犯罪 恐怖
动作 43.48 17.392 0 4.348 ··· 8.696 8.696 8.696
科幻 20 40 12 0 ··· 4 4 16
冒险 27.78 27.78 5.556 16.668 ··· 5.556 0 0
悬疑 0 13.635 45.45 0 ··· 4.545 13.635 22.725
犯罪 10.526 5.263 15.789 0 ··· 10.526 52.63 0
聚类簇 标签 数量
1 奇幻; 爱情; 科幻··· 9
2 悬疑; 惊悚 2
3 家庭; 音乐 2
4 战争; 历史; 传记··· 4
-1 犯罪; 灾难; 西部··· 5
类目
类目
动作 科幻 悬疑 喜剧 音乐 ··· 恐怖
动作 1.000 0.570 0.183 0.609 0.084 ··· 0.096
科幻 0.570 1.000 0.531 0.273 0.099 ··· 0.211
悬疑 0.183 0.531 1.000 0.038 0.019 ··· 0.275
喜剧 0.609 0.273 0.038 1.000 0.138 ··· 0.009
音乐 0.084 0.099 0.019 0.138 1.000 ··· 0.004
爱情 0.215 0.187 0.040 0.521 0.122 ··· 0.126
战争 0.077 0.085 0.035 0.070 0.171 ··· 0.011
剧情 0.148 0.142 0.085 0.252 0.102 ··· 0.112
犯罪 0.261 0.325 0.613 0.066 0.022 ··· 0.125
恐怖 0.096 0.211 0.275 0.009 0.004 ··· 1.000
类目
标签
动作 科幻 悬疑 喜剧 剧情 犯罪 恐怖
动作 55.56 0 0 11.112 11.112 11.112 11.112
科幻 41.665 0 8.333 0 8.333 8.333 33.332
冒险 55.555 11.111 22.222 0 11.111 0 0
悬疑 0 0 0 0 11.111 33.333 55.555
犯罪 13.334 0 0 6.667 13.334 66.67 0
聚类簇 标签 数量
1 动作; 科幻 2
2 冒险; 剧情; 奇幻··· 6
3 悬疑; 惊悚 2
4 家庭; 音乐 2
5 战争; 历史; 传记··· 4
-1 犯罪; 灾难; 西部··· 6
聚类 AC Eps AC/Eps
聚类1 11.023 5.386 2.048
聚类2 91.249 33.205 2.748
聚类3 87.555 30.851 2.838
电影 标签 动作 音乐 爱情 战争 剧情 犯罪 恐怖
X战警: 黑凤凰 动作 55.560 0.000 0.000 11.112 11.112 11.112 11.112
科幻 41.665 0.000 8.333 0.000 8.333 8.333 33.332
冒险 55.555 11.111 22.222 0.000 11.111 0.000 0.000
向量 50.927 3.704 10.185 3.704 10.185 6.482 14.815
复仇者联盟3: 无限战争 动作 55.560 0.000 0.000 11.112 11.112 11.112 11.112
科幻 41.665 0.000 8.333 0.000 8.333 8.333 33.332
向量 48.613 0.000 4.167 5.556 9.723 9.723 22.222
··· ··· ··· ··· ··· ··· ··· ··· ···
花木兰 动画 55.555 11.111 22.222 0.000 11.111 0.000 0.000
冒险 20.000 40.000 20.000 0.000 20.000 0.000 0.000
向量 37.778 25.556 21.111 0.000 15.556 0.000 0.000
用户名称 电影 动作 音乐 爱情 战争 剧情 犯罪 恐怖
烦烦电影 1 50.927 3.704 10.185 3.704 10.185 6.482 14.815
2 48.613 0.000 4.167 5.556 9.723 9.723 22.222
3 22.965 0.000 0.000 5.926 11.852 37.038 22.222
4 14.359 7.692 19.230 7.180 14.359 37.181 0.000
5 36.869 5.556 11.111 4.546 5.556 18.182 18.182
向量 34.746 3.390 8.939 5.382 10.335 21.721 15.488
电影阻击手 1 50.927 3.704 10.185 3.704 10.185 6.482 14.815
2 23.522 10.621 24.885 7.199 14.457 17.095 2.222
3 32.185 0.000 2.083 6.718 8.195 30.620 20.202
4 0.000 0.000 0.000 0.000 11.111 33.333 55.555
5 6.667 0.000 0.000 3.334 12.223 50.002 27.778
向量 22.660 2.865 7.431 4.191 11.234 27.506 24.114
大电影院 1 48.613 0.000 4.167 5.556 9.723 9.723 22.222
2 0.000 21.052 52.630 10.526 15.789 0.000 0.000
3 0.000 0.000 0.000 0.000 11.111 33.333 55.555
4 35.472 7.692 19.230 9.402 13.248 9.402 5.556
5 13.334 0.000 0.000 6.667 13.334 66.670 0.000
向量 19.484 5.749 15.205 6.430 12.641 23.826 16.667
深度电影圈 1 48.613 0.000 4.167 5.556 9.723 9.723 22.222
2 34.447 0.000 0.000 8.890 12.223 38.891 5.556
3 44.445 13.889 27.778 0.000 13.889 0.000 0.000
4 37.778 25.556 21.111 0.000 15.556 0.000 0.000
5 22.965 0.000 0.000 5.926 11.852 37.038 22.222
向量 37.649 7.889 10.611 4.074 12.648 17.130 10.000
用户
用户
烦烦电影 电影阻击手 大电影院 深度电影圈
烦烦电影 0.000 16.085 17.029 9.472
电影阻击手 16.085 0.000 12.443 23.852
大电影院 17.029 12.443 0.000 21.225
深度电影圈 9.472 23.852 21.225 0.000
序号 1 2 3 4
9.472 9.472 12.443 12.443
用户 聚类簇
电影阻击手 -1
大电影院 -1
烦烦电影 1
深度电影圈 1
用户 标签
电影阻击手 惊悚; 动作; 科幻
大电影院 剧情
簇1 动作; 科幻; 剧情
用户 标签
电影阻击手 惊悚电影; 动作电影; 科幻电影
大电影院 剧情电影
簇1 动作电影; 科幻电影; 剧情电影
[1] Hotho A, Jäschke R, Schmitz C, et al.Information Retrieval in Folksonomies: Search and Ranking[C]// Proceedings of the 3rd European Conference on the Semantic Web: Research and Applications. 2006: 411-426.
[2] 熊回香. 面向Web3.0的大众分类研究[D]. 武汉: 华中师范大学, 2011.
[2] (Xiong Huixiang.Research on Folksonomy Oriented to Web3.0[D]. Wuhan: Central China Normal University, 2011.)
[3] Hayman S.Folksonomies and Tagging: New Developments in Social Bookmarking[C]// Proceedings of the 2007 Ark Group Conference: Developing and Improving Classification Schemes. 2007.
[4] 苏新宁, 杨建林, 江念南, 等. 数据仓库和数据挖掘[M]. 北京: 清华大学出版社, 2006.
[4] (Su Xinning, Yang Jianlin, Jiang Niannan, et al.Data Warehouse and Data Mining[M]. Beijing: Tsinghua University Press, 2006.)
[5] Martin P, Eklund P.Embedding Knowledge in Web Documents: CGs Versus XML-based Metadata Languages[C]// Proceedings of the 7th International Conference on Conceptual Structures: Standards and Practices. 1999: 230-246.
[6] Razmerita L, Lytras M D.Ontology-Based User Modelling Personalization: Analyzing the Requirements of a Semantic Learning Portal[C]// Proceedings of the 1st World Summit on Knowledge Society. Springer, 2008: 354-363.
[7] 房小可, 纪春光. 基于标签主题和概念空间的个性化推荐研究[J]. 情报理论与实践, 2015, 38(5): 105-111.
doi: 10.16353/j.cnki.1000-7490.2015.05.021
[7] (Fang Xiaoke, Ji Chunguang.Research on the Personalized Recommendation Based on Tag Topic and Concept Space[J]. Information Studies: Theory & Application, 2015, 38(5): 105-111.)
doi: 10.16353/j.cnki.1000-7490.2015.05.021
[8] Sood S, Owsley S, Hammond K J, et al.TagAssist: Automatic Tag Suggestion for Blog Posts[C]//Proceedings of ICWSM’ 2007, Boulder, Colorado, USA. 2007.
[9] Zhang Z K, Liu C.A Hypergraph Model of Social Tagging Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010(10): P10005.
doi: 10.1088/1742-5468/2010/10/P10005
[10] 钟青燕, 苏一丹, 梁胜勇. 基于层次聚类和语义的标签推荐研究[J]. 微计算机信息, 2010, 26(12-3): 199-203.
doi: 10.3969/j.issn.2095-6835.2010.36.080
[10] (Zhong Qingyan, Su Yidan, Liang Shengyong.Tag Recommendation Research Base on Hierarchical Clustering and Semantic[J]. Microcomputer Information, 2010, 26(12-3): 199-203.)
doi: 10.3969/j.issn.2095-6835.2010.36.080
[11] 廖志芳, 王超群, 李小庆, 等. 张量分解的标签推荐及新用户标签推荐算法[J]. 小型微型计算机系统, 2013, 34(11): 2472-2476.
doi: 10.3969/j.issn.1000-1220.2013.11.011
[11] (Liao Zhifang, Wang Chaoqun, Li Xiaoqing, et al.Tag Recommendation and New User Tag Recommendation Algorithms Based on Tensor Decomposition[J]. Journal of Chinese Computer Systems, 2013, 34(11): 2472-2476.)
doi: 10.3969/j.issn.1000-1220.2013.11.011
[12] 张斌, 张引, 高克宁, 等. 融合关系与内容分析的社会标签推荐[J]. 软件学报, 2012, 23(3): 476-488.
doi: 10.3724/SP.J.1001.2012.04001
[12] (Zhang Bin, Zhang Yin, Gao Kening, et al.Combining Relation and Content Analysis for Social Tagging Recommendation[J]. Journal of Software, 2012, 23(3): 476-488.)
doi: 10.3724/SP.J.1001.2012.04001
[13] 易明, 操玉杰, 沈劲枝, 等. 社会化标签系统中基于密度聚类的Web 用户兴趣建模方法[J]. 情报学报, 2011, 30(1): 37-43.
doi: 10.3772/j.issn.1000-0135.2011.01.005
[13] (Yi Ming, Cao Yujie, Shen Jinzhi, et al.An Approach to Web User Interest Modeling Based on Density-based Clustering Algorithm in the Social Tag System[J]. Journal of the China Society for Scientific and Technical Information, 2011, 30(1): 37-43.)
doi: 10.3772/j.issn.1000-0135.2011.01.005
[14] Begelman G, Keller P, Smadja F.Automated Tag Clustering: Improving Search and Exploration in the Tag Space[C]// Proceedings of the Collaborative Web Tagging Workshop at WWW2006. 2006: 15-33.
[15] 曹高辉, 焦玉英, 成全. 基于凝聚式层次聚类算法的标签聚类研究[J]. 现代图书情报技术, 2008(4): 23-28.
doi: 10.3969/j.issn.1003-3513.2008.04.005
[15] (Cao Gaohui, Jiao Yuying, Cheng Quan.Research on Tag Cluster Based on Hierarchical Agglomerative Clustering Algorithm[J]. New Technology of Library and Information Service, 2008(4): 23-28.)
doi: 10.3969/j.issn.1003-3513.2008.04.005
[16] Gemmell J, Shepitsen A, Mobasher B, et al.Personalizing Navigation in Folksonomies Using Hierarchical Tag Clustering[C]// Proceedings of the 10th International Conference on Data Warehousing and Knowledge Discovery. Springer, 2008: 196-205.
[17] 王翠英. 标签的聚类分析研究[J]. 现代图书情报技术, 2008(5): 67-71.
doi: 10.3969/j.issn.1003-3513.2008.05.012
[17] (Wang Cuiying.Study on Tag Clustering Analysis[J]. New Technology of Library and Information Service, 2008(5): 67-71.)
doi: 10.3969/j.issn.1003-3513.2008.05.012
[18] 石陆魁, 何丕廉. 一种基于密度的高效聚类算法[J]. 计算机应用, 2005, 25(8): 1824-1826.
doi: 10.3724/SP.J.1087.2005.01824
[18] (Shi Lukui, He Pilian.Efficient Density-Based Clustering Algorithm[J]. Computer Applications, 2005, 25(8): 1824-1826.)
doi: 10.3724/SP.J.1087.2005.01824
[19] 李双庆, 慕升弟. 一种改进的DBSCAN算法及其应用[J]. 计算机工程与应用, 2014, 50(8):72-76.
doi: 10.3778/j.issn.1002-8331.1212-0093
[19] (Li Shuangqing, Mu Shengdi.Improved DBSCAN Algorithm and Its Application[J]. Computer Engineering and Applications, 2014, 50(8): 72-76.)
doi: 10.3778/j.issn.1002-8331.1212-0093
[20] Li P, Wang B, Jin W, et al.User-Related Tag Expansion for Web Document Clustering[C]// Proceedings of the 33rd European Conference on Information Retrieval. Springer, 2011: 19-31.
[21] Zezula P, Amato G, Dohnal V, et al.Similarity Search: The Metric Space Approach[M]. Springer Science & Business Media, 2006.
[1] Wang Xiwei,Jia Ruonan,Wei Yanan,Zhang Liu. Clustering User Groups of Public Opinion Events from Multi-dimensional Social Network[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[2] Huiying Gao,Tian Wei,Jiawei Liu. Friend Recommendation Based on User Clustering and Dynamic Interaction Trust Relationship[J]. 数据分析与知识发现, 2019, 3(10): 66-77.
[3] Zhang Chengzhi, Gu Xiaoxue. Clustering Machine-Generated Tags with Different Quality[J]. 现代图书情报技术, 2015, 31(10): 22-29.
[4] Gu Xiaoxue, Zhang Chengzhi. Combined with Annotated Content and User Attributes for Tag Clustering[J]. 现代图书情报技术, 2015, 31(10): 30-39.
[5] Wang Xiaoyun, Qian Lu, Huang Shiyou. Collaborative Filtering Recommendation Model Based on Rough User Clustering[J]. 现代图书情报技术, 2015, 31(1): 45-51.
[6] Yan Duanwu,Luo Shengyang,Cheng Xiao . Toward User-Document Matrix Based User Clustering for Collaborative Recommendation[J]. 现代图书情报技术, 2007, 2(3): 25-28.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn