概述

python_mmdt是一種基于敏感哈希的特征向量生成工具。核心算法使用C實(shí)現(xiàn)，提高程序執(zhí)行效率。同時(shí)使用python進(jìn)行封裝，方便研究人員使用。 本篇幅主要介紹涉及的相關(guān)基本內(nèi)容與使用，相關(guān)內(nèi)容的詳細(xì)說(shuō)明，后續(xù)詳細(xì)探討。

重點(diǎn)內(nèi)容

重點(diǎn)內(nèi)容，包括三個(gè)方面：

對(duì)象歸一化：數(shù)據(jù)的重采樣

局部敏感哈希函數(shù)的定義：特征向量的生成

特征向量的應(yīng)用：距離計(jì)算、相似度計(jì)算、分類(lèi)、聚類(lèi)

重點(diǎn)假設(shè)

數(shù)據(jù)的重采樣方法無(wú)條件適用于研究對(duì)象，且重采樣的過(guò)程會(huì)部分保留原始數(shù)據(jù)的差異性與相似性

重采樣之后的單個(gè)數(shù)據(jù)點(diǎn)（隨機(jī)變量）是滿足獨(dú)立同分布的

N取值很大時(shí)，敏感哈希函數(shù)值分布近似于正態(tài)分布，則落在指定區(qū)間內(nèi)的局部敏感哈希值是有效的

基本過(guò)程

1. 數(shù)據(jù)重采樣

我們的研究對(duì)象常常是不同的文件格式，不同的文件大小，如何方便的處理這類(lèi)格式不同，大小不一的文件呢？方法有很多種，這里我們使用采樣的方法。

采樣原始定義：

采樣是將信號(hào)從連續(xù)時(shí)間域上的模擬信號(hào)轉(zhuǎn)換到離散時(shí)間域上的離散信號(hào)的過(guò)程。

下采樣定義：

對(duì)于一個(gè)樣值序列間隔幾個(gè)樣值取樣一次，這樣得到新序列就是原序列的下采樣。

通過(guò)重采樣（本工具中特指下采樣），我們讓對(duì)象數(shù)據(jù)都處于相同的維度（大小）。這樣，就可以比較方便地定義我們自己的局部敏感哈希函數(shù)。

python_mmdt使用Lanczos采樣方法。

2. 局部敏感哈希函數(shù)

局部敏感哈希的基本概念

局部敏感哈希(Locality Sensitive Hashing，LSH)的基本思想類(lèi)似于一種空間域轉(zhuǎn)換思想，LSH算法基于一個(gè)假設(shè)，如果兩個(gè)文本在原有的數(shù)據(jù)空間是相似的，那么分別經(jīng)過(guò)哈希函數(shù)轉(zhuǎn)換以后的它們也具有很高的相似度；相反，如果它們本身是不相似的，那么經(jīng)過(guò)轉(zhuǎn)換后它們應(yīng)仍不具有相似性。

通過(guò)重采樣之后的數(shù)據(jù)，我們假設(shè)其滿足獨(dú)立同分布。同時(shí)，我們將重采樣的數(shù)據(jù)，平均分成N塊，每塊之間的數(shù)據(jù)進(jìn)行累計(jì)求和，和值分布近似服從正態(tài)分布，我們?nèi)『椭蹈選位的一個(gè)byte做為本塊數(shù)據(jù)的敏感哈希值。

例如：

• 51030000:D6E26822530202020202020202020202：51030000是4字節(jié)索引敏感哈希，D6E26822530202020202020202020202是16字節(jié)敏感哈希
• 4F454750:A4B58A07235B23F13B2F244A9B8A547B：4F454750是4字節(jié)索引敏感哈希，A4B58A07235B23F13B2F244A9B8A547B是16字節(jié)敏感哈希

3. 特征向量的應(yīng)用

1. 簡(jiǎn)單應(yīng)用

簡(jiǎn)單應(yīng)用如，索引敏感哈希可以轉(zhuǎn)成一個(gè)int32的數(shù)字，當(dāng)索引敏感哈希相等時(shí)，再比較敏感哈希的距離（如曼哈頓距離，將敏感哈希轉(zhuǎn)成N個(gè)unsigned char類(lèi)型計(jì)算敏感哈希，此時(shí)00和FF之間的距離可算作1，也可算作255，具體看實(shí)現(xiàn)）。

2. 復(fù)雜應(yīng)用

由于特征向量的維度是固定的，因此可以很方便的使用其他數(shù)學(xué)方法，進(jìn)行大規(guī)模計(jì)算。

• 如結(jié)合矩陣運(yùn)算，快速得到上萬(wàn)特征向量（樣本）的相似度矩陣，
• 如用于機(jī)器學(xué)習(xí)的分類(lèi)（KNN）、聚類(lèi)（Kmeans）等

安裝

依賴(lài)

• cmake: 2.6及以上版本
• windows: 當(dāng)前版本(0.0.3)安裝需要配置minGW編譯C代碼

pip安裝

$ pip install python_mmdt

通過(guò)whl包安裝（免編譯）

.whl 從github_release或者pypi下載編譯好的二進(jìn)制包安裝

$ pip install python_mmdt-xxx.whl

使用

命令行

安裝之后，可以通過(guò)命令行，快速計(jì)算敏感hash或比較兩個(gè)文件相似度

# calculate mmdt sensitive $ mmdt-hash $file_path# calculate file similarity $ mmdt-compare $file_path1 $file_path2

python code

用作python庫(kù)，導(dǎo)入編碼使用

# -*- coding: utf-8 -*-import unittest import os from python_mmdt.mmdt.mmdt import MMDTclass Testmmdt(unittest.TestCase):def test_process(self):mmdt = MMDT()test_path = os.path.dirname(__file__)test_samples = os.path.join(test_path, "samples")files = os.listdir(test_samples)for f in files:file_path = os.path.join(test_samples, f)r1 = mmdt.mmdt_hash(file_path)print(r1)r2 = mmdt.mmdt_hash_streaming(file_path)print(r2)sim1 = mmdt.mmdt_compare(file_path, file_path)print(sim1)sim2 = mmdt.mmdt_compare_hash(r1, r2)print(sim2)

示例

拷貝一份當(dāng)前項(xiàng)目的setup.py，命名為setup_1.py。

setup_1.py進(jìn)行兩種變換：

使用大寫(xiě)字母E全局替換小寫(xiě)字母e

使用ee全局替換大寫(xiě)字母E

計(jì)算mmdt_hash等于0.9811928175556364。

vim對(duì)比圖如：

md5、文件大小、mmdt_hash信息圖如：

其他

由于敏感哈希采用累計(jì)求和的方式，和值近似服從正態(tài)分布，所以由此計(jì)算出來(lái)的相似度，絕大部分會(huì)分布在u值附近區(qū)間內(nèi)。在這塊區(qū)間內(nèi)的相似度，其實(shí)價(jià)值很低的。相反的，在這個(gè)區(qū)間外的，如正態(tài)分布的兩側(cè)數(shù)據(jù)，價(jià)值就很高了。相似度越高的表示真的越相似，相似度越低的表示真的越不相似。而落在中間取值范圍，價(jià)值就小很多。

如比較項(xiàng)目中的setup.py和LICENSE，相似度0.62左右，但價(jià)值不大：

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的python 生成列向量_python_mmdt:一种基于敏感哈希生成特征向量的python库(一)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。