819
視覺挖掘與PostGIS空間數據庫的邂逅
標簽
PostgreSQL , PostGIS , 視覺匹配 , 空間相交 , 圈人
背景
推薦係統是廣告營銷平台的奶牛，其核心是精準、實時、高效。
這麼多廣告平台，到底誰家強？誰的核心牛逼？
1. 精準，指對用戶的描述精準，通常需要基於大量的用戶行為數據，經曆深度學習後形成的用戶畫像，或稱之為標簽係統。 標簽的準確性關係到推薦的精準度，比如你可能不會對一個正常的年輕人推薦老花眼鏡（當然如果有其他購買意向的標簽來指出他有購買老花眼鏡的欲望除外）。
2. 實時，指標簽的更新實時性，很多標簽是具有非常強的時效性的，比如一次營銷的目標人群，又或者用戶最近瀏覽的一些商品可能是有潛在購買欲望的商品，都具備時效性。如果你的標簽生成是隔天，或者個很多天的，那麼可能已經錯過了推薦時機。實時性在推薦係統中是非常重要的。
3. 高效，指基於標簽圈人的動作的效率與並發能力，作為購買廣告的金主，當然是期望他們拿到數據的速度越快越好。並且會有很多人向你的平台購買廣告，這考驗的是並發能力。
做到以上三點，這樣的廣告平台才具備一定的競爭力。
PostgreSQL 數組與GIN索引可以完美的支持這樣的業務場景，可以參考我去年寫的這個案子。
《恭迎萬億級營銷(圈人)瀟灑的邁入毫秒時代 - 萬億user_tags級實時推薦係統數據庫設計》
以上案子適合店鋪訪問分階層的場景，例如1-1000,1001-5000,....分檔。
如果店鋪的訪問次數沒有分檔，完全精細化表示，怎麼挖掘呢？
接下來，將要給大家介紹的方法，使用空間數據庫來實現以上場景。
業務背景介紹
用戶在逛淘寶時，購買一個商品，可能會看很多家店鋪，一番貨比三家後，才會決定從哪家買。
用戶每天會訪問很多的店鋪，如果某個用戶訪問某家店鋪的次數非常多，說明一個什麼問題呢？
這家店一定有什麼吸引該用戶，那麼如果店家針對這些用戶推送活動、或者采用合適的營銷手段，客戶在這家店鋪購買商品的可能性就非常高。
這個是圈人的手段之一。
數據結構可能會包括如下
用戶ID，店鋪ID1，訪問次數，店鋪ID2，訪問次數，。。。。。(例如1:1, 2:1即1號店訪問了1次，2號店訪問了1次)。
有了這些數據，業務方可以根據店鋪的訪問次數圈出一部分人群，比如A店鋪訪問超出多少次的，或者B店鋪訪問超過多少次的等。
如果讓你來處理，你會使用什麼技術呢？
數據規模介紹
店鋪ID上億、用戶數上億、訪問次數不定。
以上業務需求，如果裸算，會耗費大量的CPU。
視覺挖掘介紹
PostGIS是一個空間數據庫，如果將這些數據轉換為空間數據，則可以使用空間函數來實現圈人的目的，比如圈人可以表示為：multipoint與某條線段相交。
這個操作可以使用PostGIS的空間索引來完成。
把訪問軌跡數據轉換為multipoint的幾何類型來實現這個業務需求。
這兩個函數，可以將multipoint構造為幾何類型
https://postgis.net/docs/manual-2.3/ST_MPointFromText.html
https://postgis.net/docs/manual-2.3/ST_GeomFromText.html
ST_MPointFromText
ST_GeomFromText
某個用戶的訪問軌跡，在數據庫中存儲為多個點組成的幾何類型
而圈人，則使用兩個幾何類型的相交即可，例如訪問2號店鋪在2到100次，或者，訪問4號店鋪在3到100次的人群。轉化為求 "多線段幾何圖形" 與 "多點幾何圖形" 相交的結果集。
注意
(目前postgis GA版本還不支持這個操作, 接下來我假設postgis已支持multipoint && linestring的基礎上)。
目前&&支持的是bounding box的相交，並不是point，所以直接判斷&&的結果，得到的結果並不是我們想要的。
PostGIS眾多高難度的幾何操作都實現了，這個需求看樣子真的不是幾何需求。
&& — Returns TRUE if A's 2D bounding box intersects B's 2D bounding box.
一、例子
建表
test=> create table test(userid int8 primary key, feeds text);
CREATE TABLE
數據格式(店鋪ID:訪問次數;店鋪ID:訪問次數....)
空間函數索引
根據以上格式，構建multipoint，並創建空間索引，注意空字符串轉化為極點(0 0)。
test=> create index idx_test_feeds on test using gist ((case when feeds='' then ST_MPointFromText('MULTIPOINT(0 0)') else ST_MPointFromText('MULTIPOINT('||replace(replace(feeds,':', ' '),';',',')||')') end));
CREATE INDEX
test=> \d+ test
Table "public.test"
Column | Type | Modifiers | Storage | Description
--------+--------+-----------+----------+-------------
userid | bigint | not null | plain |
feeds | text | | extended |
Indexes:
"test_pkey" PRIMARY KEY, btree (userid)
"idx_test_feeds" gist ((
CASE
WHEN feeds = ''::text THEN st_mpointfromtext('MULTIPOINT(0 0)'::text)
ELSE st_mpointfromtext(('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text)) || ')'::text)
END))
Has OIDs: no
插入測試數據
插入幾條測試數據，分別表示這些用戶的訪問了哪些店鋪，以及次數。
insert into test values (1, '1:1');
insert into test values (2, '1:100');
insert into test values (3, '2:1');
insert into test values (4, '2:100');
insert into test values (5, '1:100;2:100');
圈人需求查詢
1. 查詢訪問1號店鋪>=2, <=100次的用戶
構造一條線段ST_LineFromText('LINESTRING(1 2, 1 100)')，查詢相交即可。
select * from test where
(case when feeds='' then ST_MPointFromText('MULTIPOINT(0 0)') else ST_MPointFromText('MULTIPOINT('||replace(replace(feeds,':', ' '),';',',')||')') end)
&&
ST_LineFromText('LINESTRING(1 2, 1 100)');
userid | feeds
--------+-------------
2 | 1:100
5 | 1:100;2:100
(2 rows)
執行計劃，可以看到使用了空間索引
Index Scan using idx_test_feeds on test (cost=0.41..48.47 rows=232 width=40)
Index Cond: (CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text
)) || ')'::text)) END && '010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry)
(2 rows)
2. 查詢訪問1號店鋪>=2, <=100次的用戶，或者，訪問2號店鋪>=2, <=100次的用戶
構造一個多線段類型ST_MLineFromText('MULTILINESTRING((1 2, 1 100), (2 2, 2 100))')，查詢相交即可。
select * from test where
(case when feeds='' then ST_MPointFromText('MULTIPOINT(0 0)') else ST_MPointFromText('MULTIPOINT('||replace(replace(feeds,':', ' '),';',',')||')') end)
&&
ST_MLineFromText('MULTILINESTRING((1 2, 1 100), (2 2, 2 100))');
userid | feeds
--------+-------------
2 | 1:100
4 | 2:100
5 | 1:100;2:100
(3 rows)
執行計劃，可以看到使用了空間索引
Index Scan using idx_test_feeds on test (cost=0.41..48.47 rows=232 width=40)
Index Cond: (CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text
)) || ')'::text)) END && '010500000002000000010200000002000000000000000000F03F0000000000000040000000000000F03F00000000000059400102000000020000000000000000000040000000000000004000000000000000400000000000005940'::geometry)
(2 rows)
3. 查詢訪問1號店鋪>=2, <=100次的用戶，並且，訪問2號店鋪>=2, <=100次的用戶
查詢兩條線段ST_LineFromText('LINESTRING(1 2, 1 100)'), ST_LineFromText('LINESTRING(2 2, 2 100)')都相交即可
select * from test where
(case when feeds='' then ST_MPointFromText('MULTIPOINT(0 0)') else ST_MPointFromText('MULTIPOINT('||replace(replace(feeds,':', ' '),';',',')||')') end)
&&
ST_LineFromText('LINESTRING(1 2, 1 100)')
and
(case when feeds='' then ST_MPointFromText('MULTIPOINT(0 0)') else ST_MPointFromText('MULTIPOINT('||replace(replace(feeds,':', ' '),';',',')||')') end)
&&
ST_LineFromText('LINESTRING(2 2, 2 100)');
userid | feeds
--------+-------------
5 | 1:100;2:100
(1 row)
執行計劃，可以看到使用了空間索引
Bitmap Heap Scan on test (cost=5.14..39.98 rows=46 width=40)
Recheck Cond: ((CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::t
ext)) || ')'::text)) END && '010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry) AND (CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry E
LSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text)) || ')'::text)) END && '0102000000020000000000000000000040000000000000004000000000000000400000000000005940'::geometry))
-> Bitmap Index Scan on idx_test_feeds (cost=0.00..5.13 rows=46 width=0)
Index Cond: ((CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ',
'::text)) || ')'::text)) END && '010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry) AND (CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geomet
ry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text)) || ')'::text)) END && '0102000000020000000000000000000040000000000000004000000000000000400000000000005940'::geometry)
)
(4 rows)
或
Index Scan using idx_test_feeds on test (cost=0.67..45.59 rows=46 width=40)
Index Cond: ((CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELSE st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::tex
t)) || ')'::text)) END && '010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry) AND (CASE WHEN (feeds = ''::text) THEN '010400000001000000010100000000000000000000000000000000000000'::geometry ELS
E st_mpointfromtext((('MULTIPOINT('::text || replace(replace(feeds, ':'::text, ' '::text), ';'::text, ','::text)) || ')'::text)) END && '0102000000020000000000000000000040000000000000004000000000000000400000000000005940'::geometry))
(2 rows)
二、postgis不支持multipoint && linestring前如何實現視覺挖掘?
那麼postgis哪些視覺、幾何運算和本文相關呢？
postgis在處理multipoint時，大多數幾何運算，會將multipoint自動轉換為閉合的、占據最大麵積或者體積的bound box.
1. B的所有部分都在A的內部，並且，B至少有1個內部的點在A的內部。
ST_Contains — Returns true if and only if no points of B lie in the exterior of A, and at least one point of the interior of B lies in the interior of A.
boolean ST_Contains(geometry geomA, geometry geomB); -- a包含b
藍色為A，灰色為B
TRUE
FALSE, 並不是所有的點都在A的內部
2. B的任何點都不在A的外麵。
ST_Covers — Returns 1 (TRUE) if no point in Geometry B is outside Geometry A
boolean ST_Covers(geometry geomA, geometry geomB);
boolean ST_Covers(geography geogpolyA, geography geogpointB);
3. A的任何點都不在B的外麵。
ST_CoveredBy — Returns 1 (TRUE) if no point in Geometry/Geography A is outside Geometry/Geography B
boolean ST_CoveredBy(geometry geomA, geometry geomB);
boolean ST_CoveredBy(geography geogA, geography geogB);
4. A與B有部分共用的部分，並且，共用的部分不是A或者B的全部(即公共部分隻是A或B的一部分)
ST_Crosses — Returns TRUE if the supplied geometries have some, but not all, interior points in common.
boolean ST_Crosses(geometry g1, geometry g2);
5. A和B沒有任何空間交集
ST_Disjoint — Returns TRUE if the Geometries do not "spatially intersect" - if they do not share any space together.
boolean ST_Disjoint( geometry A , geometry B );
6. A和B有空間相交, 與ST_Disjoint相反
ST_Intersects — Returns TRUE if the Geometries/Geography "spatially intersect in 2D" - (share any portion of space) and FALSE if they don't (they are Disjoint).
For geography -- tolerance is 0.00001 meters (so any points that close are considered to intersect) -- geography類型允許0.00001 meters的誤差
boolean ST_Intersects( geometry geomA , geometry geomB );
boolean ST_Intersects( geography geogA , geography geogB );
7. A和B有空間相交，但是A或B都不會完全包含對方。即一定有一部分在對方的外麵。
ST_Overlaps — Returns TRUE if the Geometries share space, are of the same dimension, but are not completely contained by each other.
boolean ST_Overlaps(geometry A, geometry B);
8. 返回A和B在指定幾何計算特性樣式下的運算結果，或者,判斷兩個幾何體是否符合指定的幾何特性。
ST_Relate — Returns true if this Geometry is spatially related to anotherGeometry, by testing for intersections between the Interior, Boundary and Exterior of the two geometries as specified by the values in the intersectionMatrixPattern. If no intersectionMatrixPattern is passed in, then returns the maximum intersectionMatrixPattern that relates the 2 geometries.
boolean ST_Relate(geometry geomA, geometry geomB, text intersectionMatrixPattern);
text ST_Relate(geometry geomA, geometry geomB);
text ST_Relate(geometry geomA, geometry geomB, integer BoundaryNodeRule);
https://postgis.net/docs/manual-2.3/ST_Relate.html
運算樣式如下
https://en.wikipedia.org/wiki/DE-9IM
9. 判斷A幾何特性是否包含B幾何特性
ST_RelateMatch — Returns true if intersectionMattrixPattern1 implies intersectionMatrixPattern2
boolean ST_RelateMatch(text intersectionMatrix, text intersectionMatrixPattern);
SELECT ST_RelateMatch('101202FFF', 'TTTTTTFFF') ;
-- result --
t
--example of common intersection matrix patterns and example matrices
-- comparing relationships of involving one invalid geometry and ( a line and polygon that intersect at interior and boundary)
SELECT mat.name, pat.name, ST_RelateMatch(mat.val, pat.val) As satisfied
FROM
( VALUES ('Equality', 'T1FF1FFF1'),
('Overlaps', 'T*T***T**'),
('Within', 'T*F**F***'),
('Disjoint', 'FF*FF****') As pat(name,val)
CROSS JOIN
( VALUES ('Self intersections (invalid)', '111111111'),
('IE2_BI1_BB0_BE1_EI1_EE2', 'FF2101102'),
('IB1_IE1_BB0_BE0_EI2_EI1_EE2', 'F11F00212')
) As mat(name,val);
10. A和B至少有1個公共點，但是他們的內部沒有相交。
ST_Touches — Returns TRUE if the geometries have at least one point in common, but their interiors do not intersect.
boolean ST_Touches(geometry g1, geometry g2);
11. A完全在B裏麵
ST_Within — Returns true if the geometry A is completely inside geometry B
boolean ST_Within(geometry A, geometry B);
如何實現本文的視覺挖掘?
幾何特性如下，A為存儲的multipoint(或者單點)，B為我們輸入的條件線段。
那麼應該具備如下特性:
1. A 和 B有公共點，但是他們的內部不存在相交。
或者
2. A 完全在B裏麵。
轉換為SQL
1. 點擊1號店鋪在2到100次之間的用戶有哪些？
select * from test1 where
(
st_touches( ST_LineFromText('LINESTRING(1 2, 1 100)'), feeds )
or
st_within( feeds, ST_LineFromText('LINESTRING(1 2, 1 100)') )
)
;
userid | feeds
--------+--------------------------------------------------------------------------------------------------------
2 | 0104000000010000000101000000000000000000F03F0000000000005940
5 | 0104000000020000000101000000000000000000F03F0000000000005940010100000000000000000000400000000000005940
(2 rows)
執行計劃
Bitmap Heap Scan on public.test1 (cost=8.28..12.79 rows=1 width=40) (actual time=0.159..0.201 rows=2 loops=1)
Output: userid, feeds
Recheck Cond: (('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry && test1.feeds) OR ('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry ~ test1.feeds)) -- 這個實現需要重新檢查
Filter: ((('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry && test1.feeds) AND _st_touches('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry, test1.feeds)) OR (('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry ~ test1.feeds) AND _st_contains('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry, test1.feeds))) -- 重新檢測過濾的條件
Heap Blocks: exact=1
Buffers: shared hit=3
-> BitmapOr (cost=8.28..8.28 rows=1 width=0) (actual time=0.020..0.020 rows=0 loops=1)
Buffers: shared hit=2
-> Bitmap Index Scan on idx_test1_feeds (cost=0.00..4.14 rows=1 width=0) (actual time=0.015..0.015 rows=2 loops=1)
Index Cond: ('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry && test1.feeds) -- 這裏可能會有大量符合條件的記錄
Buffers: shared hit=1
-> Bitmap Index Scan on idx_test1_feeds (cost=0.00..4.14 rows=1 width=0) (actual time=0.004..0.004 rows=1 loops=1)
Index Cond: ('010200000002000000000000000000F03F0000000000000040000000000000F03F0000000000005940'::geometry ~ test1.feeds) -- 針對單個點的 ~ — Returns TRUE if A's bounding box contains B's.
Buffers: shared hit=1
Planning time: 0.378 ms
Execution time: 0.239 ms
(16 rows)
性能優化
不管是multipoint還是linestring，理論上視覺判斷是很好判斷的，但是目前postgis沒有對這個簡單的視覺判斷加直接的索引過濾，需要使用st_touches和st_within兩個來判斷，而且multipoint會轉換為linestring，這樣的話相交的概率就大大增加了。
優化方法，每個用戶，每個店鋪對應一條記錄，店鋪和訪問次數可以使用一個point來表示。
通過st_within來判斷即可，可以走索引。
當然這麼做，和存兩個標量字段的效率就差不多了。
小結
PostGIS在民用、科研、軍工等各個領域都有應用，貫穿測繪、宇航局、氣象、視覺、導航、物流、物聯網等等各個行業。
幾乎所有的視覺或地圖類的框架也將PostGIS作為默認組件來支持。
https://postgis.net/docs/manual-2.3/
實際上有很多應用可以往視覺處理方麵靠，比如本文提到的根據店鋪的訪問次數圈人的場景，如果將其存儲為multipoint，那麼圈人的動作就可以轉換為視覺處理，求相交。
通過PostGIS的空間索引，這種應用完全可以做到毫秒級的響應。
讓我們一起迎接實時營銷的毫秒時代。
同時我們也可以開腦洞想象一下，是不是還有很多解不了的問題，可以用視覺處理來解決呢？
參考
https://postgis.net/docs/manual-2.3/
https://postgis.net/docs/manual-2.3/ST_MPointFromText.html
https://postgis.net/docs/manual-2.3/ST_GeomFromText.html
https://postgis.net/docs/manual-2.3/ST_MakeLine.html
https://postgis.net/docs/manual-2.3/ST_MLineFromText.html
《恭迎萬億級營銷(圈人)瀟灑的邁入毫秒時代 - 萬億user_tags級實時推薦係統數據庫設計》
《基於 阿裏雲 RDS PostgreSQL 打造實時用戶畫像推薦係統》
最後更新：2017-04-01 16:42:10