java算法之餘弦相似度計算字符串相似率
概述
功能需求:最近在做通過爬蟲技術去爬取各大相關網站的新聞,儲存到公司數據中。這裡面就有一個技術點,就是如何保證你已爬取的新聞,再有相似的新聞
或者一樣的新聞,那就不存儲到數據庫中。(因為有網站會去引用其它網站新聞,或者把其它網站新聞拿過來稍微改下內容就發佈到自己網站中)。
解析方案:最終就是采用餘弦相似度算法,來計算兩個新聞正文的相似度。現在自己寫一篇博客總結下。
一、理論知識
先推薦一篇博客,對於餘弦相似度算法的理論講的比較清晰,我們也是按照這個方式來計算相似度的。網址:相似度算法之餘弦相似度。
1、說重點
我這邊先把計算兩個字符串的相似度理論知識再梳理一遍。
(1)首先是要明白通過向量來計算相識度公式。
(2)明白:餘弦值越接近1,也就是兩個向量越相似,這就叫”餘弦相似性”,
餘弦值越接近0,也就是兩個向量越不相似,也就是這兩個字符串越不相似。
2、案例理論知識
舉一個例子來說明,用上述理論計算文本的相似性。為瞭簡單起見,先從句子著手。
句子A:這隻皮靴號碼大瞭。那隻號碼合適。
句子B:這隻皮靴號碼不小,那隻更合適。
怎樣計算上面兩句話的相似程度?
基本思路是:如果這兩句話的用詞越相似,它們的內容就應該越相似。因此,可以從詞頻入手,計算它們的相似程度。
第一步,分詞。
句子A:這隻/皮靴/號碼/大瞭。那隻/號碼/合適。
句子B:這隻/皮靴/號碼/不/小,那隻/更/合適。
第二步,計算詞頻。(也就是每個詞語出現的頻率)
句子A:這隻1,皮靴1,號碼2,大瞭1。那隻1,合適1,不0,小0,更0
句子B:這隻1,皮靴1,號碼1,大瞭0。那隻1,合適1,不1,小1,更1
第三步,寫出詞頻向量。
句子A:(1,1,2,1,1,1,0,0,0)
句子B:(1,1,1,0,1,1,1,1,1)
第四步:運用上面的公式:計算如下:
計算結果中夾角的餘弦值為0.81非常接近於1,所以,上面的句子A和句子B是基本相似的
二、實際開發案例
我把我們實際開發過程中字符串相似率計算代碼分享出來。
1、pom.xml
展示一些主要jar包
<!--結合操作工具包--> <dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-lang3</artifactId> <version>3.5</version> </dependency> <!--bean實體註解工具包--> <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> </dependency> <!--漢語言包,主要用於分詞--> <dependency> <groupId>com.hankcs</groupId> <artifactId>hanlp</artifactId> <version>portable-1.6.5</version> </dependency>
2、main方法
/** * 計算兩個字符串的相識度 */ public class Similarity { public static final String content1="今天小小和爸爸一起去摘草莓,小小說今天的草莓特別的酸,而且特別的小,關鍵價格還貴"; public static final String content2="今天小小和媽媽一起去草原裡采草莓,今天的草莓味道特別好,而且價格還挺實惠的"; public static void main(String[] args) { double score=CosineSimilarity.getSimilarity(content1,content2); System.out.println("相似度:"+score); score=CosineSimilarity.getSimilarity(content1,content1); System.out.println("相似度:"+score); } }
先看運行結果:
通過運行結果得出:
(1)第一次比較相似率為:0.772853 (說明這兩條句子還是挺相似的),第二次比較相似率為:1.0 (說明一模一樣)。
(2)我們可以看到這個句子的分詞效果,後面是詞性。
3、Tokenizer(分詞工具類)
import com.hankcs.hanlp.HanLP; import com.hankcs.hanlp.seg.common.Term; import java.util.List; import java.util.stream.Collectors; /** * 中文分詞工具類*/ public class Tokenizer { /** * 分詞*/ public static List<Word> segment(String sentence) { //1、 采用HanLP中文自然語言處理中標準分詞進行分詞 List<Term> termList = HanLP.segment(sentence); //上面控制臺打印信息就是這裡輸出的 System.out.println(termList.toString()); //2、重新封裝到Word對象中(term.word代表分詞後的詞語,term.nature代表改詞的詞性) return termList.stream().map(term -> new Word(term.word, term.nature.toString())).collect(Collectors.toList()); } }
4、Word(封裝分詞結果)
這裡面真正用到的其實就詞名和權重。
import lombok.Data; import java.util.Objects; /** * 封裝分詞結果*/ @Data public class Word implements Comparable { // 詞名 private String name; // 詞性 private String pos; // 權重,用於詞向量分析 private Float weight; public Word(String name, String pos) { this.name = name; this.pos = pos; } @Override public int hashCode() { return Objects.hashCode(this.name); } @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Word other = (Word) obj; return Objects.equals(this.name, other.name); } @Override public String toString() { StringBuilder str = new StringBuilder(); if (name != null) { str.append(name); } if (pos != null) { str.append("/").append(pos); } return str.toString(); } @Override public int compareTo(Object o) { if (this == o) { return 0; } if (this.name == null) { return -1; } if (o == null) { return 1; } if (!(o instanceof Word)) { return 1; } String t = ((Word) o).getName(); if (t == null) { return 1; } return this.name.compareTo(t); } }
5、CosineSimilarity(相似率具體實現工具類)
import com.jincou.algorithm.tokenizer.Tokenizer; import com.jincou.algorithm.tokenizer.Word; import org.apache.commons.lang3.StringUtils; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.springframework.util.CollectionUtils; import java.math.BigDecimal; import java.util.*; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.atomic.AtomicInteger; /** * 判定方式:餘弦相似度,通過計算兩個向量的夾角餘弦值來評估他們的相似度 餘弦夾角原理: 向量a=(x1,y1),向量b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2 * |a|=根號[(x1)^2+(y1)^2],|b|=根號[(x2)^2+(y2)^2]*/ public class CosineSimilarity { protected static final Logger LOGGER = LoggerFactory.getLogger(CosineSimilarity.class); /** * 1、計算兩個字符串的相似度 */ public static double getSimilarity(String text1, String text2) { //如果wei空,或者字符長度為0,則代表完全相同 if (StringUtils.isBlank(text1) && StringUtils.isBlank(text2)) { return 1.0; } //如果一個為0或者空,一個不為,那說明完全不相似 if (StringUtils.isBlank(text1) || StringUtils.isBlank(text2)) { return 0.0; } //這個代表如果兩個字符串相等那當然返回1瞭(這個我為瞭讓它也分詞計算一下,所以註釋掉瞭) // if (text1.equalsIgnoreCase(text2)) { // return 1.0; // } //第一步:進行分詞 List<Word> words1 = Tokenizer.segment(text1); List<Word> words2 = Tokenizer.segment(text2); return getSimilarity(words1, words2); } /** * 2、對於計算出的相似度保留小數點後六位 */ public static double getSimilarity(List<Word> words1, List<Word> words2) { double score = getSimilarityImpl(words1, words2); //(int) (score * 1000000 + 0.5)其實代表保留小數點後六位 ,因為1034234.213強制轉換不就是1034234。對於強制轉換添加0.5就等於四舍五入 score = (int) (score * 1000000 + 0.5) / (double) 1000000; return score; } /** * 文本相似度計算 判定方式:餘弦相似度,通過計算兩個向量的夾角餘弦值來評估他們的相似度 餘弦夾角原理: 向量a=(x1,y1),向量b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2 * |a|=根號[(x1)^2+(y1)^2],|b|=根號[(x2)^2+(y2)^2] */ public static double getSimilarityImpl(List<Word> words1, List<Word> words2) { // 向每一個Word對象的屬性都註入weight(權重)屬性值 taggingWeightByFrequency(words1, words2); //第二步:計算詞頻 //通過上一步讓每個Word對象都有權重值,那麼在封裝到map中(key是詞,value是該詞出現的次數(即權重)) Map<String, Float> weightMap1 = getFastSearchMap(words1); Map<String, Float> weightMap2 = getFastSearchMap(words2); //將所有詞都裝入set容器中 Set<Word> words = new HashSet<>(); words.addAll(words1); words.addAll(words2); AtomicFloat ab = new AtomicFloat();// a.b AtomicFloat aa = new AtomicFloat();// |a|的平方 AtomicFloat bb = new AtomicFloat();// |b|的平方 // 第三步:寫出詞頻向量,後進行計算 words.parallelStream().forEach(word -> { //看同一詞在a、b兩個集合出現的此次 Float x1 = weightMap1.get(word.getName()); Float x2 = weightMap2.get(word.getName()); if (x1 != null && x2 != null) { //x1x2 float oneOfTheDimension = x1 * x2; //+ ab.addAndGet(oneOfTheDimension); } if (x1 != null) { //(x1)^2 float oneOfTheDimension = x1 * x1; //+ aa.addAndGet(oneOfTheDimension); } if (x2 != null) { //(x2)^2 float oneOfTheDimension = x2 * x2; //+ bb.addAndGet(oneOfTheDimension); } }); //|a| 對aa開方 double aaa = Math.sqrt(aa.doubleValue()); //|b| 對bb開方 double bbb = Math.sqrt(bb.doubleValue()); //使用BigDecimal保證精確計算浮點數 //double aabb = aaa * bbb; BigDecimal aabb = BigDecimal.valueOf(aaa).multiply(BigDecimal.valueOf(bbb)); //similarity=a.b/|a|*|b| //divide參數說明:aabb被除數,9表示小數點後保留9位,最後一個表示用標準的四舍五入法 double cos = BigDecimal.valueOf(ab.get()).divide(aabb, 9, BigDecimal.ROUND_HALF_UP).doubleValue(); return cos; } /** * 向每一個Word對象的屬性都註入weight(權重)屬性值 */ protected static void taggingWeightByFrequency(List<Word> words1, List<Word> words2) { if (words1.get(0).getWeight() != null && words2.get(0).getWeight() != null) { return; } //詞頻統計(key是詞,value是該詞在這段句子中出現的次數) Map<String, AtomicInteger> frequency1 = getFrequency(words1); Map<String, AtomicInteger> frequency2 = getFrequency(words2); //如果是DEBUG模式輸出詞頻統計信息 // if (LOGGER.isDebugEnabled()) { // LOGGER.debug("詞頻統計1:\n{}", getWordsFrequencyString(frequency1)); // LOGGER.debug("詞頻統計2:\n{}", getWordsFrequencyString(frequency2)); // } // 標註權重(該詞出現的次數) words1.parallelStream().forEach(word -> word.setWeight(frequency1.get(word.getName()).floatValue())); words2.parallelStream().forEach(word -> word.setWeight(frequency2.get(word.getName()).floatValue())); } /** * 統計詞頻 * @return 詞頻統計圖 */ private static Map<String, AtomicInteger> getFrequency(List<Word> words) { Map<String, AtomicInteger> freq = new HashMap<>(); //這步很帥哦 words.forEach(i -> freq.computeIfAbsent(i.getName(), k -> new AtomicInteger()).incrementAndGet()); return freq; } /** * 輸出:詞頻統計信息 */ private static String getWordsFrequencyString(Map<String, AtomicInteger> frequency) { StringBuilder str = new StringBuilder(); if (frequency != null && !frequency.isEmpty()) { AtomicInteger integer = new AtomicInteger(); frequency.entrySet().stream().sorted((a, b) -> b.getValue().get() - a.getValue().get()).forEach( i -> str.append("\t").append(integer.incrementAndGet()).append("、").append(i.getKey()).append("=") .append(i.getValue()).append("\n")); } str.setLength(str.length() - 1); return str.toString(); } /** * 構造權重快速搜索容器 */ protected static Map<String, Float> getFastSearchMap(List<Word> words) { if (CollectionUtils.isEmpty(words)) { return Collections.emptyMap(); } Map<String, Float> weightMap = new ConcurrentHashMap<>(words.size()); words.parallelStream().forEach(i -> { if (i.getWeight() != null) { weightMap.put(i.getName(), i.getWeight()); } else { LOGGER.error("no word weight info:" + i.getName()); } }); return weightMap; } }
這個具體實現代碼因為思維很緊密所以有些地方寫的比較繞,同時還手寫瞭AtomicFloat原子類。
6、AtomicFloat原子類
import java.util.concurrent.atomic.AtomicInteger; /** * jdk沒有AtomicFloat,寫一個 */ public class AtomicFloat extends Number { private AtomicInteger bits; public AtomicFloat() { this(0f); } public AtomicFloat(float initialValue) { bits = new AtomicInteger(Float.floatToIntBits(initialValue)); } //疊加 public final float addAndGet(float delta) { float expect; float update; do { expect = get(); update = expect + delta; } while (!this.compareAndSet(expect, update)); return update; } public final float getAndAdd(float delta) { float expect; float update; do { expect = get(); update = expect + delta; } while (!this.compareAndSet(expect, update)); return expect; } public final float getAndDecrement() { return getAndAdd(-1); } public final float decrementAndGet() { return addAndGet(-1); } public final float getAndIncrement() { return getAndAdd(1); } public final float incrementAndGet() { return addAndGet(1); } public final float getAndSet(float newValue) { float expect; do { expect = get(); } while (!this.compareAndSet(expect, newValue)); return expect; } public final boolean compareAndSet(float expect, float update) { return bits.compareAndSet(Float.floatToIntBits(expect), Float.floatToIntBits(update)); } public final void set(float newValue) { bits.set(Float.floatToIntBits(newValue)); } public final float get() { return Float.intBitsToFloat(bits.get()); } @Override public float floatValue() { return get(); } @Override public double doubleValue() { return (double) floatValue(); } @Override public int intValue() { return (int) get(); } @Override public long longValue() { return (long) get(); } @Override public String toString() { return Float.toString(get()); } }
三、總結
把大致思路再捋一下:
(1)先分詞:分詞當然要按一定規則,不然隨便分那也沒有意義,那這裡通過采用HanLP中文自然語言處理中標準分詞進行分詞。
(2)統計詞頻:就統計上面詞出現的次數。
(3)通過每一個詞出現的次數,變成一個向量,通過向量公式計算相似率。
以上就是java算法之餘弦相似度計算字符串相似率的詳細內容,更多關於java算法的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- opencv實現車牌識別
- Java Float 保留小數位精度的實現
- python 爬取豆瓣電影短評並利用wordcloud生成詞雲圖
- 聊聊Java Double相加出現的怪事
- 教你如何用Java根據日期生成流水號